|
|
| 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 possibly 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.
- Assignments are due at 2pm on their due date, in the CSC 363 drop box.
- Assignments submitted after 2pm on their due date but before
the beginning of the next lecture will incur a penaly of 40%.
- No assignments will be accepted after the beginning of the next lecture.
- For any kind of special arrangements, contact the instructor before the assignment is due.
- January 8th, classes begin.
- January 26th, Assignment 1 due.
- February 16th, Assignment 2 due.
- February 19th - 23rd, Reading Week.
- March 2nd, Midterm.
- March 11th, last day to drop course.
- March 16th, Assignment 3 due.
- April 6th, Holiday.
- April 9th, Assignment 4 due.
- April 13th, classes end.
- Course information sheet: [ ]
- Tutorial exercises:
[ ]
[ ]
[ ]
[ ]
[ ]
[ ]
[ ]
[ ]
- Rough lecture notes:
[ ]
[ ]
[ ]
[ ]
[ ]
[ ]
[ ]
[ ]
[ ]
[ ]
[ ]
[ ]
[ ]
- Assignments:
[ ]
[ ]
[ ]
[ ]
- Solutions:
[ ]
[ ]
[ ]
[ ]
- Exam first page:
[ ]
| After last class |
The exam is marked, and I made it out of 78p instead of 100p.
Here are some numbers that have no meaning unless they are approved
[ ].
I removed the posted solutions. If you really need them, come see me.
A4 is marked. Question 4 was just slightly harder than we intended,
so we made it a bonus altogether. The assignment was thus out of 75p
and question 4 was a maximum of 10p bonus. The assignments are in my office to pick up.
I decided not to post a correct solution for Q4 because the UTM class already had their
exam. I will post a solution after our exam.
You can check the term grades that I have recorded in this file:
[ ].
There are no student names or numbers for fear of privacy concerns,
but each of you should know their own grades.
If no single line reflects your record, let me know.
It turns out, the solution posted for question 4 on A4 is wrong.
I updated the solution handout to reflect that.
Here is the front page of the exam:
[ ].
The heading says that it's for UTM, but the first page for St. George is the same.
Note that you are allowed to have as an examination aid
a single letter-sized page, handwritten on both sides.
No printouts. No photocopies.
Also note the 20% rule.
Rough lecture notes for week 13:
[ ].
We covered material in sections 8.1 and 8.2 in your textbook,
as well as the defintion of PSPACE-completeness that appears in section 8.3.
We didn't study any explicit PSPACE-complete problems though.
Here are solutions to Assignment 4:
[ ]
I will hold office hours before the exam on Monday, May 7th, 3-5pm in SF3207.
|
| Week 13 |
On Tuesday, we introduced space complexity.
We began by defining SPACE(s(n)), NSPACE(s(n)), PSPACE and NPSPACE complexity classes.
We proved that SAT∈PSPACE and that SPACE(s(n))⊆TIME(2s(n)).
We stated Savitch's Theorem and gave the main idea of the proof.
We concluded by stating the known relations between the main complexity classes,
namely that P⊆NP⊆PSPACE⊆EXP.
This material appears in sections 8.1 and 8.2 in the book.
On Thursday we have our last lecture and I plan to give an overview of the entire course.
Costis will hold office hours for remarking A3 on Tuesday, April 10th, 12-1pm, in BA3234.
|
| Week 12 |
Rough lecture notes for this week:
[ ].
Note that we went through the material in a slightly different manner, but it's essentially the same content.
Lecture notes for last week, but missing the reduction VERTEXCOVER to SETCOVER:
[ ].
On Thursday, we saw that HAMPATH and VERTEXCOVER are selfreducible.
For both of these, we gave an algorithm for the search version of the problem based on an algorithm
for the corresponding decision version. We also went through some of the details involved in proving correctness.
There were some typos in the original handout for A4, as explained
[ ].
Even though the handout says otherwise, A4 is due on Monday, April 9th, at 2pm in the usual drop box.
On Tuesday, we talked about decision problems, search problems and self-reducibility.
We went through the details that CLIQUE is self-reducible.
Unfortunately, this material is not in the book.
I'll post some lecture notes about this subject.
|
| Week 11 |
Here is assignment 4:
[ ].
It is due on Monday, April 9th, at 2pm in the CSC 363 drop box
located in BS 2220.
Rough lecture notes for the past weeks:
[ ]
[ ]
[ ]
Check out
this
and
this.
"States are blueberry muffins" - LOL.
The baker's homepage is
here.
Here are solutions to Assignment 3:
[ ]
On Tuesday, we showed that 3SAT is polytime reducible to SUBSETSUM,
establishing that SUBSETSUM is NP-complete. The reduction we did was
slightly different than the one in section 7.5, as ours produced unique numbers in the set S.
On Thursday, we will see several other reductions.
|
| Week 10 |
Check out some hints for A3:
[ ].
On Thursday, we went to the proof that 3SAT is polytime reducible to VERTEX COVER.
This type of a reduction is rather complicated, and you won't be asked to produce something
of this difficulty on assignments or tests.
However, you are responsible for understanding how and why the reduction works.
We finished the class by giving a very high-level overview of the proof of the Cook-Levin Theorem.
All this material can be found in section 7.5 in the textbook.
On Tuesday, we introduced the notions of NP-hard and NP-complete problems.
We talked about the implications of proving that a problem is NP-complete.
We then defined concepts related to propositional logic, and we stated the Cook-Levin Theorem.
Towards the end, we started the proof that 3SAT is polytime reducible to VERTEXCOVER.
|
| Week 9 |
Tutorial exercises for this week:
[ ].
On Thursday, we considered several possible relationships between P, NP and coNP.
We then introduced the notion of polytime reductions, and we showed that
determining the existence of an independent set (formalized as IS)
is polytime reducible to determining the existent of a clique (formalized as CLIQUE).
Towards the end, we argued how A ≤P B and B in P (NP) implies A in P (NP).
This is material from section 7.4. Next week, we will introduce NP-completeness.
Here is assignment 3: [ ].
It is due on Friday, March 23rd, at 2pm in the CSC 363 drop box
located in BS 2220.
On Tuesday, we continued talking about verifiers and we showed HAMPATH, SUBSETSUM are in NP by giving
polytime verifiers for them.
We considered the question of whether the complement of HAMPATH is in NP,
and we argued that we do not know how to prove this.
At the end, we gave the picture of the relatiponships between P, NP and coNP,
and stated several long-standing open problems.
|
| Week 8 |
One of the tutorial sections is cancelled as of today.
The only tutorial section left will be held in SF 1080, and it will be run by either Periklis or Costis.
A nondeterministic Turing Machine will be simulated to decide which TA to be used.
Here are solutions for the midterm:
[ ].
On Thursday, we continued talking about running time as function of input length.
We saw that arithmetic operations run in time polynomial in the length of the numbers involved,
but that the obvious primality testing algorithm is not polynomial.
We also showed that RELPRIME is in P (section 7.2).
Then we introduced the notion of verifiers and defined NP in terms of verifiers.
Read about the connection between verifiers and NTMs in section 7.3, Theorem 7.20.
In the end, we showed that COMPOSITES is in NP by giving a polytime verifier for it.
Read about some important problems involving cliques in this week's tutorial exercises.
Tutorial exercises for this week:
[ ].
On Tuesday, we talked about what it means for a problem to be in P. We discussed reasonable encodings
for integers and for graphs. We then showed that the problem of determining whether there is a path
between two given vertices in a graph is in P. This material is from section 7.2.
On Thursday, we will continue with examples of problems in NP (section 7.3).
|
| Week 7 |
Costis will hold office hours for Assignment 2 remarking on Wednesday, March 7th, 12-1pm, in BA3234.
Rough lecture notes for week 7:
[ ]
On Thursday, we looked at the efficiency of simulating multi-tape TMs and nondeterministic TMs
using regular TMs. We talked about the tractability thesis, and we introduced the classes P and NP.
Next week, we will continue with examples of languages in P and NP.
This material is in sections 7.2 and 7.3 of the book.
The midterm will be held on Friday, in lecture room, not in tutorial rooms.
Due to a great effort by Costis, I will be able to return Assignment 2 in lecture on Thursday.
Here are solutions for Assignment 2:
[ ]
On Tuesday, we started the complexity part of the course.
We defined worst case time and space complexities of TMs
and ran through some examples of assymptotic runtime analysis.
This material is in section 7.1 of the textbook.
|
| Week 6 |
Rough lecture notes for week 6:
[ ]
On Thursday, we slowly went through two more mapping reductions,
showing that neither INFTM nor its complement are recognizable.
We then gave the statement of Rice's Theorem, which appears as (solved) exercise 5.28 on p.213 in your textbook.
This concludes the computability part of the course.
After the break, we will begin the complexity part, with section 7.1 in the book.
Periklis will hold office hours for remarking requests for A1
on Friday, February 16th, 11:20 to 12:20, in BA3234.
If you cannot make it to his office hours, please contact him very soon.
Tutorial exercises for this week:
[ ].
The due date for Assignment 2 has been changed to Wednesday, February 21st.
I also updated the phrasing of some questions on the handout.
I have decided against awarding bonus marks for assignments submitted early.
Rather than going for bonus marks, I think you should concentrate on solving the assignment
and learning concepts in the process.
On Tuesday, we went through a short review of the computability chapter.
We then looked at the difference between general reductions and mapping reductions.
On Thursday, we will present other examples of reductions and wrap up the computability chapter.
|
| Week 5 |
Rough lecture notes for weeks 4 and 5:
[ ]
[ ].
On Thursday, we continued talking about mapping reducibility.
We showed that ATM is mapping reducible to HALTTM
and to ETMc.
Then we showed both ATM and its complement
are mapping reducible to EQTM, thus establishing that
neither EQTM nor its complement are recognizable.
Here is assignment 2: [ ].
It is due on Friday, February 16th, at 2pm in the CSC 363 drop box
located in BS 2220.
Tutorial exercises for this week:
[ ].
On Tuesday, we saw some examples of undecidable languages.
We saw that the questions whether a TM halts on a given input (HALTTM),
whether the language accepted by a TM is empty (ETM) and
whether two TMs accept the same languages (EQTM) are all undecidable.
Read about these in section 5.1.
At the end, we introduced the notion of mapping reducibility between two languages.
This is section 5.3.
On Thursday we will continue talking about mapping reducibility.
|
| Week 4 |
On Thursday, we used diagonalization arguments to show that the set of real numbers,
the set of infinite binary sequences and the set of all languages over a finite alphabet are all uncountable.
We then revisited the proof that ATM is undecidable and saw how it can be viewed
as a diagonalization argument. This concludes section 4.2 in the textbook.
Tutorial exercises for this week:
[ ].
On Tuesday, we gave a simple proof that ATM is undecidable.
In order to understand the underlying proof method, we introduced some mathmatical background.
We defined the notion of a countable set, and we showed that
the set of even natural numbers, the set of integers, the set of strings over the alphabet {0,1}
and the set of rational numbers are all countable.
All this material is in section 4.2 of your textbook.
|
| Week 3 |
Rough lecture notes for weeks 2 and 3:
[ ]
[ ].
On Thursday, we talked about enumerators (Theorem 3.21), about computing functions (question 2, assignment 1).
We then stated the Chruch-Turing Thesis and talked about high-level descriptions of TMs.
We saw how one can encode a TM as a string and we argued that ATM,
the language consisting of encodings ⟨M,w⟩ such that
M is a TM that accepts w, is recognized by a "universal" TM U
(see 4.2, p.174, before "The Diagonalization Method").
The universal TM is ugly to describe, but once you believe the Church-Turing Thesis,
you should be convinced that it can be done.
For a few more details on how it works,
check out this
(note: you are not responsible for material on outside links, they are for reference only;
TM conventions might be slightly different, we will stick to the ones given in class).
On Tuesday, we finished the proof that deterministic TMs can simulate nondeterministic TMs (Theorem 3.16 in book).
We also talked about the Church-Turing thesis (section 3.3).
On Thursday, we will talk about encoding TMs as input strings to other TMs,
see further examples of decidable languages
Tutorial exercises for this week:
[ ].
|
| Week 2 |
Tutorial exercises for this week:
[ ].
On Tuesday, we began with an example of a formal description of a TM.
We then showed the equivalence with 2-way infinite tape TMs and
TMs that are allowed stay-put transitions. In our proofs, we used
some formal-level details about transition functions.
On Thursday, I plan to present implementation-level details
for simulating multiple-tape TMs and nondeterministic TMs
(Theorems 3.13 and 3.16 in textbook).
Here is assignment 1: [ ].
It is due on Friday, January 26th, at 2pm in the CSC 363 drop box
located in BS 2220.
Here are some lecture notes about material presented last week:
[ ].
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.
|
| Week 1 |
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.
On Tuesday we talked about the course material in general.
On Thursday, we gave informal and formal description of Turing Machines.
This is section 3.1 in the book.
Next week, we will start by going through an example of a formal description of a TM,
and move on to equivalence with other models and robustness (3.2, 3.3).
Here are some exercises for this week's tutorial:
[ ].
In general, tutorial exercises will be shared with the
course CSC 363 taught at UTM by prof. Magen.
|
|