NEW!! grades are available Here. Disclaimer : all marks are tentative until reviewed and approved by the Department and the Faculty.

A4 and older assignment and tests are with Maeve Doyle at the undergraduate office SB 4004.

Office hour Monday 13/12 2-5pm. In my room SB 4062

Tsuyoshi will have an office hour on Monday 6/12 1400. BUT - if you are planning to use it, you better email him (morioka@cs.utoronto.ca) in advance.

Exam cover page is available here. This should help you plan your time better when solving it. More tips and comments can be found in the "Tests/Exam" page here.

Notice that approximation algorithms are covered (in a somewhat concise manner) in chapter 10.1 of the text.

Due date for A4 is the last day of classes (8/12) at the last lecture.

TEST 2 will include chapter 5 (excluding 5.2) and chapter 7 from the text. It will not contain self-reducibility or co-NP that were only covered last lecture.

Regarding A3 Q1b. Notice that NP-completeness says that (i) a problem is an NP (ii) every problem in NP reduces to it (this property is termed "NP-hardness"). Have these properties in mind when you solving 1b.

There will be a TA office hour, on Monday, 22/11, 2PM. Room SB4007B.

Tutorial exercises are different than the ones at STG. Here they are (to be discussed on tutorial on 19/11)

New dates : test 2 will be on Friday, 26/11 (in the tutorial), and the due date for assignment 3 is Monday, 22/11 3:00PM

Notice that the grades for A2 are out of 75 points.

There will be a TA office hour, on Monday, 15/11, 3PM. Room SB4007B.

Dates related messages. First, notice the due date of A3 is Nov 19th and not Nov18th. Second, I am planning to postpone the second termtest by a week; this will allow students to get A3 solution prior to the test, and also to reduce the stress level (not needing to worry about the assinment and test for the same day). I will, however, need to get your consent. We will make a vote on that issue next class 10/11.

Please bring your T1 for Tutorial tomorrow. We want to reconsider the marking protocol on one of the questions, so we encourage everyone to bring it back for remarking (if there will be a modification it will only be a positive one).

Assignment 3 is available

Final exam tentatively scheduled by Registrar's for Tuesday, 14/12/04, 9:00-12:00, in SE3093.

Remeber, deadline for submitting A2 is Friday, Oct 29, 3PM. The drop boxes are located in SB 2045.

hint to Q3 in A2. Think of a similar situation: if we want to show that a language A is undecidable, technically we are trying to prove that there is no TM that accepts every string in A and rejects every string not in A. It's not obvious how to do that directly. So instead, we do a proof by contradiction: assume A is decidable and show how we can use that information to help us decide some other language that we know is undecidable. You can use a similar idea here. The trick is to think along those lines: IF you knew how to compute T(n), how would that help you decide some language that you know is undecidable. Obviously, part of the problem is finding an appropriate language that we already know is undecidable (or that you can show is undecidable, as part of your answer).

Regarding question 2a in A2. I want to save you a possible confusion. I was asked if the question is about recognizing the input alphabet. So the answer to this and to related questions is "No! The alphabet plays no special role here. In fact, if you like, you can say S={0,1} and ignore all discussion about the input alphabet. In other words F_TM = { < M > | M is a TM that accepts all strings} and the rest of the question is as before".

There will be a TA office hour, given by Tsuyoshi (who is back!!) On Tuesday, 26/10, 3PM. Room SB4007B.

There will be no general extension to Assignment 2. For those who believe they have special circumstances supporting a request for extension, please talk to me.

Here are sample solutions to Assignment 1. Note, it does not contain a formal description in 4(a) (to be added later) and also note that these are not the only correct ways to answer the questions.

Term test 1 will take place during tutorial on Friday 15 October. The test will be on all of the material covered in lectures and tutorials, up to and including the tutorial exercises for week 5, as well as the textbook readings for weeks 1-4 and assignment 1.

The drop boxes are located in SB 2045. When you enter that door, they are to your left against the wall. The boxes are labeled with the course numbers. You should submit it before the tutorial (Friday, Oct 8, 3PM). No late submissions.

Clarification to Q1 in A1. The question ends with "Show that this type of Turing machine recognizes the class of Turing-recognizable languages". To remove doubts, this means that they recognize EXACTLY the Turing recognizable languages, no less and no more.

Change. Travis wil have his office hour at SB4007B and not SB4062 as announced earlier.

There will be an office hour of the TA Travis Gagie on Monday 4/10 15:00-16:00 in SB 4062.

A newsgroup ut.cdf.csc363h for the course was created. It is common to StG and UTM courses, and you are encouraged to ask your questions related to the material there. the nntp server is news.erin.utoronto.ca . Check http://www.utm.utoronto.ca/~w3csc/ for the technical aspects of this.

Office hours are now extended to 14-16 on Wednesdays.
Reminder -- you are welcome to meet me outside of office hour too, as long as you coordinate it first (and it is Mon/Wed).