Homework 0 solutions are available.
Jeff's regular Wednesday office hours are from 4:00 to 5:00, starting today.
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.
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.
If you are registered, you should already be enrolled on the course Moodle site. If not, you can enroll yourself with the code
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).
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.
|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|