CSC 364S: Computational Complexity and Computability, Fall 2003

Announcements

15/12/2003 Marks are now finalized and submitted; I do not have the exam papers anymore. The rest of the term work can be still picked up from the box outside of my office. Happy holidays!
12/12/2003 A first version of unofficial marks is posted now. Note that not everybody's mark is in yet (depends where you wrote the final exam). Marks can still change, this is just the raw marks!
11/12/2003 If you have any last-minute remarking requests, please email me before Friday afternoon. Hopefully unofficial marks will be available Friday evening and finalized by Monday.
8/12/2003 Assignment and test 3 are now marked; you can pick them up from the box outside of my office. Please check that your marks online are recorded correctly.
5/12/2003 There will be my office hours on Monday Dec 8th, in SF3207, 2-4pm. I should also be in my office 4-6pm on Tuesday Dec 9th.
3/12/2003 Posted solutions for test 3.
1/12/2003 Posted marks file with all remarking for topics 1 and 2. Let me know if your mark is not recorded correctly.
28/11/2003 Last year final exam is here .
28/11/2003 Posted solutions to assignment 3.
17/11/2003 A student lost his test 2 recently. If you have seen a test with the name Taheri-Nia Roozbeh on it, please let me know.

Course information

Course Information Sheet

Lectures: MF 2 in BA 1180
Instructor: Antonina Kolokolova , email: kol@cs, office SF 3204A.
Instructor office hours: M 3-4 and F 1-2, 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: W2
Your tutorial is determined by the first letter of your last name:
A-J: BA 1180, Tsuyoshi Morioka (email at cs "morioka", marking topic 2)
K-O: SS 2111, Phuong The Nguyen (emal at cs "ntp", marking topic 1)
P-Z: UC 144, Spyros Angelopoulos (email at cs "spyros", marking topic 3)

TA office hours: Tuesday before a test, time TBA, 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

Academic calendar: first class is Sep 8, last day to drop is Nov 3, last class is Dec 5.
Assignments are due Oct 1, Oct 31 and Nov 26, at the beginning of tutorial.
Tests are Oct 10 , Nov 5 and Dec 3 in the lecture room.
Final exam: See the official final exam schedule

Assignments and tests

Problem Set 1. Due Oct 1, 2003 Solutions to Problem Set 1. Solutions to Term Test 1.
Problem Set 2. Due Oct 31, 2003 Solutions to Problem Set 2. Solutions to Term Test 2.
Problem Set 3. Due Nov 26, 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) (Updated)
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
NP and NP-Completeness (Weeks 8,9 and 10)
Million dollar problem (Click on P vs NP)
Computability and Noncomputability (Weeks 11 and 12)

Problem Set 1. Due Oct 1, 2003	Solutions to Problem Set 1.	Solutions to Term Test 1.
Problem Set 2. Due Oct 31, 2003	Solutions to Problem Set 2.	Solutions to Term Test 2.
Problem Set 3. Due Nov 26, 2003	Solutions to Problem Set 3.	Solutions to Term Test 3.