Old Announcements

• Aug 15: PS3 and Test3 have been graded (very promptly!) by the TA, and they are going to be available for pick up during my office hours today (see below). Since all the marks are in, I have calculated the term marks, and you can see them by clicking here . Check your grades; make sure that they have been recorded correctly! After I have graded the final I will take into account the fact that people have given me doctor's notes for missed work. The scheme for missed (but justified) work is the following: for example, if you missed test 2 (worth 15), your final exam will be worth 40+15=55 of the final grade, and your term mark will be 60-15=45 of the final grade. In short, you will make up for the missed grade in the final exam.
• I will have extra office hours on Monday, 1:10--2:00 (UC45), and on Tuesday, 2:10--4:00 (UC45).
• As soon as your term marks are available I will post them here (by student number ONLY, so your name will NOT appear on the list). Make sure that you check your grades.
• I will let you know as soon as PS3 and Test3 are ready for pick up.
• Final Exam:
  • Click here for the final exam information.
  • The final exam has 6 questions. The first question, worth about 1/3 of the exam, is in the style of question 1 on PS3; you have to decide if a problem is in P or it is NP-complete.
  • There will also be a more difficult question where you have to prove that a problem is NP-complete.
  • There is one question on Greedy algorithms, and one question on Dynamic Programming.
  • The last question is on Computability.
  • There is a list of NP-complete problems at the end of the exam, so you don't have to memorize the definitions of NP-complete problems.
  • The exam is very problem oriented (just as Test 3), but you need to know the definitions and the proofs done in class.
  • There are NO questions on Network Flows.
• Aug 8: Solutions to PS3 have been posted below (and they have been handed out during the last tutorial). Today, at 4:10, in ES149, the TA will have extra office hours before Test 3.
• Guidelines for Test 3:
  • The test has 3 questions: the emphasis of the the first two is on NP-completeness and P, and the emphasis on the last question is on computability.
  • The test is problem oriented, and it does not have questions on definitions (like Test 2), but you still need to know all the definitions to answer the questions.
  • You are responsible for all the material from weeks 9, 10, 11 and 12. Make sure that you know how to answer the exercises from the notes, and that you are familiar with the solutions to the problems on PS3. It is especially important that you understand polytime-many-one reducibility (in the context of NP-completeness) and many-one reducibility (in the context of Computability). Do you know how to show that a problem is in P? How to show that a problem is NP-complete? How to show that it is not (semi-)decidable?
• July 29: I have posted below the notes "Computability III", which will be covered in class this week. On Thursday, Aug 3rd, Valentine Kabanets (the evening section instructor) is going to deliver my lecture. The last week of classes will consist of a review (and Test 3).
• July 28: Computability II notes have been posted below.
• July 28: The TA will have extra office hours on the following dates: August 1, at 4pm in ES149 (for questions regarding PS3), and August 8, at 4pm in ES149 (before Test 3).
• July 25: I just noticed a mistake in the latest lecture notes: in the proof of theorem 5, we just proved the right direction, so the <==> arrows should be replaced by ==>. I'll make the appropriate changes in the hard copies.
• July 21: The latest lecture notes have been posted below.
• July 20: Small errors have been corrected in the solutions to Test 2 (in the last question, in the specification of the TM, the middle answer of part (b) should be q5, print 1, left), and in PS3, in the title it said Problem Set 2, and in question 4, the last part should be (c) not (d) -- note that semi-decidable languages are not closed under complementation.
• July 19: Problem Set 3 has been posted below; I'll bring hard copies (of PS3 and of NP-completeness IV) to class on Thursday.
• July 16: The latest notes (NP-completeness IV), as well as Test 2 and solutions to Test 2, have been posted below.
• July 13: There is a mistake in the solutions to Problem Set 2; in Q1, the min cut corresponding to the max flow f (exercise 27.2-3) should be: S={s, v1, v2, v4} and T={t, v3}.
• July 10: The solutions to Problem Set 2 have been posted below; I'll bring hard copies to class on Tuesday.
• July 7:
  • The TA will have extra office hours before the test on Tuesday, July 11, 4-5 in ES149.
  • The test will cover the material from weeks 5,6,7, and 8, that is: Network Flows, NP-completeness I,II,III and CircuitSat, SAT and 3SAT. Again, make sure you know how to do all the exercises in the notes, and that you understand the direction of reductions. You have to know all the definitions, all the lemmas and theorems, and their proofs.
