CS 573 - Graduate Algorithms - Fall 2008

Wed Fri 12:30-1:45, 106 B1 Engineering Hall

Instructor:
Jeff Erickson (jeffe+573@cs.uiuc.edu), 3304 Siebel Center
Tentative office hours: Monday 11-12, Thursday 11-12, in the open area outside 3303 Siebel Center
Administrative assistant: Mark Faust, 3316 Siebel Center

Teaching assistant:
Reza Zamani Nasab (zamani@cs.uiuc.edu)
Office hours: Tues 2-3, Wed 2-3, in the open area outside 3303 Siebel Center

Course policies:

Other stuff:

Announcements

December 24:
  • The final exam has been graded; here is a list of all scores:
    17.5 17.5 23.5 29.75 31 32.5 34.75 35 35.5 36 36 36.5 40 41 42 42.5 43 44 46 50 51.5 52 52 52.5 53 53.25 54 54.25 54.5 55 57 59 60.5 61 62 63.5 67
    Final course grades should already be available from the registrar. Here is a list of all letter grades; stars indicate outliers.
    F* F* B- B- B- B- B B B B B+ B+ B+ B+ B+ B+ B+ A- A- A- A- A- A- A- A- A A A A A A A A A A A A+*
    Grades are available for students with aliases. If you want to see your final exam, talk to Jeff after classes start up again.

  • Thanks for a great semester!

December 10:
  • Homework 5 has been graded; grades are available for students with aliases. You can pick up your graded papers from Jeff or Reza during office hours. This was the last graded homework of the semester.

