 April 27

Homework 10 solutions are available.
 April 26

Homework 11 is available. This homework will not be graded; however, material covered by this homework may appear ont he final exam. Solutions will be released after class on Tuesday, May 2.
Jeff will distribute ICES forms at the end of class on Thursday, April 28. Please come to at least the last 15 minutes of Thursday's lecture to fill out the forms, even if you have already dropped the class. These forms are your opportunity to offer official feedback on the course, the instructor, and the teaching assistants. Your feedback is extremely important to me and to the department, especially because this revision of the course is still relatively new.
At the last "lecture" on Tuesday, May 2, Jeff will attempt to answer arbitrary questions from the class. We do plan to hold a review session on reading day (Thursday), so please don't limit your questions to final exam material.
The final exam will be held Friday, May 6, 710pm in 100 Gregory Hall.

You may bring two 8½"×11" cheat sheets with anything written, printed, or photocopied on both sides. Otherwise, the exam is closed everything. In particular, no medically unnecessary optical or electronic devices may be used during the exam. We will provide paper; you should bring only your cheat sheets and writing tools. I recommend multiple colors.

The exam will cover the required mateiral on all homeworks throughout the semester. Specifically, in addition to material covered on Midterm 1 and Midterm 2, the exam will cover linear programming, NPhardness, and approximation algorithms (but not SETHbased lower bounds).

Exam questions will be graded using more specific rubrics than the homework. Updated rubrics for NPhardness proofs will be avaiable soon.

We are planning to offer a conflict final exam. Please register for the conflict exam as soon as possible.
We will attempt to schedule the conflict exam to accomodate all students who have another final exam scheduled for May 3 at 7pm, or who have three exams on May 6, as required by the Student Code. Students with exam conflicts should register no later than Tuesday, May 3. We will announce the time and location for the conflict exam on Wednesday, May 4.
Once the conflict exam is scheduled, it will be open to all students, regardless of whether they have a conflict. All students planning to take the conflict exam must register no later than Thursday, May 5.
 April 22

Homework 9 solutions are available. Sorry for the delay.
 April 21

Here is the distribution of scores for Midterm 2, excluding any extra credit points from problem 4. Lettergrade cutoffs were computed from all students, excluding outliers above 95% and below 25%, as described in the grading policies. (Grade distributions for undergradautes and graduate students were nearly identical.)
A 
40 40 40 40 39 39 39 39 38 38 37 37 37 37 36 36 35 35 34 33½ 33½ 33½ 33 33 33 33 32¼ 32 32 32 32 32 32 31½ 31 31 31 31

B 
30 30 30 30 30 29¾ 29½ 29½ 29 29 29 28 28 27½ 27½ 27 27 27 26¾ 26½ 26½ 26 26 26 26 26 25¾ 25½ 25½ 25 25 25 25 25 24½ 24 23¼ 22¾ 22¾ 22½

C 
22¼ 22 21¾ 21½ 21½ 21 21 19½ 19 19 18½ 18¼ 18¼ 18 17½ 16 16 15½ 14½ 13 12¼ 11¾

F 
9 8¼

And here is the distribution of combined exam scores, for all students who took both midterms, again excluding extra credit points. Again, lettergrade cutoffs were computed from all students, excluding outliers above 95% and below 25%, as described in the grading policies.
A 
79 78 78 78 77.5 77 75½
75½
75
75
74
72
72
72
71½
71
71
71
69½
69
69
69
68
68
68
67½
67½
67½
67
66½
66
66
66
65½
65½

B 
65¼
65¼
65
63½
63½
63
62½
62½
62½
62¼
62
61½
61½
61
61
60¾
60¾
60¼
59
59
59
59
59
57½
57½
57½
56¾
56½
56¼
55½
55
55
53½
53½
53½
53
52¾
51¾
51¼
49½
49¼

C 
48
47½
47½
47½
46¾
46½
46½
46½
46
45¾
44½
44
44
42¾
41½
41
40¼
36
32

D 
31
30½
26¾
25¼
24½
24¼

