Computer Science 3719 -- Theory of Computation and Algorithms, Winter 2013
- 10/4/2013 The last assignment is now graded. The guys from our class at the senior lab have the assignments, so you can pick yours up from them.
- 10/4/2013 The last assignment is not graded yet -- so sorry for that! I wil
l post something on the webpage as soon as I hear from him. . If you have any questions, please come to my office, and I go over your solutions with you.
- 5/4/2013 There will be a pre-exam office hour next week on Wednesday from 12pm to 5pm. Please email me if you'd like to see me, and this time does not work for you.
- 5/4/2013 Please double-check that your grades are entered correctly on D2L! If there is any problem, please email me as soon as possible -- it will be much easier to take care of corrections before the final exam. And while you are there, the CEQ (course evaluations) are online this year, and open until April 9th.
- 5/4/2013 A study guide for the final exam is now posted.
- 2/3/2013 Source for assignment 4 posted.
- 27/3/2013 Assignment 4 is now posted. Due April 3rd.
- 23/3/2013 A few typos corrected in Assignment 3 problem 2: the condition should read "$G_{i-1} +{e_i}$ has fewer connected components than $G_{i-1}", there should be $S_{opt} \subseteq S_i \cup \{i+1, ..." and $S'_{opt} \subseteq S_{i+1} \cup \{i+2, ... " in the conditions, and $S_n$ in the last part should be $S_m$. Sorry for that! The new a3.pdf and a3-source.tex (also, the figure for problem 3) are now posted.
- 15/3/2013 Assignment 3 is now posted. Due Monday, March 25.
- 23/2/2013 Grades for the Assignment 2 are now posted on D2L. Most of you did very well!
- 20/2/2013 Solutions for assignment 2 are now posted below. Please check on D2L for the password to view the file.
- 12/2/2013 In 3b, QuadPartition, the input is a multiset of numbers (or drop the set notation and treat the input as a list).
- 12/2/2013 My office hours on Thursday will be from 1pm to 2pm. Please send me an email if you have any questions or if you can't make that time and would like to come and see me.
- 11/2/2013 Typo in assignment 2: in question 4b (small number partition), there should be a part of the problem description stating that there is a partition of the numbers into two groups with equal sums (just like in the regular definition of partition.) That is, the problem is the same as the Partition problem, except all numbers in the input are 1s and 2s.
- 6/2/2013 Lectures on February 25th and 27th are rescheduled to February 13th (next Wednesday) and March 6th, at 5pm to 6pm in EN-1054 (that is, an hour after the end of our Wednesday class in a different room).
- 6/2/2013 The midterm test will be on Friday, February 22nd.
- 6/2/2013 The assignment 2 due date is postponed till Friday February 15th, 3pm (sharp!). Since I am going to go over the solutions in class, I will not be able to accept any assignments submitted after the start of the lecture.
- 4/2/2013 Here is a nice set of lectures by Shai Simonson for a course similar to ours. Thanks a lot to Chris for pointing it out! Note, though, that this course starts with finite state machines, and does not have any algorithms in it.
- 4/2/2013 Assignment 2 is now posted.
- 21/1/2013 The lecture notes for lectures 4 and 5 are now posted below
- 18/1/2013 The assignment due date is now postponed till Monday, January 28th
- Here is a Turing machine simulator . Note that the way it is implemented it does not have accept/reject states; instead, it writes an answer on the tape and halts (and does not even go to the start of the output on halt). If you find a better one, let me know!
- 16/1/2013 Office hours this semester will be Mon 4pm, Tue 2pm and Thur 12pm.
- 16/1/2013 The lecture notes for lecture 3 are now posted below
- 14/1/2013 The lecture notes for lecture 2 are now posted below
- 8/1/2013 The lecture notes for the first lecture are now posted below
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: 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
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.
You are encouraged to use LaTeX for typesetting your assignments. A good (though a bit outdated) introduction to LaTeX is
"Essential LaTeX" .
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.
- Lecture 1 (Introduction, 4 problems)
- Lecture 2 (Turing machines, examples)
A Turing machine simulator . Note that the way it is implemented it does not have accept/reject states; instead, it writes an answer on the tape and halts (and does not even go to the start of the output on halt). If you find a better one, let me know!
- Lecture 3 (More examples, finite automata)
- Lecture 4 (Variants of Turing machines)
- Lecture 5 (Undecidability, Church-Turing thesis, Universal Turing Machine)
Here is Alan Turing's original paper from 1936, in which he
introduced Turing machines, universal Turing machine, and showed that
it is impossible to make an algorithm that checks formulas of first-order logic for validity (and always gives an answer).
- Complexity theory notes (next several lectures)
- Lecture on March 4th: algorithm design paradigm for languages in P; divide-and-conquer and solving recurrence relations using Master theorem.
- Greedy Algorithms
- Dynamic programming
- Scheduling case study
- Please see previous run of the course notes for regular and context-free languages.