Computer Science 3719 -- Theory of Computation and Algorithms, Winter 2015
- 13/4/2015 Reminder: final exam is April 16th, 9-11am in EN-1052. Please email me if you would like to meet with me and/or have questions. And if you are happy with your practice exam result, you do not need to come to the final.
- 28/3/2015 Reminder: practice exam is this Monday, March 30th, from 2pm to 4pm in EN-1003.
- 27/3/2015 A study guide for the final exam is now posted.
- 18/3/2015 Assignment 4 is now posted. Due March 27th. No extensions.
- 17/3/2015 My office hour tomorrow will be 11am-12pm (I will not be able to make it at the usual time). If this time does not work for you and would you would like to see me, please email and we will arrange some other time.
- 4/3/2015 I am checking on the date and room of our final exam. Will let you know as soon as I hear from them.
- 4/3/2015 Our practice exam will be on Monday, March 30th. We will start an hour earlier, at 2pm, and go till 4pm. As our usual classroom is in use at 2pm, we will be in room EN-1003. The review for the exam will then be on Friday, March 27th.
- 27/2/2015 Assignment 3 is now posted. Due March 9th.
- 10/2/2015 A nice Youtube video explaining complexity theory and P vs. NP problem.
- 9/2/2015 The study guide for the midterm is now posted.
- 5/2/2015 The schedule for the next three weeks will be as follows.
- Monday, Feb 9th: review for the midterm.
- Wednesday, Feb 11th: midterm.
- Friday, Feb 13th: class as normal.
- Monday Feb 16- Wednesday Feb 25th: no classes (first the break, then I am away).
- Friday Feb 27th: back to normal schedule.
- 27/1/2015 Assignment 2 is now posted. Due Feb 6th.
- 19/1/2015 The office hour on Wednesday Jan 21st will be an hour earlier, 11:30-12:30pm. Please email me if this time does not work for you, and we'll arrange something else.
- 15/1/2015 Notes on Turing machines are now posted.
- 15/1/2015 Assignment 1 is now posted. Due Jan 23rd.
- 6/1/2015 The make-up classes next week (Tuesday and Thursday at 3:30-5pm) will be in our usual classroom, EN-1051.
- 5/1/2015 As I will be away Feb 20th to 26th, there will be make-up classes next week, Jan 13th and Jan 15th, at 3:30-5pm (room TBA).
- 5/1/2015 Office hours have been set for Wednesday, 12:30-1:30pm. Let me know if this time slot does not work for you!
Lectures: 15:00-15:50 Monday, Wednesday and Friday in EN-1051
Instructor: Antonina
Kolokolova , email: [Your browser cannot view this email address] , office ER-6033.
Instructor office hours: Wednesdays at 12:30-1:30pm, or by appointment.
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
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.
Policy on collaboration: The work you submit must
be your own. You may discuss problems from assignments with each
other; however, you should prepare written solutions alone.
Plagiarism is a serious academic offense and will be dealt with
accordingly.
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 final exam.