Please keep in mind that these letter grades are extremely rough predictions, based on only 40% of your overall coursework. Based on past experience (in other algorithms courses), we expect most students' final course grades to be within one letter grade of these estimates, but differences of up to a full letter grade (in either direction) are still possible.
 April 21

Midterm 2 has been graded, and grades are available on Moodle. You can retrieve your exams either after class today, or during office hoursnext week. Here are the averages and means for the four problems. (Scores for problem 4 exclude extra credit points, and overall averages exclude outliers.) We will report the overall grade distribution shortly.
Problem 
 1  2  3  4  sum

Mean 
 6.74  4.75  7.27  8.81  26.70

Stdev 
 2.59  3.43  2.45  1.75  6.20

 April 19

Homework 10 is due Tuesday, April 26. LaTeX source for Homework 10 is available. This is the last graded homework of the semester.
 April 15

Due to an unavoidable scheduling conflict, our regular lecture on April 26 will be held in 217 Noyes instead of the usual lecture room.
 April 13

Homework 8 solutions are available.
 April 12

Homework 9 is due Tuesday, April 19. LaTeX source for Homework 9 is available.
 April 11

Homework 8 has been revised to include a rubric for linear prorgamming problems (Short version: Clarity over formality, English descriptions for everything, proof of correctness) and to correct a bug in problem 1(c).
 April 7

Solutions and tentative rubrics for Midterm 2 are available.
 April 6

Homework 8 is due Tuesday, April 12. LaTeX source for Homework 8 is available.
 April 5
 The conflict exam for Midterm 2 will be held from 3 to 5 tomorrow in 2102 Siebel. If you are planning to take the conflict exam, please register by 5pm today. If you registered for the conflict exam but indicated that you are not available from 3 to 5 tomorrow, I will contact you directly to make other arrangements.
 March 30

All regrade requests for Midterm 1 have been processed. I will bring the regraded exams to class this afternoon; after today, you can pick them up in office hours.
Homework 7 solutions are available.
Midterm 2 will be held Tuesday, April 5, from 7pm to 9pm.

In accordance with university policy for evening exams, there will be no lecture that day, but there will be an optional review session.
 Please go to the following rooms to take the exam, based the first letter of your last name.
 A–G: 119 MSEB
 H–O: 103 Transportation
 P–Z: 112 Transportation

You may bring one 8½"×11" cheat sheet with anything written, printed, or photocopied on both sides. Otherwise, the exam is closed everything. In particular, no medically unnecessary optical or electronic devices may be used during the exam. We will provide paper; you should bring only your cheat sheets and writing tools. I recommend multiple colors.

The exam will cover the same material as the required problems in homeworks 4–7 — tail inequalities, hashing, streaming, maximum flows, and minimum cuts (but not minimumcost flows or linear programming) — as well as any necessary prerequisite material (for exmaple, elementary graph algorithms used to compute maximum flows). The exam will have four problems, roughly one for each homework, each worth 10 points. You may want to look at past exams, including from CS 473 last spring (especially midterm 2 and the final exam), as well as the exercises in the lecture notes.

Exam questions will be graded using more specific rubrics than the homework. Standard rubrics for graph reduction problems are available.

We will offer a conflict exam on Wednesday, April 6. Please register for the conflict exam as soon as possible. We will announce the time of the conflict on Monday, April 4. We will do our best to schedule the exam at a time that accommodates everyone with a legitimate conflict, but anyone else is welcome to take the conflict exam at the same time.
 March 17

Homework 6 solutions are available.
 March 15

Homework 7 is due Tuesday, March 29 (after spring break). LaTeX source for Homework 7 is available. This is the last homework before Midterm 2.
 March 9

Homework 5 solutions are available.
 March 8

Homework 6 is due next Tuesday, March 15. LaTeX source for Homework 6 is available (except for the included figure).
 March 8

