Computer Science 3719 -- Theory of Computation and Algorithms, Winter 2011

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

Announcements

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 here (in a version of the notes for a similar course).
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.

Old announcements

-----------------------------------------------

Assignments and tests

Assignment 1. Due Jan 28, 2011. Assignment 2. Due Feb 18, 2011.
Assignment 3. Due Mar 21, 2011. Assignment 4. Due Mar 31, 2011.

-----------------------------------------------

Lecture notes

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

-----------------------------------------------

Course information

Course Information Sheet

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.

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.