Date | Announcement |
| 28/04 | I have been told that the faculty disapproves of instructors posting final marks, so I am not doing this. You may, however, wish to interpret the list of numbers as "final" numbers. | 28/04 | The marks page now includes marks for assignment 5. I am trying to arrange for the assignments to be dropped off at CSSU, but so far they appear to be closed during exams. |
| 25/04 | Here is a list of numbers. |
| 13/04 | Old assignments and tests (except for assignment 5, which is not yet marked) are now in the CSSU office in Bahen. |
| 12/04 | Exam review session:
|
| 12/04 | Ironically, after posting that last announcement I wasn't able to make it to office hours. My apologies to anyone who waited. Let me know if you would like to reschedule. |
| 10/04 | I will be holding office hours as usual leading up to the exam: usual time, usual place. |
| 10/04 | I've made up a list of exam review questions, which you'll find below. Be aware that the list is not intended to be comprehensive,
i.e. not a substitute for studying your notes, but it should be a useful study aid. I'm trying to book a room to hold a review session
where we can discuss the answers to these (and other) questions. The review session will likely be on this Friday, April 15, but
I don't yet know what time or place. More information will follow soon. Below is a link to the review questions.
Exam review questions: [ps] [pdf]
|
| 04/04 | I am canceling question 2b) on assignment 5, as I think that it is too difficult and not especially important for the course. If you already have a solution, you can still hand it in, and if it is correct there will be a small bonus. There will be no part marks for a partially correct solution, so unless you already have an answer it is probably not worth your time to try and find one. |
| 29/03 | As usual, there is a page of clarifications for assignment 5. Please check this page regularly for updates. |
| 29/03 | Please remember that there is a test this Friday, April 1. The material which will be tested consists of the topics covered from the lectures on February 8th (Time Complexity, P and NP) to March 10th (Partition and Hamiltonian Path), the corresponding tutorials, and assignments 3 and 4. You will be given a list of NP-complete problems along with the test. You may only use these problems when proving NP-completeness (the list includes all the problems we have discussed so far). If you want to look at the list, here is a copy: |
| 29/03 | Apparently CDF did not set a print quota for this course (thanks to the student who pointed this out). I apologize to those of you who have had difficulty because of this, as there is a substantial amount of material that needs to be printed out. As of now there is a print quota of 200 pages, which will hopefully suffice to print the lecture and tutorial notes, assignments, and solutions. |
| 23/03 | Assignment 5 is now available online. |
| 15/03 | I think I may have misstated a theorem in class today: if an optimization problem is solvable in polynomial time, then the corresponding decision problem is decidable in polynomial time, but not necessarily vice-versa. Also, I did not define explicitly what an "approximation algorithm" is (although it was probably obvious from context). The online lecture notes are correct. |
| 14/03 | I made a couple of updates to the notes page for assignment 4. Make sure to check this page periodically in case other issues arise. |
| 10/03 | Please read this note about assignment 4, question 4. I neglected to mention something in class that is vital to solving this question correctly, and the above link provides the missing information. Sorry for the confusion, and many thanks to the student who pointed this out! |
| 10/03 | The TAs will be holding an office hours for questions about the marking of A2 and the midterm, on Monday, March 14 from 12:30-1:30 pm in BA3201. |
| 08/03 | Solutions for assignment 3 are now online |
| 02/03 | Marks for the midterm test are now available on the marks page. |
| 02/03 | I posted the fourth assignment on the assignments page. Note that it is due March 22nd. |
| 01/03 | By majority (perhaps even unanimous) vote, we decided today on the following modifications to the schedule:
|
| 27/02 | Sample solutions for the first test are now on the assignments page. |
| 24/02 | Important: I am waiving the late penalty for assignment 3, so you can hand it in until Thursday, March 3 at 6:00 pm (in the drop box). |
| 23/02 | On the format of the test: there will be three parts. The first part has several multiple choice and short answer questions, and the other two parts are problems similar in nature to questions on the assignments. If you have understood the solutions to the assignment questions then you should do well on the test. |
| 21/02 | I've been asked to post the following announcement. I would highly recommend this talk, as it relates to what we are studying in
this course.
Professor Charles Rackoff is giving a research presentation for undergrads this week titled "What We Don't Know About Cryptography". All students are welcome to attend and refreshments will be provided.
|
| 21/02 | Marks for the second assignment are now online |
| 14/02 | Remember that there is a midterm test on Friday, February 25. The test will take place in tutorial, and you must write the test in your own tutorial section. Make sure to bring your student card with you. The test will be on the material we covered up to, and including, lecture 10 (on Post's correspondence problem). No aids are allowed. |
| 14/02 | I've posted the first question for assignment 3, in case you want to get an early start. More questions will follow soon. |
| 11/02 | Sample solutions for the second assignment are available on the assignments page. |
| 09/02 | The tutors will be holding an office hour this friday, 12:30-1:30 in BA3201 to discuss the marking of the first assignment. |
| 08/02 | I will be holding an extra office hour tomorrow (wednesday, february 9) from 3:30 to 4:30 in BA3201. |
| 07/02 | Important: I was quite late for office hours today, and I apologize to anyone who waited in vain. Partly because of this, and also because I think the extra time will be useful for many of you, I will not be applying the late penalty to assignment 2. This means that you can hand it in any time before 6:00 pm on thursday, without penalty (but I still can't accept assignments after that time). |
| 03/02 | Marks for the first assignment are available on the grades page. When you get your assignment back, make sure to check that the mark on the assignment paper matches the online mark. |
| 28/01 | Solutions to the first assignment are available on the assignments page. |
| 24/01 | Assignment 2 is available on the assignments page. |
| 24/01 | Late assignments should be submitted via the drop box in BA2220. Remember that you can hand in some of your solutions on time, and submit the rest late if necessary. |
| 21/01 | Solutions for the second tutorial exercises are available on the tutorials page. |
| 20/01 | I posted some notes and clarifications for assignment #1 |
| 13/01 | Important: It seems that the pdf version of the assignment differed from the ps version. Both versions are now correct (the pdf version was previously incorrect). Please download question #3 again and ignore the previous version. The question should involve proving that a language is recognizable. |
| 10/01 | Starting today, I will be holding office hours every monday from 3:30-4:30 pm in BA 3201. |
| 07/01 | Assignment 1 is now available on the assignments page. |
| 06/01 | I mistakenly scheduled the second test on Good Friday, which is a holiday. It has been rescheduled for the following week, on Friday, April 1. |
| 05/01 | The prerequisite for this course is CSC236/238/240. Additionally, if you are not enrolled in a computer science program then a CGPA of 3.0 is required. If you do not have these prerequisites, you should discuss your situation with me as soon as possible, or you may be removed from the course. |
| 05/01 | Tutorial exercises for this week have been posted. Check the tutorials section. |
| 04/01 | There will be tutorials this Friday, January 7. Check the tutorials section to find out your tutorial room. |