## Final exam preparation, Winter 2020

The exam is currently scheduled Monday, March 16, 2020, 2:30-4:20 p.m. It will be online with details to follow. We hope that none of you has an exam immediately following, so that we can extend the time somewhat later to compensate for the online format. The % associated with the final exam will be reduced so that the final exam will be worth at most what the midterm was worth. Submission of answers will be based on submissions through Gradescope just like you submit your homework assignments written on paper (in ink for legibility): You will take a picture of your answer and submit it online in Gradescope. Each question will be a separate submission so you don't need to tag parts. To monitor the class during exams, we will ask you to join a Zoom meeting with video turned on, just like for office hours, except that there won't be any flow control.

There will be an online Zoom review session on Sunday, March 15, with the exact timing still to be figured out. Please bring your questions.

We have posted a practice final (solutions), and some extra practice questions (solutions).

There are also even more practice questions from old exams (some solutions).

The final exam will cover the entire course but particularly the following topics. There will be some emphasis on the material not covered on the first midterm. (As a rough guide, you can expect 2/3rds of the material post midterm, 1/3rd of the material pre midterm. Topics covered in this last week of class will be a very very small part of the exam.) In reverse chronological order they are:

1. Undecidability: Halting problem and implications.

2. Diagonalization and countability.

3. Proving languages not accepted by DFAs.

4. Subset construction to convert NFA to DFA.

5. Conversion of Regular Expression to NFA.

6. Minimizing Finite state machines

7. Finite state machines with outputs at states.

8. Product construction for DFAs.

9. DFAs, NFAs and language recognition.

10. Graph representation of relations and their closures.

11. Transitive reflexive closure.

12. Relations, including composition of relations.

13. Context-free grammars and languages.

14. Regular expressions.

15. Structural induction.

16. Recursively defined functions and sets.

17. Induction and Strong Induction.

18. GCD, Euclid's algorithm and modular inverse.

19. Prime numbers.

20. Modular arithmetic.

21. Set theory.

22. English proofs.

23. Inference rules and formal proofs for propositional and predicate logic.

24. Predicates, Quantifiers and Predicate logic.

25. Boolean algebra.

26. Boolean logic and circuits.

27. Propositional Logic.