CS 473 - Undergraduate Algorithms - Spring 2009

Lecture: Tue Thu 11:00-12:15, in 1404 Siebel Center

Discussion Sections: Tue 5-6, Tue 6-7, Wed 2-3, Wed 3-4, all in 1111 Siebel Center

Instructor: Jeff Erickson (jeffe@cs.uiuc.edu), 3304 Siebel Center
Office hours: Wednesday 11-12 and Friday 1-2, in the open area outside 3303 Siebel Center
Administrative assistant: Mark Faust, 3316 Siebel Center

Teaching assistants:
  • Alina Ene (ene1@uiuc.edu) — Office hours: Monday 3-4
  • Amir Nayyeri (nayyeri2@uiuc.edu) — Office hours: Friday Monday 4:30-5:30(ish)
  • Ben Moseley (bmosele2@uiuc.edu) — Office hours: Monday 1-2
  • All office hours are in the open area outside 3303 Siebel Center

Graders: Scott Wegner and Yiran Wang

Course policies:

Other stuff:

Announcements

May 22:
All homework and exam solutions have been removed.

May 20:
  • Here are the final exam scores (out of 50, dropping the two lowest scores):
    10.5, 11.5, 12, 12, 12, 13.75, 14.75, 15, 15.5, 15.75, 16, 16, 16, 17, 17, 17, 17.5, 17.75, 17.75, 18.5, 18.5, 19, 19, 19, 19.5, 20.25, 20.5, 20.5, 21, 21.25, 21.5, 21.5, 21.5, 21.75, 22.5, 22.5, 22.5, 23.75, 24.25, 26, 26, 26.5, 26.75, 26.75, 26.75, 27.5, 27.5, 27.5, 28.5, 28.5, 29, 29.25, 29.5, 30, 30.5, 31, 31, 31.25, 31.5, 32, 32.5, 34.5, 35, 35.25, 36.5, 36.5, 37.5, 38, 38, 38, 38.5, 40.25, 40.5, 42, 42.5, 42.5, 42.5, 43, 44, 45.5, 45.5, 46, 46.5, 48, 48.5, 48.5, 49.5, 50
    The average(±stdev) score was 28.1(±10.9); the average(±stdev) scores for each problem were 5.1(±2.9), 5.4(±2.5), 2.9(±2.1), 5.1(±3.2), 4.0(±3.2), 5.9(±3.0), and 3.8(±3.5). If you want to see your final exam, come to Jeff's office.

  • All course grades have been posted to Banner. Here is the (tentative) distribution of letter grades: 4×A+ 8×A 9×A- 8×B+ 6×B 10×B- 12×C+ 9×C 6×C- 3×D+ 10×D 1×D- 2×F.

  • All grades have been recorded on Compass, including regrades. If you had a homework or exam regrades, and your new score does not appear on Compass, please let Jeff know as soon as possible. Even though official course grades have been submitted, it is still possible to change them if we have made a mistake.

May 18:
The final exam was way too hard. To compensate, we will drop the two lowest problems from everyone's final exam score, so the maximum possible score on the exam is 50. (Nobody's grade will go down because of this change.)

May 14:
Solutions for the final exam are available.

May 7:
  • Solutions for Homework 9 and Homework 10 are available.

  • Jeff will not hold office hours this Friday (May 8). He will hold extra office hours next week: Monday 2-3, Wednesday 11-12, and Wednesday 3-4. Alina, Amir, and Ben will hold office hours on Monday as usual.

  • The final exam will be held in 1404 Siebel Center (the regular lecture room) on Thursday, May 14, from 1:30 to 4:30.
    • The exam will cover all topics covered in class this semester and described in the lecture notes.
      • Recursion / induction ♥
      • Dynamic programming ♥
      • Randomized algorithms
      • Amortized analysis
      • Basic graph algorithms (whatever-first search, MST, shortest paths) ♥
      • Maximum flows, minimum cuts, matchings, assignment ♥
      • Lower bounds
      • NP-hardness ♥
      We guarantee at least one question on each topic labeled with a heart ♥. There will be slightly more emphasis on material introduced since the second midterm (flows and beyond). As usual, we expect mastery of all prerequisite material (recurrences, big-O notation, basic data structures, etc.) Topics that were not covered in class will not appear on the final exam, even if they appear in the notes. For example, there will be no questions on flows with edge demands.

    • The final exam will have seven questions; the best six will determine your score. We will do our best to write an 2-hour exam.
    • You can bring in a two-page double-sided cheat sheet, but nothing else.
    • You are strongly encouraged to look through Jeff's old exams, but keep in mind that the course material varies form one semester to the next. Most of the old exam problems have been folded into the lecture notes.
    • If you have not already received email from Jeff about taking the conflict exam, we assume you will take the regular final exam.

April 29:
Written solutions for Homework 10 are due next Tuesday, May 5. This homework is optional! If you do not submit solutions, your other homeworks will be weighted (slightly) more heavily.

April 28:
  • Solutions for Homework 8 are available.

  • Please don't forget to fill out course evaluations via ICES Online. All evaluations for CS 473 must be submitted by next Thursday, May 7.

April 22:
  • Written solutions for Homework 9 are due next Tuesday, April 28. This is the last graded homework.
  • There was a systematic grading mistake on Midterm 2. If your solution to problem 3(a) was to replace each edge weight w(e) with its reciprocal 1/w(e) and run an minimum spanning tree algorithm, please bring your midterm to Jeff for regrading. Your solution is correct if and only if all the edge weights are positive, so you should have received significant partial credit.

April 19:
As Jeff announced in class on Thursday, we have decided to make HW10 optional. (Since it would normally be due on the last day of classes, grading and returning everyone's HW10 before the final exam seems unrealistic.) You are welcome to submit written solutions to be graded if you like. If you decide to submit HW10, your overall homework grade will be the average of ten homeworks (HW0 through HW10, dropping the lowest). If you do not submit HW10, your overall homework grade will be the average of nine homeworks (HW0 through HW9, dropping the lowest).

Each homework group previously scheduled to present HW10 has been randomly reassigned to present HW8 or HW9 instead. If you presented HW7, you should already have an email from Jeff telling you which upcoming homework we expect you to present. Please contact Jeff as soon as possible if you should have received an email but did not, or if your group got inconsistent emails, or if you have a conflict that prevents you from presenting in the week you've been assigned.

This change only affects students who were scheduled to present HW10. If you presented HW5, then you should also present HW8 this week, as planned. Similarly, if you presented HW6, then you should also present HW9 next week, as planned.

April 17:
  • Homework 8 has been updated to correct a typo: In problem 1, the input graph should be directed.

  • Solutions for Homework 7 are available.

  • Midterm 2 is graded; here are all the scores:
    7, 8.75, 11, 11, 11, 11, 11.5, 11.5, 12, 12.5, 13, 14.5, 14.75, 15.25, 15.75, 16, 17, 17, 17.25, 17.5, 19, 19, 19.5, 19.75, 20, 20, 20, 20.5, 20.5, 20.5, 20.5, 20.5, 21, 21, 21, 21, 21.75, 22.5, 22.5, 23, 23, 23, 23.5, 24, 25, 25, 25, 25.25, 25.25, 26, 26, 26.25, 26.75, 27, 27, 27.25, 27.25, 28, 28, 28, 28, 28.5, 29, 29.5, 30, 30, 30, 30, 31, 31, 32, 32, 32, 32.5, 33, 33, 33.5, 34, 34, 34, 35, 35, 35.5, 36, 39, 39, 40, 40
    The average(±stdev) score was 24.1(±7.9); the average(±stdev) scores for each problem were 5.3(±3.0), 4.9(±4.3), 6.3(±3.1), 4.5(±2.8), and 4.8(±2.5). You can pick up your exams in office hours. Jeff will also bring the exams to class next Tuesday. All grades have been recorded on Compass.

  • Here are approximate letter grade cutoffs for the sum of the two midterms: F < 29 ≤ D ≤ 41 ≤ C ≤ 53 ≤ B ≤ 65 ≤ A. These were computed using my usual grading algorithm — remove outliers at the top (>77) and bottom (<25), set the B-/C+ bar at the mean (53), and make each standard deviation (12.0) worth a full letter grade.

    Please keep in mind that these are still only crude estimates of your final performance in the course; they take only 40% of the course content into account. However, it is unlikely that your final course grade will differ from this estimate by more than 2/3 of a letter grade. For example, if your midterm average is at B/C cutoff, you are unlikely to get either an A- or a D+ in the course. If you have concerns about your performance, please talk to Jeff or the TAs.

April 15:
Written solutions for Homework 8 are due next Tuesday, April 21.

April 8:
Written solutions for Homework 7 are due next Tuesday, April 14.

April 7:
Minimal perfect solutions for Midterm 2 are available. More detailed solutions and grading rubrics will be available soon.

April 6:
Solutions for Homework 6¾ are available.

April 1:
  • Solutions for Homework 6 and Homework 6½ are available.
  • Homework 6¾ is also available. This is another practice homework; similar problems might appear on Midterm 2.

  • Midterm 2 will be held in 141 Loomis on Tuesday, April 8, 7:00-8:30 pm. Loomis Laboratory is at the corner of Goodwin and Green; room 141 is the ginormous lecture hall.
    • The midterm will cover all the course material introduced before spring break, with more emphasis on later material: randomized algorithms, amortized analysis, whatever-first search, minimum spanning trees, and shortest paths (but not flows and cuts). At least one question will come directly from the head-banging sessions. We will almost certainly ask you to prove something by induction.
    • Topics that were not covered in class will not appear on any exam, even if they appear in the notes. For example, there will be no questions on tail inequalities or path compression analysis.
    • As with the first midterm, you can bring in a one-page double-sided cheat sheet, but nothing else.
    • You are strongly encouraged to look through Jeff's old exams, but keep in mind that the course material varies form one semester to the next. Most of the old exam problems have been folded into the lecture notes.
    • There will be no lecture on April 2. Jeff will hold a review session during the regular class period (11:00-12:15). Attendance is strictly optional.
    • If you cannot take the evening exam because of a conflict with another class, please send Jeff email AND talk to Jeff after class this week. The conflict exam will be held earlier on the same day as the regular exam.

March 19:

March 10:
  • Because of the weekend blackout, we are giving everyone a 24-hour extension on Homework 5. Written solutions for HW5 are now due Wednesday, March 11. Oral presentations will still take place on Wednesday and Thursday as usual.
  • Written solutions for Homework 6 are due next Tuesday, March 17.

March 8:
Oral presentations assignments for HW5, HW6, and HW7 exactly mirror the assignments for HW2, HW3, and HW4. Specifically:
  • Students who presented HW2 are expected to present HW5 this week.
  • Students who presented HW3 are expected to present HW6 next week.
  • Students who presented HW4 are expected to present HW7 the week after Midterm 2.
Please check Compass to verify which homework assignment you are expected to present.

March 5:
  • Here are all the scores for Midterm 1:
    10.25, 11, 11, 11.5, 14.5, 15, 15.5, 16, 16.5, 17, 18.5, 19, 19.25, 19.5, 21, 21, 21, 21.5, 22, 22, 22, 22.25, 23, 23, 23.5, 23.5, 23.5, 24, 24.5, 25, 25, 25, 25.25, 26, 26, 26, 27, 27.5, 28, 28, 28, 29, 29, 29, 29, 29.5, 29.5, 30, 30, 30, 30.5, 30.5, 31, 31, 31, 31, 32, 32.5, 33, 33, 33, 33, 34, 34, 35, 35, 35, 35, 35.5, 36, 36, 36, 36, 36, 37, 37, 37, 38, 38, 38, 39, 40, 40, 40, 40, 40, 40, 40, 40, 40, 40, 40
  • Here are approximate letter grade cutoffs: F < 15 ≤ D ≤ 21.5 ≤ C ≤ 28 ≤ B ≤ 34.5 ≤ A. These cutoffs were computed using my usual grading algorithm — remove outliers at the top (>39) and bottom (<12), set the B-/C+ bar at the mean (28), and make each standard deviation (6.5) worth a full letter grade.

    These letter grades are very crude estimates of your final performance in the course. It is not uncommon for students to improve (or decline) by a full letter grade between Midterm 1 and the end of the course; however, improvements of significantly more than a letter grade are extremely rare. Thus, if you got a C on Midterm 1, you might pull off a B in the course by working extremely hard, but you almost certainly won't get an A-.

  • The average(±stdev) scores for each problem were 6.0(±3.0), 6.5(±2.7), 6.1(±3.3), 5.5(±2.8), and 7.9(±3.0).
  • Jeff will bring the exams to class today. If you don't get a chance to pick up your exam today, you can get it during any office hours. All grades have been recorded on Compass.

March 3:
Written solutions for Homework 5 are due next Tuesday, March 10.

February 25:
Detailed solutions (with rubrics) for Midterm 1 are available.

February 24:

February 23:
Solutions for Homework 3½ are available.

February 20:
Solutions for Homework 3 are available.

February 17:
  • Homework 3½ is available. This homework is for practice only; do not submit solutions. However, one of the problems may appear on Midterm 1.

  • Midterm 1 will be held on Tuesday, February 24, 7:00-8:30 pm, in 180 Bevier Hall (about 1 mile south of Siebel Center, at the corner of Goodwin Ave and Gregory Dr).
    • The midterm will cover all the course material up through today's lecture: prerequisite material, recursion, divide and conquer, backtracking, dynamic programming, greedy algorithms, and randomized algorithms. There will be at most one problem on greedy and/or randomized algorithms; see Homework 3½. At least one problem will be taken directly from the head-banging sessions. We will almost certainly ask you to prove something by induction.
    • Topics that were not covered in class will not appear on any exam, even if they appear in the notes. For example, there will be no questions on Fast Fourier transforms or matroid optimization.
    • Many old exams are available. However, CS 473 covers a slightly different set of material each semester, in slightly differet order and/or depth, so many old exams include questions on topics we have not covered (or will not cover). Also, most of these old exam problems have been folded into the lecture notes.
    • You may bring one 8½"×11" piece of paper with anything you want written, printed, or photocopied on both sides. Otherwise, the exam is cosed-book, closed-notes, and closed-internet. No non-prescription magnifying devices, and no calculators or other electronic devices allowed. However, you may use a slide rule if you wish.
    • There will be no lecture on February 24. However, Jeff will hold a review session in Siebel 1404 from 11:00 to 12:15. Attendance is entirely optional.
    • If you cannot take the evening exam because of a conflict with another class, please send Jeff email AND talk to Jeff after class this week. The conflict exam will be held during the regular class period (11:00-12:30 on February 24), but in a different room.

February 13:
Homework 2 solutions are available.

February 10:
  • Written solutions for Homework 3 are due next Tuesday, February 17. Problem 1 relies on the HW2 solutions, which will be posted Friday, after the HW2 oral presentations are finished.
  • We missed a small number of students when we made oral homework assignments. Please check Compass today. If you did not get a message from Jeff telling you which homework you are supposed to present, please send Jeff email immediately; we will add you to either the HW3 or HW4 list.

February 5:
Each student has been randomly assigned to give an oral presentation for HW2, HW3, or HW4. To determine which homework you've been assigned to present, log into Compass, go to the page for CS473, and click on the 'Mail' button (just to the left of 'My Grades'). Your inbox should have a message with the subject "HWn oral presentations", where n is either 2, 3, or 4.

Yes, Compass has its own email system. No, there is no way to forward Compass email to your regular email address. Yes, this is incredibly stupid.

February 4: Homework 1 solutions are available.

February 3:
  • Written solutions for Homework 2 are due next Tuesday, February 10. Please read the instructions carefully.

January 28: Homework 0 solutions are available.

January 27:
  • Homework 1 is due next Tuesday, February 3. Groups of up to three people can submit a single common solution.
  • Lecture videos (projector and microphone feed only) will be available on the course web site starting with today's lecture. Links will appear a few hours after each lecture. I will also add links to lecture videos from Fall 2005 (the last time I was recorded) soon.

January 19:
  • Homework 0 is due next Tuesday, January 27, at the beginning of class. LaTeX source is available for students who want to typeset their solutions. You may find my notes on solving recurrences helpful.
  • Tomorrow's lecture is scheduled to start at the same time as a certain wildly popular U. Chicago law professor. If we can figure out how, we will show at least the oath of office before launching into algorithms stuff.
  • Yes, head-banging sessions start this week.

Administrivia

Audience:
CS 473 is intended for undergraduates in computer science and related areas, or graduate students outside computer science interested in building up their algorithmic background. Most graduate students in computer science, including students in the MCS and 5-year BS/MS programs, should take CS 573 instead.

Prerequisites:
Students are 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 weekly homeworks (30% total, lowest score dropped), two midterms (20% each) and a final exam (30%). There will be several opportunities for extra credit, which will be applied after the curve.

Reading material:
There is no required textbook. 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.

However, for students who prefer an actual dead-tree reference, the following recommended textbook is available in local bookstores:

  • Algorithms by Sanjoy Dasgupta, Christos Papadimitriou, and Umesh Vazirani (McGraw-Hill, 2006).

You may also find these textbooks useful:

  • Algorithm Design by Jon Kleinberg and Éva Tardos (Addison-Wesley, 2005).
  • 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.

Newsgroup: class.cs473 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.