CSC 363 — Computability and Complexity, StG, Summer 2007
Announcements
Handouts
Contact
Timetable
Books
Grading
Lateness Policy
Important Dates
Links
Instructor Matei David
email: matei at cs
office: SF 4302-F
phone: 416-946-3924
Teaching Assistants Costis Georgiou
email: cgeorg at cs
Eric Hsu
email: eihsu at cs
Mohammad Moharrami
email: mmoharrami at gmail com
Lecture Tuesday6 - 8pmGB 119
Tutorial Tuesday 8 - 9pm GB 119
Office Hours Thursday5 - 6pmSF 4302-F
Textbook M. Sipser. Introduction to the Theory of Computation. Thomson Course Technology, 2005. This is the main book I will be following. We will be interested in chapters 3, 4, 5, 7 and 8.
Reference Books M. Garey and D. Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness, 1979. This book is an excellent reference, and contains a large compendium of NP-complete problems in the back.
Cormen, Leiserson, Rivest and Stein. Introduction to algorithms (second edition). McGraw-Hill, 2001. This book is mainly concerned with algorithms, and some other courses may be based on it. For our purposes, chapters 34 and 35 are relevant.
  • 4 Assignments worth 10% each = 40%. Assignments are to be done individually.
  • 1 Midterm exam worth 15%.
  • Final exam worth 45%. In order to pass this course, you must achieve a grade of at least 40% on the final exam.
  • On the midterm exam and the final exam, you will receive 20% of the marks on each question where you answer "I don't know" and nothing else. This does not apply to homework assignments.
  • In addition to assignments, midterm and the final, which already sum up to 100%, there will be several quizzes given during tutorials. They will be 10 minutes long and cover material presented on that day or on the previous week. I expect to have 5-6 such quizzes. They will be marked quite harshly with no part marks as the assignments or the tests. I will take the 3 best quizzes from each student, weight them with 2% each, and add a maximum of 6% to the final grade.
  • Assignments are due at 6pm sharp on Tuesdays, in the CSC 363 drop box in BA 2220. I will pick them up minutes before lecture and I won't have time wait for late assignments.
  • I will not accept assignments during lecture or during tutorials.
  • I will allow each student 3 grace days, to be used as you see fit. These days end at 6pm. So, following a Tuesday due date, I will collect whatever is left in the dropbox at 6pm on Wednesday, Thursday and Friday. These will be marked as having used 1, 2 and 3 grace days, respectively.
  • If you have no grace days left and your assignment is late, it will not count.
  • For any kind of special arrangements, contact the instructor before the assignment is due.
  • May 14th, classes begin.
  • June 5th, Assignment 1 due.
  • June 19th, Assignment 2 due.
  • June 26th, Midterm.
  • July 17th, Assignment 3 due.
  • July 22nd, last day to drop course.
  • August 7th, Assignment 4 due.
  • August 10th, classes end.
Week 13 Solutions for A4: [ solutions A4 ].

Lecture notes: [ week 13 ].

In the last class, we talked about space complexity. We saw how a space bounded TM can be simulated by a time bounded TM, we gave a linear-space algorithm for SAT, and we gave details about Savitch's Theorem. This material is in the book, in sections 8.1 and 8.2.

There will be office hours for remarking A3 on Thursday, August 9th, 5-6pm in SF4302.

I will also hold office hours for general questions before the exam on both Thursday and Friday, 5-6pm, in SF4302. If you want to meet at some other time, email me to make sure I'm in my office.
Week 12 Lecture notes: [ week 12 ].

In class, we talked about self-reducibility. We saw a number of examples including SAT, 3-SAT, 3-SYMM-SAT and VERTEX-COVER. We didn't finish the proof of correctness for the last one, but a complete proof is in the lecture notes.

Tutorial notes: [ week 12 ].
Week 11 Here is Assignment 4: [ assignment 4 ]. It is due on August 7th, or whenever you run out of grace days. Check lateness policy for details. You should be able to do all but the last question using the material up to and including week 11.

Lecture notes: [ week 11 ].

This week, we saw more examples of NP-complete problems: INDPENDENT-SET, SET-COVER and finally 3SYMM-SAT. The reduction from 3SAT to 3SYMM-SAT can be found on pp14-15 in professor Steve Cook's notes available [ here ].

Tutorial notes: [ week 11 ].
Week 10 Lecture notes: [ week 9 ] [ CNFSAT to 3SAT ] [ week 10 ].

In week 9, we defined polynomial-time reductions and we saw an example of a reduction from CNF-SAT to 3SAT. In week 10, we introduced the notions of NP-hard and NP-complete. We talked briefly about Cook's Theorem that SAT is NP-complete. We then went through the main ideas for the reductions from 3SAT to VERTEX-COVER and to SUBSET-SUM. These reductions are the most difficult we will see in this course. You will not be ased to reproduce anything of this complexity in an assignment or test, but you should however understand how and why these reductions work.

