CS 473: Algorithms (Spring 2017)

Instructor
Jeff Erickson (jeffe)
Assistants
Alex Steiger (ajsteig2)
Charles Carlson (ccarlsn2)
Tong Li
Timothy Sanchirico
Phillip Shih
Shunping Xie
Yuhang Yang
Regular weekly schedule

Announcements

June 4
All homework and exam solutions have been removed from the site. (However, regrade requests for the final exam may still be submitted via Gradescope through the end of this week.)

Thanks everyone for a great semester!

May 17
• Final exams have been graded, and all graded exams have been released on Gradescope. Here is the distribution of scores. All statistics and letter-grade cutoffs were computed after excluding outliers above 95% and below 25%, but including both undergraduates and graduate students.

A 59½ 57½ 57 54 54 52 51 50¾ 50½ 49½ 48½ 48½ 47½ 47 46 45½ 45 45 44 44 43½ 43½ 42 42 41½ 41 40½ 40 39½ 39½ 39¼ 39 37½ 36½ 36½ 36 35½ 35½ 35½ 34½ 33½ 33½ 33 32½ 32 32 31¾ 31½ 31½ 31 29½ 29 28½ 28½ 28 27½ 27¼ 26½ 26½ 25 25 24¾ 24½ 24 24 23½ 23 22¾ 22½ 22½ 22 21½ 21½ 21 20½ 20½ 20½ 20¼ 20 19½ 19¼ 18¾ 18¼ 18 18 18 17¾ 17¼ 17 17 17 17 16½ 16½ 16½ 16½ 16½ 16¼ 15½ 14½ 13½ 13¼ 11¼

Problem 1 2 3 4 5 6 sum
Mean 4.82 6.31 4.62 5.44 6.25 3.62 30.95
Stdev 2.70 2.99 3.44 2.87 3.12 3.63 11.29
• Regrade requests for the final exam can be submitted via Gradescope until June 9, 2017. (After that, it will be impossible to maintain consistency.)
• Course grades have been submitted to the registrar via Banner. All grades were computed using the algorithm described on the grading policy web page. (In particular, we split each of the four 20-point homework problems into two 10-point problems, and scores over 10 points on any problem were counted as extra credit.) Here is the letter-grade distribution.

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–
C+ C+ C+ C+ C+ C+ C+ C+ C+ C  C  C  C  C  C  C  C  C  C– C– C– C–    C+ C+ C
F  F  F  F
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
• The final exam will be held next Wednesday, May 10, from 1:30pm to 4:30pm. Please go to the following rooms, based on the first letter of your last name:
• A–J: 1404 Siebel
• K–R: 0216 Siebel
• S-Z: 1404 Siebel
• You may bring TWO hand-written double-sided 8½"×11" cheat sheet to the exam. Otherwise the exam is closed-everything.
• Jeff will hold a final review session this Sunday afternoon. Watch for further details.
• We will offer a conflict exam next week (after the Sunday review session); the date will depend on when conflicted students are available. If you need to take the conflict exam, please register no later than Saturday, May 6.
• Solutions for Homework 11 are available.
April 29
Solutions for Homework 10 are available.
April 26
• Homework 11 is available. This homework is for practice only; you will not be able to submit solutions for grading. However, the material covered on this homework may appear on the final exam. Solutions will be released next Wednesday, May 3.
• Jeff will distribute ICES forms at the end of class next Monday, May 1. Please come for at least the last 15 minutes of class, even if you previously dropped the class.
April 25

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 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 22 21½ 21 21 21 20¾ 20¼ 19½ 19½ 19 18¾ 18 17¼ 16 15½ 14¾ 13¾ 13¾ 13½ 13¼ 11 11 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 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½ 47 46½ 44¼ 44 43¼ 42¼ 42¼ 42 41¾ 41 40½ 40½ 39½ 39¼ 38½ 37¾ 35 33½ 33 32½ 31½ 28¾ 27 25 23½ 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.
• Please go to the following rooms, based on the first letter of your last name:
• A–R: 1404 Siebel
• S–Z: 1310 DCL
• There will be a conflict exam on Wednesday, April 5. If you need to take the conflict exam, please register no later than Monday, April 3.
• There will be no lecture on Monday, April 3. Instead, Jeff will offer an optional review session.
• The exam will focus on material covered in Homeworks 4 through 7, although questions may rely on earlier material, including preprequisite material. The best source of study materials are the notes and previous semesters' exams. (See links below.)
• You may bring one hand-written double-sided 8½"×11" cheat sheet to the exam. Otherwise the exam is closed-everything.
March 16
• Homework 7 is due Wednesday, March 29 at 8pm, after spring break.
• Solutions for Homework 6 are available.
March 9

