"New CS 473" — Algorithms (Spring 2015)

Instructor
Jeff Erickson (jeffe)
Assistants
Chao Xu (chaoxu3)
Bing-Jui Ho
Xue Zou
Administrivia
About this course
Regular weekly schedule
Academic integrity policies
Homework and grading policies
Some stuff you already know


Announcements

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.

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

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.

February 12
Homework 2 solutions are available.

I need to remind everyone again about both components of the academic integrity policies.

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.


Weekly schedule

Lectures
Tue Thu 11:00-12:15
1310 Digital Computer Lab
Office hours
In the open area outside 3304 Siebel, unless otherwise specified.
Homework
Due Tuesdays at 5pm in the drop boxes outside 1404 Siebel.
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