CSC 364S: Computational Complexity and Computability
Summer, 2003, Wednesday Section (L5201)

Click here for the Tuesday section

Announcements

13/08/2003 Inofficial final marks are now available here . Marks will be submitted tomorrow, and official marks will appear on ROSI some time after.
11/08/2003 You can pick up your assignments and tests, including test 3, in the box outside SF 3208 (it is there together with the other section's assignments and tests). If you need to speak to a TA about a mark, please do it no later than tomorrow (Tuesday). The last assignment and test were marked by Phuong, ntp@cs.

Course information

Course Information Sheet

Lectures: W 6-8 in BA 1190
Instructor: Antonina Kolokolova , email: kol@cs, office SF 3204A.
Instructor office hours: W 5-6 (right before the lecture) in SF 3207, or by appointment.
Note: By far the best way to contact me is by email. In case of emergency, you may call the DCS main office at 978-6025.

Tutorials: W8. Your tutorial is determined by the first letter of your last name:
A-K: BA 1190 Travis Gagie
L-Z: BA 1240 Phuong The Nguyen
TA office hours: Thursday before an assignment/test, 5-6pm in SF 3207

No textbook is required for the course. See lecture notes below.
There are two recommended texts:

• Cormen, Leiserson, Rivest, and Stein: Introduction to Algorithms (Second Edition). Chapters 3, 15, 16, 25, 26, and 34.
• M. Sipser: Introduction to the Theory of Computation. Chapters 3, 4, 5 and 7.

Important dates

Assignments and tests

Problem Set 1. Due June 4, 2003	Solutions to Problem Set 1.	Solutions to Term Test 1.
Problem Set 2. Due July 2, 2003	Solutions to Problem Set 2.	Solutions to Term Test 2.
Problem Set 3. Due July 23, 2003	Solutions to Problem Set 3.	Solutions to Term Test 3.

Click here to see your marks.

Policy on collaboration: The work you submit must be your own. You may discuss problems from assignments with each other; however, you should prepare written solutions alone. Plagiarism is a serious academic offense and will be dealt with accordingly. Please use this cover page for you assignments.

Lecture Notes and tentative course outline

• Greedy Algorithms (Weeks 1 and 2)
• Dynamic Programming Algorithms (Weeks 3 and 4)
  Change Making tutorial notes
  Viterbi algorithm tutorial notes
• Flow Algorithms (Weeks 5 and 6)
  Flow Example This is an example in which the Ford-Fulkerson algorithm does not terminate.
• Turing Machines and Reductions (Weeks 6 and 7)
  Turing machine simulator
  Minimum Subset Sum tutorial notes
  
• NP and NP-Completeness (Weeks 8,9 and 10)
  Million dollar problem (Click on P vs NP)
• Computability and Noncomputability (Weeks 11 and 12)