CSE 311 Foundations of Computing I

Final exam preparation, Autumn 2012

The exam is Monday, Dec 10, 2012, 2:30-4:20 p.m and 4:30-6:20 p.m in Kane 220.

There will be review session or sessions TBD Please bring your questions.

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.

  1. Undecidability: Halting problem and evaluating properties of programs.

  2. Diagnalization 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. English proofs.

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

  24. Boolean logic and circuits.

  25. Predicates and Quantifiers.

  26. Logic.