CS 473 is the required algorithms class for all undergraduate computer science majors at the University of Illinois. This course covers fundamental techniques in the design and analysis of algorithms: recursion (including divide-and-conquer, backtracking, and dynamic programming), randomized algorithms, amortized analysis, fundamental graph algorithms (depth- and breadth-first search, minimum spanning trees, shortest paths, flows and cuts), reductions (transforming one problem into another), and NP-completeness.
CS 473 is intended for undergraduates in computer science and related areas, or graduate students outside computer science interested in building up their algorithmic background. Graduate students in CS and closely related fields (like ECE and math), including CS students in the MCS and 5-year BS/MS programs, should take CS 573 instead. Intellectually mature/ambitious undergraduates, especially those considering graduate school, should also consider CS 573.
For many students, CS 473 is the most challenging course in the undergraduate computer science curriculum. On the other hand, feedback from UIUC alumni and their employers suggests that CS 473 is also one of the most rewarding and useful courses in the curriculum, in no small part because of its difficulty. On the gripping hand, computer science majors are some of the brightest students on campus; an easier course would be an insulting waste of your time.
We assume that all students have mastered the material taught in CS 173 (discrete mathematics) and CS 225 (basic algorithms and data structures). Note that "mastery" is not the same as "exposure" or even "a good grade"; hence, Homework Zero! Programming experience is helpful; a strong mathematics background is even more helpful.
Grades will be based on weekly online quizzes (5% total), weekly written homeworks (25% total), two midterms (20% each), and a final exam (30%). There will be several opportunities for extra credit, which will be applied after the curve. See the grading policies for more details.
Almost everything—course policies, detailed schedule, lecture notes, lecture videos, homeworks, homework solutions, head-banging problems, etc.—can be found here. Hey, look! You found it!
All lectures will be recorded; links to lecture videos will be available on the schedule web page as the semester progresses. Jeff has asked the college to maintain these videos permanently. Videos from Spring 2010 are also available. Lecture videos are accessible without a password from any on-campus computer; off-campus access requires a university NetID and password. (Unfortunately, official universitypolicy explicitly forbids making these videos available to the public.)
We will use Moodle for weekly online quizzes and to record and distribute grades. Registered students should already have access to the CS 473 Moodle site with their university NetID and password. Students can enroll themselves until September 26 with the password algorithms. Guests can also access the site with the password algorithms; guests can see the online quizzes and solutions but not grades.
We will use Piazza for online discussions. Anyone can sign up for access to the CS 473 Piazza site with your favorite email address and the access code algorithms. We strongly encourage posting questions on any course-related topic to Piazza rather than emailing the course staff. You can even post your questions anonymously. (However, we can only give you extra credit for helpful posts if you post them using your real name.)