Foundations of Computing I
Final exam preparation, Fall 2013
The exam is Monday, December 9, 2013, 2:30-4:20 p.m. or 4:30-6:20 in Kane 220.
There will be a review session on Sunday December 8, at 3:00 p.m. Location TBA.
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.
In reverse chronological order they are:
- Undecidability: Halting problem and evaluating properties of programs.
- Diagonalization and countability.
- Finite Automata for Pattern Matching.
- 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.
- Graph representation of relations and their closures.
- Transitive reflexive closure.
- Relations, including composition of relations.
- 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.