CS 473 - Undergraduate Algorithms - Spring 2010

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

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

Instructor: Jeff Erickson (jeffe@illinois.edu), 3303 Siebel Center
Office hours: Monday 10-11 in the open area outside 3303 Siebel Center
Administrative assistant: Elaine Wilson, 3229 Siebel Center

Teaching assistants:

Grader: Yan Chuan Sim

Most common links:

Exam dates:
  • Midterm 1: February 18 (7-9pm; DCL 1310, MEB 153, and MEB 253)
  • Midterm 2: April 8 (7-9pm, MSEB 100)
  • Final exam: May 14 (1:30-4:30, 1404 Siebel and 1320 DCL)
    • Conflict final: May 11 (7pm-10pm, 2405 Siebel)
    • Makeup final: by arrangement

Course policies:

Other stuff:

Announcements

August 3:
All solutions have been removed form the course web site.

May 18:
  • All course grades have been submitted. You should be able to retrieve your grade online from the registrar within a day or two. Thanks for a great semester, and have a great summer!

  • Solutions to the final exam are available.

May 17:
The final exam has been graded. Scores are available on Compass. Here is the grade distribution. Green scores are 95% or higher, and red scores are 25% or lower; those outliers were excluded when computing statistics and cutoffs. Please keep in mind that the letter grade cutoffs are only for the final exam and are thus essentially meaningless; your course grade may be significantly higher or lower.

  • Sum of all 7 final exam scores: Mean (±stdev) = 39.68 (±12.81)
    A+ 68 64.5 64 63 62 61.5
    A 60.5 60.25 60 60 60 60 59.25 59
    A- 56.75 56 55 55 54.5 54 54 53.5 53.5
    B+ 52.25 52 52 51 51 50.75 50.25 50
    B 47 46.5 44.75 44.5 44.5
    B- 43 42.75 42.5 42 42 41.75 41.5 41.5 41.5 41.25 40.5 40.5
    C+ 39.5 39.5 39.5 39 38.25 38 37.75 37.75 37.75 37.5 37.5 37.5 37 35.75 35.75 35.5
    C 35 35 33.75 32 32 31.5 31.5 31.25
    C- 30 30 29.5 29.5 29.5 29.25 28.25 28 28 28 27.5 27.25 27 27
    D+ 26.5 26.5 25.5 25.5 25.5 25 24.5 24 24 23.75 23 22.75
    D 22.5 22.25 20.5 20.25 20 19.25
    D- 18
    F 17.5 15 14 12.25 11 11 10.75

May 10:
  • Office hours this week, all in the open area outside 3303 Siebel Center
    • Jeff: Monday 10-11, Tuesday 11-12:30, Thursday 11-12:30
    • David: Monday 2-3, Wednesday 2-3
    • Kyle: Monday 3-4, Thursday 2-3 (but no Friday 2-3)
    • Rachit: Wednesday 11-12, Thursday 4-5

  • The final exam will be given this Friday, May 14, from 1:30pm to 4:30pm in 1404 Siebel Center and 1320 DCL. Please flip a coin to determine which room you should go to. (If too many people show up at one room, we'll send them to the other.) The conflict final will be held on Tuesday, May 11, from 7pm to 10pm, in 2405 Siebel; everyone who needs to take the conflict exam should have registered already.

    The final exam will cover all course material covered during the semester, with slightly more emphasis on the material covered since Midterm 2: maximum flows and minimum cuts, lower bounds, and NP-hardness. Topics that were not covered either in class or in homework will not appear on any exam, even if they appear in the lecture notes.

    You may bring two 8½"×11" pieces of paper with anything you want written, printed, or photocopied on both sides; otherwise, the exam is closed-everything.

May 6:
  • Jeff will run a review session Saturday, May 8, from 4pm to 6pm, in Siebel 1404.

May 5:

April 30:
  • The conflict final exam will be held Tuesday, May 11, 7-10pm, in Siebel 2405. To register for the conflict exam, please fill out this online form no later than Friday, May 7. If you do not fill out the form, we will assume you plan to take the regular final exam on Friday, May 14.

    Unfortunately, it was impossible to schedule a single conflict exam that would work for everyone. If you need to take the conflict exam, but you already have a conflict on Tuesday May 11 (another final exam, or three exams in 24 hours), please email Jeff immediately with your final exam schedule to make other arrangements.

April 27:
  • Homework 10 is available; this homework is for practice only. There will be at least one NP-hardness problem on the final exam, so working through this homework is strongly recommended. Students/groups are welcome to submit solutions for feedback (but not for credit) in class on May 4, at which point we will post official solutions.

  • Midterm 2 has been graded. Scores are available on Compass. You can pick up your exams either during your discussion section or in office hours. Grade distributions and estimated letter-grade cutoffs are given below, computed in two different ways. In both tables, green scores are above 95%, and red scores are below writing "I don't know" on every page. Those outliers were excluded when computing statistics and cutoffs.

    Please keep in mind that these cutoffs are still only rough predictions, based on only 40% of your overall coursework. Based on past experience, we expect most students' final course grades to be within 2/3 of a letter grade of these estimates.

    • Sum of all five MT2 problem scores: Mean (±stdev) = 30.74 (±7.83)
      A+ 47½ 47 46 46
      A 43½ 43½ 43 42½ 42 42 42
      A- 41 40½ 40½ 40 40 40 39½
      B+ 38½ 38½ 38 38 38 37½ 37½ 37½ 37 36½ 36½ 36½ 36½ 36 36
      B 35½ 35½ 35½ 35 34½ 34 34 33½ 33½
      B- 33 33 32½ 32½ 32½ 31½ 31½ 31½ 31 31
      C+ 30½ 30½ 30 30 29½ 29½ 29½ 29 29 29 29 28¾
      C 28 28 28 27 27 27 26½ 26½ 26 26 25½ 25½ 25½ 25½ 25½
      C- 25 24½ 24 24 23½ 23½ 23 23
      D+ 22 22 22 22 21 21 20½
      D 20 19½ 19½ 19 19 19
      D- 17 16½ 16½ 15½
      F 14½ 13¾ 10½

    • Sum of best 8 scores on both midterms: Mean (±stdev) = 55.11 (±12.18)
      (includes only scores for people who took both midterms)
      A+ 80 79½ 79 77 76¼
      A 75 74½ 73¾ 73 72 71½ 71½ 71½
      A- 70¾ 69½ 69½ 69½ 69 69 69 68¼ 68 67½ 67½ 67½ 67½
      B+ 67¼ 67 67 66½ 66½ 66 65¾ 64¾ 64½ 64 64 63¾ 63½ 63½
      B 63 63 63 62¾ 62½ 61¾ 60½ 60¼ 59½
      B- 59¼ 58½ 58½ 57½ 56½ 56 56 56
      C+ 55 55 54½ 54 53¼ 52¾ 52¼ 52
      C 50½ 49¾ 49¼ 49 49 48½ 48½ 48 47¾ 47¾ 47½
      C- 47 46¾ 46 44 44 43¾
      D+ 43¼ 43¼ 43 43 42½ 42½ 41¾ 41¾ 41¼ 41
      D 39¼ 38¾ 38¼ 37½ 37½ 37¼ 37 36¼ 35½
      D- 34 33¾
      F 26¾ 20¼

April 23:
  • Online ICES forms for CS 473 (and your other CS courses) are now available; please fill them out! This is your chance to give official feedback about the course, the instructor, and the teaching assistants. Each form should take about 5-10 minutes to fill out. If you don't want to fill out the entire form, these three questions are the most important:

    • Rate the instructor's overall teaching effectiveness.
    • Rate the overall quality of this course.
    • What do you suggest to improve the course?

    The first two questions are the actual numerical scores that the administration uses to gauge faculty teaching quality. In short, these two scores are Jeff's grades. Averages for individual courses are used in faculty promotion cases, tenure cases, and salary decisions. Department-wide averages are used by the college and campus administration to guide budget decisions.

    The third question is by far the most useful feedback for future iterations of the class. Please be thorough and brutally honest.

    You should have access to two forms for CS 473: one for the lecture and one for your registered discussion section. Please give your feedback about Jeff in the lecture form, and feedback about the TAs in the section form. If you have specific feedback about individual TAs, please mention them by name in the narrative section at the end.

    The online ICES system closes on reading day, Thursday, May 6. Results of the evaluations will be reported back to Jeff and the TAs in late May or early June, long after grades have been submitted. All feedback is anonymous; the system asks for your NetID only to ensure that you are registered for the class and that you don't fill out the same form twice.

April 22:
  • If you cannot take the regular final exam (Friday, May 14, 1-4pm), please fill out the online survey so that we can schedule a common time for a conflict exam. The conflict exam will be scheduled no later than Wednesday, May 12. Jeff is looking into the legality of holding the conflict over the weekend (either Saturday May 8 or Sunday May 9). (Nope, it's not legal.)

    According to the few people that have already filled out the survey, the day with the fewest conflicts is Friday May 7, followed by Wednesday May 12.

April 20:
  • Homework 9 is due April 27. This will be the last graded homework.

April 13:

April 12:

April 8:

March 30:
  • Homework 7 is due April 6. Groups that presented solutions to HW1 will also present solutions for this homework.

  • Midterm 2 will be given next Thursday, April 8, from 7pm to 9pm, in 100 Materials Science and Engineering Building.

    • The midterm will cover all course material covered before spring break, but primarily focusing on material presented after Midterm 1: randomized algorithms, amortized analysis, graph representations, graph traversal, minimum spanning trees, and single-source shortest paths. At least one problem will be taken directly from the head-banging sessions. We will almost certainly ask you to prove something by induction. Flows and cuts will not be covered on this exam. Topics that were not covered either in class or in homework will not appear on any exam, even if they appear in 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 closed-everything. In particular, do not bring two pieces of paper stapled together.

    • There will be no lecture on April 8. However, Jeff will hold a last-minute review session in Siebel 1404 during the normal lecture period. Attendance is entirely optional.

    • Please contact Jeff by the end of this week (April 2) if you need to take a conflict exam.

March 17:
  • Homework 6 solutions are available.

  • Homework 6.5 has been released. Submitting this homework is optional and worth no credit, but we will provide you feedback if you choose to submit. Homework 7 will be released immediately after spring break.

March 11:
  • Homework 5 solutions are available.

  • Because of the impending spring break, no homework will be assigned next week. However, we will still hold head-banging sessions as usual next week. Homework 7 will be released the Tuesday after break (March 30).

  • Because of overwhelming demand, we are changing the oral presentation schedule slightly. Instead of two parallel sessions on Tuesday and Wednesday, there will be one session on Tuesday and three on Wednesday. All presentation slots are still between 1:30 and 4:00.

March 9:
  • Homework 6 is due March 16. Groups that presented solutions to HW3 will also present solutions for this homework.

  • Please remember that the online drop deadline is this Friday, March 12. Jeff will be on furlough this Friday, so if you want to discuss your grades before the drop deadline, please email soon to arrange a meeting tomorrow or Thursday.

March 4:
  • We have added a slight clarification to Problem 3 of Homework 5. Part (a) asks you to compute some representation of the staircase.

  • Homework 4 solutions are available.

March 2:
  • Homework 5 is due March 9. Groups that presented solutions to HW2 will also present solutions for this homework.

  • Midterm 1 has been graded. Scores are available on Compass. You can pick up your exams either during your discussion section or in office hours. Grade distributions and estimated letter-grade cutoffs are given below, computed in two different ways. In both tables, green scores are above 95%, and red scores are below 25% (equivalent to "I don't know" on every page). Those outliers were excluded when computing statistics and cutoffs.

    Please keep in mind that these cutoffs are very rough predictions, based on only 20% of your overall coursework. Based on past experience, we expect most students' final course grades to be within one letter grade of their MT1 estimates, but differences of up to a full letter grade, either up or down, are fairly common.

    • Sum of all five problem scores: Mean (±stdev) = 29.93 (±8.19)
      A+ 50 48¼ 48 47 45 45
      A 42 42 41¾ 41 41 41
      A- 40½ 40½ 39½ 39½ 38¾ 38¼
      B+ 38 38 38 37¾ 37½ 37½ 37½ 37¼ 37¼ 37 36½ 36½ 36½ 36 35½ 35½ 35½ 35½
      B 35 35 35 35 34½ 34½ 34¼ 34 33½ 33½
      B- 32½ 32½ 32½ 32½ 32¼ 32¼ 31¾ 31¾ 31½ 30½ 30¼ 30¼
      C+ 29¾ 29¾ 29¼ 29¼ 28¼ 28 27½ 27½
      C 27 26¼ 26 26 26 25¾ 25 25 25 24¾ 24¾ 24½ 24½
      C- 24 23¾ 23¼ 22¾ 22¾ 22¼ 22¼ 22¼ 22
      D+ 21¼ 20¾ 20¼ 20 19¾ 19½ 19½ 19
      D 18¼ 18 17 16¾ 16½ 16¼
      D- 16 15¾ 14¾ 14 13¼
      F 12¼ 11¾ 11 9½ 7½ 3¾

    • Sum of best four problem scores: Mean (±stdev) = 26.02 (±6.92)
      A+ 40 40 40 39¼ 39
      A 37 37 36 36 36 36 36 35¾ 35½ 35½ 35¼
      A- 34½ 33½ 33 33
      B+ 32¾ 32¾ 32½ 32½ 32½ 32½ 32¼ 32 32 32 31½ 31½ 31½ 31 31 30¾
      B 30½ 30½ 30¼ 30¼ 30¼ 30 30 30 30 30 30 30 29½ 29½ 29 28¾ 28½ 28½
      B- 28 28 27½ 27¼ 26¾ 26¾ 26¼
      C+ 25¾ 25¾ 25¼ 25 24½ 24½ 24 24 23¾
      C 23½ 23½ 23½ 23¼ 23¼ 23 23 22¾ 22½ 22 22 21¾ 21½
      C- 21¼ 20½ 20¼ 20¼ 19¾ 19½ 19¼
      D+ 19 18½ 18½ 18 18 17
      D 16½ 16½ 16¼ 15¾ 15 14¾ 14¾ 14½
      D- 13¾ 13¼ 12¼
      F 12 11½ 11 9½ 7½ 3¾

February 23:
  • Homework 4 is due March 2. Groups that presented solutions to HW1 will also present solutions for this homework.

February 19:

February 17:
  • Homework 3 solutions are available.

  • Midterm 1 will be given tomorrow night in the following rooms. Please go to the room matching the first letter of your last name:

  • The midterm will cover all the course material through last Tuesday's lecture: prerequisite material (from 173 and 225), recursion, divide and conquer, backtracking, dynamic programming, and greedy algorithms. At least one problem will be taken directly from the head-banging sessions. We will almost certainly ask you to prove something by induction. Randomized algorithms will not be covered on this exam.

  • Topics that were not covered either in class or in homework will not appear on any exam, even if they appear in the lecture notes.

  • Many old exams are available. However, CS 473 covers a slightly different set of material each semester, in slightly different 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 closed-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 tomorrow. However, Jeff will hold a last-minute review session in Siebel 1404 from 11:00 to 12:15. Attendance is entirely optional.

February 10:
  • Homework 2 solutions are available. These include two different solutions for problem 3: the "official" solution written by Rachit and Jeff before HW2 was released, and a much cleaner solution presented by several homework groups.

February 9:
  • Homework 3 is due February 16.

  • The first midterm will be next Thursday, February 18, from 7pm to 9pm. Stay tuned for room assignments. There will be no lecture on the day of the exam, and no homework due the following week.

February 2:
  • Homework 1 solutions are available. Link fixed!

  • All HW0 problems have now been graded; scores are available on Compass. You can retrieve your graded solutions either in discussion section or during any office hours (if nobody is waiting to ask questions).

February 1:
  • Homework 2 is due February 9.

  • A few homework groups assigned to present HW1 still have not signed up for a presentation time. If you are supposed to present HW1, you must reserve a slot before 1:00 Tuesday (when presentations begin). All Wednesday slots are already taken!

January 29:
  • By now you should have received email (at your illinois.edu address) telling you which three homeworks you are expected to present, instead of submitting written solutions. You can also look up your presentation assignment on Compass (under "My Grades"). Please let Jeff know as soon as possible if you did not receive an email, or if different members of your HW1 group were assigned to present different homeworks.

    HW1 presentations will take place next Tuesday and Wednesday, February 2 and 3, from 1:30 to 4:00. Each homework group assigned to present HW1 needs to reserve one 30-minute time slot. Signup sheets for the HW1 presentations have been posted outside Siebel 3303 (not 3304 as previously announced). Please reserve your slot before Tuesday's lecture. In future weeks, the signup sheet will be posted by the Wednesday before homework is due.

  • Everyone on the waiting list that needs 473 to graduate should already have received email from Jeff giving them permission to enroll. If you need to register for 473 to graduate in May and did not receive an email, please contact Jeff as soon as possible. The deadline to add the class electronically is 5pm next Monday, February 1. Unfortunately, there is no more room to add anyone else.

January 26:

January 25:
Homework 1 has been released. It is due Tuesday, February 2 at noon. You can submit written solutions either in class or in the homework drop boxes in the basement of Siebel.

January 24:
LaTeX source for Homework 0 is available. The linked zip file unpacks into a directory containing the main file (hw0.tex), a few necessary packages, and a subdirectory containing the two PDF figures. To compile the homework, you will need a recent TeX distribution that includes pdflatex. (If your distribution is not very recent, you may need to comment out a few clearly marked lines at the top of hw0.tex.)

Good TeX distributions/environments include TeXShop for Mac OS X, TeX Live for Linux (already included in many distributions), and MiKTeX for Windows. More information about LaTeX can be found at the LaTeX project home page, among many other places.

January 22:
Oral homework presentations will begin with HW1, so we need to break the class into presentations clusters quickly. Jeff has prepared an online input survey asking for the names of the other members of your HW1 group. We will assign all members of the each group to the same cluster, so you can present homeworks together. The other members of your group should also fill out the survey, confirming that you are in fact a group. Please fill out the survey no later than Thursday, January 29. Homework clusters will be announced on Friday, January 30.

The survey also contains questions about your prerequisite background. These questions are entirely optional, but they will help us understand and deal with this semester's unexpected spike in enrollment across the entire undergrad CS curriculum.

January 21:
  • Notes on induction proofs and solving recurrences are available; these should be useful for HW0 and beyond.

  • Unfortunately, we cannot accommodate everyone on the waiting list this semester. The waiting list already has an unprecedented 37 names, and in a typical iteration of CS 473, only about 10-15% of the students drop by the end of the semester. I cannot increase enrollment further without creating an unfair burden on the TAs. (The enrollment cap was already raised once, from 100 to 120.) Moreover, I cannot hire another TA; the department has already used up its entire TA budget, and even if we had money, no qualified TAs are available.

    For this reason, I will only give students permission to register late if (1) their name is on the waiting list, (2) they submit HW0, (3) CS 473 is required for their major, and (4) they are graduating in Spring 2010. I will do my best to ensure that all such students eventually get in, but it is highly unlikely that there will be room for anyone else.

January 13:
  • Welcome!

  • The class is full. If you still want/need to register, don't panic. Come to class, put your name on the waiting list, and act like a registered student. In past semesters when 473 has filled up early, everyone who wanted to register has eventually gotten in.

  • Homework 0 is due Tuesday, January 26, at the beginning of class. LaTeX source will be available soon for students who want to typeset their solutions.

  • Jeff will be out of town on Tuesday, January 19 (giving a conference talk). Sariel Har-Peled has graciously volunteered to give the first lecture. Jeff will discuss course policies and administrivia at the next lecture on Thursday.

  • Yes, there will head-banging sessions during the first 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 (discrete mathematics) and CS 225 (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), two midterms (20% each) and a final exam (30%). There will be several opportunities for extra credit, which will be applied after the curve. See the grading policies for more details.

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.

Weekly schedule:
  • Monday:
    • 10:00-11:00 — Jeff's office hours
    • 2:00-3:00 — David's office hours
    • Next week's homework released
  • Tuesday:
    • 11:00-12:15 — Lecture
    • 12:15 — Written homework due
    • 1:30-4:00 — Homework presentations (2 rooms)
    • 5:00-5:50 — Section 1
    • 6:00-6:50 — Section 2
  • Wednesday:
    • 1:30-4:00 — Homework presentations (2 rooms)
    • 4:00 — Homework solutions released
    • 4:00-4:50 — Section 3
    • 5:00-5:50 — Section 4
  • Thursday:
    • 11:00-12:15 — Lecture (except Feb 18 and Apr 8)
    • 4:00-5:00 — Rachit's office hours
    • 7:00-9:00 — Evening midterms (Feb 18 and Apr 8)
  • Friday:
    • 2:00-3:00 — Kyle's office hours