CS 473: Algorithms (Spring 2016)

Instructor
Jeff Erickson (jeffe)
Assistants
Konstantinos Koiliaris (koiliar2)
Patrick Lin (plin15)
Yipu Wang (ywang298)
Graders
Sunny Duan (syduan2)
Jingwen Jiang (jjiang18)
Lunan Li (lunanli2)
Dmytro Myronenko (myronen2)
Zhengqi Yang (zyang36)
Administrivia
About this course
Regular weekly schedule
Academic integrity policies
Homework and grading policies
Some stuff you already know


Announcements

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, 7-10pm in 100 Gregory Hall.

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. Letter-grade 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, 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.

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.

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 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

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 last-minute administrivia.) Please carefully double-check 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 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

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.
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(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.

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.


Weekly schedule

Lectures
Tue Thu 3:30–4:45
116 Roger Adams Laboratory
Tentative office hours
In the open area outside 3304 Siebel unless otherwise indicated.
Homework
Electronic submissions due Tuesdays at 8pm, via Moodle.
Homeworks are released Monday, one week before the due date.
Graded homeworks should be available by Thursday, one week after submission.

 
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