University of Toronto -- Department of Computer Science
St. George Campus -- Fall Session 2004

CSC 363H: "Computational Complexity and Computability"

Main Course Webpage

News Flash! (See the Announcements for full details.)

Mon 10 Jan: Unofficial final grades posted.
Fri 7 Jan: A4 marking scheme and comments posted.
Thu 6 Jan: A4 marks posted; A4 available for pickup.
Exam marks and unofficial final course marks will be posted over the weekend.

Site index.
Course newsgroup. New as of Tue 28 Sep!
Course schedule.
Important dates.
Policy on lateness and missed term tests.
Policy on special consideration.
Grading scheme.
Policy on remarking requests.
References and textbooks.
Useful links.

Site index

Course websites for the suburban campus and enriched section.
Policy on Electronic Correspondence. READ THIS!
Guidelines for Avoiding Plagiarism.
Important Note on Feedback.
Course Information Sheet (Adobe PDF document). Updated at 18:00 on Fri 10 Sep 2004.
Course Announcements (last updated at 08:49 (EST) on Mon 10 Jan 2005).
Current Course Marks (last updated at 08:49 (EST) on Mon 10 Jan 2005).
Lecture Summaries and Tutorial Exercises (last updated at 12:33 (EDT) on Mon 13 Sep 2004).
Homework Assignments (last updated at 11:25 (EST) on Fri 19 Nov 2004).
Term Tests and Final Exam (last updated at 16:10 (EST) on Mon 24 Jan 2005).

Course newsgroup

The course newsgroup is for discussions of topics related to the course, including questions and answers about the course material, tutorial exercises, textbook readings, lecture material, or additional problems from the textbook (but see the next paragraphs for important warnings).

Before you post a message to the newsgroup, you must read our Policy on Electronic Correspondence. By posting to the course newsgroup, you assert that you have read and understood this policy completely, including the important warnings about plagiarism.

Be aware that the danger of a course newsgroup in a theoretical course is that it is quite easy for students to give away much of the solution in their attempts to ask a question about a problem. Sometimes, in trying to see the final details of a solution, a student may post a statement that she considers "obvious". Yet, arriving at that initial statement was actually a significant part of the solution process. Similarly, a student might ask, "Is such and such a reasonable assumption?" and in so asking is giving away a big piece of the solution.
If you are unsure whether or not your question is "reasonable", please play it safe and ask your TA or instructor directly instead.

Read the newsgroup.
Post to the newsgroup.

Instructor office hours

Instructor	Office	Phone	E-mail	Office Hours
François Pitt	SF-4306E	416-978-3707	fpitt at cdf dot utoronto dot ca	T 3-5, W 3-5

TA office hours

TA office hours will be held as needed during the term (not on a regular basis). They will be announced during lectures and on the Announcements section of this website.

Lecture schedule

Section	Room	Time	Instructor
L0101	BA 1170	MW 2	François Pitt
L5101	BA 1180	T 7-9	François Pitt

Tutorial schedule