December 6:
  • The final exam will be held on Wednesday, December 17, in 1310 DCL. The exam will be comprehensive, although there will be slightly more emphasis on material from the last third of the course (flows and linear programming). The format of the exam will be similar to the midterms, but there will be seven questions instead of five, and you will have three hours to take the exam instead of two. You may bring two double-sided `cheat sheets' to the exam; otherwise, the exam is closed-everything as usual.

  • The last class period, on Wednesday, December 11, Jeff will attempt to answer arbitrary questions. Ask about the final exam. Ask about questions on old exams. Ask that question that's been bothering you since that lecture that one time. Ask that Google interview question. Ask about future special-topics classes. Ask about research in algorithms. Ask about finding an academic job. Ask about Jeff's daughter.

  • Jeff's and Reza's office hours will continue on their usual schedule until the final exam.

December 3:
  • Homework solutions are now available.
  • Homework 6 is available. This is for practice only; don't submit solutions. However, at least one (sub)problem, or something very similar, will appear on the final exam.

  • If you have not already done so, please visit ICES Online and fill out an evaluation form for this course. The deadline for completing the online course evaluations is Thursday, December 11. This is your best opportunity to provide feedback to Jeff and Reza (and to their bosses) on the quality of the course and their teaching. This feedback is extremely important! In particular, we need your suggestions to help us improve future offerings of this course.

November 20:
  • Homework 4 has been graded; grades are available for students who provided aliases on HW0 (or later by email). You can pick up your graded papers from Jeff or Reza during office hours.

November 14:
  • Midterm 2 has been graded; here is a list of all scores:
    13.75 16.25 20.25 21 21.5 23.75 24 25.75 26.75 27.25 27.5 29.5 29.75 30 30 30.25 31 31 31.75 31.75 33.25 33.75 34 34.5 36.5 37 37.5 37.75 38 38 38.25 38.25 39.75 40.5 40.75 41 43 44 46 47 49
    Grades are available for students who provided aliases on HW0 (or later by email). Letter grades reflect the score distribution of the midterms only; as such, they are only rough predictors of your final course grade. You can pick up your graded exams from Jeff or Reza during office hours.

  • Today is the last day to drop the class without adding a W to your transcript.

November 12:
  • Homework 3 has been graded; grades are available for students who provided aliases on HW0 (or later by email). You can pick up your graded papers from Jeff or Reza during office hours.

November 6:

November 5:

November 3:
  • Midterm 2 will be held Wednesday, November 5, 7–9pm, in 103 Transportation.

November 2:

October 23:

October 18:
  • Midterm 1 has been graded; here is a list of all scores:
    15 19 19 19 19.5 20 23 24.5 25 25 25.5 26 27 29 29 29.5 30 30 30 33 34 35 35 36 39 39 40.5 41 41 41.5 42 42 42 42.5 43 44 44 44 45 47 48
    Grades are available for students who provided aliases. Letter grades reflect the score distribution of the midterm only; as such, they are very rough predictors of your final course grade. You can pick up your graded exams from Jeff or Reza during office hours.

October 17:
  • Homework 4 is due October 31.
  • Homework 2 has been graded; grades are available for students who provided aliases on HW0 (or later by email). You can pick up your graded papers from Jeff or Reza during office hours.
  • Jeff is traveling next Monday, so he will hold office hours Tuesday 10-11 instead.

October 13:

October 8:
  • Minimal and detailed solutions to Midterm 1 are available.
  • Homework 3 is due Wednesday, October 22.
  • Homework 4 (on randomized algorithms) will be due Monday, Nov 3, just before Midterm 2. In order to give you two weeks to work on it, we will release Homework 4 a day or two before Homework 3 is due.

October 5:
  • Homework 2 solutions are available. The best running times I know for the homework problems are the following:
    1. (a) O(n2); (b) O(n) [greedy]; (c) O(n2 log n) [not described in the solutions], but we will give full credit for O(n3)
    2. O(n2)
    3. O(2n n2)
    4. O(n3) for both parts. Part (a) can probably be improved to O(n2), but I haven't tried very hard.
    5. O(mn)
    6. O(n3/2 log n), but we will give full credit for O(n4)

October 2:
  • Homework 1 has been graded; grades are available for students who provided aliases on HW0. You can pick up your graded papers from Jeff or Reza during office hours.

    If you did not provide an alias on HW0, and you want your future homework and exam grades to appear on this site, please send email to Jeff with your preferred individual alias.

  • Midterm 1 will be held Monday, October 6, 7-9pm, in DCL 1310.
    • The exam will cover NP-completeness, recursion (including backtracking and divide-and-conquer), dynamic programming, and greedy algorithms. (Approximation algorithms will wait until the second midterm.) The exam will have five questions, at most one of which will be about greedy algorithms. You may want to look at some old exams. We will not ask directly about any prerequisite material (big-Oh notation, recurrences, binary search trees, solving quadratic equations, etc.), but you may need to use it anyway.

    • You may bring one 8.5"x11" sheet of paper to the exam, with anything written, printed, or photocopied on both sides. Otherwise, the exam is closed-book, closed-notes, and closed-web. No electronic devices of any kind are allowed. You may bring a slide rule or an abacus if you like, but you woan't need it. We will provide answer booklets.

  • Because of the Monday evening exam, there will be no lecture on Friday, October 3. Jeff will hold extra office hours in 106B1 Engineering Hall during the normal Friday class period; please come pick up your HW0 and HW1, and ask questions about HW2 (due Friday evening) or the exam.

September 18:

September 14:

September 12:
  • Thanks to everyone who found and reported typos and other bugs in the lecture notes and homework solutions! All the errors that have been reported to me (either in person, by email, or on the newsgroup) have been fixed.

September 11:
  • The HW0 grades incorrectly included extra credit points (for typesetting) in the raw totals; this has been fixed.

September 10:
  • Homework Zero has been graded; grades are available for students who provided aliases. You can pick up your graded papers from Jeff during his office hours. As expected, the hardest problems were #2 (RangeTop) and #5 (Fibonacci sums).

    A HW0 score below 20/50 is a red flag; this strongly indicates that you need to strengthen your mastery of background material (especially proofs by induction) if you want to pass the course. Your lowest homework grade will be dropped, but please keep in mind that you need at least a 50% average to pass the course, and exam scores tend to be lower than homework scores. If you have any concerns, please come talk to Reza or Jeff during office hours.

September 3:
  • Homework Zero solutions (also latex source) are available. Revised September 4.

  • Homework 1 is due on September 17. For this and all future homeworks, groups of up to three people can submit a common solution. Please submit your solutions to Mark Faust in 3316 Siebel Center.

  • There will be a graph review session on Thursday, September 4, starting at 5:00, in 4403 Siebel Center. (Unfortunately, the room may be a little cramped; all the larger rooms are being used by engineering RSOs and Google.)

August 26:
  • Hello and welcome! The course web site is still under heavy construction; please be patient.

  • Please note that the class has moved from its original room Siebel Center (which held only 43 students) to 106B1 Engineering Hall (which holds 72). Everyone who wants to register should now be able to. In the unlikely event that the class fills again, anyone still interested in registering should come to class during the first week to add their name to the waiting list. Students who register late are still expected to turn in Homework Zero.

  • Homework Zero is due in class at 12:30pm on Wednesday, September 3. (This will be the only homework due in class.) LaTeX source code is available, if you'd like a template for your solutions. You may also find Jeff's notes on solving recurrences helpful.

Administrivia

Audience:
CS 573 is intended for graduate students in computer science and related areas, including students in the 5-year CS master's program. Mathematically/algorithmically mature undergraduates are also welcome to register, but you need my permission first.

Prerequisites:
Students are assumed to have an undergraduate degree in computer science or a related field, such as electrical/computer engineering or mathematics. Students are also assumed to have mastered the material taught in CS 173 and CS 225 (discrete mathematics, basic algorithms and data structures). We emphasize that "mastery" is not the same as "exposure" or even "a good grade". Hence, Homework Zero. Programming experience is helpful; a strong mathematics background is even more helpful.

Coursework:
Grades will be based on 6-8 homeworks (30% total, lowest score dropped), two midterms (20% each) and a final exam (20%). There will be many opportunities for extra credit, which will be applied after the curve.

Reading material:
There is no required textbook. Instead, Lecture notes will be posted to the course web site as the semester progresses. For almost every topic we will cover, both Jeff Erickson and Sariel Har-Peled have lecture notes online from previous semesters. For students who prefer an actual dead-tree book as an additional reference, we recommend any of the following:
  • Algorithm Design by Jon Kleinberg and Éva Tardos (Addison-Wesley, 2005).
  • Algorithms by Sanjoy Dasgupta, Christos Papadimitriou, and Umesh Vazirani (McGraw-Hill, 2006).
  • Introduction to Algorithms by Thomas H. Cormen, Charles Leiserson, Ronald L. Rivest, and Clifford Stein (MIT Press/McGraw-Hill, 2001). The first edition is also fine.
If there is sufficient demand, hard copies of Jeff's lecture notes will be made available at a local copy shop.

Newsgroup: class.cs573 on the news server news.cs.uiuc.edu
Please read the newsgroup at least once a day. Important announcements will be posted both on this web site and on the newsgroup. You must sign up for access if you have not already done so.