Old Announcements

• Aug 13: For those who cannot make it to my office hours to pick up test 3, I will bring the tests to the exam, and return them AFTER the exam is over! If you want to see your tests BEFORE the exam, I have office hours until 6pm.
• Aug 13: I will be in UC45 (my office) most of the day on Tuesday, marking the final exam. If you want to talk to me about your marks, please come and see me. As I wrote below, I plan to submit the final marks by Wednesday (Aug 15).
• Aug 13: Frank is going to hold the Test 3 re-marking office hours in UC48 on Tuesday (Aug 14), 4--6pm. Please bring all your re-marking requests on Tuesday, as I plan to submit the final marks by Wednesday. Also, make sure that you read the TAs comments (posted below) carefuly before you bring your test for remarking.
• Aug 13: Test 3 has been marked. You can pick up the tests during my office hours today, 4--6pm. Click here to read about the day section tests, and click here to read about the evening section tests. Also, click here to see the day section marks, and click here to see the evening section marks. The marks are listed by student numbers; MAKE SURE THAT YOU CHECK ALL YOUR MARKS. Finally, click here to make sure that I have your justifications for missed term work.
• Aug 8: Test 3 and solutions have been posted below.
• Aug 8: Click here for the Problem Set 3 marking scheme and comments; make sure that you read this very carefully before seeing Alan today.
• Aug 7: I (the instructor) will hold the following office hours:
  • Tuesday Aug 7, 4--6pm (as usual)
  • Friday Aug 10, 4--6pm (additional office hours)
  • Monday Aug 13, 4--6pm (additional office hours)
• Aug 7: Click here for a solution to Q6(a) in last year's final exam; many students asked me how to do this question.
• Aug 1: Latest (and last) notes, Computability III, have been posted below.
• Aug 1: Click here for info on Test 3.
• Aug 1: Click here for info on Final Exam.
• Aug 1: NEW SCHEDULE of TA office hours:
  • For help before Test 3: Thursday, Aug 2, 4-6pm, in UC48
  • For re-marking Problem Set 3: Wednesday, Aug 8, 5-7pm, in SF3207
• Aug 1: Solutions to PS3 have been posted below.
• July 27: Computability II notes have been posted below.
• July 27: Next office hours (all in SF3207):
  • For help with Problem Set 3: Monday, July 30, 7-9pm
  • For help before Test 3: Monday, Aug 6, 5-7pm
  • For re-marking Problem Set 3: Wednesday, Aug 8, 5-7pm
• July 26: Click here for the final examination timetable.
• July 24: Visit TAing if you would like to be a TA next year.
• July 24: Click here to read some comments and directions to Problem Set 3.
• July 18: Greg Kondrak is going to hold office hours for the re-marking of Test 2 in SF3207, from 5:30 until 7:30, on Wed July 25. Please click here to read about his marking scheme before going to his office hours.
• July 18: Latest notes, Computability I, have been posted below.
• July 18: Correction in solutions of Test 2: Q3 of the evening section, at the beginning should check if there is such an independent set at all, and should carry the parameter B around. The corrected solutions have been re-posted below.
• July 18: Please prove the correctness of your reduction in Q2b) in PS3 (your reduction should be simple, and so should be the proof of correctness). You do not have to prove the correctness of the reductions in Q3, PS3.
• July 18: I am going to be away until next Tuesday, so I will answer (some of) your emails when I return.
• July 18: Some general comments about your marks (people have been asking my opinion regarding their performance in csc364). The last day to drop courses is coming up (July 22, I believe, but I am not sure). I think that at this point everyone can make an informed decision about staying or not in csc364; Problem Sets 1 and 2 have been returned, and Tests 1 and 2 have been returned (Test 2, day section, will be returned today in class), and I have posted the final exam from last summer, as well as Problem Set 3, and Test 3 from last summer. So you know what to expect. I have also explained that I do not plan to adjust marks, considerably at least. I may, at the end of the course, adjust the average of Test 2 evening section (40%) to be the same as the day section (50%). Since you have four pieces of work graded, you can project your final mark given the current effort that you put into csc364. I understand that many students work full-time during the summer, and I know that it is hard to combine a job with a course, but I am responsible for teaching a certain material, and for grading your understanding of it.
• July 14: Click here for last summer's Test 3, and click here for last summer's Final Exam.
• July 12: Latest notes have been posted below.
• July 12: Two correction to solutions of PS2: in question 1 in the definition of the array R; revised solutions have been posted below.
• July 11: Frank Van Bussel prepared a detailed marking scheme for Problem Set 2; click here to read it (and make sure that you read it before you ask Frank to re-mark your problem set).
• July 11: Next week there is going to be just one hour of lectures; day section: there is no lecture on Thursday, July 19. Evening section: there is just one hour of lecture on Tuesday, July 17, 7--8pm (no second half). Next week we are starting computability.
• July 11: Test 2 and solutions (both sections) have been posted below.
• July 6: Problem Set 3 has been posted below.
• July 6: Frank Van Bussel is going to hold office hours for the re-marking of PS2 on Thursday, July 12, at 3:00--4:00 and at 6:00--7:00, both times in SF3207.
• July 11: Frank Van Bussel prepared a detailed marking scheme for Problem Set 2; click here to read it (and make sure that you read it before you ask Frank to re-mark your problem set).
• July 11: Next week there is going to be just one hour of lectures; day section: there is no lecture on Thursday, July 19. Evening section: there is just one hour of lecture on Tuesday, July 17, 7--8pm (no second half). Next week we are starting computability.
• July 11: Test 2 and solutions (both sections) have been posted below.
• July 6: Problem Set 3 has been posted below.
• July 6: Frank Van Bussel is going to hold office hours for the re-marking of PS2 on Thursday, July 12, at 3:00--4:00 and at 6:00--7:00, both times in SF3207.
• July 5: The latest notes have been posted below.
• July 4: The solutions to PS2 have been posted below.
• July 4: The material covered before Test 2 in the previous years was different than this year (we did Randomized algorithms one year, and network flows the other year), so these tests are not good to prepare for the test this year. However, the format will be the same as for Test 1, and you should prepare by reviewing the notes, doing the exercises in the notes, and reviewing PS2.
• July 4: Greg Kondrak will hold office hours on Monday (July 9) in the University College Math Aid Center (UC48, just accross from my office), from 5:10pm until 7pm. These office hours are for questions before Test 2.
• July 3: PS2 is due today at the beginning of the tutorial. I will post the solutions by tomorrow. Test 2 is going to take place next week, in tutorial. The evening section will write the test (all three tutorials) in MS2172. The day section will write the test in the usual tutorial room. The test will cover NP-completeness (I,II,III and IV--this week).
• July 3: If you cannot hand in a Problem Set at the time when it is due, and you have a valid excuse (eg., sickness + doctor's note), I will transfer the 5% of the Problem Set to the final exam (so your term mark will be worth 5 points less, and your final exam mark will be worth 5 points more). I will do the same with missed tests (again, you must have a valid excuse accompanied by valid documentation).
• June 28: Latest notes have been posted below.
• June 27: Mohammad, who marked Test 1, is going to be in his office (SF3208) on Thursday, June 28, around noon and between 3 and 5pm. This is the last oportunity to get Test 1 remarked, as Mohammad is leaving.
• June 24: There will be no office hours on Tuesday; instead, I am going to hold office hours on Wednesday 4--5pm (in UC45 as usual).
• June 24: Click here for a note on Question 4 in PS2.
• June 21: For Test 1 re-marking requests: June 25, in SF3207, 5--7pm.
• June 21: The latest notes (NP-completeness II) have been posted below. Note that I have elaborated considerably on what was said in class about the formal/informal definition of NP; please read the notes carefully, and make sure you understand everything. Also, I have posted below a discussion of PvsNP (by S. Cook). You are NOT required to read this material for this course, but you may find it interesting.
• June 20: I have added the following two students to the classlist:
  • 920342890
  • 990120123
  Please make sure that you are indeed enrolled in the course.
• June 19: The tests have been marked; I will return the evening section tests in class today, and the day section tests in class tomorrow. The evening section average is 58%, and the day section average is 56%. I do not intend to adjust the marks (now or at the end of the course, partly since in both sections 1/5 of the class has an A), so the mark you get is the mark you get. The following two people did not write the test in their section:
  • 981613240
  • 981415720
  Could you please contact me? (By email or in person). Also, the following people took the test, but were not on the official class list:
  • 980650280
  • 971529340
  • 981886370
  • 920342890
  • 990120123
  If you are one of these five numbers, please make sure that you are enrolled in the course by checking ROSI or by going to the Comp Sci Undergraduate Office.
• June 15: For Test 1 re-marking requests: June 25, in SF3207, 5--7pm.
• June 14: Latest notes have been posted below.
• June 13: Problem Set 2 has been posted below.
• June 13: Test 1 and solutions have been posted below.
• June 13: For PS1 re-marking requests: Monday, June 18, in SF3207, 4--7pm. Please note that this is the last day to get PS1 re-marked, as Mohammad is not going to be available later.
• June 9: Both sections will write Test 1 this Tuesday (June 12) in tutorial. All the evening tutorials will write the test in MS2172; please go there at 6pm. The test covers all the material presented until now, that is, material in the notes posted below. Make sure that you can do all the exercises in the notes, and that you review the solutions to PS1.
• June 8: Notes for this week have been posted below.
• June 7: In Q5b) in PS1, |t_i|>=j should be |t_i|<=j.
• June 6: There was a mistake in Q1 in PS1; i) should be in and g) should be out. I have re-posted the solutions with the correction.
• June 6: Solutions to PS1 have been posted below.
• June 4: Test 1 from Summer 99
• June 4: I have asked about cdf accounts and print quotas for csc364. The undergraduate CS office does not provide cdf accounts for this course as it is a pencil-and-paper course, and most people have access to the web from other sources already (such as permanent cdf accounts). If you have a cdf account, and you NEED to increase your print quota, contact admin@cdf .
• June 1: Upcoming office hours:
  • Before Test 1: Monday, June 11, in SF3207, 6--7pm.
  • For PS1 re-marking requests: Monday, June 18, in SF3207, 4--7pm.
