University of Toronto, Department of Computer Science CSC463H Computational Complexity and Computability Winter 2012

Students should consult this page at least once a week and check for new announcements.

Course Info

Instructor
Name: Kaveh Ghasemloo
Email:
Office: 10 King's College Road, Sandford Flemming Bulding, Room 4306B
Teaching Assistants:
Names: Yu Wu & Dustin Wehr
Email:
Lectures
When: Wednesdays 6PM-8PM
Where: BA 1210
Tutorials
When: Wednesdays 8PM-9PM
Where: BA 1210
Office Hours
When: Wednesdays 5PM-6PM
Where: SF 4306B
or email the instructor for an appointment.
Course Website
http://www.cs.toronto.edu/~kaveh/csc463h/
http://j.mp/csc463h
Textbook
Michael Sipser, "Introduction to the Theory of Computation", 2nd Edition, 2006.
Supplementary Lecture Notes (by Stephen Cook)
Turing Machines and Reductions
Computability and Noncomputability
NP and NP-Completeness
References
S. Arora and B. Barak, "Complexity Theory, A Modern Approach", 2009.
Free online draft.
Oded Goldreich, "Computational Complexity: A Conceptual Perspective", 2008.
Free online draft.
Michael R. Garey and David S. Johnson, "Computers and Intractability: A Guide to the Theory of NP-Completeness", 1979.
Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest and Clifford Stein, "Introduction to Algorithms", 3rd Ed., 2009.
Dingzhu Du, Ker-I. Ko, "Problem solving in automata, languages, and complexity", 2001.
Course Material
Course Description
Course Contents
Marking Scheme
Marking Scheme
Title Points Notes
Assignments 55

A0: 5 pints, A1: 10 points, A2: 15 points; A3: 10 points, A4: 15 points.

Tests 20

T1: 10 points; T2: 10 points.

Take Home 10

See the instructions below.

Final Exam 40

To pass this course you should get at least 50% in the final exam.

Total 125

Anyone with score above 100 points will get 100 points (the extra points are bonus, i.e. if you miss a test and an assignment worth 15 point you still can get 100 points).

Course Information Sheet
csc463w12info.pdf

General Remarks

• Email is the preferred way to contact the instructor and the teaching assistant. Feel free to email the instructor regarding any course related issues. Questions by email are also welcome. We will try to answer your emails in 3 working days.
• Please use informative subject lines for your emails and include "[CSC463]", e.g. "[CSC463] a question about Turing machines" or "[CSC463] clarification for assignment 1".

Announcements