Tutorial notes: [ week 10 ].
Week 8 Here is Assignment 3: [ assignment 3 ]. It is due on July 17th. Check lateness policy for details. You should be able to do questions 1-3 using the material up to and including week 8.

There will be office hours for remarking A2 and the midterm this Thursday, July 5th, 5-6pm, in SF4302, held by Costis.

There will be office hours before A3 is due on Monday, July 16th, 5-6pm, in SF4302, held by Eric.

Lecture notes: [ week 8 ].

In class, we introduced the classes P and NP. We saw two examples of languages in P: RELPRIME and PATH. We also introduced the concept of verifiers and saw an example of a language in NP: HAMPATH.
Week 7 Next week, July 3rd, we will use the room BAB025 for lecture. This one is supposed to have A/C. We'll see how that goes.

Lecture notes: [ week 7 ].

This week, we started the complexity chapter. In class, we talked about the motivation for studying complexity. We then defined worst-case running time for a TM with some examples. We argued that simple TMs can simultate multi-tape TMs in square the time, and that simple TMs can simultate NTM but the time increase is exponential. If you missed this lecture because of the midterm, read section 7.1 to get up to speed. We will continue with sections 7.2 and 7.3 next week.

Solutions for the midterm: [ solutions midterm ].
Week 6 Solutions for A2: [ solutions A2 ].

Office hours for remarking A1 have been moved to Monday 25th, 5-6pm in SF4302, due to airline traffic congestion.

Lecture notes: [ week 6 ].

In class, we saw more examples of mapping reducibilities. At the end, we stated Rice's Theorem. This concludes the computability chapter.

There will be office hours for A1 remarking requests on Thursday 21st, 5-6pm, in my office, SF4302. Both the TA who marked A1 and I will attend, so you can come for either remarking or for general questions. In addition to that, I will hold office hours on the day before the midterm, Monday 25th, in my office, 5-6pm.

For those of you who did not catch this in class, the midterm will go from 6:30 to 7:30 in order to give people time to get there. We will then take a break, and I will lecture 7:45-9. The midterm covers everything that we have seen in weeks 1-6, that is, the entire computability chapter.
Week 5 Solutions for A1: [ solutions A1 ].

A few notes on A2: [ notes A2 ].

Here are solutions for quiz 2: [ quiz 2 ]. They contain more details than you need to put in a quiz.

Lecture notes: [ week 5 ].

In class, we talked about reducibility in general and mapping reducibility. We saw several examples of reductions and mapping reductions. This material is in chapter 5, sections 5.1 and 5.3 (we're skipping 5.2). Next week, we will continue talking about mapping reductions and we will wrap up the computability chapter.
Week 4 There was a typo in Q2. It's fixed now.

Here is Assignment 2: [ assignment 2 ]. It is due on June 19th. Check lateness policy for details. You should be able to do questions 1-3 using the material up to and including week 4.

Lecture notes: [ week 4 ].

This week, we studied diagonalization arguments. We defined the notion of countable set and we saw some examples of countable sets. We used a diagonalization argument to show that the set of real numbers is not countable. Returning to computability, we argued that the number of all languages is uncountable, while the number of computational devices (TMs) is countable, so there is a language not recognized by any TM. Afterwards, we proved that ATM is undecidable also using a diagonalization argument. This material is in section 4.2. Next week, we will start chapter 5, reducibility.
Week 3 Lecture notes: [ week 3 ].

In lecture, we talked about nondeterministic TMs and we saw that they recognize the same class of languages as deterministic TMs. We then talked informally about how a TM could simulate a C program, and we introduced the Church-Turing thesis. We argued that the language ADFA, consisting of strings which encode a DFA B and a string w such that B accepts w, is decidable. The same argument can be adapted to show that ATM is recognizable.
Week 2 Here is Assignment 1: [ assignment 1 ]. It is due on June 5th. Check lateness policy for details.

Lecture notes: [ week 2 ].

In lecture, we defined what a configuration of a TM is, how configurations yield other configurations, what the computation of M on an input w means. Then we introduced the notions of recognizable and decidable languages and we saw a diagram of what we currently know about theses classes of languages. In order to give evidence that Turing Machines are the right model of computations, we started investigating several variants: TMs that are allowed stay-put transitions, TMs with tape infinite in both directions and finally, multiple-tape TMs. We saw that regular TMs can simulate all these augmented TMs. This material is in 3.2. Next week, will talk about nondeterministic TMs and section 3.3.
Week 1 Lecture notes: [ week 1 ]. Disclaimer: lecture notes are only meant to give an idea of what we did in lecture. In no way are lecture notes to be taken as a substitute for lectures.

In lecture, we saw the motivation for this course and a high-level overview of the course contents. We then started talking about Turing Machines. This is section 3.1 in the book. Next week, we will go through sections 3.2 and 3.3.

If you do not meet the prerequisites for this course, you will be automatically removed. To avoid this, talk to the instructor about getting a waiver.