Study Materials
Materials that will be helpful for studying for exams will be posted here.
Exam 2 Materials
This exam will be held on Friday, November 22.
Topics
- Turing machines
- Types
- Single-tape vs multi-tape
- Deterministic vs non-deterministic
- Describing algorithms in terms of Turing machine operations
- Types
- Language classes
- Turing recognizable
- Decidable
- P
- NP
- NP-complete
- Time Complexity
- Big-O notation
- Polynomial vs exponential time
- Reducibility
- Implications for decidable and turing recongizable languages
- NP-completeness
Exam 1 Materials
Regular Languages Practice Problems
Topics
- Regular Languages
- Deterministic finite automata
- Nondeterministic finite automata
- Regular expressions
- Pumping lemma
- Context-free languages
- Context-free grammars
- Pushdown automata