# Final exam topics

The final exam is cumulative. here is a sample final exam (solutions).

You are responsible for all material covered in lecture or on the homeworks. A (potentially incomplete) list of topics is included below:

Prelim 1 topics: Functions, cardinality, Induction, Number theory - see prelim 1 study guide

Prelim 2 topics: Combinatorics, Probability, Graph theory - see prelim 2 study guide

## Topics since prelim 2:

Graph theory:

- coloring, chromatic number
- bipartite graphs, spanning trees
- relation, equivalence relation, reflexive, symmetric, transitive

Automata:

- Definitions:
- DFA, NFA, Regular expression
- language, language of a (DFA, NFA, RE)
- extended transition function

- Theorems:
- Kleene's theorem
- pumping lemma

Logic:

- propositional logic, first order logic
- representing english statements

- semantics of propositional logic
- truth table, interpretation, entailment, validity, satisfiability

- natural deduction proofs in prop. logic
- understand the rules
- be able to build proofs

- soundness, completeness
- semantics of first-order logic
- interpration function, domain, validity