CSE 311: Foundations of Computing I
Winter, 2020
Paul Beame
MWF 1:30-2:20, CSE2 G01 (Streaming online in Panopto/Canvas as of 3/9/20)
Office hours: M 2:30-4:00, WF 2:30-3:00
CSE 668 (Online as of 3/9/20)
Email and discussion:
email list: cse311a_wi20 [archives]Please send any e-mail about the course to cse311-staff@cs.
We will use the Ed discussion board for this class. You will need to sign up by accepting the invitation. Use this board to discuss the content of the course. That includes everything except the solutions to current homework problems. Feel free to discuss 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. There are many editions of this book and lots of used copies available; new copies are extremely expensive. A copy should be available on short-term loan from the Engineering Library.
Lectures
| # | date | topic | slides | inked | reading (Rosen) | |
| 1 | Mon, Jan 6 | Propositional Logic | 1.1, 1.2 (7th) 1.1 (6th) | |||
| 2 | Wed, Jan 8 | Logical Equivalence/Gates | 1.1-1.3 (7th) 1.1-1.2 (6th) | |||
| 3 | Fri, Jan 10 | Circuits/Proofs of Equivalence | 12.1-12.3 (7th) 11.1-11.3 (6th) | |||
| 4 | Mon, Jan 13 | Boolean Algebra/Circuits | 12.1-12.3 (7th) 11.1-11.3 (6th) | |||
| 5 | Wed, Jan 15 | Canonical Forms, Predicate Logic | 1.4-1.5 (7th) 1.3-1.4 (6th) | |||
| 6 | Fri, Jan 17 | Predicate Logic, Inference | 1.6-1.7 (7th) 1.5-1.7 (6th) | |||
| Mon, Jan 20 | Martin Luther King Day NO CLASS | |||||
| 7 | Wed, Jan 22 | Logical Inference and Proofs | 1.6-1.7 (7th) 1.5-1.7 (6th) | |||
| 8 | Fri, Jan 24 | Predicate Logic Proofs | 1.6-1.7 (7th) 1.5-1.7 (6th) | |||
| 9 | Mon, Jan 27 | Set Theory | 2.1-2.3 (6th, 7th) | |||
| 10 | Wed, Jan 29 | Modular Arithmetic | 4.1-4.2 (7th) 3.4-3.5 (6th) | |||
| 11 | Fri, Jan 31 | Applications of Mod, Number Theory, Factoring | 4.1-4.3 (7th) 3.4-3.6 (6th) | |||
| 12 | Mon, Feb 3 | GCD, Euclid's Algorithm, Modular Equations | 4.3-4.4 (7th), 3.5-3.7 (6th) 5:20-8:25 of this video |
|||
| 13 | Wed, Feb 5 | Induction | 5.1 (7th), 4.1 (6th) | |||
| 14 | Fri, Feb 7 | Induction and Strong Induction | 5.1 (7th), 4.1 (6th) | |||
| 15 | Mon, Feb 10 | Strong Induction and Recursion | 5.2-5.3 (7th), 4.2-4.3 (6th) | |||
| 16 | Wed, Feb 12 | Recursively Defined Sets & Structural Induction | 5.3 (7th), 4.3 (6th) | |||
| Fri, Feb 14 | MIDTERM exam | |||||
| Mon, Feb 17 | President's Day NO CLASS | |||||
| 17 | Wed, Feb 19 | Structural Induction, Regular Expressions | pp.878-880 (7th) pp. 817-819 (6th) | |||
| 18 | Fri, Feb 21 | Regular Expressions, Context-Free Grammars | pp.851-854 (7th) and pp.790-793 (6th) | |||
| 19 | Mon, Feb 24 | CFGs, Relations, Directed Graphs | 9.1 and pp. 594-601 (7th), 8.1 and pp. 541-548 (6th) | |||
| 20 | Web, Feb 26 | Finite State Machines | ||||
| 21 | Fri, Feb 28 | DFAs, FSMs with output | ||||
| 22 | Mon, Mar 2 | Minimization, NFAs | ||||
| 23 | Wed, Mar 4 | RegExp to NFAs, NFAs to DFAs | ||||
| 24 | Fri, Mar 6 | The Limitations of DFA/NFA/RegExp | html | |||
| 25 | Mon, Mar 9 | Cardinality, Diagonalization, Uncomputability | p.201 + 13.5 (7th) p.177 + 12.5 (6th) | |||
| 26 | Wed, Mar 11 | Undecidability of the Halting Problem | ||||
| 27 | Fri, Mar 13 | Undecidability, Reductions, and Turing Machines |
| TA | Office hours | Room |
| Siddharth Iyer | Tuesdays 3:30-4:20 | CSE2 151 |
| Suraj Jagadeesh | Tuesdays 1:00-1:50 | CSE 220 |
| Karishma Mandyam | Wednesdays 10:30-11:20 | CSE2 152 |
| Josh Shin | Mondays 12:30-1:20 | CSE2 153 |
| Tuesday, Jan 21 12:00-12:50 | CSE 220 | |
| Betty Sun | Fridays 3:30-4:20 | CSE 220 |
| Jason Waataja | Mondays 4:00-4:50 | CSE2 153 |
| Tuesday, Jan 21 10:30-11:20 | CSE 220 |
| Section | Day/Time | Room |
| AA Siddharth Iyer | Th 11:30-12:20 | DEN 213 |
| AB Jason Waataja/Betty Sun | Th 12:30-1:20 | LOW 220 |
| AC Suraj Jagadeesh | Th 1:30-2:20 | LOW 101 |
| AD Karishma Mandyam/Josh Shin | Th 2:30-3:20 | LOW 101 |
| Section Materials | Date | Problems | Solns |
| 01 | Jan 9 | ||
| 02 | Jan 16 | ||
| 03 | Jan 23 | ||
| 04 | Jan 30 | ||
| 05 | Feb 6 | ||
| 06 | Feb 13 | ||
| 07 | Feb 20 | ||
| 08 | Feb 27 | ||
| 09 | Mar 5 | ||
| 10 | Mar 12 |
Homework [Grading guidelines, Submission instructions]:
- Homework #1, due Wednesday, January 15 2020, at 11:00 PM.
- Homework #2, due Wednesday, January 22 2020, at 11:00 PM.
- Homework #3, due Wednesday, January 29 2020, at 11:00 PM.
- Homework #4, due Wednesday, February 5 2020, at 11:00 PM.
- Homework #5, due Wednesday, February 12 2020, at 11:00 PM.
- Homework #6, due Wednesday, February 26 2020, at 11:00 PM.
- Homework #7, due Wednesday, March 4 2020, at 11:00 PM.
- Homework #8, due Wednesday, March 11 2020, at 11:00 PM (Problems 1-4) and Friday, March 13, 12:00 PM (Problems 5 and 6 Extra Credit).
- Final Homework, due Wednesday, March 18 2020, at 11:00 PM.
Exams:
- Midterm exam:
In class, Friday 14-Feb-2020,
The midterm will cover everything up to the end of ordinary induction (but not strong induction). It will be closed book and closed notes. However, you will get lists of inference and equivalence rules with the exam.
To get an idea of the content and length of the exam, take a look at the following material
- A set of practice problems
- A previous midterm
- Final exam:
UPDATE 3/11: There will be a comprehensive Final Homework Assignment to replace the final exam. It will be due March 18 at 11:00 p.m. and submitted in Gradescope, just like ordinary homework assignments, but it will not use grinch so that we can give partial credit. It will be worth more than a regular homework assignment and less than the midterm.The final exam will online at the officially scheduled time Monday 16-Mar-2020, 2:30-4:20 pm (possibly extending later to compensate for the online format). (The percentage associated with the final exam will be at most that of the midterm.)Submission will be using ordinary Gradescope like your homework assignments with solutions written on paper (in ink for legibility) and photographed and submitted just like homework, except that each question will be a separate submission so there is no confusion about tagging.
We will also ask you to join an exam Zoom meeting with video enabled and audio off so we can monitor the class during the exam.
(The Zoom meeting won't have flow control like office hours do, so all can join. I have been involved in several Zoom meetings with dozens of people already this week and this works well.)
Information about the coverage of the final as well as a practice final and some other sample questions , even more sample questions are on the final exam preparation web page. Note that the sample exams may include occasional problems on topics we did not cover.
Handouts: