CS 473: Algorithms (Spring 2020)

Instructor
Jeff Erickson (jeffe)
Assistants
Meghan Shanks
Tanvi Bajpai
Yipu Wang
Yuanyuan Qi
Caleb Ju
Rafi Long
Tongchuan Shen
Xiangchen Song
Zhengyao Lin
Administrivia
About this course
Regular weekly schedule
Some stuff you already know


Announcements

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
 F 

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

Lectures
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.
Homework
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