Notes, Assignments, Study Guides

Notes

• Introduction to Theory of Computation
• Introduction to OCAML
• OCAML basics
• OCAML example: sets as lists (optional)
• Alphabets, strings, substrings, empty string, lexicographic ordering
• Alphabet and friends in OCAML
• Languages, examples, constructions
• Deterministic Finite Automata
• DFAs in OCAML
• Regular Languages
• Implementation of union in OCAML
• Non-deterministic automata, examples
• Regular Expressions
• Nonregular languages and the Pumping Lemma
• Lexers
• Context Free Grammars
• Pushdown Automata definition
• CFG <-> PDA
• Pumping lemma for CFGs
• Basics of Parsing
• Turing Machines
• Decidable Problems
• The Halting Problem
• Reducibility
• Mapping Reducibility
• Time Complexity
• The P and NP classes. P
• NP-complete problems

Assignments

• Assignment 1
• Assignment 2
• Assignment 3
• Assignment 4
• Assignment 5
• Assignment 6
• Assignment 7
• Assignment 8
• Assignment 9
• Assignment 10

Study Guides

• Midterm 1 study guide
• Midterm 2 study guide
• Final study guide