CSC 236  Intro to Theory of Computation
Section L5101
Fall 2010
Index of this document
Contact information

L5101 
Instructor: 
Gerald Penn 
Lectures: 
R 79, BA 1180 
Office: 
PT 396B 
Telephone: 
(416)9787390 
Office Hours: 
TR 56, or by appointment 
Email: 
gpenn@cdf.utoronto.ca 
Email that includes MIME or HTML attachments will not be read nor responded
to.
For information on section L0101, please read that
section's webpage.
Back to the index
Tutorials
All tutorials are held R 67 in BA 1180.
A bulletin
board has also been created for the class, which will be monitored
by the TAs.
Back to the index
Course outline

Induction

The principle of mathematical induction and its variants

Program correctness

Preconditions and postconditions

Correctness proofs of iterative programs

Correctness proofs of recursive programs

Recurrences

Solution of recurrence equations

Application to the time complexity of divideandconquer algorithms

Propositional logic

Syntax and semantics of the propositional calculus

Propositional equivalences

Applications to the design of digital circuits

Complete sets of connectives

Predicate logic

Syntax and semantics of the predicate calculus

Firstorder equivalences

Applications to query languages for relational databases

Regular expressions and finite state automata

Formal languages

Syntax and semantics of regular expressions

Finite state automata (FSA) as language recognisers

Equivalence of deterministic and nondeterministic FSA

Equivalence of FSA and regular expressions

The ``Pumping Lemma'' and its applications

Contextfree Grammars
Back to the index
Calendar of important courserelated events
T
Date 
Event 
Thu, 16 September 
First lecture 
Thu, 23 September 
First tutorial 
Thu, 23 September 
Assignment 1 distributed,
Quiz 1 (in tutorial) 
Sun, 26 September 
Last day to add course 
Thu, 30 September 
Quiz 2 (in tutorial) 
Thu, 14 October 
Assignment 1 due (in tutorial),
Assignment 2 distributed 
Thu, 21 October 
Midterm 1 (in tutorial) 
Wed, 3 November 
Last day to drop course 
Thu, 4 November 
Assignment 2 due (in tutorial) 
Thu, 11 November 
Midterm 2 (in tutorial),
Assignment 3 distributed 
Thu, 2 December 
Last lecture,
Assignment 3 due (in tutorial) 
1021 December 
Final Exam period 
Back to the index
Evaluation and related policies
There will be five homeworks, two midterm exams, and a final exam. The
relative weights of these components towards the final mark are shown in
the table below:
Homeworks 
27% (3 at 9% each) 
Quizzes 
3% (2 at 1.5% each) 
Midterms 
30% (2 at 15% each) 
Final 
40% 
Important note on midterms: Midterms will be conducted
in tutorial.
Important note on homeworks: Homeworks will be distributed electronically,
collected in tutorial only, and returned in tutorial only. No late
homeworks will be accepted without a signed medical certificate.
With a signed medical certificate, a late outstanding assignment may be
``cancelled'' at the instructor's discretion, in which case the marks for
that piece of work will be distributed over the other marked work for the
course in weighted proportion to the other work's contribution to the course
grade. A missed midterm will be cancelled, but again only with a
signed medical certificate.
Remarking: Homeworks or exams written in pencil or erasable ink
will not be remarked. In the case of homeworks, a request for remarking
should be directed to the tutor who marked the assignment. The tutor
is only required to remark once  if you still believe your solution is
correct, you may appeal to the instructor.
Silent policy: The TA is not obliged to answer questions
posed less than 24 hours before any assignment is due, and is not
obliged to answer questions already answered on the newsgroup at any time.
Students are encouraged to use the bulletin board for the course to pose
their questions.
Policy on collaboration: Discussing homeworks is permitted only
with other students in the class. Copying from others' homeworks
is strictly prohibited  you must write up your solutions on your own.
If challenged by either your tutor or the instructor, you must be able
to reproduce and explain any solution you submit in an oral exam.
No student is permitted to discuss any midterm or final exam with any other
student until the instructor or TAs provide the solutions to the exam.
Failure to observe this policy is an academic offense, carrying a penalty
ranging from a zero on the homework to suspension from the university.
Back to the index
Announcements
In this space, you will find announcements related to the course. Please
check this space at least weekly.

2 December: In lieu of my office hours on Tuesday, 7th December, there
will be a special review session from 5 to 7pm in BA 2155.

2 December: MATERIAL COVERED IN WEEK 12: rightregular grammars,
contextfree grammars, derivations, reflexivetransitive closures, pushdown
automata. You should read Chapter 8.

25 November: MATERIAL COVERED IN WEEK 11: the pumping lemma, constrained
inductive proofs, proving asymptotic bounds.

18 November: MATERIAL COVERED IN WEEK 10: nondeterministic finite state
automata, the equivalence of deterministic and nondeterministic finite
state automata.

11 November: MATERIAL COVERED IN WEEK 9: operations over sets of strings,
regular expressions, regular languages, deterministic finite state automata.

4 November: MATERIAL COVERED IN WEEK 8: relational databases, formal language
theory, operations over strings. You should read Chapter 7.

28 October: MATERIAL COVERED IN WEEK 7: the language of firstorder predicate
logic, quantifiers and scope, prenex normal form, interpretations of firstorder
logic. You should read Chapter 6.

21 October: MATERIAL COVERED IN WEEK 6: common proof methods formulated
in propositional logic, disjunctive normal form, conjunctive normal form,
Boolean functions, complete sets of connectives, predicates and relations.

14 October: MATERIAL COVERED IN WEEK 5: propositional logic, truth assignment
functions, truth tables, logical equivalence. You should read Chapter
5.

7 October: CORRECTION TO ASSIGNMENT 1: Question 2 should read "n,m ≥
2," instead of "n+m ≥ 2."

7 October: MATERIAL COVERED IN WEEK 4: Recursive program correctness.
You should read the rest of Chapter 2.

30 September: MATERIAL COVERED IN WEEK 3: iterative program correctness,
partial correctness, loop invariant lemmata, termination sequences.
You should read Chapter 2, sections 16.

23 September: MATERIAL COVERED IN WEEK 2: complete induction, structural
induction. You should read Chapters 3 and 4 in the notes.

16 September: MATERIAL COVERED IN WEEK 1: the principle of wellordering,
(simple) induction, common pitfalls of inductive proof, strengthening the
inductive hypothesis. You should read Chapters 0 and 1 in the course
notes.

16 September: PREREQUISITES. To take this course you must (1) have
passed (CSC 148 or CSC 150) and CSC 165 and (2) either have
a CGPA of at least 1.5 or be enrolled in a CSC subject POSt. Note
that the University's automatic registration system does not check for
prerequisites: even if you have registered into the course, you will
not receive credit for it unless you had satisfied the prerequisite by
the time you registered.
Back to the index
Handouts
In this space you will find online postscript versions of course handouts,
including homeworks and solutions (posted after the due date).
To view these handouts you will need access to a postscript previewer.
If your machine does not have the required software, you can allegedly
download
it for free.
Back to the index
Old exams
Some midterm and final exams for earlier incarnations of this course
(with no solutions).
Back to the index
Gerald Penn, 6 December,
2010
This webpage was adapted from the webpage for an earlier instantiation
of this course, created by Vassos
Hadzilacos.