Announcements

Problem Set Nine Out
March 11, 2013

Problem Set Nine goes out today and is due on Friday, March 15 at 12:50PM. This problem explores P and NP and concludes with a wrap-up of all the complexity and computability classes we've covered in this course.

You may use a late day on this assignment if you would like. If so, it is due immediately after you take the final exam. Due to university policy, we cannot accept any submissions received after 11:30AM.

Good luck!

Problem Set Eight Out
March 4, 2013

Problem Set Eight goes out today and is due on Monday, March 11 at 12:50PM. This problem explores unsolvable problems and the limits of what computers can do. It concludes with an exploration of why languages like ATM and LD matter in the real world, and I hope that this forms a satisfying coda to our treatment of computability.

Good luck!

Problem Set Seven Out
February 25, 2013

Problem Set Seven goes out today and is due on Monday, March 4 at 12:50PM. This problem set explores the RE and R languages and the limits of Turing machines. This will be your first experience probing the limits of what problems can be solved by computers, and I hope you find it exciting!

Good luck!

Turing Machines and Self-Assembling Molecules
February 25, 2013

Anna Saplitski found an awesome video describing how self-assembling molecules can simulate Turing machines. This incredible video details the amazing connection between computational processes, emergent behavior, and how complex objects can be built from smaller pieces. I highly recommend it!

Problem Set Six Out
February 15, 2013

Problem Set Six goes out today and is due on Monday, February 25 at 12:50PM. It explores context-free languages, their representations, their properties, and their limits.

Good luck!

Midterm Review Sessions
February 9, 2013

Julius will be holding an online review session on Saturday from 7PM-10PM. We will send out the Google hangout link when the time approaches.

Maurizio will be holding an in-person review session on Sunday, Feb. 10 from 5PM-7PM in Hewlett 200.

Problem Set Five Out
February 8, 2013

Problem Set Five went out today and is due next Friday, February 15 at the start of class. This problem set explores regular languages, their representations, and their limits. This will be your first foray into computability theory, and I hope that you find it fun and exciting!

We have two online tools you can use in this course of this problem set, both of which are linked under the "Resources" section of this page. Our DFA/NFA developer is a full development environment in which you can design, build, test, and debug finite automata. The regular expression developer will let you build regular expressions and test them on a variety of different inputs.

Good luck!

Second Practice Midterm Available
February 7, 2013

We have posted a second practice midterm exam you can use to help prepare for the upcoming midterm. Solutions to the first practice midterm are also available.

Practice Midterm Available
February 4, 2013

The CS103 midterm is next Tuesday, February 12 from 7PM - 10PM, location to be announced soon. It is open-book, open-note, open-computer, but closed-network, so it's totally fine to bring your laptop with you to the exam.

We have posted a practice midterm exam. This was the exam given in fall quarter, so its content, form, and structure should be similar to that of the real exam. We will release solutions on Wednesday.

Problem Set Four Out
February 1, 2013

Problem Set Four went out today. The checkpoint assignment is due next Monday, February 4 at 12:50PM and the remaining problems are due next Friday, February 8 at the start of class. This problem set explores properties of propositional and first-order logic, as well as the power of SAT solving algorithms.

Good luck!

Problem Set Three Out
January 25, 2013

Problem Set Three went out today. The checkpoint assignment is due next Monday, January 28 at 12:50PM and the remaining problems are due next Friday, February 1 at the start of class. This problem set explores relations, functions, cardinality, and the pigeonhole principle. After completing it, you'll have a much stronger understanding of discrete structures.

Good luck!

Problem Set Two Out
January 18, 2013

Problem Set Two went out today. The checkpoint assignment is due next Tuesday, January 22 at 5:00PM and the remaining problems are due next Friday, January 25 at the start of class. This problem set is all about induction and its applications in computer science. By the time you're done, you'll have a much deeper understanding of just how versatile induction can be.

Good luck!

Notes on the Division Algorithm
January 16, 2013

There is a positively fascinating essay on the division algorithm, its proof, and why it's mathematically so important. I highly recommend giving it a read. It's available online if you are interested in reading through it.

Winston Churchill is a Carrot
January 14, 2013

