CSC463H Winter 2012

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:

Midterm questions and solutions from CSC463 by Prof. Cook
Midterm questions and solutions from CSC365 by Prof. Cook

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

Lecture Notes

Time Table

Links

DCS Resources: Discussion/Bulletin Board for CSC463H
Note: although the instructor or the teaching assistant might check the board from time to time, in general it is not monitored, if you want to ask a question from them please email it to them or ask in person.; Undergraduate CS Course Help Centre
Course Websites from Previous Years: CSC463H1 Fall 2011: Computational Complexity and Computability by Stephen Cook; CSC2401H Fall 2011: Introduction to Computational Complexity by Stephen Cook; CSC363H1 Winter 2011: Computational Complexity and Computability by François Pitt; CSC365H1 Winter 2011: Enriched Computational Complexity and Computability by Stephen Cook
Turing Machine Simulators: Turing IDE
Note: this seems to be a good TM simulator. I may add more samples in future.
Samples: sample.tm, ending_in_1.tm, add_1_to_the_right.tm, erase.tm, shift_right.tm.; Tm
Note: another TM simulator.
LaTeX Resources: TeXLive, a cross platform TeX/LaTeX distribution; LEd, editor for Windows; Kile, editor for Linux/Unix; TeXShop, editor for Mac; TeXMaker, cross platform editor; TeX.SX, Q & A site for TeX/LaTeX; A (Not So) Short Introduction to LaTeX2e; Symbols accessible from LaTeX; The Comprehensive TeX Archive Network
Some Interesting Articles: Turing Machine, Wikipedia.; Turing Machines, The Stanford Encyclopedia of Philosophy (Spring 2011 Edition).; Alan Turing, "On Computable Numbers, with an Application to the Entscheidungs problem", 1937.; Stephen A. Cook, "The P versus NP Problem", 2000.; Bill Gasarch, "The P =? NP poll", June 2002.
Misc: Theory Group at University of Toronto, Department of Computer Science; Complexity Zoo; Mathematics StackExchange, a Q & A site for mathematics; Computer Science StackExchange, a Q & A site for Computer Science; cstheory: TCS StackExchange, a Q & A site for TCS; Theory Matters; ACM SIGACT
Some Theory Blogs: Theory of Computing Blog Aggregator maintained by Arvind Narayanan; Gödel’s Lost Letter and P=NP blog by Richard J. Lipton and Kenneth W. Regan; in theory blog by Luca Trevisan; my choices by Oded Goldreich; Computational Complexity blog by Lance Fortnow and Bill Gasarch; Shtetl-Optimized blog by Scott Aaronson; cstheory community blog

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.

For more information see Advice About Academic Offences by Jim Clarke

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

Course Info