You have been assigned a specific tutorial section (listed below), based on the first letter of your last (family) name. Please attend the tutorial section that you were assigned, to allow us to keep the tutorial sizes balanced. If you have a problem with your tutorial, please contact your instructor immediately (it's better to fix problems than to ignore them).

Note that tutorial sections may need to be reorganized during the first few weeks of term in order to keep them balanced. Any such change will be announced ahead of time in lecture and on the Announcements page.

Section L0101

Time	Room	TA's name	for students whose last name starts with...
F 2	BA 3008	Alex Hertel	A - C
F 2	BA 3012	Philipp Hertel	D - K
F 2	BA 3116	Paul McCabe	L - S
F 2	BA 3000	Phuong Nguyen	T - Z

Section L5101

Time	Room	TA's name	for students whose last name starts with...
T 6	BA 3008	Alex Hertel	A - L
T 6	BA 3012	Philipp Hertel	M - Z

Important dates

Thursday 9 September	First day of classes
Wednesday 22 September	Deadline to enrol
Tuesday 5 October	Assignment 1 DUE
Monday 11 October	Thanksgiving (University closed)
Friday 15 October (for L0101) Tuesday 19 October (for L5101)	Term Test 1
Tuesday 26 October	Assignment 2 DUE
Wednesday 3 November	Deadline to drop
Friday 19 November	Assignment 3 DUE
Friday 26 November (for L0101) Tuesday 30 November (for L5101)	Term Test 2
Wednesday 8 December	Assignment 4 DUE
Wednesday 8 December	Last day of classes
December 13 - 20	Final Examination period

For the assignments, submission instructions and deadlines are given on the Assignments page. For the term test(s), the specific time and place are given on the Term Test page.

Policy on lateness and missed term tests

All assignments will be due no later than 6pm on their due date (see the important dates above for the exact due date of each assignment). Late assignments will be accepted up to 24 hours after the deadline, with the following penalties.

Submission time	Penalty (as a percentage of the total)
by 6pm on Tuesday	no penalty
by 10am on Wednesday	-10%
by 6pm on Wednesday	-25%
after 6pm on Wednesday	-100%

Note that lateness penalties are computed as a percentage of the total marks on the assignment, so for example, a student who gets 57/100 with a penalty of -10% will have their mark recorded as 47/100 (57/100 - 10/100).

Late assignments must be handed into the course drop box in room BA 2220 (or to the secretary in room SF-3302 who can verify the submission time).

If you miss a term test, you will get a mark of zero unless you have informed your instructor beforehand and they have agreed that you may miss it. (See the section on special consideration below to request special consideration because of illness or other circumstances.)

Policy on special consideration

If you are unable to complete homework or if you miss a midterm test due to major illness or other circumstances completely outside of your control, please contact your instructor immediately in order to receive special consideration. Note that special consideration will be considered on an individual basis and will not be given automatically.

In order to receive special consideration, you must fill out the following Request for Special Consideration form and bring it to your instructor together with your supporting documentation.

In the case of illness, medical documentation must be supplied on the standard University of Toronto Student Medical Certificate (Adobe PDF document). You can also obtain a paper copy of this certificate from your college registrar. (A simple "note" from your doctor is not acceptable.)

Grading scheme

4 Homework Assignments:	40%	(10% each)
2 Term Tests:	20%	(10% each)
1 Final Examination:	40%

In order to pass the course, you must achieve a mark of at least 40% on the final examination. In other words, you will automatically fail the course (your final mark will be lowered to no more than 40) if your mark on the final exam is below 40%, irrespective of your computed final mark.

Policy on remarking requests

All remarking requests must be received within one month of the date when the assignment or test was returned. (It is your responsibility to pick up your assignment or test from the CSSU, in room BA-2283, if you were not in lecture or in tutorial when it was returned.)
We CANNOT accept remarking requests for term tests that were written using pencil!
Your mark will decrease if the marker sees something that was incorrectly awarded too high a mark.
If there is a simple addition mistake in your assignment or test, just show the work to your instructor (not your TA).
For all other remarking requests, please print this remarking form, fill it in completely, and attach it to your assignment or test. (Remarking requests will not be considered if the remarking form is missing or incomplete.)
You must be specific and clearly demonstrate that the marking scheme was not followed correctly for your assignment or test. Note that marks are awarded based on merit, not on need, so statements like "I worked really hard" or "I really need those marks" are not good reasons.
Give the form and your assignment or test directly to the marker or to your instructor. Remember to submit your work together with the form.
If you are comparing your work to that of another student, hand in BOTH assignments or tests (your request will be ignored otherwise).
If you are still not satisfied after getting back your remarked assignment (or after having a meeting with the marker), contact your instructor to discuss your situation.

References and textbooks

Required textbook

Michael Sipser: Introduction to the Theory of Computation. PWS Publishing Company (1997), ISBN: 0-534-94728-X.

The textbook will be used for readings and exercises throughout the term.

The author maintains a list of errata for the textbook.

Additional references

Hopcroft, Ullman: Introduction to Automata Theory, Languages, and Computation. Addison-Wesley (1979), ISBN: 0-201-02988-X.
(For material on computational computability.)
Garey, Johnson: Computers and Intractability: A Guide to the Theory of NP-Completeness. W.H. Freeman (1979), ISBN: 0-7167-1045-5.
(For material on computational complexity.)
Cormen, Leiserson, Rivest, Stein: Introduction to Algorithm (2nd edition). McGraw-Hill (2001), ISBN: 0-07-013151-1.
(Good general-purpose reference.)

University of Toronto -- Department of Computer Science St. George Campus -- Fall Session 2004