CSE 311: Foundations of Computing I

Autumn, 2016

Paul Beame

Section A: MWF 10:30-11:20, GUG 220
Office hours: MWF 11:30-12:00 and T 2:50-3:30
CSE 668

Shayan Oveis Gharan

Section B: MWF 1:30-2:20, EEB 125
Office hours: MWF 2:30-3:00 and M 11:30-12:00
CSE 636

Email and discussion:
Class email list: cse311_au16     [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. Especially over the first 6-7 weeks of the course, the following textbook can be a useful companion: Rosen, Discrete Mathematics and Its Applications, McGraw-Hill. We will support two versions equally: (1) a special reduced version of the 7th edition which at $60 costs < 1/4 of the ridiculous price of the full text, and (2) the 6th edition, which is available used through the bookstore for even less money. It should also be available on short-term loan from the Engineering Library.

Course Calendar


# date topic slides inked (A) inked (B) reading (Rosen)
1 Wed, Sep 28 Propositional Logic pdf pdf pdf 1.1, 1.2 (7th) 1.1 (6th)
2 Fri, Sep 30 Logic/Gates pdf pdf pdf 1.1-1.3 (7th) 1.1-1.2 (6th)
3 Mon, Oct 3 More Logic/Circuits pdf pdf pdf 12.1-12.3 (7th) 11.1-11.3 (6th)
4 Wed, Oct 5 Boolean Algebra/Circuits pdf pdf pdf 12.1-12.3 (7th) 11.1-11.3 (6th)
5 Fri, Oct 7 Canonical Forms, Predicate Logic pdf pdf pdf 1.4-1.5 (7th) 1.3-1.4 (6th)
6 Mon, Oct 10Predicate Logic pdf 1.6-1.7 (7th) 1.5-1.7 (6th)
7 Wed, Oct 12 Logical Inference and Proofs pdf pdf pdf 1.6-1.7 (7th) 1.5-1.7 (6th)
8 Fri, Oct 14 Predicate Logic Proofs pdf pdf pdf 1.6-1.7 (7th) 1.5-1.7 (6th)
9 Mon, Oct 17 Set Theory pdf pdf pdf 2.1-2.3 (6th, 7th)
10 Wed, Oct 19 Modular Arithmetic pdf pdf pdf 4.1-4.2 (7th) 3.4-3.5 (6th)
11 Fri, Oct 21 Applications of Mod, Number Theory pdf pdf pdf 4.1-4.3 (7th) 3.4-3.6 (6th)
12 Mon, Oct 24 Factoring, GCD, Euclid's Algorithm pdf pdf pdf 4.3-4.4 (7th), 3.5-3.7 (6th)
13 Wed, Oct 26 Modular Equations, Exponentiation pdf pdf pdf 4.4,5.1 (7th), 3.7,4.1 (6th)
14 Fri, Oct 28 Induction pdf pdf pdf 5.1 (7th), 4.1 (6th)
15 Mon, Oct 31 Strong Induction and Recursion pdf pdf pdf 5.2-5.3 (7th), 4.2-4.3 (6th)
16 Wed, Nov 2 Recursively Defined Functions pdf pdf pdf 5.3 (7th), 4.3 (6th)
17 Fri, Nov 4 Recursively Defined Sets & Structural Induction pdf pdf pdf 5.3 (7th), 4.3 (6th)
Mon, Nov 7 MIDTERM exam
18 Wed, Nov 9 Structural Induction, Regular Expressions pdf pdf pdf pp.878-880 (7th) pp. 817-819 (6th)
Fri, Nov 11 NO CLASS: Veteran's Day
19 Mon, Nov 14 Context-Free Grammars pdf pdf pdf pp.851-854 (7th) and pp.790-793 (6th)
20 Wed, Nov 16 Relations, Directed Graphs pdf pdf pdf 9.1 and pp. 594-601 (7th), 8.1 and pp. 541-548 (6th)
21 Fri, Nov 18 Finite State Machines pdf pdf pdf
22 Mon, Nov 21 FSMs with Output pdf pdf pdf
23 Wed, Nov 23Minimization, NFAs pdf pdf pdf
Fri, Nov 25 NO CLASS: Thanksgiving
24 Mon, Nov 28 NFAs, RegExp, NFAs to DFAs pdf pdf pdf
25 Wed, Nov 30 Pattern Matching, NFA->RegExp, Limits of FSMs pdf pdf pdf
26 Fri, Dec 2 Limits of FSMs, Cardinality pdf pdf pdf
27 Mon, Dec 5 Cardinality, Halting Problem pdf pdf pdf p.201 + 13.5 (7th) p.177 + 12.5 (6th)
28 Wed, Dec 7 Undecidability pdf pdf pdf
29 Fri, Dec 9 Turing Machines pdf pdf pdf

TA Office hours Room
Joshua Fan Mon 9:30-10:20 CSE 218
Jiechen Chen Mon 12:30-1:20 CSE 218
Kaidi Pei Mon 3:30-4:20 CSE Breakout
3rd floor
Jie Du Tue 9:30-10:20 CSE 220
Jefferson Wagenen Tue 10:30-11:20 CSE 021
Kaiyu Zheng Tue 12:30-1:20 CSE Breakout
4th floor
Wei Lin Tue 2:00-2:50 CSE 220
Sarang Joshi Tue 3:30-4:20 CSE Breakout
5th floor
Michelle Prawiro Tue 4:00-4:50 CSE 220
Wed 9:30-10:20 CSE 218
Evan McCarty Fri 12:30-1:20 CSE 218
Simone Zhang Fri 3:00-3:50 CSE 021

Section Day/Time Room
AA/BE Kaidi Pei , Jie Du Th 8:30-9:20 MGH 234
AB Joshua Fan Th 9:30-10:20 MGH 254
AC Jefferson Van Wagenen, Simone Zhang Th 10:30-11:20 Sieg 134
AD Jiechen Chen Th 11:30-12:20 MGH 231
AE/BD Laura Vonessen Th 12:30-1:20 MGH 231
AF/BF Wei Lin Th 1:30-2:20 Loew 106
BA Evan McCarty Th 12:30-1:20 MGH 234
BB Sarang Joshi Th 1:30-2:20 MGH 287
BC Kaiyu Zheng Th 2:30-3:20 MEB 242

Section Materials Date Problems Solns
01 Sept 29 pdf pdf
02 Oct 6 pdf pdf
03 Oct 13 pdf pdf
04 Oct 20 pdf pdf
05 Oct 27 pdf pdf
06 Nov 3 pdf pdf
07 Nov 10 pdf pdf
08 Nov 17 pdf pdf
09 Dec 1 pdf pdf
10 Dec 8 pdf pdf

Homeworks [Grading guidelines, Submission guidelines]:


  • Midtermmxam:
    In class, Monday, 7-Nov-2016
    The midterm will cover everything up to the end of Lecture 14 on induction. It will be closed book and closed notes. You will get lists of inference and equivalence rules on the exam. You may find these practice questions for the midterm useful. Solutions are available here. Also, to get an idea of the length, the following is a previous 311 midterm. Solutions are available here. There will be a review session Sunday, Nov 6, 4:00-7:00 pm in EEB 105; please bring your questions. Here are the notes from Sunday's review session.
  • Final exam:
    Monday, 12-Dec-2016
    The final exam has been rescheduled so that both lectures can take a common exam. The times will be 2:30-4:20 pm (the original exam time for the 1:30 section) and 4:30-6:20 pm both in KNE 220. Students may take the exam at either time but must sign up on a Catalyst survey by Sunday night December 11 by 11:59pm indicating which time they will take the exam.

    Students must bring their UW ID and have it ready to be checked during the exam.

    Information about the coverage of the final as well as a practice final(solutions) and some other sample questions(solutions), even more sample questions(some solutions) are available on the final exam preparation web page. There will be a review session on Sunday, Dec 11, 4:00-6:00pm in EEB 105; please bring your questions.

Grading Scheme (Roughly):

Homework 50%
Midterm 15-20%
Final Exam 30-35%