CS 473: Algorithms

Recent Announcements

Tue Nov 12

Homework 9 is due next Tuesday, November 19, at 9pm.

Wed Nov 6

Solutions for Midterm 2 are available.
Solutions for Conflict Midterm 2 are available.

Tue Nov 5

Homework 8 is due next Tuesday, November 12, at 9pm.

Fri Nov 1

Practice Midterm 2 solutions and Homework 7 solutions are available.

Thu Oct 31

Here are some extra practice problems to work through some of the main probability concepts we have seen. These are basic exercises but you are highly recommended to work through these with your classmates. No solutions are provided but you can ask on Ed or come to one of the office hours.

Wed Oct 30

Practice Midterm 2 is available. One of the instructors will walk thourgh this exam in the review session tomorrow. Complete solutions will be posted on Friday.

Tue Oct 29

Today's lecture will start at 2:30 instead of 2:00, thanks to an unlucky combination of illness and scheduling conflicts. (The lecture will end at 3:15 as usual.) The lecture schedule page includes links to video and scribbles from the same lecture in Fall 2022; today's abbreviated lecture will also be recorded as usual.

Mon Oct 28

Midterm 2 will be held next Monday, November 4, from 7pm to 9pm.

• The exam will cover all material covered in Homeworks 4, 5, 6, and 7: discrete probabillity (including tail inequalities), randomized algorithms (including treaps and hashing), and maximum flows.
• The exam will be held in exactly the same rooms in the Transportation Building as Midterm 1. Please go to the room that matches the first letter of your last name:
  • A–J: 103 Transportation
  • K–P: 114 Transportation
  • R–V: 112 Transportation
  • W–Z: 101 Transportation
• Please read and understand the exam policies. In particular, you are allowed to bring one double-sided 8½"×11" handwritten cheat sheet to the exam. A list of useful probability definitions and inequalities will be provided with the exam, but we still recommend including this material in your own hand-written cheat sheets.
• Instead of a lecture this Thursday, there will be an optional review session at the usual lecture time and location. Makrand will walk through a sample midterm; we will post the sample midterm here by Wednesday. The review session will be recorded as usual.
• We are offering a conflict exam on Tuesday, November 5. If you cannot attend the regular midterm for any of the reasons outlined in the student code, please fill out this registration form no later than Friday, November 1. On Monday, we will email the precise time and location of the conflict exam to students who have filled out the registration form.
• If you have a DRES accommodation, you are welcome to take the exam at the DRES Testing Accommodation Center either Monday or Tuesday. We strongly recommend scheduling your exam at TAC immediately if you have not done so already.

Sun Oct 27

Homework 6 solutions are available.

Wed Oct 23

Homework 7 is due next Wednesday, October 30, at 9pm. This is the last homework before Midterm 2.

Sun Oct 20

Homework 5 solutions are available.

Wed Oct 16

Homework 6 is due next Wednesday, October 23, at 9pm.

Tue Oct 15

Midterm 1 has been graded. All graded exams are now available on Gradescope.

• Regrade requests can be submitted on Gradescope until Tuesday, October 29.
• Here is a distribution of midterm scores and predicted course grades so far.
  • For each student, we computed an overall average = 36% Homeworks 0–3 (with lowest 2 scores dropped) + 64% Midterm 1. The orange curve shows these overall averages in sorted order, omitting a small handful of students with averages below 36%. 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!
  • This graph only includes students who took the regular exam. (The conflict exam and the regular exam had very similar score distributions.)
  

• We will adjust grades upward at the end of the course. Scores on this midterm were significnalty lower than in previous years, which means this exam was significantly harder than usual. We are planning to make the remaining exams easier. We also expect to raise the letter-grade cutoffs, but specifics will depend on final overall averages.
• 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. Ingoring any future changes to the grade cutoffs, past experience suggests that most students‘ final averages 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 and/or Makrand before dropping the class. Students who are thinking of dropping the class and/or are seriously concerned about their midterm performance will have priority over others during instructor office hours this week.

∞

Earlier announcements