## CSE 311
Foundations of Computing I

## Final exam preparation, Fall 2016

The exam is **Monday, December 12, 2016, 2:30-4:20 p.m.** or **4:30-6:20** in **Kane 220**.

Students may take the exam at either time but **must sign up on a Catalyst survey by Sunday night December 11 by 11:59pm** indicating which time they will take the exam.
**Students must bring their UW ID and have it ready to be checked during the exam. **

There will be a review session in EEB 105:

Please bring your questions.
We have posted a practice final(solutions), and
some extra practice questions (solutions).

There are also even more practice questions from old exams (some solutions).

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.
- Proving languages not accepted by DFAs.
- Finite Automata for Pattern Matching.
- 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.
- English proofs.
- Inference rules and formal proofs for propositional and predicate logic.
- Predicates, Quantifiers and Predicate logic.
- Boolean algebra.
- Boolean logic and circuits.
- Propositional Logic.