MWF 1:30-2:20, CSE2 G01

Office hours: M 2:30-4:00, WF 2:30-3:00

CSE 668

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 | Context-Free Grammars | pp.851-854 (7th) and pp.790-793 (6th) | ||

19 | Mon, Feb 24 | 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 | Finite State Machines | |||

22 | Mon, Mar 2 | FSMs with Output | |||

23 | Wed, Mar 4 | Minimization, NFAs | |||

24 | Fri, Mar 6 | NFAs, RegExp, NFAs to DFAs | |||

25 | Mon, Mar 9 | The Limitations of DFA/NFA/RegExp | |||

26 | Wed, Mar 11 | Cardinality, Uncomputability | p.201 + 13.5 (7th) p.177 + 12.5 (6th) | ||

27 | Fri, Mar 13 | Undecidability of theHalting Problem | |||

28 | Fri, Jun 1 | 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 |

**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.

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

The final exam will at the officially scheduled time Monday 16-Mar-2020, 2:30-4:20 pm.

**Handouts:**