May 1, 2012
Marks are submitted. They should appear on ROSI soon. Average mark: 74%.
Questions 3 and 8 in the fianl exam were more difficult than I intended and only a few students could answer them so I relaxed the 50% score requirement for passing the course.
Apr. 18, 2012
The course finished today. I hope that you have enjoyed it. Have a great summer. :)
Apr. 16, 2012:
If you have questions you can drop by BA3201 on Tuesday, Apr. 17, from 4PM to 6PM to ask them.
I will post some marker remarks today about assignments and tests. Please check the site tonight if you want to read them.
Apr. 13, 2012:
The Help Center (located in BA2270) is open during the exam period from Monday-Thursday 4-6pm. You can drop by the Help Centre to ask questions.
You can also ask questions on the following CS Q&A website: Computer Science - Stack Exchange. If you have trouble finding reductions between NP-complete problems, check this post by Jeff Erickson.
Email questions are welcome as always. If you have a question, don't leave it to the last day. You can also ask for your scores in the tests and assignments. I strongly recommend that you pick up your test and assignment papers so you will not repeat them in the final exam. You can drop by the help center to pick them up from Dustin (TA) during the its operation hours.
Take Home papers will not be marked before the final exam.
Apr. 12, 2012:
Test T2 is marked. Email the instructor if you want to know your mark. You can pick your test papers tomorrow afternoon, from 2PM-4PM from my office.
Assignment A4 is being marked but not finished yet. You can pick up your assignment A4 papers tomorrow as well. Also assignment A3 papers if you haven't picked them up.
Regarding the Final Exam
The final exam will be about the whole course (both computability and complexity). There will be no definition questions, but if you don't know the definitions you will have hard time solving the problems. The exam will be 3 hours long. .
To prepare for the final exam: check the previous semester's final exam for sample questions. Make sure that you know the definitions (as stated in the book), and the solutions to the assignments and tests. Study examples and problems in the textbook from the chapters we have covered from the textbook (ch. 3,4,5, 7, 8, 9.1) (particularly reductions and completeness proofs). You can study the previous semester's assignments/tests.
Reminder: to pass this course you must get at least 50% in the final exam. If you don't, you will fail the course independent of how well you have done in the assignments/tests.
The proofs of the following theorems will not be in the final exam: Cook-Levin theorem (SAT is NP-complete), Path is NL-complete, NL=coNL.
CFGs/CFLs will not be part of the final exam.
No aids are allowed in the exam. For more information about what you can or can't bring to the exam check the regulations for final exams. If in doubt or have questions please talk to the undergrad office.
Apr. 8, 2012:
The solutions for assignment A4 are posted.
Apr. 5, 2012:
For assignment A4, question 1, if you have trouble solving the problem solve it with using integers in place of just 0 and 1 in vector b. Note that a >= t iff there is a nonnegative integer w s.t. a+w = t.
I will have an office hour on April 17, from 4PM to 6PM.
One of the TAs will have an office hour on April 16. I will post the time after I check it with TAs.
You can pick up your assignment A3 this afternoon (2PM-3PM).
Mar. 31, 2012:
I will hold an office hour on Monday, April 2, from 4PM to 5PM.
If you are struggling to finish the assignment A4/takehome by the due date (Wednesday, April 4), email me and I will consider giving you up to 3 days of extension.
Mar. 28, 2012
Similar to the previous test, there is going to be a question about basic definitions in complexity theory that we have covered so far in the course so make sure you know these definitions from chapter 7 of Sipser.
Mar. 27, 2012
To prepare for the test, you may want to review chapter 7 from Sipser (particularly the NP-completeness proofs) and the excises at the end of the chapter.
There is an office hour tomorrow from 5PM-6PM, drop by my office if you have any questions.
Questions by email are also welcome and I will try to answer email questions quickly (till tomorrow noon).
Mar. 26, 2012:
Assignment A4 is posted.
Solutions for assignment A3 are posted.
Mar. 25, 2012:
The due date for assignment A3 is extended till 6PM Monday, Mar. 26.
The definition of Graph Homomorphism in the assignment is also corrected. If you have solved the question with the previous definition, that is also fine. I have also added an explanation about the extension problem.
We will have the test T2 on Wednesday, Mar. 28, from 6PM-7PM. The test will be only from the complexity theory part of the course we have covered. The space complexity will not be in the test.
Assignment A4 will be posted tonight. The due date for it is Apr. 4, 6PM.
I have added a list of topics selected so far, see below.
Mar. 23, 2012:
There will be an office hour from 4:30PM-5:30PM.
Mar. 15, 2012:
Assignment A3 and takehome are posted. Assignment A4 will be posted also today. The dues dates are also updated.
Please check the the first question of the takehome and let the instructor know your selected topic as soon as possible. Contact the instructor if you have difficulty selecting a topic.
Mar. 3, 2012:
You can drop by Yu Wu's office (SF 4302C) this afternoon to pick up your assignments.
Feb. 28, 2012:
We will continue the course as planned. Tomorrow we will have the first test (from 6PM to 7PM).
The questions in the test will be similar to those you have solved in the assignments, but if you want to see more examples check the midterm tests and their solutions on the following pages:
Remember that this test will cover only the computability part of the course.
The solutions of the last two assignments are now accessible from the course webpage.
For a fast review of the material you can also check François Pitt's lecture notes for CSC363H.
I will have an office hour tomorrow from 4PM to 5:45PM before the test so if you have any questions drop by my office.
The assignments A1 and A2 are marked, but some of them need to be remarked. You can pick them up by this Friday.
Feb. 16, 2012:
We have finished marking the assignments A1. We hope to finish marking assignment A2 during the weekend. Check the website during the next few days for the instructions on how to pick up your assignments.
Next week (Feb. 20-Feb. 24) is the Reading Week, so no lecture/tutorial on Feb. 22.
Test1 will be on Wednesday, Feb. 29, 6PM-7PM. The question will be from the first part of the course (computability theory, chapters: 3, 4, 5). The lecture will follow the test (7PM-9PM). No tutorial on Feb. 29.
Feb. 15, 2012:
We have finished the first part of the course (computability theory) last week. We have started the complexity theory part this week. The plan is to cover the following chapters from the textbook: 7 (time), 8 (space), 9 (intractability).
The due date for assignment A3 is extended to Wednesday, Mar. 7, 6PM . It is going to be mainly complexity theory questions.
There will be an office hour on Monday, Feb. 27, 4PM-6PM, two days before the test. I will announce the place of the office hour later.
Feb. 6, 2012:
There was a problem with assignment A2 not being linked till Saturday. I have simplified the assignment. The due date is also extended till Friday, Feb. 10, 6PM. Considering the simplification and the extension, I think that you should have sufficient time to finish it. Question 2 is also clarified.
If you want to see more questions in addition to those discussed in the tutorial, you can check the exercises in Sipser (our textbook). It has good exercises, many of them with answers. Another good book with lots of excises is Du and Ko (see the references section)
Jan. 30, 2012:
The assignment A2 will be posted by tomorrow.
The deadline for assignment A1 is now extended to Friday, Feb. 3, 6PM.
The solutions for assignment A0 are now posed. Use "csc463h" and "winter12" to access them.
Jan. 25, 2012:
Since we didn't have enough time today to discuss SD-hardness and SD-completeness more carefully, I am thinking about extending the deadline for assignment A1 from Wednesday, Feb. 1, 6PM to Friday, Feb. 3, 6PM. Please let me know by Monday, Jan. 30 if you have any reservations about this.
There will be an extra office hour next week on Monday, Jan. 30, 5PM-6PM.
The questions and solutions of problems discussed in the tutorials are available from Prof. Cook's CSC463H1 Fall 2011 course webpage.
The Complete version of assignment A1 is posted.
Assignment A0 is updated to clarify that machine model is one-sided and that your machines only needs to work on inputs of correct format, you don't need to perform syntax checking.
Added the due dates for future assignments.
Added the dates for tests.
Jan. 24, 2012:
Assignment A0 is updated to clarify the definition of the successor function.
Note that the definition of the TM given in the question 1 (including the table for the transition function) is just an example to explain the format of the answer. You should define your own TM.
Please send the clarification questions about the assignments to the instructor.
Jan. 23, 2012:
You should be able to access LaTeX and Kile on CDF machines. You can find some useful links in the LaTeX resources section.
Assignment A1 is posted. Due date is Wednesday, Feb. 1, 6PM. Questions 4 and 5 will be added after this week's lecture.
Assignment A0 is posted. Due date is Friday, Jan. 27, 6PM.
Jan. 18, 2012:
You can find two TM simulators at the links sections.
Jan. 11, 2012:
Today's tutorial will be an introductory session to the course. I will also explain logistics (marking scheme, etc.).
Jan. 2, 2012:
Course starts on Jan. 11.
Nov. 22, 2011:
Students should check this page regularly (at least once a week) for new announcements.

