Provided Materials
On the final I will supply one “cheat sheet”:The set of symbols and descriptions on the Useful Symbols page.
Topic Distribution
Expect the final to be comprised of:
- 1/3 Topics from the first half
- 1/3 Finite Automata and Regular Expressions
- 1/3 Remainder of topics from the second half
Topics
The following topics are all fair game for the final:
- Sets
- Definition
- Notation
- Set builder notation
- Set equality
- Subset / proper subset
- Power sets
- Union / intersection / difference
- Lists
- Definition
- Notation
- Comparison with sets
- Relations
- Definition
- Notation
- Cartesian product
- Functions
- Definition
- Notation
- Comparison with relations
- Function composition
- Math functions vs. computer functions
- Partial vs. total functions
- One-to-one / onto / bijective functions
- Invertable functions
- Propositional logic
- Propositions
- Propositional vs. Predicate Logic
- Recursion and Induction
- Definitions
- Tracing recursive functions
- Regular Expressions
- Definitions
- Formal notation (not Java syntax) / construction of REs
- Relation to formal languages
- Connections with finite automata
- Finite Automata
- Definitions / Notation
- NFA vs DFA
- Construction of FAs
- Turing Machines
- Definitions / Notation
- Construction of TMs
- Computability
- Halting problem
- Formal Grammars
- Chomsky hierarchy
- Connections with FAs, PDAs, TMs
- Connections with formal languages
- Connections with regular expressions