CS 573 — Graduate Algorithms — Fall 2010

Lecture: Wed Fri 12:30–1:45, in 218 Ceramics Building

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

Teaching assistant: Alina Ene (ene1@uiuc.edu)
Office hours: Tue 2-3 and Thu 2-3, in the open area outside 3303 Siebel Center

Course information:

Schedule and lecture notes

Announcements

January 11: All solutions have been removed from the course web site.

December 20:
  • All final exams have been graded; grades should be available on Compass. Here is the score distribution:
    Mean±stdev = 38.79±9.25
    A+: 61½ 58
    A:   52 51.8 51½ 50 50 50 48¾ 48½ 48½ 48½ 47¾ 47½ 47½ 47¼
    A-: 45½ 44½ 44½ 44½ 44¼ 44 43½ 40 39¼ 38¾ 38¾
    B+: 38½ 37½ 37½ 35¾ 35½ 35½ 35½ 35 34 34 33¼ 32¾
    B:   29½ 29½ 29 28¾ 28¼ 28 28
    B-: 26 25¾ 25¾ 24¾ 23 21¾
    F:   18½
  • All course grades have been submitted. You should be able to retrieve your course grade online from the registrar within a day or two.

  • Thanks for a great semester! Have a safe and restful winter break.

December 17:

December 14:
  • We have finished grading all homework problems (including regrades). Please email Alina if you are missing grades in Compass, or some of your grades have been incorrectly recorded in Compass.

  • Alina is holding office hours today at 2pm.

December 13:
  • The final exam will be held Tuesday, December 14, from 7pm to 10pm, in 112 Chemistry Annex. The exam will cover everything covered in lecture before Thanksgiving break (no network simplex or approximation by LP rounding), with slightly more emphasis on flows, cuts, and linear programming.

    You may bring two (8½"×11") sheets of paper with anything written, printed, photocopied, on both sides. No other papers, books, or electronic devices can be used. We will provide a list of NP-hard problems.

    If you need to take a conflict exam, you should have already made arrangements with Jeff.

November 30:
  • Homework 4 has been graded. You can pick up your homework during office hours.

November 29:
  • Homework 5 solutions are available.
  • Homework 6 is "due" Wednesday, December 8, but not really. This is practice only, in preparation for the final exam.

November 15:
  • Homework 5 problem 5 has been revised to remove some typos (indicated in red in the new version).
  • Midterm 2 solutions have been revised to include alternate solutions to problems 2 and 5(a).

November 12:
  • Grades for Midterm 2 are now posted on Compass. Here are statistics and very rough letter-grade equivalents:

    • Mean±stdev = 29.11±8.12
    • 12½ ≤ B- ≤ 18 ≤ B ≤ 23½ ≤ B+ ≤ 29 ≤ A- ≤ 34½ ≤ A ≤ 40 ≤ A+

    Here are statistics and rough letter-grade equivalents for both midterms, dropping the 2 lowest problems. Because they account for only 40% of your overall coursework, these are VERY rough predictors of your final course grade.

    • Mean±stdev = 55.95±8.55 (excluding top and bottom outliers)
    • 39 ≤ B- ≤ 44 ≤ B ≤ 50 ≤ B+ ≤ 56 ≤ A- ≤ 62 ≤ A ≤ 73 ≤ A+

    I've already sent email to all students I think are in any danger of failing. If you are concerned about your grade, please talk to me after class this afternoon. The paper drop deadline is this afternoon at 5pm; I will be in my office after 2:30 to sign forms for students who want to drop the course.

November 8:
  • Homework 5 is due Friday, November 19 (just before Thanksgiving break).

November 4:

November 3:
  • Homework 4 solutions are available. Rubrics will be added soon.

  • Midterm 2 will be held this evening from 7pm to 830pm, in Education Building, room 2. (That's roughly one block sounth of David Kinley Hall; please give yourself extra time to get there.) The exam will cover the following topics:
    • Material covered on Midterm 1 (but this won't be the main focus)
    • Greedy algorithms
    • Approximation algorithms
    • Randomized algorithms and data structures (including treaps, skip lists, hashing, and amplification)
    You may bring one (8½"×11") sheet of paper with anything written, printed, photocopied, on both sides; however, you may not bring a microscope. No other papers, books, or electronic devices can be used. We will provide a list of NP-hard problems.

    There will be no lecture this afternoon. However, Jeff will be in the usual lecture room at the usual time to answer any questions.

November 2:
  • Homework 3 has been graded. You can pick up your homework during office hours.

November 1:
  • Jeff will have office hours from 11:30 to 12:30 today instead of 10-11. He will also hold office hours tomorrow afternoon from 2 to 3. Sorry for the last minute notice!

October 26:
  • Problem 4(c) in Homework 4 has been revised; the probability of choosing u should be w(v)/(w(u)+w(v)).
  • The Homework 3 solutions have been revised to fix an off-by-one error in problem 3 ("else if deg(z) > n-5" should be "else if deg(z) > n-6") and to add some more details in problem 1.

October 23:

October 20:
  • Homework 2 has been graded. You can pick up your homework during office hours.

October 19:

October 7:
  • Midterm 1 has been graded; all grades have been posted on Compass. Here is the grade distribution (for all five problems), along with rough letter-grade equivalents. Red and green grades are outliers, which were removed before computing letter-grade cutoffs.
    Sum of all five scores: Mean (±stdev) = 32.15 (±6.71)
    A+ 49 47 46 46 45 45
    A 41.5 40.5 39.5 39.5 38 37.5
    A- 36.5 36 36 35.5 35 34.5 34 34 34 33.5 33 33 33 33 32.5
    B+ 32 32 31 31 31 30 29.78 29.5 29.5 29 28.75 28.5 28.25
    B 27 27 26.5 26.5 26 26 25.25 25 24 24 23.5
    B- 23 22.25 21.5 19.5
    F 14.75 12
    • Means(±stdev) for each problem: 8.11 (±2.79), 2.87 (±2.43), 7.98 (±2.97), 8.26 (±2.56), 4.09 (±3.29)
    • Median for each problem: 10, 3, 9, 9, 3
    • "I don't know"s for each problem: 2, 10, 2, 3, 17

October 1:

September 28:

September 27:
  • Midterm 1 will be held this Wednesday, September 29, from 7pm to 830pm, in David Kinley Hall, rooms 119 and 123. The exam will cover the following topics:
    • Prerequisites (induction, recurrences, basic data structures)
    • NP-hardness
    • Divide and conquer
    • Backtracking
    • Dynamic programming (but not the advanced tricks)
    You may bring one (8½"×11") sheet of paper with anything written, printed, photocopied, on both sides; however, you may not bring a microscope. No other papers, books, or electronic devices can be used. We will provide a list of NP-hard problems.

    There will be no lecture Wednesday afternoon. However, Jeff will be in the usual lecture room at the usual time to answer any questions.

September 26:
  • Homework 1 has been graded. You can pick up your homework during office hours.

September 15:

September 13:
  • Homework 2 is due Monday, September 27.

  • And don't forget: Homework 1 is due today at 5pm. Submit your homework in the drop boxes in the basement of Siebel.

September 5:
  • Homework 0 solutions have been revised; the original solution to problem 5(c) was incorrect. Everybody now gets full credit for problem 5(c); your actual scores on problem 5(c) will be awarded as extra credit. Also, two students will be awarded extra credit for reporting the bug. And yes, this is the standard response to finding a bug in the homework solutions.

September 3:

September 1:
  • Homework 1 is due next Friday, September 10 Monday, September 13.

August 25:
  • A revision of Homework 0 is available, which addresses two issues:
    • Removed a parity issue in Problem 3 that maked the problem more difficult. We will accept solutions to either version of the problem.
    • Revised problem 5 to clarify the experiment: Prof. Jay is running a while loop.
  • A new version of the LaTeX source is available; the previous version was missing two files.

August 25: