| Date |
Announcement(s) |
15/4
|
Office hour on Wednesday 16/4 11-1. At my office. Also you can collect your A3+E6 there. I will leave the uncollected package at the office with Kathleen
|
15/4
|
Notice that an aid-sheet will be allowed for the exam. Here is a Cover Page of the Exam
|
6/4
|
A hint was added in A3, Q1
|
1/4
|
A3 uploaded, due Friday 11/4.
|
26/3
|
A3 will be different from the STG's one, and will only be posted next week (recall that its due date is at the last day of class 11/4).
|
23/3
|
Remember test 2 is on Fridy 28/4. The test will be on all of the material covered
since Test 1 up until NP completeness:
techniques for recognizability (dovetailing),
undecidability of ATM,
informal reductions (undecidability of HALTTM,
ETM, EQTM),
mapping reductions "≤m" (definition and properties),
unrecognizability of REGULARTM and
REGULARTM,
unrecognizability of EQTM and
EQTM,
unrecognizability of INFTM and
INFTM,
Rice's Theorem,
complexity measures and computational model,
complexity classes TIME(t(n)) and SPACE(s(n)),
the tractability thesis (what can be efficeintly computable is in P).
Complexity classes, P, NP, coNP. Polytime reductions "≤p"
(definition and properties), NP completeness.
|
12/3
|
Ex 5 uploaded, due Monday 17/3.
|
11/3
|
Final exam is on 18/4, at 4PM and not 28/4 as I announced before>
|
28/2
|
E4 is due tomorrow, Friday.
|
18/2
|
A2 was uploaded. Also, returned A1 will be waiting at Kathleen's office, SE 4004. It will probably get there by tomorrow, Wednesday.
|
15/2
|
To remove doubts. Ex 3 is due today. It used to say "Ex 2" is due. This is b/c of incosistency about whether or not we count the second exercise that you didn't have to submit. Anyway, Ex3 today!
|
6/2
|
Material for test: up to countability of sets. Will not contain the discussion about A_TM !
|
1/2
|
Campus is closed today: no tutorial will be held and A1 will be due on Monday at class<
|
30/1
|
Notice -- deadline for A1 is Friday at tutorial.
|
22/1
|
As I've mentioned in class, you are not supposed to submit the second exercise (ex2 of downtown section), but you are required to try and solve it! Here it is. Siavosh will go over it on Friday's tutorial.
|
18/1
|
Recall that Ex1 is due today. You should hand it in at the beginning of tutorial.
|
17/1
|
Assignment 1 is uploaded. Due Friday Feb 1.
|
10/1
|
Ex 1 is uploaded. Due next tutorial, Friday 18/1.
|
8/1
|
Web page is still under construction. please revisit later to check more details.
|