Here is the distribution of scores. 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 verage is slightly higher 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.

Please keep in mind that these letter grades are extremely rough predictions, based on only 20% of your overall coursework. Based on past experience, we expect most students' final course grades to be within one letter grade of these estimates, but differences of a full letter grade (in either direction) are not uncommon.

That said, if your midterm score is significantly below 25%, you should seriously consider dropping the class.

A 40 40 39 39 38½ 38 38 38 37 37 37 36 36 36 36 35½ 35 35 35 35 35 35 34½ 34 34 33½ 33½ 33½ 33½ 33 32½ 32½ 32½ 32½ 32 32 31½ 31½ 31 31 30½ 30½ 30 30 29½ 29½ 29 28½ 28 28 26 26 26 26 25½ 25½ 25 25 25 25 24½ 24½ 24½ 24½ 24½ 24½ 24 24 23 23 23 23 22½ 22½ 22 22 21½ 21 20½ 20½ 19½ 19½ 19 19 19 18½ 17½ 17 16½ 16½ 15½ 15 14 14 13½ 13 13 13 12½ 11½ 10½ 10½ 10 9¾ 9¾ 9½ 8¼ 8 8 7½ 7¼ 7 6 5½ 5¼ 5 2¾ 2½ 2½ 2½

Problem 1 2 3 4 sum
Mean 5.68 5.40 7.61 7.39 25.74
Stdev 3.87 3.17 2.96 2.72 7.60
• Jeff will hold extra office hours from 9am to noon tomorrow (March 10), specifically for students who need to discuss their exams before the drop deadline. Please do not ask homework questions.
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
• Both of our midterms will be held in 1404 Siebel and 1310 DCL. For Midterm 1, please go to the following rooms, based on the first letter of your last name:
• A–J: 1310 DCL
• K–Z: 1404 Siebel
(These will change for Midterm 2. If we get the same rooms for the final exam, everyone will have two of their three exams in 1404.)
• Here are links to several exams from Jeff's previous iterations of CS 473. (The order that we cover material changes from semester to semester, so don't just look at past Midterm 1s.) For lots of even earlier exams, see the bottom of Jeff's lecture notes page.
February 16
Homework 3 solutions are available.
February 15
Midterm 1 will be held next Tuesday, February 21, from 7pm to 9pm.
• There will be a conflict exam on Wednesday, February 22. If you need to take the conflict exam, please register no later than Monday, February 20.
• There will be no lecture on Monday, February 20. Instead, Jeff will offer an optional review session.
• The exam will cover everything covered in Homeworks 0 through 3, including prerequisite material. The best source of study materials are the notes and previous semesters' exams. Yes, the exam will be significantly easier than the homework.
• You may bring one hand-written double-sided 8½"×11" cheat sheet to the exam. Otherwise the exam is closed-everything.
February 9
• Homework 3 is due next Wednesday, February 15 at 8pm.
• This is the last homework before Midterm 1.
• Problem 0 is just for practice/amusement; do not submit solutions.
• Homework 2 solutions are available.
• Midterm 1 will be held Tuesday, February 21, 7–9pm, not "Tuesday, February 20" as previously announced. Stay tuned for location info. The midterm will cover all material covered in Homeworks 0 through 3. There will be no lecture Monday February 20; Jeff will hold an optional review session instead.
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
• Homework 1 has been revised. We split problem 2 to give more opportunity for partial credit. You may find the notes on greedy algorithms helpful for proving your algorithm in part (b) correct.
• Class is in 100 Gregory Hall today.
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
• Welcome! We're working hard to get everything set up before the semester begins. Meanwhile, you may notice broken links and/or text that refers to previous semesters.
• The first lecture is this Wednesday, January 18.
• Homework 0 is due next Wednesday, January 25 at 8pm. Each student must submit their own individual solutions on Gradescope. A LTeX solution template will be available soon.

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