Final Exam Logistics
March 15, 2016

The final exam will be on Wednesday, March 16. It's a cumulative exam is is weighted toward the topics from PS7 - PS9. The exam is closed-book and closed-computer. You can bring one double-sided 8.5" × 11" sheet of notes with you while you take the exam.

Room assignments are divvied up by last (family) name:

  • Abd – Lup: Go to Cubberly Auditorium.
  • Lux – Vo: Go to Bishop Auditorium.
  • Wan – Zhu: Go to 420-041.

Good luck!

Regular Expression Equivalence Checker
February 29, 2016

We've just put together a tool you can use to check if two regular expressions are equivalent. You can find it here or under "Resources" to the right.

Second Midterm Logistics
February 26, 2016

The second midterm exam will be this upcoming Monday, February 29. It covers material from Problem Set 4 through Problem Set 6 and Lectures 09 - 16. The exam is closed-book and closed-computer. You can bring one double-sided 8.5" × 11" sheet of notes with you while you take the exam.

Room assignments are divvied up by last (family) name:

  • Abd – Pre: Go to Hewlett 200.
  • Pri – Vil: Go to Hewlett 201.
  • Vo – Xie: Go to Hewlett 101.
  • Yan – Zhu: Go to Hewlett 103.

Good luck!

FSM Demo
February 17, 2016

Here's a link to the pushbutton as a finite state machine demo from today's class. Enjoy!

Midterm Logistics
February 3, 2016

The first midterm exam will be this upcoming Monday, February 8. It covers material from Problem Set 1 through Problem Set 3 and Lectures 00 - 08. The exam is closed-book and closed-computer. You can bring one double-sided 8.5" × 11" sheet of notes with you while you take the exam.

Room assignments are divvied up by last (family) name:

  • Abd – Lin: Go to Cubberly Auditorium.
  • Liu – Raj: Go to 370-370.
  • Ram – Zhu: Go to 420-040.

Good luck!

Winston Churchill is a Carrot
February 1, 2016

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.

Some Words of Encouragement
January 30, 2016

As we approach the first midterm exam, I thought I'd share two resources that I've found helpful in the past when feeling stressed about math.

First, here's an excellent YouTube video from Mathematigal talking about how not to be afraid of math:

Second, here's an article by a journalism professor dispelling his belief that he was inherently "bad at math."

Hope this helps!

Problem Set One Out
January 8, 2016

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!

Welcome to CS103!
January 1, 2016

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!


46D: Final Exam Distribution
45: Timeline of Results
37R: Midterm 2 Regrade
37D: Midterm 2 Scores
26R: Midterm 1 Regrade
26D: Midterm 1 Scores
24: Guide to Induction
19: Exam Strategies
15: Reviewing Graded Work
14: Logic and Proofs
12: Negating Formulas
11: Greek and Hebrew Letters
09: Guide to Indirect Proofs
08: Mathematical Vocabulary
07: Guide to Proofs
06: Honor Code Policies
05: Problem Set Policies
04: Set Theory Definitions
03: How to Succeed
02: Math Preqreqs
01: Syllabus
00: Course Information


Problem Set 9
Problem Set 8
Problem Set 7
Problem Set 6
Problem Set 5
Problem Set 4
Problem Set 3
Problem Set 2
Problem Set 1

Practice Problems

Another Practice Final Exam
Practice Final Exam
Challenge Problems 3
Extra Practice Problems 10
Extra Practice Problems 9
Extra Practice Problems 8
Another Practice Midterm 2
Practice Midterm 2
Challenge Problems 2
Extra Practice Problems 7
Extra Practice Problems 6
Extra Practice Problems 5
Extra Practice Problems 4
Practice Midterm 1
Challenge Problems 1
Extra Practice Problems 3
Extra Practice Problems 2
Extra Practice Problems 1


Course Reader
CS103A Website
Lecture Videos
Office Hour Calendar
Truth Table Tool
First-Order Logic Syntax Checker
Binary Relation Editor
Where to Get Solutions
DFA/NFA Editor
Regex Editor
CFG Editor
TM Editor
Regex Equivalence Checker
Guide to Self-Reference
Guide to the Lava Diagram


27: The Big Picture
26: NP-Completeness II
   Slides | Condensed
25: NP-Completeness I
   Slides | Condensed
24: Unsolvable Problems III
   Slides | Condensed
23: Unsolvable Problems II
   Slides | Condensed
22: Unsolvable Problems I
   Slides | Condensed | Quine Source
21: Turing Machines III
   Slides | Condensed
20: Turing Machines II
   Slides | Condensed
19: Turing Machines I
   Slides | Condensed
18: Context-Free Grammars
   Slides | Condensed
17: Nonregular Languages
   Slides | Condensed
16: Regular Expressions
   Slides | Condensed
15: Finite Automata III
   Slides | Condensed
14: Finite Automata II
   Slides | Condensed
13: Finite Automata I
   Slides | Condensed
12: Induction II
   Slides | Condensed
11: Induction I
   Slides | Condensed
10: Graphs II
   Slides | Condensed
09: Relations and Graphs
   Slides | Condensed
08: Binary Relations
   Slides | Condensed
07: Cardinality
   Slides | Condensed
06: Functions
   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