CSC 236 -- Intro to Theory of Computation
Fall 2006
Index of this document
Contact information
| Instructor: |
Vangelis
Markakis |
| Lectures: |
Wednesdays, 5-7, NE 140 |
| Office: |
SE 2038E |
| Telephone: |
905-828-5417 |
| Office Hours: |
Wednesdays, 3-5 or by appointment |
| Tutor |
Daniela
Rosu |
| Tutorials |
Fridays, 2-4, CC 3124 |
Back to the index
Course outline
-
Induction
- The principle of mathematical induction and its variants
-
Recurrences
- Solution of recurrence equations
-
Application to the time complexity of divide-and-conquer algorithms
-
Program correctness
- Preconditions and postconditions
-
Correctness proofs of iterative programs
-
Correctness proofs of recursive programs
-
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
Announcements
In this space, you will find announcements related to the course.
Please
check this space at least weekly.
-
September 9: PREREQUISITES. To take this course you must have
passed CSC 148 and MAT 102.
-
September 10: The first lecture will be on the principle of well-ordering and induction. Relevant
material from the book are Sections 1.1 and 1.2.
-
September 13: Lecture 1. Principle of
induction, examples.
-
September 18: The next lecture will be on complete induction and
the principle of well ordering. We will essentially finish Chapter 1.
-
September 19: Assignment 1 is out. Check the Handouts Section. It
is due in tutorial on October 6, no later than 3:15PM.
-
September 20: Lecture 2. More examples using induction. The
principle of complete induction. Examples using complete induction.
-
September 24: Please note that from now on the office hour of your tutor and the tutorial
session will be on Fridays, 2-4, at CC3124 and not at CC2134.
The next lecture will be on the principle of well-ordering and on structural induction.
The relevant material is Chapter 4 and the very beginning of Chapter 1.
-
September 27: Lecture 3. The Principle of Well-ordering. Recursively defined sets. Structural
induction.
-
October 2: The next lecture will be on recursively defined functions and divide and conquer
algorithms. The relevant material from the textbook is Section 3.1 and Section 3.2.
-
October 4: Lecture 4. Recursively defined functions. Solving
recurrence equations. Divide and conquer algorithms.
-
October 6: Assignment 2 is out. Due date is October 27. Next
lecture will cover more examples on recurrence relations and big-Oh
notation. Relevant
material is the remaining of Chapter 3.
-
October 11: Lecture 5. Recurrence equations arising from divide and
conquer algorithms. Mergesort. Intro to program correctness for recursive
algorithms.
-
October 15: I posted
the solutions to the quizzes and to A1. This week my office hours will be on WED 1-3 and NOT 3-5
as I have to attend some other event. Next lecture will be on program correctness of recursive algorithms.
Relevant material from the textbook is Section 2.7 and 2.8.
-
October 18: Lecture 6. Program correctness for recursive programs.
Quicksort and binary multiplication.
-
October 25: Lecture 7. Program correctness
for iterative programs.
-
November 1: Assignment 3 is out. It is due on November 17. The lecture today will be on Propositional
Logic. Relevant material is Chapter 5.
-
November 1: Lecture 8. Propositional Logic, truth tables, logical
equivalences (Sections 5.1-5.6).
-
November 6: In the next
lecture we will continue and finish propositional logic and we will start first order logic. Relevant
material is Sections 5.9-5.11 and 6.1-6.3.
-
November 7: Solutions to midterm are now posted.
-
November 8: Lecture 9. CNF/DNF forms, Complete sets of connectives.
Introduction to Predicate logic.
-
November 13: Next lecture will be on First-Order Logic. Relevant material
is Chapter 6.
-
November 15: Lecture 10. Chapter 6. Syntax and Semantics of First-Order Logic. Logical equivalences in
First-Order logic, prenex normal form.
-
November 22: Assignment 4 is out. Due date is December 15.
Today we will move to Chapter 7 and talk about regular expressions and finite state machines.
-
November 22: Lecture 11. Languages and regular expressions. Finite State Automata.
-
November 29: Lecture 12. More on regular expressions and DFA's. Brief
intro to NFA's and examples.
-
December 1: Lecture 13. Equivalence between DFA's and NFA's. Closure
properties. The Pumping Lemma.
-
December 4: Solutions to Assignment 2 are now posted.
-
December 5: Solutions to Assignment 3 are now posted. Also a reminder that A4 is due during Daniela's
office hours on Dec 15, no later than 4pm at my office SE 2038E.
-
December 15: A solution to Quiz 3 is now posted.
-
December 16: The drawings of the DFA's and NFA's for A4 are now posted. The rest of the answers for A4
will be posted no later than Monday.
-
December 16: Complete solutions to Assignment 4 are now posted.
Back to the index
Handouts
In this space you will find on-line pdf versions of course
handouts,
including homeworks and solutions.
Back to the index
Evaluation and related policies
There will be four homeworks, three quizzes, one midterm exam, and a final exam. The
relative weights of these components towards the final mark are as follows:
| Homeworks |
32% (4 at 8% each) |
Quizzes
|
8% (3 at 2%, 3% and 3%)
|
| Midterm |
20% |
| Final |
40% |
The quizzes and the midterm will be conducted
in tutorial.
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. The same applies for a missed quiz or midterm.
Grading of assignments: Homeworks, quizzes and midterms will be graded by
the tutor. If you believe your solution deserved a better grade, you should contact
your tutor either in the tutorial hours or by emailing her and arranging a
meeting. In case that you still cannot resolve your question, you should contact
me.
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
Tentative Calendar of course-related events
| Date |
Event |
| Wed, 13 September |
First lecture |
| Fri, 15 September |
First tutorial |
| Wed, 20 September |
Assignment 1 distributed |
| Fri, 22 September |
Quiz 1 (in tutorial) |
| Sun, 24 September |
Last day to add a course |
| Fri, 6 October |
Assignment 1 due (in tutorial),
Assignment 2 distributed
|
Fri, 13 October
|
Quiz 2 (in tutorial)
|
| Fri, 20 October |
Midterm (in tutorial) |
| Fri, 27 October |
Assignment 2 due (in tutorial),
Assignment 3 distributed |
| Sun, 5 November |
Last day to drop a course |
| Fri, 10 November |
Quiz 3 (in tutorial) |
| Fri, 17 November |
Assignment 3 due (in tutorial),
Assignment 4 distributed |
| Wed, 6 December |
Last lecture,
Assignment 4 due (in tutorial)
|
| 11-21 December |
Final Exam period |
Back to the index
Old exams
Some midterm and final exams for earlier incarnations of this course
are available here
(with no solutions).
Back to the index
This web-page was adapted from the web-page for an earlier
instantiation
of this course, created by Vassos
Hadzilacos.