CSC 236 -- Intro to Theory of Computation
Section L5101
Fall 2010
Index of this document
Contact information
|
L5101 |
Instructor: |
Gerald Penn |
Lectures: |
R 7-9, BA 1180 |
Office: |
PT 396B |
Telephone: |
(416)978-7390 |
Office Hours: |
TR 5-6, 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 web-page.
Back to the index
Tutorials
All tutorials are held R 6-7 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 divide-and-conquer 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
-
First-order 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
-
Context-free Grammars
Back to the index
Calendar of important course-related 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) |
10-21 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: right-regular grammars,
context-free grammars, derivations, reflexive-transitive closures, push-down
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: non-deterministic finite state
automata, the equivalence of deterministic and non-deterministic 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 first-order predicate
logic, quantifiers and scope, prenex normal form, interpretations of first-order
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 1-6.
-
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 well-ordering,
(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 on-line 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 web-page was adapted from the web-page for an earlier instantiation
of this course, created by Vassos
Hadzilacos.