CSC236 at UTM - Introduction to the Theory of Computation - Fall 2008

Lecture: Monday 14 - 16, SE 2082 Tutorial: Friday 14-15, NE 268

Instructor: Avner Magen

Office hours: Monday 12-13 (SB 4062, 905-569-4741).

Tutor: Daniela Rosu (email: drosu at cs dot utoronto dot ca)

Office hours: Friday 15-16 (NE 142).

Useful Information


Assignments and Problems sets

Selected lecture notes

lecture 7: correctness, recursive and iterative programs
lecture 11: Automata. Regular languages.
Here are examples for reasoning about some languages that are accepted by automata.


Date Announcement(s)
Office hour TODAY at my * UTM * office 3-5. returned A3 will be available and can be picked from my room. (sorry for the very late notice -- I was sick and didn't know if I could make it).
I will hold office hour at my ** St George ** office, SF2301B tomorrow Friday 1-3.
solutions to PS6 available.
solutions to A3 available.
Here is what the head page of the exam will look like. This will confirm that an aid shet is allowed and you can also see the number of questions and relevant weights.
Here are (partial) solutions to term test 2.
Ps6 is up. You don't have to submit it, but remember that this is a very good hint to what the formal-languages-chapter questions in the exam will be like!
Extension to A3. Will be due Dec 5.
A correction for A3 Q1. The 'while' condition in the code should read "while (j <= length (A)" (and not j < length A). Additionally, there should be a command to increment j. My apologies! A new version was posted 9:20PM today.
solutions to PS4+PS5 are up
Some sample questions for the test are poted here
Assignment 3 is posted
Material for the test:
(i) running time of recursive programs. (this includes understadning recursive functions and finding/estimating a closed form for them.) Chapter 3.2 + 3.3
(ii) program correctness for recursive programs.
(iii) program correctness for iterative programs. Whole of Chapter 2 for (ii) and (iii)
(iv) the very first class about formal languages which includes operation of strings, and operations on languages, but excludes regular expressions. Chapter 7.1
I will post some sample questions to help prepare for the test later on.
IMPORTANT: There will be extra class Thursday 13/11 from 11AM to 1PM. Location: Ganita lab SE 3023C.
I suggest having an extra lecture, reviewing issues that seem to require more clarification. I will concentrate on program correctenness and a bit on formal languages, but if you have questions on any part of the course, I will try to answer them. The times I suggest:
Thursday (Nov 13) 11-13, or
Thursday (Nov 13) 13-15.
Please send me an email if you are interested and which of the above options can you do (if you can either one please let me know that too).
PS5 is ready.
Due to popular demand, Daniela will hold office hours. This will be right after tutorial, Fridays 15-16 starting THIS WEEK (Nov 7). Room NE 142.
solutions to A2 available.
today (lecture 8) we started by discussing section 2.4 of the text. Everything in Chapter 2 of the text should look familiar enough (even though we have not covered all examples. We then started to discuss Formal Languages. Please review chapter 7, section 7.1+7.2.
A minor clarification to Q4 was added in the hints page for A2.
PS4 is posted. Due Nov 7.
Notice that I have added a section for selected lecture notes. This is mainly to cover critical parts when introducing themes or examples tht are not covered by the text.
Make sure you checked the hints in the handouts page. Hints file was updated today 27/10.
If you downloaded the assignment before 16/10 make sure you do it again, as there were some small changes that were added to the version then: bonus question was added to Q4, and the requirement that b and e be natural numbers, with e >= b was added at he same question.
The due date for Assignment 2 has changed to November 3. This is to allow for the needed material to be well "digested". The Assignment is already available.
material for the test: Cahpter 1 about induction (simple and complete induction and well ordering principle. Also, the first class about recursive functions (Chapter 3,section 1).
Reading material from the book - chapter 3, section 2.
Hints and clarifications to A1 are posted (check "handots" link above).
Notice that Q4 there should be submitted only as part of the second assignment in October 27.
Problem set 2 is uploaded. Due 26/9.
I beleive the problem with viewing the page in explorer is fixed. Please tell me if you still detect funny behaviour.
I just realized that the course page cannot be viewed properly with windows explorer. I am trying to fix that. Meanwhile, here is the Assignmetns and Problems sets (or, better yet, use firefox...).
Remember -- office hour today at 12:00.
Assignment one is ready. Check above under "handouts".
Tutorial are in NE 268 from now on. There was a confusion (responsilibity is mine not Daniela the TA) and Daniela was teaching in the old classroom.
Text book will be available at the bookstore next week. Meanwhile, here is a pdf version of chapters 0,1,2.
Don't forget there the first tutorial will be held tomorrow, Friday 12/9.
First problem set is uploaded. Due next Friday, 19/9.
Web page just set up. Still very partial currently. Will become complete next week