CS473
CS473
Thanks for a great semester!
| Undergraduates | Graduates |
|---|---|
| A+ A+ A+ A A A A A A A A A A A A A A A– 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 B B B– B– B– B– B– B– B– B– B– | B+ B+ B+ B+ B B B B B B– B– |
| C+ C+ C+ C+ C+ C+ C+ C+ C+ C+ C+ C+ C+ C C C C C C– C– C– | |
| D+ D+ D– |
All outstanding exam regrade requests were resolved before computing letter grades; adjusted grades will appear on Banner in another day or two. Future changes to homework or exam grades, if any, will not affect the letter-grade cutoffs. Thus, some students' grades may still go up because of outstanding regrade requests or extra-credit homework.
| A | 59½ 57½ 56½ 55½ 54½ 54½ 54 51½ 51½ 50½ 50 49¼ 49 48¾ 48½ 48½ 48 48 47½ 47 46½ 46 46 45½ 45½ 45½ 45½ 45½ 44¼ 44 44 43½ 43½ |
|---|---|
| B | 42½ 42½ 42 42 42 41½ 41½ 41½ 40½ 40½ 40¼ 40 39½ 39½ 38¾ 37½ 37½ 37 37 36½ 35¾ 35½ 35 35 34½ 34 34 33¾ 33½ 33¼ 33 33 32½ 32½ 31¾ 31¾ 30¾ |
| C | 30 29¾ 29½ 29¼ 29 29 29 28¼ 28 28 28 26 26 25½ 25½ 25¼ 25 25 24¾ 24¼ 24 23½ 23½ 23¼ 22¾ 22½ 21¼ 21 21 20½ 19½ |
| D | 31 30½ 26¾ 25¼ 24½ 24¼ |
| F | 14 |
| Problem | 1 | 2 | 3 | 4 | 5 | 6 | sum | |
|---|---|---|---|---|---|---|---|---|
| Mean | 6.38 | 4.83 | 4.66 | 6.43 | 6.25 | 8.56 | 36.92 | |
| Stdev | 3.52 | 2.98 | 3.39 | 3.26 | 2.07 | 1.52 | 9.76 |
Here are summary statistics for all three exams. The average (± stdev) total exam score, excluding outliers as usual, is 95.12 (± 20.41) out of 140 possible points. While these total exam scores are reasonably good predictors of your final course grades, please keep in mind that they exclude homework averages (which typically increase or decrease grades by at most a third a letter grade) and extra credit points (which can only improve your grade).
| A | 138½ 132½ 131½ 129 128 127¼ 123½ 123 123 122½ 121 119 118½ 118 116½ 116 116 115¾ 115½ 114½ 114 114 113¾ 113 112 112 111½ 111½ 110 110 109 |
|---|---|
| B | 107¾ 107½ 107 107 107 106¼ 106¼ 105¼ 105¼ 103½ 102 101½ 101 100 100 99 98 98 98 97¾ 97 96½ 96 94¾ 94½ 94½ 94 94 92½ 91¾ 91 90¾ 90¾ 90½ 89¾ 89 86½ 86 85 84¼ 83½ 83¼ 82½ 82¼ |
| C | 81 79¼ 78¾ 77½ 77¼ 76 75 74¾ 74½ 73½ 72¾ 72½ 72¼ 71½ 70¾ 70½ 70¼ 70 67¼ 66¾ 65 64½ 51½ 51½ 50¼ 48 |
| D | 44¾ |
Video (part 1, part 2) and slides (pdf, note) from the review session are available.
Exam rubrics for NP-hardness proofs and approximation algorithms are available.
There will be a final-exam review session this Thursday, May 5, 1:00–3:00, in 2405 Siebel. Please bring questions!
Jeff will hold office hours as usual this Wednesday, but not this Friday.
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, 7-10pm in 100 Gregory Hall.
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.
| 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, letter-grade 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.
| 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 |
Homework 7 solutions are available.
Midterm 2 will be held Tuesday, April 5, from 7pm to 9pm.
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 3-point 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 letter-grade 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 |
Here is the distribution of scores, excluding any extra credit points from problem 3. Overall statistics and letter-grade 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 |
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.
Homework 0 solutions are available.
Jeff's regular Wednesday office hours are from 4:00 to 5:00, starting today.
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(n1.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.
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.
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).
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.
| 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 |