The exam is Monday, Jun 8, 2015, 2:30-4:20 p.m. in MLR 301.
Notes: One page of notes allowed, front and back.
Review sessions:
- Saturday, June 6th, 2015: 1pm in EEB 105 (James)
- Sunday, June 7th, 2015: 2pm in EEB 105 (TAs)
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:
- Undecidability: Halting problem and evaluating properties of programs (upcoming).
- Diagonalization and countability (upcoming).
- Transitive reflexive closure.
- Relations, including composition of relations.
- Graph representation of relations and their closures.
- Proving languages not accepted by DFAs.
- Subset construction to convert NFA to DFA.
- Conversion of Regular Expression to NFA.
- Minimizing Finite state machines
- Finite state machines with outputs at states.
- Product construction for DFAs.
- DFAs, NFAs and language recognition.
- Context-free grammars and languages.
- Regular expressions.
- Structural induction.
- Recursively defined functions and sets.
- Induction and Strong Induction.
- GCD, Euclid's algorithm and modular inverse.
- Prime numbers.
- Modular arithmetic.
- Set theory and functions.
- English proofs.
- Inference rules and proofs for propositional and predicate logic.
- Boolean logic and circuits.
- Predicates and Quantifiers.
- Logic.