Final exam topics
The final exam is cumulative, so it includes all topicis covered for
prelim 1 and 2; see the prelim 1 study
guide and the prelim 2 study
guide. Here are the additional topics covered by the final.
Automata Theory:
- Definitions:
- DFA, NFA, Regular expression
- language, language of a (DFA, NFA, RE)
- extended transition function
- Theorems:
- Kleene's theorem
- pumping lemma
Logic:
- propositional logic
- translating from English to propositional logic and back
- semantics of propositional logic
- truth tables, interpretation, entailment, validity,
satisfiability
- formal deductive systems: derivations from axioms
- You will not be asked to do a proof from axioms; you
just have to understand the idea of a formal derivation from
axioms
- first-order logic
- translating from English to first-order logic and back
- understanding the role of domains and quantification
Graph theory:
- basic notions:
- directed and undirected graph, degree, path
- graph isoomorphism
- Eulerian path
- graphs and scheduling; topological sort
- coloring, chromatic number
- bipartite graphs
- relation, equivalence relation, reflexive, symmetric, transitive
Here is the final that was given in
spring 2016 for this course. It did not cover exactly the same list of
topics (we didn't do natural deduction this semeseter, for example),
but it's very close. Here are the
(
solutions).