Late Policy Clarification
November 18, 2015

For Problem Set Eight, you're welcome to use your remaining late days. However, all submissions must be received no later than Monday, November 23.

Problem Set Eight Correction
November 16, 2015

In the Password Checking problem on Problem Set Eight, Problem 6.iv should ask you to prove that L is not in R, not that it's not in RE (we haven't talked about how to prove languages aren't in RE yet). Sorry for the typo!

Second Midterm Logistics
November 11, 2015

The second midterm exam is this upcoming Monday, November 16 from 7PM - 10PM. The exam location is divvied up by your last (family) name:

  • Aga - Ven: Go to Hewlett 200
  • Ver - Zhe: Go to 370-370

Good luck!

Problem Set Six Correction
October 31, 2015

The original automaton given in Problem 5 of Problem Set Six is incorrect. There should be a Σ-transition from the start state back to itself. We've posted an update to the electronic copy. Sorry about that!

Midterm Logistics
October 23, 2015

The first midterm exam is this upcoming Monday, October 26 from 7PM - 10PM. The exam location is divvied up by your last (family) name:

  • Aga - Ven: Go to Hewlett 200
  • Ver - Zhe: Go to 370-370

Good luck!

Problem Set Three Correction
October 10, 2015

We accidentally gave out an impossible problem in Problem Set Three. On Problem Three, part (v), the statement to prove should not be a biconditional. Instead, you should just prove that if <A has height two or less, then its covering relation is a strict order. It turns out that the other direction of implication isn't actually true. We've posted a corrected version of the problem set to the course website. Sorry about that!

Problem Set Two
October 2, 2015

Problem Set Two goes out today. The checkpoint is due on Monday and the remaining problems are due on Friday. We strongly recommend reviewing this handout on how to negate first-order formulas before starting it, as you'll need this skill at several points in the assignment.

Good luck!

Problem Set One Out
September 25, 2015

The very first problem set of the quarter, Problem Set One, goes out today and is due in two parts. The checkpoint assignment is due this upcoming Monday at the start of class and will be graded based on effort. The remaining problems are then due on Friday at the start of class. We hope that this problem set gives you a lot of practice with the three main proof techniques we've seen so far and gives you a sense of what you can do in the realm of discrete math. If you have any questions, please feel free to reach out to us!

We're using GradeScope this quarter for assignment submissions. To sign up for GradeScope, please have each group member register using the code given in the Problem Set Policies handout. We strongly recommend leaving at least two hours of buffer time when submitting just in case you run into any technical issues.

Good luck!

For Fun: Four Mathematical Links
September 25, 2015

If you'd like a fun little diversion, check out Vi Hart's video about Pythagoras and √2.

Also, as mentioned in lecture, if you assume 1 = 0, you can prove anything, including that Winston Churchill is a carrot. Just thought I'd share that gem of wisdom with you.

Many of you have also asked for some clarification about the proof of Cantor's theorem. If you're curious to learn more about the mathematical nature of infinity, check out this Vi Hart video about infinity or this Numberphile video about infinities. Thanks to our awesome TA Sarah for finding these videos!

Welcome to CS103!
September 18, 2015

Welcome to CS103, an 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 with questions.

See you soon!


35: Timeline of Results
33D: Midterm 2 Distribution
24: Guide to Induction
23R: Midterm 1 Regrade
17: Exam Strategies
13: Logic and Proofs
11: How to Negate Formulas
10: Greek and Hebrew Letters
08: Mathematical Vocabulary
07: Guide to Proofs
06: Honor Code Policies
05: Problem Set Policies
04: How to Succeed
03: Math Prereqs
02: Set Theory Definitions
01: Syllabus
00: Course Information


Problem Set Nine
Problem Set Eight
Problem Set Seven
Problem Set Six
Problem Set Five
Problem Set Four
Problem Set Three
Problem Set Two
Problem Set One

Practice Problems

Practice Problems Eight
Practice Problems Seven
Challenge Problems Two
Practice Midterm Exam 2
Practice Problems Six
Practice Problems Five
Practice Problems Four
Challenge Problems One
Practice Midterm Exam
Practice Problems Three
Practice Problems Two
Practice Problems One


Course Reader
CS103A Website
Office Hours Schedule
Truth Table Tool
Relation Editor
DFA/NFA Editor
Regex Editor
CFG Editor
Turing Machine Editor


26: Complexity Theory, Part I
   Slides | Condensed
25: Unsolvable Problems, Part II
   Slides | Condensed
24: Unsolvable Problems, Part I
   Slides | Condensed
23: Turing Machines, Part III
   Slides | Condensed | Quine
22: Turing Machines, Part II
   Slides | Condensed
21: Turing Machines, Part I
   Slides | Condensed
20: Context-Free Grammars
   Slides | Condensed
19: Nonregular Languages
   Slides | Condensed
18: Regular Expressions
   Slides | Condensed
17: Finite Automata III
   Slides | Condensed
16: Finite Automata II
   Slides | Condensed
15: Finite Automata I
   Slides | Condensed
14: Eulerian and Hamiltonian Graphs
   Slides | Condensed
13: Induction II
   Slides | Condensed
12: Induction I
   Slides | Condensed
11: Graphs II
   Slides | Condensed
10: Graphs I
   Slides | Condensed
09: Functions III
   Slides | Condensed
08: Functions II
   Slides | Condensed
07: Relations II, Functions I
   Slides | Condensed
06: Binary Relations I
   Slides | Condensed
05: Mathematical Logic III
   Slides | Condensed
04: Mathematical Logic II
   Slides | Condensed
03: Mathematical Logic I
   Slides | Condensed
02: Indirect Proofs
   Slides | Condensed
01: Direct Proofs
   Slides | Condensed
00: Set Theory
   Slides | Condensed