The material presented in this guide covers the concepts emphasized on the final examination. It is meant to guide students studying and reviewing for the final exam; it is not guaranteed to be comprehensive. Actual test questions will differ from the examples given here. Students should use this guide in addition to other study activities (like re-reading Chapters 7, 8, 9, 10, 11, and 14, handouts, reviewing completed assignments, , quizzes, videos, etc.)

Things to know:

- Functions:
- properties (injective, surjective, bijective)
- functional composition
- inverse functions
- countability (countable vs. uncountable sets)

- Recurrence relations:
- solving simple recurrence relations
- proving solution correct via mathematical induction

- Mathematical structures:
- binary operations
- semigroups
- monoids
- groups
- homomorphisms

- Properties of binary operations:
- associativity
- commutativity
- identity
- idempotence
- invertibility

- Basic graph theory:
- representations and applications,
- terminology
- trees
- isomorphisms

- Graph algorithms:
- Huffman encoding,
- Dijkstra's shortest path algorithm

- Coding theory:
- group codes
- Hamming distance
- single error correction group codes
- canonical parity check matrices

- Modeling computation and languages:
- deterministic finite automata
- regular sets
- regular expressions
- context-free grammars and languages
- parse trees
- recursive descent parsing
- Turing machines
- Church-Turing thesis
- Halting problem
- classes of grammars