CSE 311 Foundations of Computing I

Final exam preparation, Fall 2014

The exam is Monday, December 8, 2013, 2:30-4:20 p.m. or 4:30-6:20 in Kane 210.

These will all be in EEB 125! There will be the following review sessions in EEB 125:

Please bring your questions.

We have posted a practice final, and some extra practice questions. You can find (most of) the solutions to the practice exam here. We omitted the DFAs, because they take a while to make.

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.

  2. Diagonalization and countability.

  3. Finite Automata for Pattern Matching.

  4. Proving languages not accepted by DFAs.

  5. Subset construction to convert NFA to DFA.

  6. Conversion of Regular Expression to NFA.

  7. Minimizing Finite state machines

  8. Finite state machines with outputs at states.

  9. Product construction for DFAs.

  10. DFAs, NFAs and language recognition.

  11. Graph representation of relations and their closures.

  12. Transitive reflexive closure.

  13. Relations, including composition of relations.

  14. Context-free grammars and languages.

  15. Regular expressions.

  16. Structural induction.

  17. Recursively defined functions and sets.

  18. Induction and Strong Induction.

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

  20. Prime numbers.

  21. Modular arithmetic.

  22. Set theory and functions.

  23. English proofs.

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

  25. Boolean logic and circuits.

  26. Predicates and Quantifiers.

  27. Logic.