| Announcements | | Course information | | Assignments and tests | | Lecture notes |
12/4/2012 Here are the solutions to the midterm . Please email me if you have any questions or need the password.
5/4/2012 There will be pre-exam office hours on Friday, April 13th, from 12pm till around 4:30-5pm. Please email me if you are going to be coming in the final hour so I will make sure to be here. And email me if you cannot make this time, and would like an appointment.
4/4/2012 Here are the term marks. The two values correspond to two calculation methods we discussed. If you made any special arrangements with me about missing tests/assignments, please email me! And if your term value is in red, please come talk to me!
4/4/2012 Solutions to assignment 3 are now posted. Please email me if you don't have the password (discussed in Tuesday class).
2/4/2012 A study sheet for the final exam is now posted. Please let me know if you notice any mistakes or omissions.
26/3/2012 Notes for dynamic programming and scheduling case study are now posted.
21/3/2012 Assignment 3 is now posted. Due April 2nd.
19/3/2012 As discussed in class today, there will be no assignment 4. The remaining 10% will be divided between assignments and the final exam; there were two variants of such a division (+2% each assignment and +4% final or +5%last assignment and +5% final); the maximum of the two will be used for each person.
19/3/2012 The notes on Greedy Algorithms are now posted
7/3/2012 There is no class today -- the university is closed till 5pm. Enjoy the snow day! I will be in tomorrow after around 12pm till about 3pm, if you would like to come to ask questions.
5/3/2012 There was a strong movement to move the midterm to Monday; so let's have it on Monday. Thus, Wednesday lecture will be new material, and next Monday, March 12th, is the midterm. I will have office hours on Wednesday 1-2pm, as usual; if you would like to see me at other time please send me an email.
4/3/2012 Solutions to assignment 2 and study guide for the midterm are now posted.
27/02/2012 There are no lectures this week. Next week, on Monday March 5th we will have a review before the midterm; the midterm itself is Wednesday March 7th.
22/02/2012 Extension for assignment 2: If you need extra time, you can submit assignment 2 by 2pm on Monday, at the main office. However, if you submit it on Friday by 2pm you will get extra 10% of your mark.
12/02/2012 Assignment 2 is now posted. Due on Friday, Feb 24 at 2pm in the main office.
1/2/2012 Extension for assignment 1: please bring it to me tomorrow (Thursday) before 3:15. If I am not in the office, then slide it under the door.
1/2/2012 For the next several lectures I will be following a long set of notes on complexity theory, posted below. Please ignore for now all mentionings of regular and context-free languages
30/1/2012 Small correction: in the assignment question 1c, please make a non-deterministic Turing machine which is not a deterministic TM. Otherwise, since deterministic TMs are a special case of non-deterministic, the question becomes meaningless.
18/1/2012 Assignment 1 is now posted.
16/1/2012 I will be away Feb 26th to March 4th. To make up the two lectures, the next 4 lectures (starting this Wednesday, Jan 19th) will run till 5:30pm, with a short break in the middle. Please let me know as soon as possible if you have a time conflict with this!
16/1/2012 The office hours will now be to 5-6pm on Mondays and 1-2pm on Wednesdays.
16/1/2012 Notes for lecture 2 are posted below
11/1/2012 The notes for the first lecture are posted below.
9/1/2012 Our office hours will be 5-6pm (after the class) on Mondays and Wednesdays.
4/1/2012 The first lecture is Monday January 9th, as scheduled. Will see you there!
You are encouraged to use LaTeX for typesetting your assignments. A good introduction to LaTeX is "Essential LaTeX" .
A study guide for the midterm test.
Lectures: 15:30-16:45 on Mondays and Wednesdays in EN-1051
Instructor: Antonina
Kolokolova , email: [Your browser cannot view this email address] , office ER-6033.
Instructor office hours: M/W 17:00-18:00
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.
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.