CSE 311: Foundations of Computing I
Spring, 2018
Kevin Zatloukal
Section A: MWF 1:30-2:20, SIG 134
Office hours: WF 2:30-3:00 and M 12:00-1:00
CSE 212
Paul Beame
Section B: MWF 10:30-11:20, MUE 153
Office hours: MF 11:30-12:00 and M 3:00-4:00
CSE 668
Email and discussion:
email list: cse311_sp18 [archives]Please send any e-mail about the course to cse311-staff@cs.
Discussion Board (log in with your UW netid)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 | Mon, Mar 26 | Propositional Logic | 1.1, 1.2 (7th) 1.1 (6th) | |||
| 2 | Wed, Mar 28 | Logical Equivalence/Gates | 1.1-1.3 (7th) 1.1-1.2 (6th) | |||
| 3 | Fri, Mar 30 | More Logic/Circuits | 12.1-12.3 (7th) 11.1-11.3 (6th) | |||
| 4 | Mon, Apr 2 | Boolean Algebra/Circuits | 12.1-12.3 (7th) 11.1-11.3 (6th) | |||
| 5 | Wed, Apr 4 | Canonical Forms, Predicate Logic | 1.4-1.5 (7th) 1.3-1.4 (6th) | |||
| 6 | Fri, Apr 6 | Predicate Logic | 1.6-1.7 (7th) 1.5-1.7 (6th) | |||
| 7 | Mon, Apr 9 | Logical Inference and Proofs | 1.6-1.7 (7th) 1.5-1.7 (6th) | |||
| 8 | Wed, Apr 11 | Predicate Logic Proofs | 1.6-1.7 (7th) 1.5-1.7 (6th) | |||
| 9 | Fri, Apr 13 | Set Theory | 2.1-2.3 (6th, 7th) | |||
| 10 | Mon, Apr 16 | Modular Arithmetic | 4.1-4.2 (7th) 3.4-3.5 (6th) | |||
| 11 | Wed, Apr 18 | Applications of Mod, Number Theory | 4.1-4.3 (7th) 3.4-3.6 (6th) | |||
| 12 | Fri, Apr 20 | Factoring, GCD, Euclid's Algorithm | 4.3-4.4 (7th), 3.5-3.7 (6th) | |||
| 13 | Mon, Apr 23 | Modular Equations, Exponentiation | 4.4 (7th), 3.7,4.1 (6th) | |||
| 14 | Wed, Apr 25 | Induction | 5.1 (7th), 4.1 (6th) | |||
| 15 | Fri, Apr 27 | Strong Induction and Recursion | 5.2-5.3 (7th), 4.2-4.3 (6th) | |||
| 16 | Mon, Apr 30 | Recursively Defined Functions | 5.3 (7th), 4.3 (6th) | |||
| 17 | Wed, May 2 | Recursively Defined Sets & Structural Induction | 5.3 (7th), 4.3 (6th) | |||
| 18 | Fri, May 4 | Structural Induction, Regular Expressions | pp.878-880 (7th) pp. 817-819 (6th) | |||
| Mon, May 7 | MIDTERM exam | |||||
| 19 | Wed, May 9 | Context-Free Grammars | pp.851-854 (7th) and pp.790-793 (6th) | |||
| 20 | Fri, May 11 | Relations, Directed Graphs | 9.1 and pp. 594-601 (7th), 8.1 and pp. 541-548 (6th) | |||
| 21 | Mon, May 14 | Finite State Machines | ||||
| 22 | Wed, May 16 | FSMs with Output | ||||
| 23 | Fri, May 18 | Minimization, NFAs | ||||
| 24 | Mon, May 21 | NFAs, RegExp, NFAs to DFAs | ||||
| 25 | Wed, May 23 | The Limitations of DFA/NFA/RegExp | ||||
| 26 | Fri, May 25 | Cardinality, Uncomputability | p.201 + 13.5 (7th) p.177 + 12.5 (6th) | |||
| Mon, May 28 | Memorial Day NO ClASS | |||||
| 27 | Wed, May 30 | Undecidability of theHalting Problem | ||||
| 28 | Fri, Jun 1 | Undecidability, Reductions, and Turing Machines |
| TA | Office hours | Room |
| Darin Chin | Fridays 12:30-1:20 | CSE 021 |
| Yuqi Huang | Fridays 3:00-3:50 | CSE 220 |
| Joy Ji | Mondays 9:30-10:20 | CSE 007 |
| Sean Jaffe | Mondays 4:30-5:20 | CSE 220 |
| Kaiyu Zheng | Tuesdays 9:30-10:20 | CSE 021 |
| Daniel Fuchs | Tuesdays 10:30-11:20 | 3rd floor breakout |
| Kush Gupta | Tuesdays 12:00-12:50 | 4th floor breakout |
| Joshua Fan | Tuesdays 2:00-2:50 | CSE 220 |
| Cheng Ni | Tuesdays 4:30-5:20 | CSE 021 |
| Section | Day/Time | Room |
| AA Joshua Fan | Th 12:30-1:20 | JHN 022 |
| AB Joy Ji, Yuqi Huang | Th 1:30-2:20 | CHL 015 |
| AC Darin Chin | Th 2:30-3:20 | CMU 226 |
| AD/BD Kaiyu Zheng | Th 11:30-12:20 | MGH 231 | BA Sean Jaffe, Kush Gupta | Th 12:30-1:20 | MEB 242 |
| BB/AE Cheng Ni | Th 9:30-10:20 | GLD 435 |
| BC Daniel Fuchs | Th 10:30-11:20 | MGH 271 |
| Section Materials | Date | Problems | Solns |
| 01 | March 29 | ||
| 02 | April 5 | ||
| 03 | April 12 | ||
| 04 | April 19 | ||
| 05 | April 26 | ||
| 06 | May 3 | ||
| 07 | May 10 | ||
| 08 | May 17 | ||
| 09 | May 24 | 10 | May 31 |
Homeworks [Grading guidelines, Submission guidelines]:
- Homework #1, due Wednesday, April 4 2018, at 11:59 PM.
- Homework #2, due Wednesday, April 11 2018, at 11:59 PM.
- Homework #3, due Wednesday, April 18 2018, at 11:59 PM.
- Homework #4, due Wednesday, April 25 2018, at 11:59 PM.
- Homework #5, due Wednesday, May 2 2018, at 11:59 PM.
- Homework #6, due Wednesday, May 16 2018, at 11:59 PM.
- Homework #7, due Wednesday, May 23 2018, at 11:59 PM.
- Homework #8, due Thursday, May 31 2018, at 11:59 PM.
Exams:
- Midterm exam:
In class, Monday 7-May-2018,
The midterm will cover everything up to the end of ordinary induction in Lecture 15 (but not strong 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. Also, to get an idea of the length, the following is a previous 311 midterm. Here are solutions to the practice problems and solutions to the practice midterm . There will be a review session Sunday, May 6, 3:30-5:30 p.m. in EEB 105. - Final exam:
Monday, 4-June-2018
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 Sieg 134. Students may take the exam at either time but must sign up on a survey by Sunday night June 3 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, June 3, 3:30-5:00pm in EEB 105; please bring your questions.
Handouts: