CS 204: Algorithms I    home page winter 2003      revised April 8 2003

what's new

1. 3 old final exams (see ``course content'')
2. quiz 5.2: restricted to questions on MST and SSSP
3. 2 old midterms (see ``course content'')
4. hints for problem sets; solutions to 1 quiz/week
5. for drop-in purposes, TAs each have one office hour (listed below); for other times, arrange an appointment by email
6. seminars start January 13; seminar schedule and TA list have been added below
   YOU MUST ATTEND THE SEMINAR IN WHICH YOU ARE REGISTERED
7. information on plagiarism has been updated; see the appeals and cheatsheet links mentioned below (in the section on grading)

instructors (* course coordinator)

TAs (* head TA)

seminar schedule

SEM J01   Monday    16:00  CAB 273   Xiaohu Lu     [marker: Li/Ghosh alternating]
SEM J02   Tuesday   08:00  CAB 281   Yang Wang     [marker: Lisheng Sun]
SEM J03      cancelled   
SEM J04   Tuesday   17:00  CAB 269   Yang Wang     [marker: Xiaohu Lu]
SEM J05   Wednesday 16:00  CAB 269   Lisheng Sun   [marker: Guang Li]
SEM J06   Thursday  08:00  CAB 269   Lisheng Sun   [marker: Yang Wang]
SEM J07   Thursday  13:00  BS M 141  Xiaohu Lu     [marker: Shubhashis Ghosh]

course content

• CS dept. catalogue description   (including section and textbook information)
• textbook: Introduction to Algorithms, 2nd edition (Cormen/Leiserson/Rivest/Stein)
• old midterms 2001.ps   2001.pdf   2002.ps   2002.pdf   Prof. Leonard 2002.ps  
• old final exams Hayward2001.ps   Hayward2001.pdf   Hayward2002.ps   Hayward2002.pdf   Leonard2002.ps   Leonard2002.pdf  

grading (fall 2002 and winter 2003)

• 44%    in-seminar quizzes    (best 4 scores from 5 problem sets)
• 17%    midterm exam          (in class, Friday February 28, 50 minutes)
• 39%    final exam        (3 hours)
• Absence for a quiz, midterm, or final will usually result in a score of 0; at the discretion of the instructor, if an acceptable excuse exists and can be supported by documentation, the marks for a missed quiz or midterm may be shifted to the final exam.
• For a missed final, the student must apply to the Faculty of Science (not the instructor) for permission to write the deferred exam; the time/date of the deferred exam for the winter 2003 semester will be Friday May 2, 1pm, room TBA.
• Following recent departmental practice, all cases of plagiarism will be forwarded by the instructor to the dean. See the appeals webpage of the university secretariat (in particular, the cheatsheet link, for a description of plagiarism, and processes for dealing with plagiarism.
• grade cutoffs will be assigned within a few points of each of the following, taking into consideration the final distribution of marks
  • 9     90
  • 8     80
  • 7     70
  • 6     60
  • 5     55
  • 4     50
• Any questions concerning the grading of a term test (quiz or midterm) should be brought to the attention of the marker (this will be either the instructor or a TA) within 7 days of the date on which the test has been returned to the class (lecture or seminar) in question; after that time, marks cannot be changed.
• This course has multiple sections. You must write all exams/quizzes in the lecture/seminar sections in which you are registered. Exams and lectures vary slightly between sections, so you should attend the lectures in which you are registered.
• Final grades for each section will be set individually for each section, in consultation with the instructors of the other sections.

seminars         (seminar schedule here)

• 10 seminars (2 for each problem set) will be used to administer quizzes
  • the first quiz for a problem set will take 15 minutes
  • the second quiz for a problem set will take 30 minutes
  • the two quizzes for each problem set will total 11 marks
• remaining seminars (and time remaining after the quizzes in the 10 quiz seminars) will be devoted to helping students master course contents
• unless otherwise authorized by an instructor, students must write the quiz in the section in which they are registered
• each quiz will consist of questions based on randomly selected from the corresponding problem set (so quiz questions may vary among seminars)

problem sets

• problem set #1:   .ps   pdf   hints I   hints II   soln I   soln II
  loop invariant, insertion-sort, merge-sort, [selection-sort, bubble-sort,] asymptotic notations
• problem set #2:   .ps   pdf   hints I   hints II   soln I   soln II
  recurrences, heaps
• problem set #3:   .ps   pdf   hints I   hints II   soln I   soln II
  heap-sort, priority-queue, quick-sort, sorting lower bound
• problem set #4:   .ps   pdf   hints I   hints II   soln I   soln II
  dynamic programming concepts, matrix chain multiplication, longest common subsequence, disjoint-sets and union-find, graph traversal: BFS and DFS
• problem set #5: NOTE: IGNORE WHAT IT SAYS IN THE HINTS ABOUT WHAT WILL BE ON QUIZ 5.2.
  QUIZ 5.2 will be restricted to problems on MST and SSSP
  The remaining topics (Strassen, decision problems, P, NP) will not be on this quiz, but may be on the final exam.
    .ps   pdf   hints I (last year)   hints II (last year)   hints III (last year)   soln I   soln II
  biconnected component, MST: Kruskal and Prim, Dijkstra's SSSP algorithm, Strassen's algorithm, decision problems, P, NP