Final Exam Graded
December 13, 2013

After four long days of exam grading, the TAs and I have finished grading the final exam. We've released a handout containing solutions and statistics. The exams should be available soon for pickup in the filing cabinet where the midterm was returned. We'll push grades to the grade reporter by the end of the evening.

The TAs are currently finishing up grading Problem Sets 8 and 9. We'll try to get back to you with feedback on those problem sets by Sunday.

Thanks for a great quarter, everyone, and have a wonderful break!

Final Exam Logistics
December 3, 2013

The final exam will be in several rooms in Hewlett, divvied up by last name:

  • Last name Aba - Ber: Go to Hewlett 101
  • Last name Bil - Ell: Go to Hewlett 102
  • Last name Emb - Gra: Go to Hewlett 103
  • Last name Gre - Zuo: Go to Hewlett 200

We have pretty much exactly enough room to hold everyone, so please try to show up to the room corresponding to your last time.

As with the midterm, you can bring any notes to the exam for which you are the original author. You can also use a computer to access the course website or to view any notes for which you are the original author. If you own a copy of Sipser, you can bring that as well. No other materials will be permitted.

Problem Set 9 Released Early
November 29, 2013

In case you want to get a jump on the final problem set, we've posted Problem Set 9 a bit early. This problem set explores P, NP, and NP-completeness and hopefully will be a great way to round out the quarter.

The last few topics that will be necessary to complete this problem set will be covered in Monday's lecture (namely, NP-completeness, SAT, and 3SAT), so don't worry if you don't fully understand all the problems yet. If you have a copy of Sipser, you can read ahead a bit to see these topics early.

This problem set is due on Friday, December 6 at 2:15PM. No late periods can be used on this problem set and no late submissions will be accepted. Our goal is to release solutions as soon as the problem set comes due so that you have the maximum possible time to prepare for the final exam.

Good luck!

Extra Credit Practice Final
November 28, 2013

We have just released an extra credit practice final exam. It's worth five points extra credit and is due right after you take the final exam. If you make a good-faith effort to complete all the problems and submit this practice final exam, we'll give you an automatic 5 points extra credit. Our hope is that this rewards you for taking the time to study for the final exam.

We will not release solutions to this practice final. If you have any questions about it, feel free to stop by office hours, email the staff list, or stop by a final exam review session (to be announced later).

We will release two additional practice exams (not for extra credit) between now and the final exam.

Hope this helps!

Thanksgiving Office Hours
November 21, 2013

During the Thanksgiving Break, starting this Saturday (11/23) through next Sunday (12/1), there will be no regularly scheduled Office Hours. We will resume the posted schedule on the Monday after break (12/2).

In the event that a TA decides to hold impromptu/remote OH, we will email the students list to let you all know about it. Additionally, remember that you are always encouraged to send questions about the PSets to the Staff List. We will do our best to be prompt about responding over break, but understand that there may be a longer delay than usual.

Wishing everyone a relaxing break!

Problem Set 8 Out
November 18, 2013

Problem Set 8 goes out today and is due on Monday, December 2. This problem set is all about impossible problems and what makes them so hard, and we hope that this serves as a fitting coda to our treatment of computability theory. Note that this deadline is after Thanksgiving break, so you should have a fair amount of time to finish.

For planning purposes: this is the last problem set on which you can use a late period, and Problem Set 9 will go out as soon as it's due. Since no late submissions will be accepted for Problem Set 9, we advise against taking a late day on this problem set, since if you start Problem Set 9 on Wednesday of the last week of class you will only have two days to complete the assignment.

Good luck!

On Being "Bad at Math"
November 13, 2013

There is an excellent article by a journalism professor dispeling the idea that someone can be "bad at math." It's an excellent read, especially in Week 8 of a rigorous math course.


Problem Set 7 Out
November 11, 2013

Problem Set 7 goes out today and is due on Monday, November 18. This problem set explores R and RE languages and will be your first foray into the limits of computation. We hope that you have a lot of fun with it!

Good luck!

Office Hours Updated
November 4, 2013