Assignments (55 points)

Assignments should be written using the provided LaTeX file and the pdf version should be emailed to the email address of teaching assistant containing the appropriate subject line, e.g. ”[CSC463] Assignment 0”. You should include your full name in the email and attach your solutions as a pdf file to it. The teaching assistants will go over the solutions in the tutorial, so no late assignments will be accepted. You should not change the LaTeX template files provided for writting assignments other than filling in the parts marked as TODO. In particular, you should not change the formatting. The answer for each question should not be more than 3 pages.

Assignment 0 (5 points)
Due: Friday, Jan. 27, 6PM
Questions: A0.pdf
LaTeX file: A0temp.tex
Solutions: A0sol.pdf
Marker's Remarks: A0mr.pdf
Assignment 1 (10 points)
Due: Wednesday, Feb. 1, 6PM; Extended: Friday, Feb. 3, 6PM
Questions: A1.pdf
LaTeX file: A1temp.tex
Solutions: A1sol.pdf
Marker's Remarks: A1mr.pdf
Assignment 2 (15 points)
Due: Wednesday, Feb. 8, 6PM; Extended: Friday, Feb. 10, 6PM; Extended: Sunday, Feb. 12, 6PM
Questions: A2.pdf
LaTeX file: A2temp.tex
Solutions: A2sol.pdf
Marker's Remarks: A2mr.pdf
Assignment 3 (10 points)
Due: Sunday, Feb. 19, 6PM; Extended: Sunday, Mar. 25, 6PM; Extended: Monday, Mar. 26, 6PM
Questions: A3.pdf
LaTeX file: A3temp.tex
Solutions: A3sol.pdf
Marker's Remarks: A3mr.pdf, and some counter-examples to common incorrect solutions
Assignment 4 (15 points)
Due: Wednesday, Mar. 21, 6PM; Extended: Wednesday, Apr. 4, 6PM
Questions: A4.pdf
LaTeX file: A4temp.tex
Solutions: A4sol.pdf
Marker's Remarks: TBA

