# CS 473: Algorithms (Fall 2022)

Instructor
Jeff Erickson (jeffe)
Assistants
Farouk Harb
Robert Andrews
Pooja Kulkarni
Benjamin John
Haoxiang Sun
Tyler Gall
Regular weekly schedule

### Announcements

November 18
• Solutions for Homework 9 are available.
• "Homework 10" is available. This is a small collection of practice problems, some of which draw on material from earlier in the course. We will release solutions on Monday, December 5.
November 17
• Regrade requests can be submitted directly on Gradescope until Friday, December 16.
• Here is a distribution of midterm scores and predicted course grades so far.
• For each student, we computed an overall average = 30% Homeworks 0–7 (with lowest 6 scores dropped) + 70% Midterm 1. The orange curve shows these overall averages in sorted order. Those averages were used to compute the vertical letter-grade boundaries, following the advertised fixed cutoffs.
• The blue dots show the corresponding midterm scores for each student. Dots further above the orange curve indicate students with lower homework averages. Note that the two plots are on different scales.

• Here is a scatterplot of Midterm 1 scores versus midterm 2 scores, with letter-grad cutoffs assuming a 90% homework average.

• At least for now, there is no curve. As with Midterm 1, the overall score distibution for Midterm 2 is slightly higher than in past (pre-pandemic) semesters of CS 473. Thus, we expect to use the advertised fixed cutoffs to compute course grades.

Assuming a homework average of 90% (the class median), a total midterm score of 63 or higher is consistent with an A in the course, a total midterm score between 42 and 62 is consistent with a B, and a midterm score between 22 and 42 is consistent with a C.

• Please keep in mind that this is only a rough prediction of your final course grades, based on less than a third of the overall work. Past experience suggests that most students‘ final course grades will be within half a letter grade of these estimates, but there are a few differences of a letter grades or more (in either directions) every semester.
November 10
Solutions for Homework 8 are available. (Whew!)
November 9
Homework 9 is due next Thursday, November 17, at 9pm. This will be the last graded homework of the semester.
November 2
Homework 8 is due next Wednesday, November 9, at 9pm.
October 28
Solutions for Midterm 2 are available.
October 26
Solutions for Homework 7 are available.
October 25
Midterm 2 will be held next Monday, October 31, from 7pm to 9pm, in 141 Loomis.
• The exam will cover the same material as Homeworks 4, 5, 6, and 7: discrete probability, randomized algorithms, hashing, string matching, and maximum flows/minimum cuts, including material from today's lecture. The exam will assume familiarity with relevant prerequisite material, especially basic graph algorithms, but the main emphasis will be on material from this course.
• There will be a conflict exam on Tuesday, November 1, for students who cannot take the regular exam for any of the reasons outlined in the student code. To register for the conflict exam, please fill out this form by Friday, October 28.
• Instead of the regular lecture, there will be an optional review session on Thursday, October 27; Jeff will walk through a sample exam.
• Please read and understand the exam policies. In particular, you are allowed to being one double-sided handwritten cheat sheet to the exam.
• Lots of study materials are available:
• Jeff's textbook and notes, especially chapters/notes linked from the schedule page.
• Jeff's past CS 473 exams can be found in his course materials archive. (Topical coverage varies from semester to semester; you can safely ignore past midterm questions on material we have not covered.)
• Other useful resources, including lecture notes, lecture videos, slides, homeworks, exams, and other course materials from other CS 473 instructors and from comparable algorithms courses elsewhere.
• There will be no question 3.
October 21
Solutions for Homework 6 are available. (Sorry for the delay.)
October 18
Homework 7 is due next Tuesday, October 25, at 9pm. This is the last homework before Midterm 2.
October 12
Solutions for Homework 5 are available.
October 11
Homework 6 is due next Tuesday, October 18, at 9pm. This one has only two problems.
October 9
• Regrade requests can be submitted directly on Gradescope until Monday, October 23.
• Here is a distribution of midterm scores and predicted course grades so far.
• For each student, we computed an overall average = 30% Homeworks 0–3 (with lowest 3 scores dropped) + 70% Midterm 1. The orange curve shows these overall averages in sorted order, omiyying a small handful of students with averages below 40%. Those averages were used to compute the vertical letter-grade boundaries, following the advertised fixed cutoffs.
• The blue dots show the corresponding midterm scores for each student. Dots further above the orange curve indicate students with lower homework averages. Note that the two plots are on different scales.

• At least for now, there is no curve. Despite lower average scores on problem 3, the overall score distibution for Midterm 1 is slightly higher than in past (pre-pandemic) semesters of CS 473. Thus, we expect to use the advertised fixed cutoffs to compute course grades.

Assuming a homework average of 96% (the class median), a midterm score between 30 and 40 is consistent with an A in the course, a midterm score between 20 and 30 is consistent with a B, and a midterm score between 10 and 20 is consistent with a C.

• Please keep in mind that this is an extremely rough prediction of your final course grades, based on less than a third of the overall work. Past experience suggests that most students‘ final course grades will be within one letter grade of these estimates, but differences of 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.
• Students are strongly encouraged to talk with Jeff before dropping the class. Students who are thinking of dropping the class and/or are seriously concerned about their midterm performance will have priority will have priority over others during Jeff's office hours this week.
October 5
Solutions for Homework 4 are available.
October 4
Homework 5 is due next Tuesday, October 11, at 9pm.
September 28
Solutions for Midterm 1 are available.
September 27
Homework 4 is due next Tuesday, October 4, at 9pm.
September 22
Solutions for Homework 3 have been updated to include a faster solution to problem 1 (found by a student).
September 21
Solutions for Homework 3 are available. (Yes, that really is the best solution we found for problem 1.)
September 20
Midterm 1 will be held next Monday, September 26, from 7pm to 9pm, in 141 Loomis.
• The exam will cover the same material as Homeworks 0, 1, 2, and 3: prerequisite material, divide-and-conquer algorithms, fast Fourier transforms, and dynamic programming. Nothing on the exam will require more advanced dynamic programming techinques (divide-and-conquer optimization, monotonicity, or SMAWK).
• There will be a conflict exam on Tuesday, September 27, for students who cannot take the regular exam for any of the reasons outlined in the student code. To register for the conflict exam, please fill out this form by Friday, September 23.
• Instead of the regular lecture, there will be an optional review session on Thursday, September 22; Jeff will walk through a sample exam.
• Please read and understand the exam policies. In particular, you are allowed to being one double-sided handwritten cheat sheet to the exam.
• Lots of study materials are available:
September 14
Solutions for Homework 2 are available.
September 13
• Homework 3 is due next Tuesday, September 20, at 9pm. This is the last homework before Midterm 1.
September 7
Solutions for Homework 1 are available. (Problem 3 was fun!)
September 6
Homework 2 is due next Tuesday, September 13, at 9pm.
August 30
Solutions for Homework 0 are available.
August 29
Homework 1 is due next Tuesday, September 6, 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 (if any) on Gradescope. Please remember to list all group members at the top of the first page of each submission. Finally, please see the academic integrity policies for group homework.

August 22
Homework 0 and the LaTeX homework template are actually available now.
August 9
• Welcome! We're working hard to get everything set up before the semester begins. Meanwhile, you may notice broken links and/or text that refers to previous semesters.
• The first lecture is Tuesday, August 23.
• Homework 0 is due the following Tuesday, August 30 at 9pm. Each student must submit their own individual solutions on Gradescope. A LaTeX template for homework solutions is available.

### Regular weekly schedule

Lectures
Tue Thu 2:00–3:15, 2079 Natural History Building
Office hours:
Almost all in 3300G Siebel (the open area near 3304). These times are likely to change during the first few weeks of the semester; please watch for announcements on Ed Discussion.

 Jeff Wed 4–5, Fri 11–12 (on Zoom), and Fri 3–4 Farouk Mon 11-12 and 1–2 Haoxiang Wed 1–2 Pooja Fri 1–3 Robert Mon 2-3 and Thu 3:30–4:30 Tyler Mon 12–1 Monday Farouk 11-12, Tyler 12–1, Farouk 1–2, Robert 2–3 Tuesday — Wednesday Haoxiang 1–2, Jeff 4–5 Thursday Robert 3:30–4:30 Friday Jeff 11–12 (on Zoom), Pooja 1–3, Jeff 3–4
Homework
Due Tuesdays 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