• The latest lecture notes have been posted below. There are two files for week8: "NP-completeness III", and "NP and NP-completeness". From the latter you are only responsible for the material on CircuitSat, 3SAT, and SAT.
• TA's extra office hours:
  • Tuesday, July 4, 4-5 in ES149, for questions regarding PS2
  • Tuesday, July 11, 4-5 in ES149, before Test 2
• July 4: The latest lecture notes (NP-completeness II) have been posted below; I'll bring hard copies to class today.
• June 29: Today's tutorial has been canceled.
• June 27: The TA, Ying Zhu, will have the following office hours:
  • Tuesday, July 4, 4-5 in ES149, for questions regarding PS2
  • Tuesday, July 11, 4-5 in ES149, before Test 2
• June 26: The latest lecture notes (NP-completeness I) have been posted below; I'll bring copies to class on Tuesday.
• June 20: Solutions to Test 1 have been posted below; again, I'll bring "hard" copies to class today. As always, comments and corrections are greatly appreciated.
• June 19: Problem Set 2 has been posted below; I'll bring "hard" copies to class on Tuesday.
• June 15: Test 1 will take place today during the tutorial. Problem Set 1 has been marked.
• June 9: The latest lecture notes (Dynamic Programming II) have been posted below. The solutions to PS1 have been posted below as well. Remember that Test 1 will take place on Thursday, June 15, (make sure you know how to solve all the exercises in the lecture notes). The TA (Ying Zu) will have pre-test office hours on Tuesday, June 13, at 4:10 right after the lecture in ES149.
• June 5: Last week's lecture notes (Dynamic Programming I) have been posted below. I'll bring copies to class tomorrow=Tuesday.
• June 1: The TA (Ying Zhu) is going to hold extra office hours on Tuesday June 6 (for questions related to PS1), and on Tuesday June 13 (before the test). Both times, from 4:10 until 5:00 in ES149 (i.e. right after the lecture, in the same room).
• May 26: Here is a hint for question 2(a) on the first problem set: fix a min cost ST T_opt. Define a set of edges to be promising if it is contained in T_opt. Now show that "T is promising" is a loop invariant of Kruskal's algorithm. From this, with a one sentence observation, you CAN conclude that there is a unique min cost spanning tree (concentrate on the fact that you can let any min cost ST be T_opt).
• May 26: the latest lecture notes (Greedy Algorithms II) have been posted below.
• May 25: The first tutorial will take place today, at 2:10 in ES149 (the same room where the lecture is). Also, my office hours start today, 1:10 to 2:00 in UC45 (basement of Univ College).
• May 23: I'll bring copies of the first set of notes to class.
• May 23: Some of you asked me about subcase(b) on page 5 of the notes (Greedy Algorithms I). People seem to have trouble understanding why i < j. Here is a clarification: First of all, you don't need the Exchange Lemma for this particular part. Just suppose that j < i (we know that i is not equal to j). Then, since j is not in T_2, it is not in T, and since j < i, the algorithm looked at e_j already, so e_j must have been rejected, so it forms a cycle in T, but then it also forms a cycle in T_1; contradiction, since T_1 is a tree. Thus i < j.
• May 19: The first set of notes has been posted below. Comments and corrections are appreciated.
• May 18: You should read chapters 17.1 and 17.2 in the text book.
• May 17: Since many people have csc324 on Tuesdays, my office hours will be on Thursdays, 1:10 -- 2:00, in UC45 (basement of Univ College). Office hours will start next week.
• May 16: There is no tutorial this week; tutorials start on Thursday, May 25.
• May 6: My office hours will be on Tuesdays 2-3, in UC45. You can also see my at other times by appointment.
• May 4: I'm back, so you can send me questions about the course, if you have any.
• I'm away until May 3. If you have any questions that cannot wait until then, you can contact the evening section instructor, Valentine Kabanets: kabanets@cs.toronto.edu