CSC 236F -- Introduction to Theory of Computation

Fall 2007, UTM

Index of this document

Contact information

Instructor: Avner Magen
Lectures: Mondays, 2-4, NE 268
Office: SB 4062
Telephone: 905-569-4741
Office Hours: Monday 1-2 or by apinemtment
Tutor Alireza Moayerzadeh
Tutorials Friday, 2-3, CCIT 2150 (starting Oct 5)

Back to the index

Course (rough) outline

Back to the index

Text Book

Course notes for CSC B36H/236H/240: Introduction to the Theory of Computation, by Vassos Hadzilacos, Copyright 1998-2006. Identical to last year's version.

Also, for the part about regular languages, use chapter 1 of the book by Michael Sipser: Introduction to the Theory of Computation. PWS Publishing Company (2005), ISBN: 0-534-95097-3.
Back to the index


  • Assignmetns and Problems sets
  • Tutorial Exercises and Lecture summaries

  • Announcements

    (in this space, you will find announcements related to the course. Please check it regularly.)

  • Jan 9: I know you are impatient about the marks for the course. I am planning to enter them to ROSI today or tomorrow. So stay strong!
  • Dec 19: PS3 is ready for pick up at the office (with Kathleen).
  • Dec 18: Office hour tomorrow, Wed 19/12, 11:00-13:00, at my office SB4062.
  • Dec 18: some clarifications about the exam:
    1.Context Free Langauges/Pushdown Automata will not be covered.
    2. Aid sheet: should be handwritten (as it says on the instructions in the cover page I posted last week.
  • Dec 16: Unfortunately I won't be able to hold office hourse tomorrow: I am out of town and got stranded due to the storm. I will keep you posted about a possible alternative tomorrow, Monday.
  • Dec 13: Here is the cover page of the exam which contains instruction and general information.
  • Dec 11: I may be having office hour on Monday, 17/12, 11-1,. Please let me know if this time is good for you and whether you think you will attend.
  • Nov 28: Problem 3 was uploaded.
  • Nov 21: Check the last update for A2 (simpllifying question 4)!
  • Nov 20: Deadline extension for A2: You should submit it in class, Monday 26/11. Also, notice that two more questions were added to the assignment.
  • Nov 10: Assignment 2 was uploaded.
  • Nov 1: Problem set 2 was uploaded.
  • Nov 1: Please prepare questions from PS1,A1 or the term test. There will be some time to go over such questins in tutorial tomorrow.
  • Oct 30: Deadline extension for PS2: You should submit it by 2:00 PM in tutorial, or at the drop box.
  • Oct 24: I will be availabe Thursday Oct 25 for office hour to ask questions re the term test. Any time between 2 and 4:30 is good. To remind you, my room is SB 4062
  • Oct 24: TERM TEST. The test will be closed book (no aid allowed). It will be on all of the following material: simple induction, complete induction, well ordering, running time of recursive algorithms, recurrence relations and how to solve them. Notice that the test will notinclude program correctness.
  • Oct 17: Deadline extension for A1: You should submit it in calss on Monday 22/10. Notice that Prof C. Rackoff will replace me in that lecture.
  • Oct 15: Check the pdf version of A1 again. There was a typo in the addendum.
  • Oct 14: A small addendum to question 4 was introduced.
  • Oct 7: Assignment 1 was uploaded.
  • Oct 7: No class tomorrow, Monday (thanksgiving day). Next week there will be a lecture instead of tutorial. Same time and place (Friday Oct12, CCIT2150).
  • Oct 4:Remember -- submit your assignments tomorrow, Friday Oct 5 at the tutorial, or before tutorial in the drop box.
  • Oct 4:Tutorial from now on in CCIT2150 which is a much bigger room.
  • Oct 1:There is one or two PS1 papers that were found in the drop box. If you would like to get it back and improve it before the new deadline of Oct 5, please collect it from the Undergraduate Counselor, Kathleen Kazmeirczak, in SB-4004.
  • Oct 1: Since there were some typos, and a hint that was added in the last minute, I decided to give an extension for submitting PS1. The new due date is Friday, Oct 5, at the tutorial, or before it in the box. For those who have already submitted when reading this, you will be allowed to take your papers back and improve them. Sorry about this last minute notice.
  • September 29: The following Forum , linked also from the StG 236 webpage, may be useful.
  • September 21: Problem set 1 was uploaded.
  • September 19: Check the Exercises page, and solve first set for Friday's tutorial.
  • September 16: I was assured that the bookstore now carries the textbook.
  • September 12: There will be tutorial this Friday, Sep 14, at 2:00.
  • Back to the index


    The course infosheet

    Here is a link to the webpage of a similar course taught in St George Campus by Prof Francois Pitt.

    Forum discussing assigments, clarifications etc.,

    Important dates (including marking scheme)