We have regraded two problems on Midterm 1. The posted rubric for dynamic programming problems specifies an automatic zero if the English description of the underlying recrusive function is missing; the same requirement was announced in Homework 1. We originally graded problems 2 and 4 with this penalty in full force.
However, a review of past homeworks revealed that this requirement was not consistently enforced in grading HW1 and HW2. Applying it in full force for the first time on an exam would be too severe. We regraded those problems with a 3point penalty for omitting the English decription. The midterm solutions have been updated to reflect the modified rubric. This regrade affected 16 students.
Future homeworks and exams will apply the original rubric.
Here are the new midterm scores; all grades have been updated on Moodle. When we compute final course grades, we will use the original midterm 1 scores to determine lettergrade boundaries, but the new scores to determine individual letter grades.
A 
39 39 39 39 39 38½ 38½ 38½ 38 38 38 38 38 38 38 38 38
37½ 37 37 37 36½ 36 36 36 36 36 35½ 35½ 35½ 35½ 35 34½ 34½ 34¼ 34 34 34 34 34 34 33½ 33 33 33 33 32½ 32½ 32

B 
31½ 31¼ 31 31 31 31 31 30½ 30½ 30¼ 30 30 30 29½ 29 29 29 29 28¼ 28 28 28 27¾ 27 27 27 27 27 26½ 26½ 26¼ 26 25½ 25 25 25 23½ 23¼ 23 22

C 
21¾ 21½ 21 21 19 19 18¾ 18 17½ 16¼ 16 15½ 15 13½ 13¼ 13 13 12¾ 12½ 11¾

F 
10

 March 4

Midterm 1 has been graded, and preliminary grades are available on Moodle. You can retrieve your exams either during office hours on Monday or before/after class on Tuesday. (We still need to do some lastminute administrivia.) Please carefully doublecheck your exam to verify that your scores have been recorded correctly.
Here is the distribution of scores, excluding any extra credit points from problem 3. Overall statistics and lettergrade cutoffs were computed from the undergraduate scores, excluding outliers above 95% and below 25%, as described in the grading policies. (The overall average for graduate students was slightly higher.) Individual problem stats include everyone.
Please keep in mind that these letter grades are extremely rough predictions, based on only 20% of your overall coursework. Based on past experience (in other algorithms courses), we expect most students' final course grades to be within one letter grade of these estimates, but differences of up to a full letter grade (in either direction) are fairly common.
A 
39 39 39 39 39 38½ 38½ 38½ 38 38 38 38 38 38 38 38 38
37½ 37 37 37 36½ 36 36 36 36 36 35½ 35½ 35½ 35½ 35 34½ 34½ 34¼ 34 34 34 34 34 34 33½ 33 33 33 33 32½ 32½ 32

B 
31½ 31¼ 31 31 31 31 31 30½ 30½ 30¼ 30 30 30 29½ 29 29 29 29 28¼ 28 28 27¾ 27 27 27 26½ 26 25 25 25 24½ 24 23½ 22 22

C 
21½ 20½ 19¼ 19 18¾ 18½ 16¼ 16 16 15½ 15 15 15 15 14 13½ 13¼ 13 13 13 12¾ 12¾ 12½ 11¾ 10¾

F 
10 10

Problem 
 1  2  3  4  sum

Mean 
 7.66  4.85  8.37  6.01  26.19

Stdev 
 1.54  3.17  2.09  4.07  8.48

 March 2

Homework 4 solutions are available.
 February 29

Homework 5 is due next Tuesday, March 8. LaTeX source for Homework 5 is available.
 February 26

Solutions and tentative rubrics for Midterm 1 are available.
 February 24

The conflict exam this afternoon is in 4403 Siebel.
 February 23

Homework 4 is due next Tuesday, March 1. LaTeX source for Homework 4 is available.
 February 22

As announced in class, Midterm 1 will be held tomorrow, Tuesday, February 23, from 7pm to 9pm.
 Please go to the following rooms, based the first letter of your last name.
 A–G: 119 MSEB
 H–O: 103 Transportation
 P–Z: 112 Transportation

You may bring one 8½"×11" cheat sheet with anything written, printed, or photocopied on both sides. Otherwise, the exam is closed everything. In particular, no medically unnecessary optical or electronic devices may be used during the exam. We will provide paper; you should bring only your cheat sheets and writing tools. I recommend multiple colors.

The exam will cover the same material as the required problems in homeworks 0–3: Prerequisites, dynamic programming (but not more advanced techniques like SMAWK), and elementary randomized algorithms (but not hashing). The exam will have four problems, roughly one for each homework, each worth 10 points.

