Mon 25 Nov: Other Computational Ideas

1. DNA Computing, Quantum Computing, Game of Life, etc (Not examinable)

Mon 2 Dec: P and NP

1. Review of Test 5
2. P is decision problems decidable in polynomial time. slides
3. NP adds nondeterministism. slides

Wed 4 Dec: NP-Completeness

1. Review Assign 9
2. Take-away: NP-complete problems are hardest in NP; examples include SAT (satisfiability) and HamiltonPath; many believe there is no polynomial-time algorithm for any NP-complete problem.
3. Practice 24
4. Planning for the Final.

Fri 6 Dec: Revision