CSE 311: Foundations of Computing I

Spring, 2015

Instructor: James R. Lee

Office hours: MW 2:30-3:30pm, CSE 640

MWF 1:30-2:20pm, MLR 301

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

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

Discussion board (moderated by Gunnar and Ian2)

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 slides (inked) reading
30-Mar Propositional logic pdf pdf 1.1-1.2 (7th), 1.1 (6th)
1-Apr Digital circuits, more logic pdf pdf 1.1-1.3 (7th) 1.1-1.2 (6th)
3-Apr Booelan algebra, combinatorial logic pdf pdf 12.1-12.3 (7th) 11.1-11.3 (6th)
6-Apr Boolean algebra and circuits pdf pdf 12.1-12.3 (7th) 11.1-11.3 (6th)
8-Apr Canonical forms, predicate logic pdf pdf 1.4-1.5 (7th) 1.3-1.4 (6th)
10-Apr Predicate logic, logical inference pdf pdf 1.6-1.7 (7th) 1.5-1.7 (6th)
13-Apr Proofs I pdf pdf 1.6-1.7 (7th) 1.5-1.7 (6th)
15-Apr Proofs II pdf 1.6-1.7 (7th) 1.5-1.7 (6th)
17-Apr Set theory pdf pdf 2.1-2.3 (6th,7th)
20-Apr Functions, modular arithmetic pdf pdf 4.1-4.2 (7th) 3.4-3.5 (6th)
22-Apr Modular arithmetic and applications pdf pdf 4.1-4.3 (7th) 3.4-3.6 (6th)
22-Apr Proof review session pdf [optional]
24-Apr Primes, GCD pdf pdf 4.3-4.4 (7th), 3.5-3.7 (6th)
[optional] Sections 1-2 here on hashing/pattern matching.
27-Apr Primes, GCD, fewer tangents pdf pdf 4.3-4.4 (7th), 3.5-3.7 (6th)
29-Apr Solving modular equations pdf pdf 4.4, 5.1 (7th), 3.7, 4.1 (6th)
1-May Induction pdf pdf 5.1 (7th), 4.1 (6th)
4-May Strong induction and recursion pdf 5.2-5.3 (7th), 4.2-4.3 (6th)
6-May Strong induction and GCD analysis pdf pdf 5.3 (7th), 4.3 (6th)
8-May MIDTERM exam
11-May Recursively defined sets and structural induction pdf pdf 5.3 (7th), 4.3 (6th)
13-May Structural induction pdf pdf 5.3 (7th), 4.3 (6th)
15-May Regular expressions and context-free grammars pdf pdf
18-May Context-free grammars & finite state machines pdf pdf
20-May Finite state machines pdf pdf
22-May State minimization and NFAs pdf pdf
25-May Memorial day
27-May NFAs, DFAs, and regular expressions pdf pdf
29-May Limitations of FSMs: Irregular languages pdf
1-Jun Graphs and relations pdf pdf 9.1 and pp. 594-601 (7th), 8.1 and pp. 541-548 (6th)
3-Jun Inifinities and diagonalization pdf pdf
5-Jun The halting problem and undecidability pdf pdf
6-Jun Final exam review session pdf

TA Office hours Room
Evan McCarty Thu, 3-4pm CSE 021
Mert Saglam Tue, 11-12pm CSE 021
Krista Holden Thu, 10:30-11:30am CSE 220
Gunnar Onarheim Tue, 3-4pm CSE 021
Ian Turner Wed, 12-1pm CSE 218
Junhao (Ian) Zhu Thu 4-5pm CSE 021

Section Day/Time Room
AA Evan Th, 1230-120 THO 234
AB Mert Th, 130-220 DEN 217
AC Ian Th, 230-320 MGH 254
AD Krista Th, 1130-1220 MGH 251

Homeworks [Grading guidelines]:

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


  • Midterm exam:
    In class, 8-May-2015
  • Final exam:
    8-Jun-2015, 2:30-4:20pm
    MLR 301 (the usual room)