• May 31: The latest notes have been posted below.
• May 31: Brief justifications are enough for Question 1 in PS1.
• May 29:
  • Why is the case j < i (case(II), subcase(b) of the proof of correctness of Kruskal's algorithm) not possible?: Suppose that j < i. Then e_j was cansidered before e_i. Since e_j is not in T_2, this means that e_j was rejected, and therefore that T with e_j has a cycle. But T with e_j is in T_1, so T_1 must have a cycle. Contradiction, since T_1 was a ST.
  • You should read the following sections in the text book: 17.1, 17.2, 17.5 (Greedy Algorithms), and Chapter 24 (Spanning Trees)--you can ignore Prim's algorithm. You are not responsible for Huffman codes or for 17.4.
• May 25: New notes have been posted below.
• May 24: Students have complained that some people are using solutions from last summer to do Problem Set 1. This is a valid concern, and I want to say several things about it: The Problem Sets are worth very little, and they are intended as preparation for the Test. If you are plagiarizing answers, you will not be prepared for the upcoming Test where ALL questions are going to be NEW questions. Finally, not all the questions in Problem Set 1 are "recycled", so it will be easy for the TAs to spot plagiarism. The next Problem Sets and Tests will have ONLY new questions.
• May 22: Tutorials start today.
• May 17: The notes for the first week have been posted below. Note that I will not bring hard copies of the notes to class.
• May 16: Tutorials:
  • Day Section: SS1088 with G. Kondrak.
  • Evening Section: divided by LAST NAME as follows:
    • A-G: in WB219 with F. Van Bussel
    • H-M: in MS2172 with M. Salavatipour
    • N-Z: in SS2130 with A. Skelley
• May 16: Problem Set 1 has been posted below.
• May 9: Tutorilas will start on Tuesday May 22.
• May 7: Classes start next week. An information sheet for the course has been posted above.