CSC 364H L0101: Computability and Complexity
Summer 2000

Instructor: Michael Soltys, email: my last name at cs.toronto.edu

Check this web page regularly for announcements and solutions. All documents below are in PostScript. If you need a PostScript previewer, go to Ghostview Software.

Course Information

Important Dates

• June 8: Problem Set 1 is due.
• June 15: Test 1.
• July 6: Problem Set 2 is due.
• July 13: Test 2.
• Aug 3: Problem Set 3 is due.
• Aug 10: Test 3.

• Aug 21: Click here for the final marks.
• I am marking the exams... (unofficial) final marks will be posted here as soon as I'm done. If you have questions regarding the marking of Test 3 or PS 3, email Ying Zhu at yz@cs.toronto.edu
• Old Announcements

• Explanation of big-Oh notation
• week 1: Greedy Algorithms I
• week 2: Greedy Algorithms II
• week 3: Dynamic Programming I
• week 4: Dynamic Programming II
• week 5: Network Flows (chapters 27.1 and 27.2 in the textbook)
• week 6: NP-completeness I
• week 7: NP-completeness II
• week 8:
  • NP-completeness III
  • Also, for material on CircuitSat, 3SAT, and SAT, read the notes NP and NP-completeness
• week 9: NP-completeness IV
• week 10: Search Problems and Computability I
• week 11: Computability II
• week 12: Computability III
• week 13: Review

• Problem Set 1 and solutions
• Problem Set 2 and solutions
• Problem Set 3 and solutions

• Test 1 and solutions
• Test 2 and solutions
• Test 3 and solutions

• csc364 evening section
• PostScript previewers: Ghostview Software