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)
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.
# | 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]:
Exams:
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
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: