CS 473: Algorithms (Spring 2020)

This course was offered on a Pass/No-Pass basis.
Jeff Erickson (jeffe)
Meghan Shanks
Tanvi Bajpai
Yipu Wang
Yuanyuan Qi
Caleb Ju
Rafi Long
Tongchuan Shen
Xiangchen Song
Zhengyao Lin
About this course
Regular weekly schedule
Some stuff you already know


June 9
All homework and exam solutions have been removed from the web site.
May 20
All final exams have been graded; graded exams are available on Gradescope. I'm happy to announce that every student who took the final exam passed the class by a comfortable margin.

All course "grades" have been submitted to the registrar.

Because of the special circumstances of this exam, the score distribution cannot be trusted to accurately reflect either the difficulty of the exam or the relative performance of any student. 45 students (out of 129) took the final exam. Every student was told in advance the minimum score they needed to pass to class; for a significant majority of the students who took the exam, this minimum score was zero. Nevertheless, for future reference, here is the distrbution of scores.

Problem #1 #2 #3 #4 #5 #6 Total
Mean 7.36 6.14 6.88 5.44 4.83 10.0 40.65
Stdev 3.81 2.91 2.73 3.80 4.10 0.0 10.41

Regrade requests for the final exam will be open until June 10. Regrades cannot effect anyone's class standing; please treat these as requests for clarification and feedback. (We reserve the right to ignore requests focusing on points or other minor details.) We have already responded to all outstanding midterm regrade requests, and we expect to clear the few remaining homework regrades over the next few days.

Finally, I want to publicly thank the TAs and the CAs for all their hard work throughout the semester, especially through the last several weeks of pandemic lockdown!

Have a great summer, and stay safe!

May 13
Solutions and rubrics for the final exam are available, including the broken last problem. 🤦‍♂️
May 5
The final exam will be released on Gradescope Monday, May 11 at 8am CDT, and will be due Tuesday, May 12 at 10pm CDT, with a four-hour time limit.
May 1
ICES Online forms for CS 473 will be available from Monday, May 4 through Friday, May 15. Please take a few minutes to fill them out!
April 30
Homework 10 solutions are available. Part (d) of problem 3 is now extra credit, because Jeff couldn't solve it. We'll update the solutions later if we figure out.
April 23
Homework 9 solutions are available.
April 23
Midterm 2 has been graded; all graded exams are now available on Gradescope.

The following statistics and letter-grade cutoffs were computed after excluding outliers above 95% and below 25%. (Gradescope reports higher averages, because it does not exclude these outliers.) Raw grades listed below have been rounded to the nearest ½ point.

Problem #1 #2 #3 #4 Total
Mean 6.68 6.85 6.51 8.10 28.15
Stdev 2.40 2.89 3.16 2.64 6.04

 A  40 40 40 40 40 39 38½ 38 37½ 37 37 36½ 36½ 36½ 36 36 36 36 35½ 35 35 35 35 35 35 34 34 34 34 34 34 34 33½ 33½ 33 33 33 33 33 33 33 33 32½ 32½
 B  32 32 32 32 31½ 31½ 31½ 31 31 31 31 30 30 30 30 30 29½ 29½ 29 29 29 29 29 29 28½ 28½ 28½ 28½ 28½ 28 28 27½ 27 27 27 27 27 27 27 26 26 26 26 26 25½ 25 25 25
 C  24 24 24 24 24 23½ 23 23 23 23 23 22 22 22 22 21½ 21 20½ 20 20 20 19 19 18 17 17 17
 D  16 15½ 13 13 12
 F  10 7

Here is a scatterplot of exam scores versus submission time.

Here are scores and letter grade cutoffs for the first two midterms combined. Only students who took both midterms are included here; letter grade cutoffs are based on a mean±stdev of 61.22±9.64, which excludes outliers above 95% and below 25%. As usual, raw scores have been rounded to the nearest ½ point.

 A  80 80 78 78 78 78 77 76½ 76½ 76 76 75½ 75½ 75 74½ 74½ 74 73½ 73 73 73 72 71½ 71½ 71 71 71 70½ 70½ 70½ 70 70 70 69½ 69 69 69 68½ 68½ 68½ 68 68
 B  67½ 67 67 67 66½ 66½ 66½ 66½ 66 66 66 65½ 65½ 65½ 65½ 65½ 65 65 64½ 64½ 64 64 63 63 62½ 62½ 62 62 61½ 61½ 61½ 61 61 61 61 61 60½ 60½ 60 60 59½ 59½ 58 58 58 57 57 56½ 56 55½ 55½ 55 54½ 54½ 54 53½
 C  52½ 52½ 52 52 52 52 52 51½ 51 51 50½ 49½ 48½ 45½ 45½ 45½ 44½ 43 40½ 39½
 D  37½ 35 27½
 F  15½

In a normal semester, these letter grades would be rough predictions of overall course grades, based on only 40% of the coursework. Past experience suggests that most students‘ course grades fall within one letter grade of these estimates, but differences of up to half a letter grade (in either direction) are quite common.

Students are strongly encouraged to talk with Jeff before dropping the class. Students with questions or concerns about their performance will have priority in Jeff's office hours on Monday and Thursday; if those times are inconvenient, please send Jeff email.

April 21
Homework 10 is due next Wednesday, April 29 at 9pm. This is the last homework.

Because we cannot meet to distribute paper ICES forms, all courses on campus are being evaluated through ICES Online this semester. The evaluation forms for CS 473 (presumably like every other CS class) will be available from Monday, May 4 through Friday, May 15.

April 18
Homework 9 has been revised to fix two minor bugs in problem 3. (We're only considering graphs without isolated vertices, and I dropped two edges between the upper right vertices.)
April 16
Homework 8 solutions are available.
April 15
Homework 9 is due next Wednesday, April 22 at 9pm.

My petition to offer this class on a Pass/No-Pass basis was approved early this morning. It may take another day or two for the change to be processed and for students to be notified by email from the registrar. Please see Piazza for more information.

April 10
Solutions and rubrics for Midterm 2 are available.

Homework 8 has been updated to fix some minor cosmetic issues.

April 7
Homework 8 is due next Wednesday, April 15 at 9pm.
April 5
Midterm 2 has been posted to Gradescope; the assignment will be available Monday at 8am (CDT).

I have moved the submission deadline from noon to 3pm (CDT) on Wednesday, April 8. You still have 180 minutes to complete the exam.

Since last week, Gradescope has been updated to automatically save/submit your work every few seconds. On the one hand, you should not have to submit anything explicitly; the staff will see only your latest revision before the deadline. On the other hand, if you edit a previously saved solution, your earlier work will be overwritten automatically. Please be careful.

A page of useful formulas is available for your use during the exam. (All these formulas are also provided in the Gradescope assignment.)

April 3
Homework 7 solutions are available.
March 28
Midterm 2 will be released on Gradescope next Monday, April 6, at 8am (CDT) and will be due next Wednesday, April 8 at noon 3pm (CDT). The format of the exam will closely resemble the dry run currently accessible on Gradescope (see @255 and @265). In particular, once you open the exam on Gradescope, you will have 180 minutes to complete it. Please familiarize yourself with the exam interface this week (using the fake "Dry Run" assignment) to avoid any surprises during the actual exam.

The exam will cover the same material as Homeworks 4, 5, 6, and 7:

I will hold an online review session next Friday starting at 3:30 CDT. Just like all other post-COVID lectures, I will post prerecorded videos covering a selection of practice problems. I'm happy to answer questions about either those problems, or other problems that you propose, during the "review session". The review session will be recorded; video will be available on the course web page as soon as I can post it.

You can find study questions in my archive of all past exams ever. Please look through all previous CS 473 exams under "Current (2015) revision", not just past Midterm 2s; we covered randomized algorithms at different times each semester. (Some past exam problems refer to topics like Bloom filters that we did not cover this semester; you can ignore those.) You can also find study problems at the end of each of the lecture notes (or for flows, the textbook chapter) linked from the official lecture schedule.

The exam will be designed to be taken on paper in 120 minutes, with only a one-page cheat sheet. (The extra hour is a buffer to accommodate the unfamiliar exam format and to protect against any unexpected technology issues.) That means each question will be designed to be answerable in 20 minutes from a cold start, under normal exam conditions. tl;dr: The exam will be significantly easier than the homework.

You are welcome to use any of this semester's course materials (textbook, lecture notes, past homework and exam solutions) during the midterm. I will post a formula sheet summarizing several basic facts about probability, including important definitions (expectation, uniformity, universality, independence) and inequalities (Markov, Chebyshev, higher moment, Chernoff) later this week, which you are also welcome to use during the exam. Nevertheless, I strongly recommend writing up your own one-page cheat sheet as a form of studying.

All other materials, including past semester's course materials, other internet resources, other textbooks, and (most importantly) other people, are not permitted. Do not ask questions about the exam during online office hours, or on Piazza. Do not discuss the exam with anyone between Monday at 8am and Wednesday at 3pm. If you need clarification for any exam problem, please post a private message to Piazza, but please remember that the course staff cannot watch Piazza 24-7.

The exam will not be proctored. We are trusting you to take the exam honestly. In particular, we are trusting each of you to take the exam by yourself, with no help from anyone, within the declared time limits. The exam is first and foremost a mechanism to give you honest feedback on your mastery of the course material; please treat it as such. All academic integrity policies are still in place.

March 26
Homework 6 solutions are available.
March 25
Homework 7 is due next Wednesday, April 1 at 9pm. This is the last homework before Midterm 2.
March 24
The campus has extended the drop deadline and the deadline to choose credit/no-credit to April 30. Please see the newly announced Academic Policy Modifications for Spring 2020.
March 23
All class meetings and office hours will be held via Zoom for the rest of the semester. Here are links for all recurring events: Jeff will not be giving live lectures over Zoom. Instead, Jeff will post (new) pre-recorded lecture videos, at least 24 hours before each regular class meeting, and we will use the meetings themselves for questions and discussion of the lecture material. In effect, this turns the regular class meetings into extended "conceptual office hours".

Starting this week we will use Queue@Illinois to queue up questions during office hours and class meetings. All queues will remain open 24-7 (so you can post questions in advance), but the staff will be on-duty to answer only during the scheduled Zoom meetings.

Most office-hour questions should be posted to the public queue, so that other listeners can benefit from the discussion.
π Day
Homework 5 solutions are available.
March 13
Lecture today is cancelled because it's the last 90 minutes before spring break and its nice outside. Jeff will post a video lecture of the material he was planning to cover in class.
March 11
Yesterday I mistakenly posted that Homework 5 would be due after break, which conflused several students. To compensate for this confusion, we are extending the deadline for Homework 5 by 48 hours. Homework 5 is now due Friday, March 13, at 9pm. Sorry for the screwup!
March 10
March 6
Midterm 1 has been graded; all graded exams are now available on Gradescope.

The following statistics and letter-grade cutoffs were computed after excluding "outliers" above 95% and below 25%. (Gradescope reports higher averages, because it does not exclude these outliers.) Raw grades listed below have been rounded to the nearest ½ point.

Problem #1 #2 #3 #4 Total
Mean 8.36 7.72 7.23 7.54 28.90
Stdev 2.04 2.87 2.29 2.46 8.08

 A  40 40 40 40 40 40 40 40 40 39½ 39½ 39½ 39½ 39 39 39 39 39 39 39 38½ 38½ 38½ 38 38 38 38 38 38 38 38 38 38 38 38 37½ 37½ 37½ 37½ 37½ 37½ 37½ 37 37 37 36½ 36½ 36½ 36½ 36½ 36½ 36 36 36 36 35½ 35½ 35½ 35 35 35 35
 B  34½ 34½ 34 34 34 34 34 34 33½ 33½ 33½ 33 33 33 33 33 33 32½ 32½ 32½ 32½ 32½ 32 32 31½ 31½ 31 31 31 30½ 30½ 30½ 30½ 30½ 30½ 30½ 30 30 29½ 29 29 29 28½ 28½ 28½ 28 28 28 28
 C  27 26½ 26½ 26 25½ 25 25 24½ 24 22½ 22½ 22 22 21½ 21½ 21 20
 D  18½ 17½ 15½ 13

Please keep in mind that these letter grades are extremely rough predictions of your final course grade, based on only 20% of your overall coursework. Past experience suggests that most students‘ final course grades will fall within one letter grade of these estimates, but differences of up to a full letter grade (in either direction) are quite common, and there are a few differences of two letter grades or more (in either directions) every semester.

Scores on this exam skewed significantly higher than usual; in particular, the scores above 95% are obviously not really “outliers”. I cannot promise that this trend will repeat itself in future exams.

Students are strongly encouraged to come talk with Jeff before dropping the class. Jeff will be available for extra office hours next Tuesday 3-5 (and if necessary later in the week), specifically for students who are thinking of dropping the class and/or who are seriously concerned about their midterm performance.

March 5
Homework 4 solutions are available.
March 4
Homework 5 is due Wednesday, March 11 at 9pm.
February 28
Our final exam has been scheduled for Monday, May 11, from 1:30 to 4:30.
February 27
Solutions and rubrics for Midterm 1 are available.
February 26
Homework 4 is due Wednesday, March 4 at 9pm.
February 21
Midterm 1 will be held next Tuesday, February 25, from 7pm to 9pm.
February 20
Homework 3 solutions are available.
February 18
Homework 3 has been revised to fix a bug in problem 1, which mirrored an error in last Wednesday's lecture. (The square array A is neither Monge or totally monotone; consider the boundary cases i=j and i=j-1.) Problem 1 is now extra credit.
February 13
Homework 2 solutions are available.
February 12
Homework 3 is due Wednesday, February 19 at 9pm. This is the last homework before Midterm 1.
February 10
Homework 1 solutions are (finally) available.
February 5
Homework 2 is due Wednesday, February 12 at 9pm.
January 30
Homework 0 solutions are available.
January 29
Homework 1 is due Wednesday, February 5 at 9pm.

Starting with this homework, groups of up to three students can submit joint solutions for each problem. For each problem, exactly one member of each group should submit that group's solution and identify the other group members on Gradescope. Please remember to list all group members on the first page of each submission. Finally, please see the academic integrity policies for group homework.

January 28
Starting this week, Tanvi and Jeff will hold weekly conceptual office hours, which are exclusively for help with the concepts and techniques underlying the course material, not for questions about the current homework. Of course, we strongly encourage you to ask conceptual questions in the other office hours as well!

Also, some of our office hours have changed; please see the schedule at the bottom of this page.

January 23
Homework 0 has been revised with the correct due date and to ask for a brief justification in problem 1(a).

A couple of quick clarifications, since the web pages were inconsistent:

January 21

Regular weekly schedule

Wed Fri 3:30–4:45, 1404 Siebel
Office hours:
All in 3300G Siebel (the open area near 3304). These times are likely to change in the first couple of weeks; please watch for announcements on Piazza.
Due Wednesdays at 9pm on Gradescope.
Homeworks are released at least one week before the due date.
Under normal circumstances, graded homework should be returned within 10 days of submission.

Si maintenant vous me donnez une équation que vous aurez choisie à votre gré, et que vous desirez connaître si elle est ou non soluble par radicaux, je n’aurai rien à y faire que de vous indiquer le moyen de répondre à votre question, sans vouloir charger ni moi ni personne de la faire. En un mot les calculs sont impracticables.
Évariste Galois
For every polynomial-time algorithm you have, there is an exponential algorithm that I would rather run.
Alan Perlis
Algorithms are for people who don't know how to buy RAM.
Clay Shirky