The exam is Monday, Dec 14, 2015 in EEB 105.
Section A is 12:30-2:20pm.
Section B is 2:30-4:20pm.

Notes: One page of notes allowed, front and back.

Here is a practice final from last year, and some extra practice questions. You can find (most of) the solutions to the practice exam here.

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.) In reverse chronological order they are:

1. Undecidability: Halting problem and evaluating properties of programs (upcoming).

2. Diagonalization and countability (upcoming).

3. Transitive reflexive closure.

4. Relations, including composition of relations.

5. Graph representation of relations and their closures.

6. Proving languages not accepted by DFAs.

7. Subset construction to convert NFA to DFA.

8. Conversion of Regular Expression to NFA.

9. Minimizing Finite state machines

10. Finite state machines with outputs at states.

11. Product construction for DFAs.

12. DFAs, NFAs and language recognition.

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 and functions.

22. English proofs.

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

24. Boolean logic and circuits.

25. Predicates and Quantifiers.

26. Logic.