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