CS 473
About this course Course staff Announcements Stuff you already know
Lecture topics (with notes and videos) Homeworks (with solutions) Exams (with solutions) Lectures and office hours
Gradescope (entry code 5KKB3X) MediaSpace Ed Discussion Other useful resources
Homework policies Exam policies Grading policies Accommodations Health and wellness Academic integrity Conduct

Announcements

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.
Set Oct 12
Complete Homework 4 solutions are available. (Sorry.)
Fri Oct 11
Homework 4 solutions are available.
Wed Oct 9
Homework 5 is due next Wednesday, October 16, at 9pm. (Sorry for the late posting.)
Wed Oct 2
Solutions for Midterm 1 are available.
Solutions for Conflict Midterm 1 are available.
Tue Oct 1
Homework 4 is due next Tuesday, October 8, at 9pm.
Fri Sep 27
Practice Midterm 1 solutions are available.
Thu Sep 26
Homework 3 solutions are available.
Wed Sep 25
Practice Midterm 1 is available. Makrand will walk thourgh this exam in the review session tomorrow. Complete solutions will be posted on Friday.

Every homework and exam from Jeff's previous offerings of CS 473 and CS 374 can be found on this page.

Tue Sep 24
Midterm 1 will be held next Monday, September 30, from 7pm to 9pm.
  • The exam will cover all material covered Homeworks 0, 1, 2, and 3: prerequisite material, divide-and-conquer, FFTs and convolutions, backtracking, and dynamic programming. The exam will not cover any material on probability or randomized algorithms.
  • The exam will be held in four different rooms, all on the first floor of the Transportation Building. 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.
  • 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, October 1. 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, September 27. 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.
Thu Sep 19
Homework 2 solutions are available. These solutions include the standard rubric that we will use for all dynamic programming solutions.
Tue Sep 17
Homework 3 is due next Tuesday, September 24, at 9pm. This is the last homework before Midterm 1.
Fri Sep 13
Homework 1 solutions are available.
Tue Sep 10
Homework 2 is due next Tuesday, September 17, at 9pm.
Fri Sep 6
Homework 0 solutions are available.
Tue Sep 3
Homework 1 is due next Tuesday, September 10, at 9pm.

Starting with this homework, teams of up to three students can submit joint solutions.

  • You are responsible for forming your own teams. You may work with people outside your team, as long as your team writes your own solutions and you cite everyone they worked with.
  • Team solutions must represent an honest collaborative effort by all members of the group. (See our academic integrity policies.)
  • For each problem, exactly one member of each homework team should submit the team's solution and identify all other team members on Gradescope.
  • You may submit solutions for each problem multiple times, but only the last submission counts. So we strongly recommend identifying team members for every submission.

Tue Aug 27
  • One new thing we are adding this semester is a mechanism to help students in the class get to know each other. We plan to break the class into groups of about six students each; we will send email next week informing everyone who is in their group. Then we will ask each student to fill out a short survey once a week describing your interaction. If enough students fill out the survey for enough weeks (exact thresholds to be determined), the entire class will get a small amount of extra credit. You are welcome, but not required, to work with your assigned group on homework.
  • The class is full, with 200 on-campus students. A few students have contacted us asking if it's still possible to register. Normally there is a bit of churn at the start of the semester; historically at least a handful of students drop within the first week. We do expect (but cannot guarantee) that everyone who wants to register for the course will get in before the September 9 add deadline.

    If you want to take CS 473, but you have not been able to register:

    • Come to class, starting this afternoon, just as if you were already registered.
    • Submit the homework, just as if you were already registered. (You will need to enroll yourself on Gradescope, with the code 5KKB3X.) In particular, your Homework 0 is due on September 4 even if you are not yet registered.
    • Check Self-Service at least once a day, and register if you can.
    • Please talk with Jeff immediately after class on Thursday, September 5, if you are unable to register by then.

    Finally, if you are a registered student, and you decide that you do not want to take this class, please drop as quickly as possible so that someone else can get in.

Mon Aug 26
Homework 0 is due next Wednesday, September 4, at 9pm.

(Homework is normally due on Tuesday, but Monday, September 2 is a university holiday.)

Wed Aug 21
Please be patient while we finish setting up. Meanwhile, please explore all the links in the menu at the top of this page!