COMP3310/3610 Theory of Computation
School of Information Technologies,
University of Sydney


List of the main topics covered in 2007 semester 2. Note thatthis is not a complete list of topics, and is meant to be only an indication of the most important topics that were discussed in COMP3310/3610. Topics that are mainly aimed at the advanced COMP3610 are marked as “(adv)” in the list below.

Week 1:

• course outline

• COMP3310/3610 has two assignments (each 10% of the final unscaled mark), a midterm exam (15% of the final mark) and a final exam (60% of final mark), plus 5% for tutorial work.

• COMP3310/3610 lectures cover the normal and advanced stream. Parts of the midterm, assignments and the final exam will be different for the two streams. Part of the material covered will not be in any of the assessments for the normal stream. These parts will be clearly identified.

• Final exam will be closed book, with only on double sided A4 sheet with notes allowed (hand-written or printed ok)

• Main definitions of finite state automata

• Fermat's last theorem was briefly mentioned in the lecture. For more information see these pages

• Reading material from Sipser: ch 0 (review), ch1 sections 1.1

Week 2:

• Finite state automata, non-deterministic automata

• Regular operations, closure properties for regular languages

• Regular expressions and regular languages

• the pumping lemma and non-regular languages

• Reading material from Sipser: ch 0 (review), ch1 sections 1.1-1.4

Week 3:

• Using the pumping lemma for regular languages

• context free grammars, Chomsky normal form

• Stack automata and context free languages

• Closure properties for context free

• The Turing machine

• Reading material from Sipser: ch 0 (review), ch1 sections 1.4, ch2 sections 2.1, 2.2, 2.3

• Advanced topics: ambiguity in context free grammars, the pumping lemma for context free

• Turing's 1936 paper, introducing Turing machines

Week 4:

• Turing machines, definitions, non-determinism

• Decidability, the halting problem

• Counting and proving the existence of undecidable problems

• Universal Turing machines (advanced)

• The halting problem, acceptance problem and diagonalization

• Reading from Sipser: ch3 and ch4

• More information on Hilbert's problems and in particular Hilbert's 10th and the theorem of Matiyasevic

• lambda calculus

Week 5:

• More on undecidability

• The halting problem, acceptance problem and diagonalization

• Reducibility, many-one reductions, proving undecidability through reductions

• Emptiness, regularity and equality

• Rice's theorem

• Proof of Rice's theorem

• Reductions through computation histories (advanced)

• Post's correspondence problem (PCP)

• Proof of undecidability for PCP (advanced)

• More on reducibility

• Sipser ch4 and 5.

Week 6:

• Recursion theory, self reference (adv)

• logical theories and decidability, incompleteness theorem (adv)

• Introduction to complexity theory, Complexity and models of computation

• Polynomial time, the Euclidean algorithm

• NP, non-determinism and verifiers, definitions of NP

• nondeterministic machines and verifiers

• nondeterministic machines and verifiers proof of equivalence (advanced)

• NP completeness, Satisfiability and hamiltonian paths

• NP-hard problems

• Sipser ch 7

• Sipser ch 6 for some of the advanced topics

Week 7:

• certificates and verifiers

• P versus NP, reducibility

• Satisfiability and NP completeness

• Cook Levin Theorem

• Proof of the Cook Levin theorem (advanced)

• 3SAT, Clique, Hamiltonian path, undirected hamiltonian path, vertex cover

• Introduction to space complexity

• Sipser ch 7,9

Week 8:

• NP-completeness, hamiltonian paths

• Space complexity

• Savitch's theorem

• The quantified boolean formula (QBF) problem

• PSPACE completess

• logspace, logpsace reducibility, NL=coNL

• Sipser ch7, ch 8

Week 9:

• guest lecture by Prof. Ran Libeskind-Hadas (Harvey-Mudd College)

• on PSPACE completeness

• PSPACE completeness and game playing strategies

• the generalized geography game and PSPACE completeness

• Sipser ch 8
  
  

Week 10:

• midterm quiz

• review of midterm quiz solutions

Week 11:

• Randomness and information

• Kolmogorov or descriptive complexity

• incompressible strings

• definition of the class BPP

• Sipser ch 6.4

Week 12:

• Time hierarchy theorems (adv)

• Space hierarchy theorems (adv)

• randomization and randomized algorithms

• approximation algorithms

• parametrized complexity and fixed parameter tractability

• the P versus NP problem and 4 different worlds

• Sipser 9.1, 10.1

Week 13:

• Review