Section A: MWF 1:30-2:20, SIG 134

Office hours: WF 2:30-3:00 and M 12:00-1:00

CSE 212

Section B: MWF 10:30-11:20, MUE 153

Office hours: MF 11:30-12:00 and M 3:00-4:00

CSE 668

Please send any e-mail about the course to **cse311-staff@cs**.

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.

# |
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:**