Computer Science

Syllabus

• Basic sorting, selection, and graph algorithms; dynamic programming.
• Abstract models of computation: Turing machines, examples, and the Church thesis.
• One-tape and two-tape Turing machines for recognizing palindromes.
• The definition and existence of a universal Turing machine.
• Simulation of multi-tape Turing machines by one-tape Turing machines.
• Recursive and recursively enumerable languages; basic closure properties.
• Non-recursive and non-recursively enumerable languages; the halting problem.
• Time complexity classes and the class P.
• Arthur–Merlin games, the class NP, co-NP, and examples of languages in NP.
• The PRIM language, polynomial-time reductions, and NP-completeness.
• Boolean formulae and the SAT language.
• Cook's theorem: SAT is NP-complete; further examples of NP-complete languages.