- June 14
- All homework and exam solutions have been removed from the course web site.
Thanks to everyone for a great semester!
- May 18
- All course grades have been uploaded to Banner.
- May 16
- The final exam has been graded; scores are available on Moodle. Here is the distribution of scores. Statistics and letter-grade cutoffs exclude outliers above 95% and below 25% and include undergraduates only. (The average score was about 4 points higher for graduate students.)
A |
59
53 46 45½ 45 45 42½ 42 41 40½ 38¼ 37¾ 37½
|
B |
35 35 34½ 32¾ 32 32 31 30¼ 29½ 29 28¾ 28½ 27½ 27¼ 27¼ 26¾ 26¾ 26¼ 25½ 25¼ 25 24¾
|
C |
22¾ 22½ 22¼ 22¼ 19¾ 16½ 15½
|
F |
12
|
Problem |
| 1 | 2 | 3 | 4 | 5 | 6
| sum
|
Mean |
| 5.35 | 4.52 | 2.63 | 5.40 | 5.33 | 5.54
| 29.50
|
Stdev |
| 2.44 | 2.88 | 3.36 | 3.36 | 3.54 | 3.08
| 8.69
|
Overall course grades will be uploaded to Banner very shortly; these will not be recorded on Moodle. I actually computed all course grades twice, first exactly as advertised in the course policies, and then a second time pretending Midterm 1 problem 3 and Final Exam problem 3 did not exist. Each student received the higher of the two resulting letter grades. Here is a tentative letter-grade distribution. (A few students' grades may still go up.) All undergraduates received at least a C–; all graduate students received at least a B.
Undergraduates | Graduates |
A+ A A A A– A– A–
| A+ A+ A+ A A A A A A A A A– A– |
B+ B+ B+ B+ B+ B B B B B B– B–
| B+ B+ B+ B B B– |
C+ C+ C– C– | |
- May 8
- Solutions and tentative rubrics for the final exam are available.
- May 7
- Partial Homework 11 solutions are available.
The final exam will be held Friday, May 8, 7-10pm, in DCL 1310.
-
The exam will cover the entire semester, including minimum cost flows and linear programming (but not network simplex or randomized minimum cuts).
-
You may bring two 8½"×11" cheat sheets, with anything written, printed, or copied on both sides. Otherwise, the exam is closed everything. In particular, no medically unnecessary optimal 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.
-
There are currently no plans for a conflict final exam. If you need to take a confict exam, please send Jeff email as soon as possible. By university rules, if you do have an exam conflict (either two simultaneous exams or three exams in 24 hours), the largest class must offer a conflict exam; as far as I know, nobody has a conflict that can't be resolved by a larger class.
- May 5
- Jeff will hold an optinal review session Thursday 11-12:30 (the usual lecture time) in 1109 Siebel. Please bring questions!
- April 30
- Homework 10 solutions are available.
Homework 11 has a few practice problems on linear programming, for practice only.
Jeff's office hours tomorrow will be 1-2 instead of 11-12.
- April 23
- Midterm 2 has been graded; scores will be uploaded to Moodle shortly. You can retrieve your exams either during office hours or after class today. Please carefully double-check your exam to verify that your scores have been recorded correctly.
Here is the distribution of scores, which includes the 3 points of extra credit for problem 2(d). Statistics and letter-grade cutoffs exclude outliers above 95% and below 25% and include undergraduates only. (The average was about 2 points higher for graduate students.)
A |
39 38½ 38 38 38
37½ 37½ 37½ 37½ 37½ 37 37 36½ 36½ 36½ 36¼ 35¼ 34¾ 34½ 34 33½ 33¼ 33 32¾
|
B |
32 30 29¾ 29 28½ 28¼ 28 28 27 27 26 26 25¾ 25
|
C |
24¼ 24¼ 23½ 23½ 23¼ 20½ 20¼ 20 |
Problem |
| 1 | 2 | 3 | 4 | sum
|
Mean |
| 9.12 | 6.61 | 6.77 | 6.11 | 28.59
|
Stdev |
| 1.70 | 1.83 | 1.96 | 3.52 | 5.71
|
Here are cumulative scores for both midterms, with rough estimates of corresponding letter grades. Totals include all five problems from Midterm 1 and the extra-credit points from Midterm 2. Again, the statistics used to compute letter-grade cutoffs exclude outliers and graduate students; students who missed either midterm are also excluded.
A |
85
83½ 78 78 75¼ 75 75 73 70¾ 70 69¾ 69 67¾
|
B |
63¼ 63¼ 62¼ 61½ 61½ 59½ 58½ 57½ 56¾ 55½ 55½ 55½ 55 54½ 54½ 54¼ 54 53½ 52½ 51 50½ 48¾ 47¾ 46¾ 45½
|
C |
44¾ 43¼ 42½ 39¼ 35¼ 34¾ 28¼
|
Please keep in mind that these letter grades are 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.
- April 22
- Homework 9 solutions are available.
Jeff needs to cancel his 1:00 office hours today. He will hold extra office hours Friday 1-2 (in addition to the usual Friday 11-12) and Monday 1-2 instead. Sorry for the late notice!
- April 21
- Homework 10 is due Tuesday, April 28. This will be the last graded homework.
- April 15
- Homework 9 is due Tuesday, April 21.
- April 14
- Solutions to Midterm 2 are available. Problem 2(d) was broken; everyone will get full credit for that part, as extra credit points.
- April 9
- Homework 8 solutions are available, except for 2(c), which may or may not actually have a solution.
- April 8
- Midterm 2 will will be held Thursday, April 9 from 7pm to 9pm in 269 Everitt Lab.
-
The exam will focus on material covered since Midterm 1 through the middle of last week:
- Randomized algorithms (including treaps and hashing)
- Maximum flows and minimum cuts
The exam will assume familiarity with earlier course material (preprequisites, NP-hardness, approximation, dynamic programming), but there will be no questions specifically about that material. There will be no questions on more advanced dynamic programming techniques.
-
There will be no lecture tomorrow, but Jeff will hold an optional review session in 1310 DCL during the regular lecture period. Please bring questions.
-
As in Midterm 1, you may bring one 8½"×11" cheat sheet, with anything written, printed, or copied on both sides. Otherwise, the exam is closed everything. In particular, no medically unnecessary optimal or electronic devices may be used during the exam. We will provide paper; you should bring only your cheat sheet and writing tools. I recommend multiple colors.
-
There will be a conflict exam on Friday, April 10. If you need to take the conflict exam, please fill out the registration form no later than 3pm tomorrow. I will announce the exact time and location by email tomorrow afternoon.
-
Unfortunately, the elevators in Everitt are out of order; the exam room is accessible only by stairs. Please contact Jeff as soon as possible if you require physical accommodation.
- April 7
- Problem 1(b) on Homework 7 is now an extra credit problem. Sorry about that.
- April 2
- Homework 7 solutions are available.
Homework 6 solutions have been updated to include problem 2(b).
- April 1
- Homework 8 is due next Tuesday, April 7. No, really.
- March 17
- Homework 7 is due March 31, the Tuesday after spring break.
Homework 6 solutions are available.
Jeff's office hours this Friday are cancelled. I'll try to have extra office hours leading up to Midterm 2.
- March 11
- Homework 5 solutions are available.
- March 10
- Homework 6 is due next Tuesday, March 17. Just two problems this time. Once again, please submit your solutions electronically via Moodle.
- March 8
- Midterm 1 has been graded; individual scores are available on Moodle. You can retrieve your exams either during office hours or after class on Tuesday. Please carefully double-check your exam to verify that your scores have been recorded correctly.
Here is the distribution of scores. The statistics and letter-grade cutoffs exclude outliers above 95% and below 25%, but do not distinguish between undergrads and graduate students. (The score distribution was slightly higher for undergraduates.)
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 gade (in either direction) are fairly common.
A |
48 47 47
41¾ 41¾ 40½ 38¾ 37¼ 36 36 34¾ 33½ 32½ 32¼ 31¼
|
B |
31 30¾ 29½ 29¼ 28¾
28½ 28¼ 27½ 27¼ 26¾
25¾ 25¼ 25 24¼ 23
22¾ 22¾ 22¾ 22½ 22
22 22 21
|
C |
20½ 19¾ 19½ 19¼ 19¼
16 16 15¼ 15 15
14½ 13½ 12½
|
F |
11½ 10¼ 7½ 2½ 1¼
|
Problem |
| 1 | 2 | 3 | 4 | 5 | sum
|
Mean |
| 4.96 | 5.46 | 2.89 | 5.23 | 6.74 | 25.85
|
Stdev |
| 2.17 | 3.35 | 3.26 | 3.91 | 2.60 | 7.84
|
- March 3
- Homework 5 is due Tuesday, March 10. Like the previous homework, submit your solutions electronically via Moodle.
- February 25
- Solutions for Midterm 1 are available.
- February 23
- Midterm 1 will be held tomorrow in 269 Everitt Lab. Unfortunately, the elevators in Everitt are out of order; the exam room is accessible only by stairs. Please contact Jeff as soon as possible if you require physical accommodation.
A page listing standard NP-hard problems will be provided on the exam; you are welcome to use any of these problems in your own NP-hardness proofs.
Homework 4 solutions are available.
- February 18
- Homework 3 solutions are available.
Homework 4 has been revised to make problem 1 significantly easier. All changes are indicated in red.
- February 17
-
Midterm 1 will be held Tuesday, February 24 from 7pm to 9pm
-
The exam will cover all material covered through the end of last week:
- NP-hardness
- approximation algorithms
- dynamic programming (excluding the advanced material covered in this week's lectures)
-
There will be no lecture next Tuesday, but Jeff will hold an optinal review session in 1310 DCL during the regular lecture period. Please bring questions.
-
You may bring one 8½"×11" cheat sheet, with anything written, printed, or copied on both sides. Otherwise, the exam is closed everything. In particular, no medically unnecessary optimal or electronic devices may be used during the exam. We will provide paper; you should bring only your cheat sheet and writing tools. I recommend multiple colors.
Homework 4 is also due next Tuesday, February 24. Don't worry, it's short.
Starting with Homework 4, all homework solutions must be submitted electonically via Moodle. We are hopeful that avoiding paper will both speed up grading and make our feedback more accessible.
-
Submissions must be PDF files, one for each numbered problem. Not plain text, not Word, not HTML, not OpenOffice, not LaTeX, not JPEG, not PNG, not RAW. Just PDF.
-
We strongly recommend using LaTeX, but any workflow that produces a PDF file should be fine. If you insist on hand-writing and scanning your homework, please write very neatly, preferably using a pen on white unlined paper, and use a high-quality scanner. Please do not take a picture of your hand-scribbled first-draft solutions with your phone. If we cannot read your submission, we cannot give you credit for your work.
-
For group submissions, exactly one member of the group should submit the solution to each problem. (Different group members are allowed, but not required, to submit solutions for different problems.) Please make sure that every group member's name and NetID appears prominently on the first page of each submission.
-
You can update your solutions as many times as you like before the deadline, so submit early and submit often.
- February 12
-
Homework 2 solutions are available.
I need to remind everyone again about both components of the academic integrity policies.
- Cite your sources. Even sources like "office hours" and "Piazza".
- Write solutions in your own words. Copying another source verbatim is plagiarism even if you cite that source. You are welcome to use any source at your disposal to help figure out solutions, but put them all away before you start writing. If you can't write your solution without referring to another source, you're not ready to start writing.
In particular, please do not submit an uncredited verbatim copy of my homework solutions from a previous semester.
- February 10
-
Homework 3 is due next Tuesday, February 17.
- February 5
-
Homework 1 solutions are available.
- February 3
-
Homework 2 is due next Tuesday, February 10.
- January 30
-
Homework 0 solutions have been revised. Several students submitted solutions to problem 4 that were significantly simpler than mine; I updated my first solution to reflect this improvement.
We will use Moodle to record and transmit homework and exam grades. Everyone officially registered for the course should already be enrolled; if you are not already enrolled, you can enroll yourself with the code CS473++
.
- January 29
-
Homework 0 solutions are available.
To clarify for future homeworks: The "I don't know" policy does not apply to extra credit problems.
- January 27
-
Homework 1 is due next Tuesday, February 3.
- January 23
-
Links to this week's lecture videos are now available. Videos are automatically posted on this page an hour or so after each lecture.
LaTeX source for Homework 0 and LaTeX solution template are available.
Homework 0 has been revised to clarify problem 1. We want algorithms that use as few flips as possible in the worst case, not that use as few flips as possible for the given stack of pancakes. Finding the shortest sequence of flips that sorts a given stack of pancakes is NP-hard.
- January 21
-
Jeff moved his Wednesday office hours to 1-2pm, starting today. (Sorry, I had a scheduling conflict.)
The link to the Piazza site on this page works now.
- January 20
-
Homework 0 is due next Tuesday, January 27, at 5pm. Everyone must submit individual solutions for this homework. For all future homeworks, you can submit solutions in groups of up to three students. We will post a LaTeX solution template soon.
A tentative lecture schedule is available. We have not yet finalized the dates of the midterms, but that should be done by the end of the week. Links to Jeff's lecture notes (for topics where they exist) will be added over the next several days.
- January 16
-
Welcome! We're working hard to get everything set up here before the semester begins. Meanwhile, you may notice a few broken links or pages that refer to previous courses.
If you are an undergraduate CS major who took CS 373 (not CS 374): You need the older version of CS 473, which is being offered for the last time this semester.
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.