The Office Hours schedule was just updated to include more hours later in the week and over the weekend. Some of the locations are TBD, but we will update at some point during the week.

Midterm Solutions Released
November 4, 2013

Midterm solutions and statistics are now available. Midterms and printed solutions are available for pickup in a specially-marked filing cabinet across from the homework submissions filing cabinet.

Problem Set 6 Out
November 4, 2013

Problem Set 6 goes out today and is due on Monday, November 11. This problem set explores the limits of regular languages and the expressive power of context-free grammars. We hope that this will help you solidify your understanding of regular languages and how to show that languages are context-free.

Good luck!

On Not Fearing Math
November 3, 2013

YouTube star Mathematigal has an excellent video about her experiences as a math major and how not to be afraid of math:

Midterm Rooms
October 28, 2013

The midterm will be spread across five rooms on campus by last name:

Applications of Regular Languages
October 27, 2013

Although finite automata might seem very theoretical, they have all sorts of uses in software.

Many UI controls (buttons, dropdown menus, etc.) use finite-state machines to decide when to respond to the user. As an example, here is an interactive demo of the finite-state machine for a pushbutton. You can see what state the button is in as you move the mouse around and iteract with it.


Midterm Review Sessions
October 25, 2013

We will be holding a midterm review session on Saturday, October 26 from 2:15PM - 4:15PM in 370-370. Everyone is welcome to attend! If you have any questions you'd like answered, please try to ask them on the Moderator page so that we can put materials together for then.

Dilli will be converting his normal Sunday SCPD office hours into an remote review session for SCPD students.

Problem Set Five Out
October 25, 2013

Problem Set Five goes out today. This problem set explores finite automata, regular languages, and their properties, and will be your first foray into computability theory. We hope that you enjoy it!

To make it easier to design and test the automata and regular expressions on the problem set, we have released two online tools. First, we have a DFA/NFA Developer where you can design, test, and submit finite automata for Problem One and Problem Two. Second, we have a Regular Expression Developer where you can design, test, and submit regular expressions for Problem Three. Let us know if you have any questions about them!

Finally, as in the past two problem sets, you can submit your answers to the feedback questions online through this form.

Good luck!

Practice Exams Released
October 21, 2013

We have just release two practice midterm exams you can use to help prepare for the midterm. These exams were given in Winter 2012-2013 and Fall 2012 and are similar in structure to this quarter's midterm. The exams are available under the "handouts" link.

We have also released a handout on exam strategies and policies that we hope will help you get a better sense for how to approach the exam and what we're looking for.

Problem Set Four Out
October 18, 2013

Problem Set Four goes out today. This problem set explores functions, cardinality, diagonalization, and mathematical logic. The checkpoint problem is due Monday, October 21 and the rest fo the assignment is due on Friday, October 25.

To make it easier for us to aggregate feedback, we've put the feedback question online for this problem set. Once you've finished the problem set, please fill out the feedback question online.

Good luck!

Diagonalization Video
October 17, 2013

Numberfile has a video about countable and uncountable infinities and the diagonalization of the real numbers:

Thanks to Jessica Pfund for finding this!

"Proof" Techniques
October 16, 2013

Dan Spaeth found this amazing collection of questionable proof techniques. Highly recommended!

Naturals and Reals
October 14, 2013

Minute Physics has a great video on differing cardinalities. You can see it here:

Thanks to Nick Freybler for finding this!

Problem Set Three Out
October 11, 2013

Problem Set Three goes out today. This problem set explores graphs, relations, and the pigeonhole principle and will give you a chance to play around with discrete structures. The checkpoint problem is due Monday, October 14 and the rest fo the assignment is due on Friday, October 18.

To make it easier for us to aggregate feedback, we've put the feedback question online for this problem set. Once you've finished the problem set, please fill out the feedback question online.

Good luck!

Problem Set Two Out
October 4, 2013

Problem Set Two goes out today. It's all about induction, and by the time you've completed it you'll have a much deeper understanding for just how powerful a proof technique induction can be. There's a checkpoint problem due on Monday, October 7, and the rest of the problems are due on Friday, October 11.

Good luck!

Winston Churchill is a Carrot
September 30, 2013

