CSC 236 -- Intro to Theory of Computation
Section L5101
Fall 2005
Index of this document
Contact information
|
L5101 |
| Instructor: |
Gerald Penn |
| Lectures: |
R 7-9, BA 1200 |
| Office: |
PT 396B |
| Telephone: |
(416)978-7390 |
| Office Hours: |
T 6-7, R 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 1200.
A newsgroup, ut.cdf.csc236h,
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
Back to the index
Calendar of important course-related events
| Date |
Event |
| Thu, 15 September |
First lecture |
| Thu, 15 September! |
First tutorial |
| Thu, 22 September |
Assignment 1 distributed,
Quiz 1 (in tutorial) |
| Sun, 25 September |
Last day to add course |
| Thu, 29 September |
Quiz 2 (in
tutorial) |
| Thu, 6 October |
Assignment 1 due (in tutorial),
Assignment 2 distributed |
| Thu, 13 October |
Midterm 1 (in tutorial) |
| Thu, 27 October |
Assignment 2 due (in tutorial),
Assignment 3 distributed |
| Sun, 6 November |
Last day to drop course |
| Thu, 10 November |
Midterm 2 (in tutorial) |
| Thu, 17 November |
Assignment 3 due (in tutorial),
Assignment 4 distributed |
| Thu, 8 December |
Last lecture,
Assignment 4 due (in tutorial) |
| 12-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 |
24% (4 at 6% each) |
| Quizzes |
6% (2 at 3% each) |
| Midterms |
30% (2 at 15% each) |
| Final |
40% |
Important note on midterms: Midterms will be conducted
in tutorial, by your tutors.
Important note on homeworks: Homeworks will be distributed
electronically,
collected in tutorial only, and returned in tutorial only. No
late
homeworks will be accepted, except in case of documented medical or
similar
emergencies.
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.
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.
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.
- 13 December: A4 can be collected from the AI secretary in PT 283.
- 1 December: OFFICE HOURS DURING WEEK 13: will be
held in
PT 276 (Tuesday) and BA 3234 (Thursday) instead of PT 396B.
- 1 December: MATERIAL COVERED DURING WEEK 12: state
invariants,
non-deterministic finite state automata, closure properties of regular
language, the pumping lemma. You should read Chapter 8 of the
notes.
- 29 November: EXTRA OFFICE HOURS THIS WEEK: Wed, 30 November, 5-6;
Thursday,
1 December 4-5 (and also 5-6 as usual); Friday, 2 December 5-6.
- 29 November: MATERIAL COVERED DURING WEEK 11: regular
expressions,
deterministic
finite state automata.
- 17 November: MATERIAL COVERED DURING WEEK 10: integrity
constraints,
formal
languages, regular languages. You should read Chapter 7 of the
notes.
- 17 November: ASSIGNMENT 3 may be handed in on 22 November in PT
283
before
4pm, and in PT 276 from 4pm to 6pm.
- 10 November: MATERIAL COVERED DURING WEEK 9: prenex normal form,
rules
of logical equivalence for predicate logic, relational databases, and
how
to start trash fires in the Bahen Centre.
- 9 November: MIDTERM 2 will take place on 10 November. You
are
responsible
for everything we have covered from recursive program correctness up to
but not including first-order predicate logic. Rmember that the
exam
takes place during tutorial. Exams written in pencil will not be
remarked.
- 8 November: CORRECTION ON A3: in question 1, there should be an
extra
precondition
on m that it is less than or equal to the length of the array A.
- 3 November: MATERIAL COVERED DURING WEEK 8: first-order predicate
logic.
You should read Chapter 6 of the notes.
- 1 November: EXTENSION FOR ASSIGNMENT 3: the new due date is now
Tuesday,
22 November at 6pm. Further details on where to submit will be
made
available closer to this deadline.
- 27 October: MATERIAL COVERED DURING WEEK 7: laws of logical
equivalence
and logical equivalence proofs, proofs by contraposition, case and
contradiction,
Boolean functions, disjunctive normal form, conjunctive normal form,
complete
sets of connectives.
- 20 October: MATERIAL COVERED DURING WEEK 6: propositional
logic.
You should read Chapter 5 of the notes.
- 13 October: MATERIAL COVERED DURING WEEK 5: the
divide-and-conquer
recurrence
theorem, proof of asymptotic run-time bounds continued. You
should
read Chapter 3 of the notes.
- 6 October: MIDTERM 1 will take place on 13 October. You
will be
responsible
for the material covered in lecture up through iterative program
correctness.
This corresponds to Chapters 0, 1, 4, and sections 1-6 of Chapter 2 in
the lecture notes. The exam takes place during tutorial and
will last the entire 50 minutes. Exams written in pencil will not
be remarked (so bring pens).
- 6 October: MATERIAL COVERED DURING WEEK 4: termination proofs,
recursive
program correctness, inductive proof of asymptotic run-time bounds.
- 5 October: EXTENSION FOR ASSIGNMENT 1: the new due date is
now
Friday,
7 October at 6pm. You may submit your homework in PT 283 until
4pm,
after which you may submit in PT 396B. Homeworks will also be
accepted
in lecture and tutorial on Thursday, 6 October.
- 29 September: CHANGE IN LECTURE TIME FOR 6 OCTOBER: On 6
October,
lecture will take place from 6 to 8, and tutorial will take place from
8 to 9. This change only affects 6 October.
- 29 September: MATERIAL COVERED DURING WEEK 3: structural
induction,
partial
program correctness, termination sequences. You should read
Chapters
2 and 4.
- 22 September: MATERIAL COVERED DURING WEEK 2: complete induction,
recursively
defined sets. You should finish Chapter 1.
- 17 September: MATERIAL COVERED DURING WEEK 1: proof by
enumeration of
cases,
the principle of well-ordering, simple induction. You should
read Chapter 0, and Sections 1.1-1.2.
- 17 September: On-line versions of Chapters
0 and 1 of your notes will be available until the printer provides
our hard copy.
- 25 August: PREREQUISITES. To take this course you must (1)
have
passed CSC 148 or CSC 150 and (2) have passed CSC 148
in
a term before Fall, 2003 or have passed CSC 165 (in any term) and
(3) either
have a CGPA of at least 2.5 or be enroled 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, 17
December,
2005
This web-page was adapted from the web-page for an earlier
instantiation
of this course, created by Vassos
Hadzilacos.