Homework

Here is a list of homework assignments.

• Homework 0: a programming assignment, reviewing constructive definitions.
• Homework 1: a written assignment, reviewing cardinality.
• Homework 2: a programming assignment, reviewing regular expressions and DFA.
• Homework 3: a written assignment, reviewing regular languages.
• Homework 4: a programming assignment, reviewing non-deterministic finite automata and pumping lemma.
• Homework 5: a written assignment, reviewing circuit sizes.
• Homework 6: a programming assignment, reviewing the definition of Turing machine.
• Homework 7: a written assignment, reviewing Turing Machines and computability.
• Homework 8: a written assignment, reviewing polynomial-time reductions.
• Homework 9: a programming assignment, reviewing reductions from Hamiltonian Path and other graph problems.