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!


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 5
Problem Set 4
Problem Set 3
Problem Set 2
Problem Set 1

Practice Problems

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


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