CSE 311: Foundations of Computing I

Autumn, 2015

James R. Lee

Section B: MWF 1:30-2:20, EEB 105
Office hours: MW 2:30-3:30, CSE 640

Shayan Oveis Gharan

Section A: MWF 9:30-10:20, CMU 120
Office hours: MW 10:30-11:30, CSE 636

Email and discussion:
Class email list: multi_cse311a_au15     [archives]

Please send any e-mail about the course to cse311-staff@cs.

Discussion board (moderated by TBA)

Use this board to discuss the content of the course. That includes everything except the solutions to current homework problems. Feel free to discuss homeworks and exams from past incarnations of the course, and any confusion over topics discussed in class. It is also acceptable to ask for clarifications about the statement of homework problems, but not about their solutions.

There is no required text for the course. Some lectures will have associated reading material linked below. Over the first 6 weeks or so, the following textbook can be a useful companion:
Rosen, Discrete Mathematics and Its Applications, McGraw-Hill.

(The 6th or 7th editions of the text are equally useful. Used or rental copies of either edition are available for vastly less than the ridiculously high new copy prices.)


date topic slides inked (A) inked (B) reading
30-Sep Propositional logic pdf pdf pdf 1.1-1.2 (7th), 1.1 (6th)
2-Oct Digital circuits, more logic pdf pdf pdf 1.1-1.3 (7th) 1.1-1.2 (6th)
5-Oct Booelan algebra, combinatorial logic pdf pdf pdf 12.1-12.3 (7th) 11.1-11.3 (6th)
7-Oct Boolean algebra and circuits pdf pdf pdf 12.1-12.3 (7th) 11.1-11.3 (6th)
9-Oct Canonical forms, predicate logic pdf pdf pdf 1.4-1.5 (7th) 1.3-1.4 (6th)
12-Oct Predicate logic, logical inference pdf pdf pdf 1.6-1.7 (7th) 1.5-1.7 (6th)
14-Oct Proofs I pdf pdf pdf 1.6-1.7 (7th) 1.5-1.7 (6th)
16-Oct Proofs II pdf N/A N/A 1.6-1.7 (7th) 1.5-1.7 (6th)
19-Oct Set theory pdf 2.1-2.3 (6th,7th)
21-Oct Functions, modular arithmetic pdf pdf pdf 4.1-4.2 (7th) 3.4-3.5 (6th)
23-Oct Modular arithmetic and applications pdf pdf pdf 4.1-4.3 (7th) 3.4-3.6 (6th)
26-Oct Primes, GCD pdf pdf pdf 4.3-4.4 (7th), 3.5-3.7 (6th)
28-Oct Primes, GCD, fewer tangents pdf pdf pdf 4.3-4.4 (7th), 3.5-3.7 (6th)
30-Oct Solving modular equations pdf pdf pdf 4.4, 5.1 (7th), 3.7, 4.1 (6th)
2-Nov Induction pdf pdf pdf 5.1 (7th), 4.1 (6th)
4-Nov Strong induction and recursion pdf pdf pdf 5.2-5.3 (7th), 4.2-4.3 (6th)
6-Nov Strong induction and GCD analysis pdf pdf pdf 5.3 (7th), 4.3 (6th)
9-Nov MIDTERM exam review slides
11-Nov NO CLASS: Veteran's day
13-Nov Recursively defined sets and structural induction pdf pdf pdf 5.3 (7th), 4.3 (6th)
16-Nov Structural induction pdf pdf pdf 5.3 (7th), 4.3 (6th)
18-Nov Regular expressions and context-free grammars pdf pdf pdf
20-Nov Context-free grammars & finite state machines pdf pdf pdf
23-Nov Finite state machines pdf pdf pdf
25-Nov State minimization and NFAs pdf pdf pdf
27-Nov NO CLASS: Thanksgiving
30-Nov NFAs, DFAs, and regular expressions pdf pdf pdf
2-Dec Limitations of FSMs: Irregular languages pdf
4-Dec Graphs and relations pdf 9.1 and pp. 594-601 (7th), 8.1 and pp. 541-548 (6th)
7-Dec Infinities and diagonalization pdf pdf pdf
9-Dec The halting problem and undecidability pdf pdf
11-Dec Reductions and Turing machines pdf

TA Office hours Room
Sam Castle Wed, 12:00-1:00 CSE 021
Jiechen Chen Tue, 4:00-5:00 CSE 218
Rebecca Leslie Mon, 8:30-9:30 CSE 218
Evan McCarty Tue, 11:30-12:30 CSE 220
Tim Oleskiw Tue, 3:00-4:00 CSE 218
Spencer Peters Tue, 1:00-2:00 CSE 218
Robert Weber Wed, 3:30-4:30 CSE 678 (except Oct 21st at CSE 110)
Ian Zhu Thu, 4:30-5:30 CSE 021

Section Day/Time Room
AA Sam Th, 830-920 MGH 242
AB Rebecca Th, 930-1020 MGH 234
AC Robert Th, 1030-1120 JHN 075
BA Jiechen Th, 1230-120 MGH 228
BB Tim Th, 130-220 MGH 242
BC Evan Th, 230-320 MEB 242

Homeworks [Grading guidelines]:

Assignments will be submitted via Gradescope. An account will be created for you.


  • Midterm exam:
    In class, Monday, 9-Nov-2015
  • Final exam:
    Monday, 14-Dec-2015, EEB 105
    Sec A: 12:30-2:20pm
    Sec B: 2:30-4:20pm