As mentioned in lecture, if you assume 1 = 0, you can prove anything.

Here is a fun proof online that uses the 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.

Vi Hart on Pythagoras and √2
September 27, 2013

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

Problem Set One Out
September 27, 2013

Problem Set One goes out today. This problem set explores basic proof techniques - direct proofs, proofs by contradiction, and proofs by contrapositive - through a variety of examples. We hope that this problem set will help you get used to writing mathematical proofs!

This problem set is split into two parts - a set of checkpoint problems that are due on Monday, September 30 and a set of normal problems due on Friday, October 4. The checkpoint problems are graded based primarily on effort - did you make a good, honest effort to solve the problems? - and will be graded and returned by Wednesday, October 2. Our hope with the checkpoint problems is that you will put in the effort to write the best proofs that you can so that we can provide useful feedback on your proofs' correctness and clarity in advance on the normal problem set due date. You can then use this feedback to tune your answers for the rest of the problem set.

We recommend that you look over the handout on problem set policies and handout on the Honor Code in CS103 prior to starting this problem set. These handouts contain useful information about how to approach the problem sets, as well as our policies for submitting assignments, asking for regrades, and collaborating with other students. For this problem set in particular, we suggest also reading over the handout on set theory definitions, which contains formal definitions of the set operations we saw on the first day of class.

Good luck!

Welcome to CS103!
September 18, 2013

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!


00: Course Information
01: Syllabus
02: Problem Set Policies
03: Honor Code
04: Set Theory Definitions
07: Guide to Proofs
14: Practice Midterm 1
14S: Practice Midterm 1 Solns
15: Practice Midterm 2
15S: Practice Midterm 2 Solns
16: Exam Strategies
18: Extra Review Problems
18S: Extra Review Solns
19S: Midterm Solns
24: Alternate TM Proofs
25: Extra Practice Problems
25S: Solns to Extra Problems
28: Extra Practice Problems 2
28S: Solns to Extra Problems 2
29: EC Practice Final
31: Additional Practice Final 1
31S: Solns to Practice Final 1
32: Additional Practice Final 2
32S: Solns to Practice Final 2
34: Final Exam
34S: Final Exam Solns

Discussion Problems

Discussion Problems 1
Discussion Problems 2
Discussion Problems 3
Discussion Problems 4
Discussion Problems 5
Discussion Problems 6
Discussion Problems 7
Discussion Problems 8


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


Course Reader
Lecture Videos
Theorem and Definition Reference
Office Hours Schedule
DFA/NFA Designer
Regex Designer


00: Set Theory
   Slides (Condensed)
01: Direct Proofs
   Slides (Condensed)
02: Indirect Proofs
   Slides (Condensed)
03: Induction I
   Slides (Condensed)
04: Induction II
   Slides (Condensed)
05: Graphs I
   Slides (Condensed)
06: Graphs II
   Slides (Condensed)
07: Binary Relations
   Slides (Condensed)
08: The Pigeonhole Principle
   Slides (Condensed) Code
09: Cardinality
   Slides (Condensed)
10: Mathematical Logic I
   Slides (Condensed)
11: Mathematical Logic II
   Slides (Condensed)
12: Finite Automata I
   Slides (Condensed)
13: Finite Automata II
   Slides (Condensed)
14: Finite Automata III
   Slides (Condensed)
15: Regular Expressions
   Slides (Condensed)
16: Nonregular Languages
   Slides (Condensed)
17: Context-Free Grammars
   Slides (Condensed)
18: Turing Machines I
   Slides (Condensed)
19: Turing Machines II
   Slides (Condensed)
20: Turing Machines III
   Slides (Condensed)
21: Unsolvable Problems
   Slides (Condensed)
22: Decidability
   Slides (Condensed)
23: Reducibility I
   Slides (Condensed)
24: Reducibility II
   Slides (Condensed)
25: Complexity Theory I
   Slides (Condensed)
26: Complexity Theory II
   Slides (Condensed)
27: NP-Completeness I
   Slides (Condensed)
28: NP-Completeness II
   Slides (Condensed)
29: The Big Picture