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