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

Announcements | Course information | Assignments and tests | Lecture notes


older announcements...


Course information

Lectures: 15:00-15:50 Monday, Wednesday and Friday in EN-1051
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
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 or in limited time? 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.


Assignments and tests

Assignment 1. ( LaTeX Source). Due Jan 28, 2013 Assignment 2. ( LaTeX Source). Due Feb 15, 2013. (Solutions 2)
Assignment 3. Due Mar 25, 2013 ( LaTeX Source). The image for problem 3. Assignment 4. Due Apr 3, 2013 ( LaTeX Source). The image for problem 2.

You are encouraged to use LaTeX for typesetting your assignments. A good (though a bit outdated) introduction to LaTeX is "Essential LaTeX" .


Lecture notes

I will be posting lecture notes as we go; you are welcome to check the lecture notes from the previous run of this course.

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