CSC236 / Introduction to the Theory of Computation

Summer 2006

Table of Contents


Announcements
Important Dates
Course Information
Lectures
Tutorials
Homework / Midterm Test
Grades

Announcements


August 22 Unofficial final grades have been posted. I added ten marks to every exam score: the mark entitled "exam_adjusted" includes these extra marks, while "exam_unadjusted" represents your raw score (in case you're curious). The grade called "final" is your final grade (i.e. either the average of exam_adjusted and term, or just exam_adjusted, whichever is higher).
August 18 Grades for the second homework are now online. I will leave the graded papers with the CSSU sometime soon (but probably not today). Unofficial exam grades will likely be available online during the weekend.
August 11 Here are a couple of links to related courses at MIT, where you might be able to find examples with solutions to help you study. You can also browse for other courses from the main OpenCourseWare page. Thanks to Ryan for pointing these out.
August 9 If you didn't attend the lecture yesterday, please note that there is no late penalty for homework #2. You may submit your solution via the drop box, without penalty, until friday at 6pm. After 6pm on friday I will no longer accept solutions for the homework. Sample solutions will be available friday evening.
August 2 As I mentioned in lecture yesterday, no more questions will be added to the second homework. I've split the homework into two parts again: please hand in the parts separately with the cover sheets, as with the first homework.
July 31 Grades for the midterm test have been posted. I'll return the test papers on tuesday.
July 22 I posted the first five questions of homework #2 in the homework section.
July 22 For your information, the final examination timetable has been published by the faculty of arts and science. here is a link to it.
July 12 On Tuesday, July 18 there will be an opportunity for you to discuss the grading of your homework with the tutors who marked it. This office hour will be in the usual place and time, i.e. BA3234 at 4:00 pm.

If you believe that there was an error in the grading of your assignment, do the following: on a new sheet of paper, write down precisely where you believe an error was made. Staple or clip this sheet to the front of your assignment and submit it in lecture or during office hours. Note that there will be a statute of limitations for re-mark requests (i.e. a time limit after which they may no longer be submitted), so please do this as soon as you can.

July 12 You can now find sample solutions for the midterm test in the homework section.
July 11 I just posted the grades for part 2 of the homework.
July 6 I will be holding an extra office hour on Friday, July 7, at 4:00 pm in BA3234. This session is specifically to discuss the solutions to the first homework, and to help you prepare for the midterm test.
July 6 The late part 1's have now been graded, and the marks posted.
July 4 Most of the grades for part 1 of the homework are posted in the grades section. Part 2, and the late part 1's, haven't been completely graded yet.
July 4 Sample solutions for the first homework are now available in the homework section.
June 30 Midterm test:
  • The midterm test will be on Tuesday, July 11 during the regular lecture time (7-9 pm)
  • Topics which are fair game: everything up to, and including, first-order logic
  • Here is one page that has several links to previous midterms. An internet search is a good way to find others. However, note that it may not be sufficient (or even necessary) to study every question on those tests.
  • Hania will be discussing (some of) the solutions to the homework questions in tutorial on Tuesday
June 28 Some time this afternoon, there should be a drop box available for this course in the usual place in Bahen: please submit your late assignments there.
June 27 I'm working on a way for you to hand in late assignments: with any luck, I will post an announcement here in the early afternoon tomorrow with instructions. In the meantime, you can try to find me in my office, Sandford Fleming room 4301-E.
June 23 It appears that many of you are having difficulty formulating a loop invariant for question 5. I gave a fairly substantial hint in yesterday's office hours, which I've written up. You can view the hint here.
June 22 Since I missed tuesday's office hours, I'm holding an extra office hour on monday at 2 pm. Also, you do not need to send me a request for today's office hours if you wish to come: I will be there in any case at 6 pm.
June 13 I added one last question to homework #1. The homework is now complete: no more questions will be added. Please note the submission instructions at the top of the assignment. The two cover sheets are available in the homework section.
June 8 I added two more questions to homework #1. For those of you who weren't in class on tuesday: I plan to separate the homework into two parts, and ask you to submit each part separately, so that two TAs can mark them in parallel. However, I haven't yet decided on the division (since the homework is not yet complete). So, in the meantime, please write the solution to each question on a separate sheet of paper, so as to be able to partition your solutions accordingly when I make up my mind.
June 1 There was an error in question 5 of the homework: the line i:=i+1 was missing from the program. You may need to clear your browser's cache to download the new version.
May 31 The first five questions of homework #1 are now available from the homework section. More questions will follow soon.
May 25 I scheduled a second set of office hours on thursdays, from 6-7 pm, in BA3234. These office hours will be by request only: write me an email if you want to meet with me during these office hours (try to give me some notice, say by wednesday night).
May 18 Note that there will be a tutorial next week, from 6-7 pm in BA1190. I will be posting some exercises each week in the tutorials section. Time permitting, the tutor will discuss the solutions to these exercises in the tutorial.
May 17 I scheduled one set of office hours for tuesdays from 4-5 pm, in BA3234, starting next week.
May 17 Apparently I do not have the authority to waive the CGPA requirement. If you want this requirement waived, you must submit your request directly to the undergraduate office (on the 4th floor of Bahen) by May 31. I am able to waive course prerequisitites, so these will proceed as we discussed yesterday.

Important Dates


May 16:First lecture
June 27:Homework #1 due
July 11:Midterm test
July 24:Last day to drop without academic penalty
August 8:Last lecture, homework #2 due

Course Information


Instructor:Paul McCabe
Lectures:Tuesdays, 7-9 pm, BA1190
Tutorials:Tuesdays, 6-7 pm (no tutorial in the first week)
Office hours:Tuesdays, 4-5 pm, BA3234
Thursdays, 6-7 pm, BA3234 (by request only)
Textbook:"Course notes for CSC236", by Vassos Hadzilacos
(Available from the U of T bookstore)
Marking Scheme:
Homework:20%
Midterm exam:30%
Final exam:50%
If your final exam grade is higher than your term grade, then your final exam will count for 100%.
You must achieve a grade of at least 40% on the final exam to pass this course.
Homework is due at the beginning of lecture. Late homework will be penalized 10% per day.
Click here to view a copy of the syllabus.

Lectures


May 16Induction (Ch. 1)
May 23Program Correctness (Ch. 2)
May 30Recursively-Defined Functions, Divide and Conquer Recurrences (Ch. 3)
June 6Recursively-Defined Sets, Structural Induction; Propositional Logic (Ch. 4, 5.1-5.2)
June 13Propositional Logic, Boolean Functions, Normal Forms (Ch. 5.3-5.10)
June 20Complete Sets of Operators; Predicate Logic (Ch. 5.11, 6.1-6.3)
June 27Non-standard Structures, Axioms, Relational Databases
July 4Formal languages, Regular Expressions, Deterministic Finite State Automata (Ch. 7.1-7.3)
July 11Midterm test
July 18Non-deterministic FSAs + equivalence to DFSAs, Closure Properties of Regular Languages
July 25Equivalence of FSAs and Regular Expressions; The Pumping Pemma
August 1Context-free Grammars, Pushdown automata
August 8Pumping Lemma for CFLs, Non-Context-Free Languages; Review

Tutorials


May 23Tutorial exercises
May 30Tutorial exercises
June 6Tutorial exercises
June 13Tutorial exercises
June 20Tutorial exercises
June 27Tutorial exercises

Homework / Midterm Test


Homework #1Cover sheets:Part 1Part 2
Midterm Test
Homework #2Cover sheets:Part 1Part 2

Grades


Click here