Exam questions will be graded using more specific rubrics than the homework. Standard rubrics for induction proofs and dynamic programming algorithms are available.

The conflict exam will be held Wednesday, February 24, from 3pm to 5pm. If you have already registered for the conflict exam, I will send you email later by Tuesday with the location.
 February 17

Homework 3 solutions are available.
 February 16

Due to an unavoidable scheduling conflict, next Tuesday's review session will be held in 217 Noyes Lab instead of the usual lecture room.
 February 10

Homework 2 solutions are available.
 February 7
 Homework 3 is due Tuesday, February 16 at 8pm. LaTeX source for Homework 3 (without the pdf figure) is available. This is the last homework before Midterm 1.
Midterm 1 will be held Tuesday, February 23 from 7pm to 9pm. In accordance with university policy for evening exams, there will be no lecture that day, but there will be an optional review session. More information about the exam will be avilaable shortly.
We will offer a conflict exam on Wednesday, February 24. Please register for the conflict exam no later than Thursday, February 18. We will announce the time of the conflict no later Monday, February 22. We will do our best to schedule the exam at a time that accommodates everyone with a legitimate conflict, but anyone else is welcome to take the conflict exam at the same time.
 February 3

Homework 1 solutions are available.
 February 2
 Homework 2 is due Tuesday, February 9 at 8pm. LaTeX source for Homework 2 is available. Yes, there are only two problems.
 January 27
 Homework 1 has been revised to reflect the updated submission deadline (8pm instead of 5pm), to include directions on submitting group solutions, and to give more information about what we want to see in a dynamic programming solution. The actual problems have not changed.
Homework 0 solutions are available.
Jeff's regular Wednesday office hours are from 4:00 to 5:00, starting today.
 January 26
 Homework 1 is due Tuesday, February 2 at
5pm 8pm. LaTeX source for Homework 1 is available. For this and all future homeworks, groups of up to three students can submit joint solutions for each problem. Please read the academic integrity policies about group work.
 January 24
 A LaTeX template for homework solutions is now (finally) available.
 January 23
 Homework 0 has been revised to clarify that problem 2 does not require a proof of correctness.
Incidentally, there have been several recent breakthroughs on problem 2(b), which are well beyond the scope of this class: Grønlund and Pettie in 2014, Chan and Lowenstein in 2015, and Gold and Sharir in December 2015. (For somewhat older results, see Erickson 1999.) An algorithm that runs in O(n^{1.999…9}) time (for some finite number of 9's) would be a major breakthrough, easily worthy of a PhD thesis, if not tenure.
Video for Thursday's lecture has been successfully posted to both MediaSpace and Echo360. Feeback on both platforms is welcome; I expect to converge to just one in the next few weeks.
 January 21
 Sorry, I screwed up on Tuesday and lost the video. Hopefully I'll have the kinks worked out of the system this afternoon.
Everyone's tentative office hours have been posted. Jeff is holding office hours this Friday 11–12 and 3–4; regular weekly office hours start next Monday. Most office hours will be held in the open area outside Jeff's office (3304 Siebel), but late Monday office hours (the ones closest to the homework deadline) will be held in a separate dedicated classroom: 214 Ceramics.
 January 19

Homework 0 is due next Tuesday, January 26, at 5pm. Solutions must be submitted electrnoically, as one PDF file per problem, via Moodle. A LaTeX solution template will be available Real Soon Now.
If you are registered, you should already be enrolled on the course Moodle site. If not, you can enroll yourself with the code CS473
.
You can also access the course Piazza site using the access code CS473
. You can enroll using any email address you like, even if you are not officially registered.
The initial enrollment of 140 students includes 95 undergraduates (= 81 CS majors + 14 others = 77 seniors + 18 juniors) and 45 graduate students (= 26 computer science + 19 others = 15 PhD + 23 MS + 7 MCS).
 January 13

Welcome! We're working hard to get everything set up here before the semester begins. Meanwhile, you may notice a few broken links or references to previous courses. Stay tuned!
If you are graduate student in CS or a related area: You're in the right place. This class satisfies all degree requirements and program of study requirements for either CS 473 and CS 573.