CSC 236  Intro to Theory of Computation
Fall 2006
Index of this document
Contact information
Instructor: 
Vangelis
Markakis 
Lectures: 
Wednesdays, 57, NE 140 
Office: 
SE 2038E 
Telephone: 
9058285417 
Office Hours: 
Wednesdays, 35 or by appointment 
Tutor 
Daniela
Rosu 
Tutorials 
Fridays, 24, 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 divideandconquer 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

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
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 wellordering 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, 24, at CC3124 and not at CC2134.
The next lecture will be on the principle of wellordering and on structural induction.
The relevant material is Chapter 4 and the very beginning of Chapter 1.

September 27: Lecture 3. The Principle of Wellordering. 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 bigOh
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 13 and NOT 35
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.15.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.95.11 and 6.16.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 FirstOrder Logic. Relevant material
is Chapter 6.

November 15: Lecture 10. Chapter 6. Syntax and Semantics of FirstOrder Logic. Logical equivalences in
FirstOrder 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 online 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 courserelated 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)

1121 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 webpage was adapted from the webpage for an earlier
instantiation
of this course, created by Vassos
Hadzilacos.