CS 473: Algorithms (Spring 2017)

Instructor
Jeff Erickson (jeffe)
Assistants
Alex Steiger (ajsteig2)
Charles Carlson (ccarlsn2)
Vivek Madan (vmadan2)
Tong Li
Timothy Sanchirico
Phillip Shih
Shunping Xie
Yuhang Yang
Administrivia
About this course
Regular weekly schedule
Academic integrity policies
Homework, exam, and grading policies
Some stuff you already know


Announcements

May 17
May 11
Solutions and tentative rubrics for the final exam are available. We hope to have the final exam graded early next week.
May 7
Overheads from Jeff's review session are available: one sheet per page or 4 sheets per page.
May 6
Jeff will hold a final review session tomorrow afternoon from 2pm to 4pm in 1404 Siebel. Please bring questions.
May 3
April 29
Solutions for Homework 10 are available.
April 26
April 25
Midterm 2 has (finally) been graded, and all graded exams have been released on Gradescope.

Here is the distribution of scores (except for a few minor last-minute changes). All statistics and letter-grade cutoffs were computed after excluding outliers above 95% and below 25%, as described in the grading policies, which is why the overall average is slightly lower than reported on Gradescope. However, these stats include grades from both undergraduates and graduate students; I expect the undergraduates-only cutoffs to be slightly lower.

Scores on this exam were significantly higher than for Midterm 1; in particular, a high percentage of the class earned more than 95% of the points. As a result, letter grades for the individual midterms should not be taken too seriously.

A 40 40 40 40 40 40 39½ 39½ 39½ 39½ 39 39 38½ 38½ 38½ 38½ 38½ 38½ 38 38 38 38 38 38 38 38 38 37½ 37½ 37½ 37½ 37½ 37¼ 37 37 37 37 37 36½ 36½ 36 36 36 35¾ 35½ 35 35
B 34¼ 34¼ 34 34 34 33½ 33¼ 33¼ 32¾ 32¾ 32¼ 32 31¾ 31¾ 31½ 31½ 31 30½ 30 29½ 29½ 29 28¾ 28½ 28½ 28¼ 28 27¾ 27¼ 26¾ 26½ 26½ 25 24
C 22 21½ 21 21 21 20¾ 20¼ 19½ 19½ 19 18¾ 18 17¼ 16 15½ 14¾ 13¾ 13¾ 13½ 13¼
D 11 11
F 10 10

Problem 1 2 3 4 sum
Mean 7.06 8.01 7.03 7.17 29.27
Stdev 2.81 1.97 3.28 2.92 8.07

And here is the distribution of combined scores for both midterms, again with letter grade cutoffs computed after removing outliers. Please keep in mind that these letter grades are still only rough predictions, based on only 40% of your overall coursework. Based on past experience, we expect most students' final course grades to be within half a letter grade of these estimates, but larger differences (in either direction) are not uncommon. (In particular, one student's score on Midterm 2 was 35 points higher than their score on Midterm 1!)

A 80 79 78 78 78 78 77 76 75 75 74½ 74½ 74½ 73½ 73½ 73½ 73¼ 72½ 72½ 72 71¾ 71½ 71½ 71 71 71 71 70½ 70½ 70½ 70 69½ 69½ 68¼ 68 68 67¾ 67½ 67
B 66¼ 66 66 65½ 65½ 65 64¼ 64 63 63 62½ 62 62 61¾ 60½ 60 60 60 59¾ 59½ 57½ 56¾ 56¼ 56 53½ 52½ 52½ 51¼ 50¾ 50¼ 50 49¾ 48¾ 48 47½ 47½
C 47 46½ 44¼ 44 43¼ 42¼ 42¼ 42 41¾ 41 40½ 40½ 39½ 39¼ 38½ 37¾ 35 33½ 33 32½ 31½ 28¾
D 27 25 23½
F 19¾ 19 18½ 18 16¼
April 21
Solutions for Homework 9 are available.
April 20
Homework 10 is due Wednesday, April 26 at 8pm.
April 17
Homework 9 has been revised. In particular, problem 2 has been removed (because apparently Jeff was sleep-deprived when he wrote it).
April 15
Solutions for Homework 8 are available.
April 13
Homework 9 is due Wednesday, April 19 at 8pm.
April 6
Solutions and tentative rubrics for Midterm 2 are available.
April 5
Homework 8 is due Wednesday, April 12 at 8pm.
March 31
Solutions for Homework 7 are available.
March 30
Midterm 2 will be held Tuesday, April 4, 7–9pm.
March 16
March 9
March 8
March 1
February 28
Homework 4 has been revised. In problem 1(b), we only want the analysis in terms of the number of nodes.
February 24
Homework 4 has been revised to clarify problem 2.
February 23
February 17
February 16
Homework 3 solutions are available.
February 15
Midterm 1 will be held next Tuesday, February 21, from 7pm to 9pm.
February 9
February 2
Homework 1 solutions are available.
February 1
Homework 2 is due next Wednesday, February 8 at 8pm. Only two problems this time (but the first one is long).
January 30
January 26
Homework 0 solutions are available.
January 25
Homework 1 is due next Wednesday, February 1 at 8pm.
January 24
Jeff is holding extra office hours 4-5 today and 11-12 tomorrow.
January 23
A wild LaTeX solution template appeared.
January 18
Class will be held in 100 Gregory Hall on Monday, January 30, so that 1404 Siebel can be used by a distingushed visiting speaker. This will likely happen a couple more times this semester.
January 15

Regular weekly schedule

Lectures
Mon Wed 4:00–5:15, 1404 Siebel
Office hours:
All in 3300G Siebel (the open area near 3304)
(Watch for rescheduling announcements on Piazza)

Jeff Tue 11–12 / Thu 4-5
Alex Fri 4-5
Charlie Mon 1:30–2:30
Vivek Wed 11:30-12:30
Homework
Due Wednesdays at 8pm, uploaded to Gradescope.
Homeworks are released at least one week before the due date.
Under normal circumstances, graded homework should be returned within 10 days of 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