CSC 364H1Y - Summer 2004

Syllabus and Textbook Readings

Date	Topics	Events	Readings
May 18	What is an Algorithm?	-	Cormen: 1-4 (skim) Sipser: 0 (skim), 3.1
May 25	Turing Machines and Computability	-	Sipser: 3.2-3.3
June 1	Nondeterminism (supernatural computing) and the existence of uncomputable functions	Quiz 1	Sipser: 4
June 8	The Universal Turing Machine, Reductions, and the Halting Problem	-	Sipser: 5
June 15	Good vs. Bad Algorithms Algorithm Techniques I: Greedy Algorithms	Quiz 2 HW 1 due	Cormen: 16
June 22	Greedy Algorithms continued Algorithm Techniques II: Divide and Conquer	-	Cormen: 2.3, 33.4
June 29	Algorithm Techniques III: Dynamic Programming	Test I	Cormen: 15
July 6	Algorithm Techniques IV: Augmenting Paths	Quiz 3	Cormen: 26.1-26.3
July 13	Hard Problems, a return to Nondeterminism, and Completeness	HW 2 due	Cormen: 34.1-34.2 Sipser: 7.1-7.3
July 20	Reductions, Cook's Theorem and the Existence of Hard Problems	-	Cormen: 34.3 Sipser: 7.4
July 27	NP-completeness and the Million Dollar Problem	Test II	Cormen: 34.4 Sipser: 7.5
August 3	Many, many problems are hard!	Quiz 4 HW 3 due	Cormen: 34.5
August 10	Advanced Algorithms: Linear Programming	-	Cormen: 29.1-29.3