Announcements | | Course information | | Assignments and tests | | Lecture notes |

17/04/11 A (very preliminary!) marks for the exam are now posted. Contact me no later than 12pm on Monday if there is any problem.

12/04/11 Please check that your marks are recorded correclty. Contact me immediately (before the final exam) if you notice any problem! Highlighted cells are for special arrangements; if you had a special arrangement and it is not indicated, please contact me immediately as well.

06/04/11 A review class on Tuesday, April 12th, 12 to 1pm at EN-1051 (usual time and place for our Tuesday lecture) has been confirmed. Will see you there and then! Of course, you are welcome to email me if you have any questions before or after.

05/04/11 A study guide for the final exam is now posted.

29/03/11 The assignment 4 is now due Monday, April 4th in the general office by 2pm (they have a break from 1pm to 1:30pm, please come either before or after). It is 2pm sharp , the TA will come at 2pm to pick it up and if your assignment is not in, then it's late!

28/03/11 Notes on complexity theory are now posted. Sorry for the delay!

27/03/11 Notes on Complexity Theory will be posted soon; in meanwhile, most of the information can be read

19/03/11 Assignment 4 is now posted. Due March 31st.

17/03/11 The assignment 3 is now due Monday, March 21st. Bring it to the General Office before it closes (say by 3:30pm, they close at 4pm).

12/03/11 Lecture notes 20 (with more examples of reductions) are now posted.

11/03/11 By popular demand assignment 3 is now due Friday, March 18th.

10/3/11 Lecture notes up to 19 are posted.

Assignment 1. Due Jan 28, 2011. | Assignment 2. Due Feb 18, 2011. |

Assignment 3. Due Mar 21, 2011. | Assignment 4. Due Mar 31, 2011. |

A study guide for the midterm test. A study guide for the final exam.

- Lecture 1 (review of algorithm design, Knapsack)
- Lecture 2 (notation and regular expressions)
- Lecture 3 (deterministic finite automata)
- Lecture 4 (non-deterministic finite automata)
- Lecture 5 (closure of regular languages under union)
- Lecture 6 (end of closures, equivalence of NFAs and DFAs)
- Lecture 7 (GNFAs, constructing a regular expression from an automaton)
- Lecture 8 (Nonregular languages, pumping lemma)
- Lecture 9 (Pushdown automata)
- Lecture 10 (More pushdown automata, context-free grammars)
- Lecture 11 (More context-free grammars)
- Lecture 12 (Equivalence: constructing PDAs from GFGs)
- Lecture 13 (Equivalence: constructing CFGs from PDAs)
- Lecture 14 (Pumping lemma for CFLs)
- Lecture 15 (Turing machines)
- Lecture 16 (TMs: adding 1, one-way vs. two-way tape)
- Lecture 17 (Multi-tape and non-deteministic Turing machines)
- Lecture 18 (Undecidability)
- Lecture 19 (Closures and reductions)
- Lecture 20 (Proving undecidability via reductions, examples)
- Lecture 21: proving that regular languages are decidable, and Lecture 22: proving that testing if a grammar generates empty set of strings is decidable. Please see Sipser's book for the proofs.

- Complexity theory notes

** Lectures: ** 12:00-12:50 Tuesday and Thursday, and 13:00-13:50 Friday, all in EN-1051

** Instructor: ** Antonina
Kolokolova , email: [Your browser cannot view this email address] , office ER-6033.

** Instructor office hours: ** TBA

** Textbook: ** There will be no main textbook for this course; some course notes will be posted online.

There will be three reference books. The main reference book will be Sipser: intro to the theory of computation.

- M. Sipser:
*Introduction to the Theory of Computation*(2nd edition). - Cormen, Leiserson, Rivest, and Stein:
*Introduction to Algorithms*(3rd Edition). - Kleinberg and Tardos:
*Algorithm design.*

** Marking scheme ( tentative! ): ** 4 assignments of 10% each, one midterm test 20% and a final exam 40%. Note
that the last assignment may be due during the last week of the semester (to provide an adequate preparation for the final exam).

** CS 3179 Tentative course outline (updated) **

What is an algorithm? What does it mean for a problem to be computationally easy, hard or unsolvable? What can be solved by a computer with only small finite memory? This course is an introduction to the theory of computation, an area which studies these types of questions. We will talk about what is known (and what is open) about the power of computation.

We will start with a simple memoryless model, finite automata, and show that they can compute precisely everything expressible by regular expression. Then we will talk about more powerful kinds of automata; then the Turing machine: it will allow us to say what is an algorithm. We will move on to complexity theory; in particular, we will study problems for which no algorithm better than a brute-force search for a solution is known (or believed) to exist (the famous million-dollar P vs. NP problem ). We will then show that for some problems no algorithm exists at all, no matter how inefficient.