Main Course Webpage

General information


Here are some guidelines for electronic communication (email and bulletin board postings). These are meant to allow us to better cope with the potentially high volume of email we receive, and to answer all of your queries more efficiently.

  • Please use email for all personal matters; post all other questions/comments on the course bulletin board.
  • Please use a descriptive subject line—be specific (for email, always include the course number).
  • To help prevent your messages being incorrectly tagged as spam, please email or post from your UTORmail account ( and avoid using HTML or MIME.
  • We will generally answer queries within two business days (not counting weekends), although we may take longer during particularly busy times (e.g., around assignment due dates). For your own sake, please do not rely on getting same-day answers (which we do not have the resources to guarantee, unfortunately).

Giving feedback

Rather than wait until the official course evaluations at the end of the term, by which point it's too late to make a difference, please feel free to get in touch with me at any point during the term with any suggestion or complaint that you have about any aspect of the course. In particular, don't hesitate to let me know if there are aspects of the course that you particularly like, so that I can keep them that way, or if there are specific aspects that you dislike, so that I can make changes (or discuss with you my reasons for doing things that way).

If you are uncomfortable bringing your concerns directly to me, you might consider mentionning it to your TA so that they can pass them on to me. Failing that, feel free to use any means that make you more comfortable to give me feedback: writing a letter and slipping it under my door, sending anonymous e-mail, etc. (But don't abuse that: it's hard to get a discussion started when you cannot reply to the other person, and some of those issues undoubtedly require discussion!)

Note that this does not mean that I will accept unfounded complaints! If you have a complaint or criticism that you are ready to discuss in a reasonable manner, that's great. If you are merely unhappy but you have nothing constructive to say (e.g., "this course is terrible", with no thought about why or how it is terrible), then you should wait and think it over until you come up with something more concrete that we can work with. Remember that the goal is to help improve the course, not just to vent. But in that case, please do think about it and let me know!

Contact information


Name: François Pitt
Email: fpitt [at] (this is the best way to reach me)
Phone: 1 416 978-3707
Fax: 1 416 946-7132 (please include my name on all faxes)
Office: Room BA 4264 (Bahen Centre for Information Technology, 40 St. George Street)
Mail: Department of Computer Science, University of Toronto
Toronto, Ontario, M5S 2E4 (CANADA)

Regular Office Hours

Instructor: T 1:30–3:30, W 12:30–1:30, R 3:30–5:30, in room BA 4264.
TA: T.B.A.

Tutorials and Lectures

Lectures take place MWF2 in room BA 1220.

Tutorials take place MWF2 in room BA 1220—note that tutorials will take place on DIFFERENT days of the week throughout the term.

There will be a tutorial on the first week, though it will be more of an introductory lecture, with review of the prerequisite and background material for this course. It will be given by the instructor in the lecture room.

See the second page of the Course Information Sheet (PDF) for a complete calendar of important dates and course events.

Grading scheme

Work Weight
6 Exercises: 12% (2% each)
3 Assignments: 24% (8% each)
2 Term Tests: 24% (12% each)
1 Final Examination: 40%
  • Homework exercises and assignments are due by 6pm on their due date—see the Homework page for detailed submission instructions.
  • Exercises are to be completed individually, to help you cement your own understanding of the course material.
  • Assignments are to be completed in small groups (3–4 students), to help you learn together by working through more difficult problems. (Details of the mechanisms for this are provided on the Homework page.)
  • Term Tests will be closed-book, but you will be allowed one aid sheet for the final exam.
  • On tests and exam, answering "I don't know" (and nothing else) is worth 20%, to encourage awareness of (and honesty about) your level of understanding. This does not apply to exercises and assignments, where you have time to ask questions and learn.
  • 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 below a passing grade) if your mark on the final exam is below 40%, irrespective of your computed final mark. This is to ensure that everyone who passes the course has at least a rudimentary understanding of the material.
  • See the Course Information Sheet (PDF) for the exercise, assignment and test due dates, and below for the course policies on grace days, special consideration and remarking requests.
  • Check the Homework page and the Tests/Exam page for more information and policies specific to each exercise, assignment or term test.

Policy on grace days

In order to allow you to better manage your time, each student will be allotted three (3) "grace days" at the start of the term.

At any point during the term, you may submit homework one or two day(s) late (but not three days late), without penalty, by using up one or two of your grace days—the time of submission remains the same.

It is not possible to use "partial" grace days—a grace day is either used fully (allowing you to submit your homework up to 24 hours late), or not at all.

Any homework submitted late after all of your grace days have been used up will be penalized by 33.33% for each day of lateness—where the number of days is rounded up, i.e., even just a few minutes late will be considered the same as one full day late. It is almost certainly better to submit partially completed homework on time!

Grace days can only be used for homework—it is not possible to use grace days to write term tests on a different day than the rest of the class.

In order to submit a group assignment one day late without penalty, there must be as many grace days used up as there are students in your group (similarly for submissions two days late). Normally, each student in the group will use up their own grace day(s). But if one student has run out of grace days, it is possible for someone else to "cover" by using up more of their grace days. Note that this should only be done after careful consideration: an unscrupulous student could use this to take advantage of others in the group in order to submit more late work than their grace day allotment would normally allow.

Policy on special consideration

If you are unable to complete homework or if you miss a term 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 other words, you risk getting a mark of zero for unsubmitted work unless you contact your instructor promptly.

In order to receive special consideration, you must fill out the following Special Consideration Form (PDF) [see the LaTeX links below for the source file] 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 (PDF). You can also obtain a paper copy of this certificate from your college registrar or in your registration handbook. (A simple "note" from your doctor is unfortunately not acceptable.)

Policy on remarking requests

Important Change:

For work that has been marked and returned electronically (by e-mail), please submit all remarking requests electronically instead of on paper—simply send an e-mail to the instructor with the details of your request. Make sure to include your CDF username and please do not attach your homework to your request (we already have the electronic copy).

Original policy

All remarking requests must be received within one month of the date when the homework or test was returned. It is your responsibility to check your CDF email regularly (for work returned electronically) or to pick up your homework or test from the instructor during office hours (for work returned on paper during lecture or tutorial).

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 homework or test, just show it to your instructor (not your TA).

For all other remarking requests, please print this Remarking Form (PDF) [see the LaTeX links below for the source file], fill it in completely, and attach it to your homework 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 homework 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 unfortunately not good reasons.

Give the form and your homework 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 homeworks or tests.

If you are still not satisfied after getting back your remarked homework or test (or after having a meeting with the marker), contact your instructor to discuss your situation.

Textbook and references

Required textbook

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

LaTeX links

LaTeX is a general-purpose typesetting system that makes it easy to generate high-quality documents, particularly when formatting mathematical formulae.

Source files

Here are source files for the various handouts, forms and cover sheets used in this course, as well as macros for all course-specific notation.

Tutorials, guides, references, etc.

Useful links