An interesting consequence of proof by contradiction is that starting with a false statement, it's possible to prove anything.

Here is a fun proof online that uses the incorrect assumption that 1 = 0 to prove that Winston Churchill is a carrot. If you have the time to read over it, it's quite entertaining.

Problem Set One Out
January 11, 2013

Problem Set One went out today. The checkpoint assignment is due next Monday, January 14 at the start of class and the remaining problems are due next Friday, January 18 at the start of class. This problem set is designed to get you used to writing mathematical proofs and to get you thinking about set theory, the integers, and even a bit of cryptography!

Good luck!

Vi Hart on Pythagoras and √2
January 11, 2013

Here is Vi Hart's video about Pythagoras and √2. Enjoy!

Welcome to CS103!
January 7, 2013

Welcome to CS103, an exciting and fast-paced introduction to discrete mathematics, computability theory, and complexity theory! We have an great quarter ahead of us filled with interesting and exciting results in the power and limits of computation, and I hope that you're able to join us.

If you have any questions in the meantime, feel free to email me at htiek@cs.stanford.edu with questions.

See you soon!

Handouts

00: Course Information
01: Syllabus
02: Prior Experience Survey
08: Diagonalization
12: Practice Midterm
12S: Practice Midterm Solns
13: Practice Midterm 2
13S: Practice Midterm 2 Solns
15: CS103 Midterm
15S: CS103 Midterm Solns
24: EC Practice Final
25: Practice Final I
25S: Practice Final I Solns
26: Practice Final II
26S: Practice Final II Solns
27: Final Exam
27S: Final Exam Solutions

Assignments

Problem Set 1
  (checkpoint solutions)
  (solutions)
Problem Set 2
  (checkpoint solutions)
  (solutions)
Problem Set 3
  (checkpoint solutions)
  (solutions)
Problem Set 4
  (checkpoint solutions)
  (solutions)
Problem Set 5
  (solutions)
Problem Set 6
  (solutions)
Problem Set 7
  (solutions)
Problem Set 8
  (solutions)
Problem Set 9
  (solutions)

Discussion Problems

Discussion Problems 1
  (solutions)
Discussion Problems 2
  (solutions)
Discussion Problems 3
  (solutions)
Discussion Problems 4
  (solutions)
Discussion Problems 5
  (midterm week; no recitation)
Discussion Problems 6
  (solutions)
Discussion Problems 7
  (solutions)
Discussion Problems 8
  (solutions)
Discussion Problems 9
  (solutions)

Resources

Course Notes
Lecture Videos
Definitions and Theorems
Office Hours Schedule
Grades
DFA/NFA Developer
Regex Developer

Lectures

00: Set Theory
  Slides (Condensed)
01: Direct Proofs
  Slides (Condensed)
02: Indirect Proofs
  Slides (Condensed)
03: Induction, Part I
  Slides (Condensed)
04: Induction, Part II
  Slides (Condensed)
05: Graphs and Relations
  Slides (Condensed)
06: Functions and Cardinality
  Slides (Condensed)
07: Unequal Cardinalities
  Slides (Condensed)
08: Mathematical Logic I
  Slides (Condensed)
09: Mathematical Logic II
  Slides (Condensed)
10: Mathematical Logic III
  Slides (Condensed)
11: Finite Automata I
  Slides (Condensed)
12: Finite Automata II
  Slides (Condensed)
13: Finite Automata III
  Slides (Condensed)
14: The Pumping Lemma
  Slides (Condensed)
15: Pushdown Automata
  Slides (Condensed)
16: CFGs
  Slides (Condensed)
17: Turing Machines
  Slides (Condensed)
18: Turing Machines II
  Slides (Condensed)
19: Turing Machines III
  Slides (Condensed)
20: Decidability and Undecidability
  Slides (Condensed)
21: co-RE and Reducibility
  Slides (Condensed)
22: Mapping Reducibility
  Slides (Condensed)
23: Mapping Reducibility II, Complexity
  Slides (Condensed)
24: P and NP
  Slides (Condensed)
25: NP-Completeness
  Slides (Condensed)
26: NP-Completeness II
  Slides (Condensed)
27: The Big Picture
  Slides