Tests (30 points)

Test 1 (10 points)
When: Wednesday, Feb. 29, 6PM-7PM
Questions: T1.pdf
Solutions: T1sol.pdf
Marker's Remarks: TBA
Test 2 (10 points)
When: Wednesday, Mar. 28, 6PM-7PM
Questions: T2.pdf
Solutions: T2sol.pdf
Marker's Remarks: TBA
Take Home (10 points)
Due: Wednesday, Apr. 4, 6PM
Questions: TH.pdf
LaTeX file: THtemp.tex for Q2 and Q3, THessay.tex for Q1
Takehome Topics
Topic Book Selected by
Cryptography Arora and Barak 3 *
Quantum Computation Arora and Barak 3
Randomized Algorithms Arora and Barak 3
Average Case Complexity: Levin’s Theory Arora and Barak 1
Decision trees Arora and Barak 1
Communication complexity Arora and Barak 1
PCP theorem and hardness of approximation Arora and Barak 1
Interactive proofs Arora and Barak 0
Boolean circuits Arora and Barak 0
Computational Difficulty One Way Functions Goldreich 3
Encryption Schemes Goldreich 3
Approximation, Search or Optimization Goldreich 3
Zero-Knowledge Proof Systems Goldreich 3 *

Final Examination (40 points)

Final Examination (40 points)
When: Wednesday, Apr. 18, 7PM-10PM
Where: BN2N (320 Huron Street, Benson Building, 2nd Floor, Large Gymnasium, North End)
Questions: FE.pdf
Notes:
Faculty of Arts and Sciences April 2012 Examination Schedule
Faculty of Arts and Sciences Examination Reminders
Faculty of Arts and Sciences Examination Rules

Time Table

Policy Regarding Plagiarism and Academic Offense

University of Toronto has strict rules against plagiarism. You must not submit work belonging to others as yours. It is considered an academic offense and will be dealt with accordingly. The work you submit must be your own, if you are going to get help from any resource (books, online resources, people including other students, ...) other than the course material (textbook, course lecture notes) you should acknowledge them explicitly and give proper credit to them in your work.

For this course, you have the permission to discuss and work on assignments together with other students, but you should prepare the written solutions alone. It is fine to get help to understand, but the work you submit must represent your understanding in your words. You should be able to explain what you have submitted to the instructor orally without any previous preparation or notice during the semester. To make sure that you are writing what you have understood in your own words, don't take any notes from your discussions, wait a few hours before writing any notes related to them, and do not show your written answers to other students before due dates. Copying assignments and allowing others to copy your assignment are strictly forbidden.