CS 473: Algorithms (Spring 2016)

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


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

Tue Thu 3:30–4:45
116 Roger Adams Laboratory
Tentative office hours
In the open area outside 3304 Siebel unless otherwise indicated.
Electronic submissions due Tuesdays at 5pm, 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