About This Course
- What is this?
CS 498 section DL (unofficially "New CS 473") is the first pilot offering of a planned revision to CS 473, which will also serve as a replacement for CS 573.
- This revision is aimed at advanced undergraduates and graduate students in computer science and related disciplines. The initial enrollment of 70 students included 33 undergraduates (= 20 CS + 11 CE + 3 other) and 37 graduate students (16 ECE + 10 CS + 3 Math + 11 other).
- The course will cover a wide range of algorithm design and analysis techniques including the following:
- Advanced dynamic programming
- Randomized algorithms
- Hashing, filtering, and streaming algorithms
- Maximum flows and minimum cuts
- Linear programming
- Approximation algorithms
Grades will be based on regualr written homeworks (30% total), two midterms (20% each), and a final exam (30%). See the grading policies for more details.
CS 374 or equivalent, or graduate standing. In particular, we assume that students have mastered the material taught in CS 173 (discrete mathematics, especially induction) 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!
- Am I in the right place?
Well, that depends.
- If you are an undergraduate CS major who has taken CS 373, you are in the wrong place. You need the old version of CS 473 to graduate. This is the last semester that old CS 473 is being offered, so you'd better take it now.
- If you are an undergraduate who has taken CS 374, you are in the right place! Welcome!
- If you are an undergraduate who has taken neither CS 373 nor CS 374, you are in the wrong place. You have to take CS 374 first.
- If you are an undergraduate who has taken both CS 373 and CS 374, you don't exist.
- If you are an undergraduate who has taken the old version of CS 473, you may be in the right place. This revision has significant overlap with the olver version of 473.
- If you are a graduate student in computer science or a related discipline, you are in the right place! Welcome! In particular:
- If you are a CS PhD student whose program of study includes CS 573, you are in the right place.
- Yes, even if you've already taken an undergraduate-level algorithms class.
- If you are a graduate student without an undergraduate background in computer science, you might be in the right place. (This is a new course, so we don't really know.) Based on our experience in CS 573, a strong background in proof-based mathematics is probably more important than strong programming experience. If you have any concerns, please talk to Jeff as soon as possible.
- Finally, if you want an easy A, you are probably in the wrong place.
This course replaces CS 573 as a prerequisite for all 500-level algorithms courses:
This course satisfies the following degree requirements:
Finally, this course is an approved technical elective for EE and CE majors.
- The 400-level logic/computation requirement for Math/CS majors.
- The CS/Informatics requirement for the MS program in Bioinformatics.
- Any other requirement satisfied by CS 473 or CS 573.
- Web site
- 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!
- Lecture notes
Jeff's algorithms lecture notes will be the primary reference for this class. We will post revisions and new notes to the lecture page as the semester progresses. The lecture note site also contains homeworks and exams from Jeff's past algorithms classes.
The lecture notes have bugs. We will award extra credit to any student who identifies a mistake and offers a suitable correction on Piazza. Yes, typos and spellign mistaks count.
All lectures will be recorded. Lecture videos will appear automatically on a separate page (TBD), and links to lecture videos will be added to the schedule web page as the semester progresses. Videos of Jeff's lectures from CS 473 Fall 2013 and CS 374 Fall 2014 are also available. Jeff has asked the college to maintain these videos permanently.
- We will use Piazza for online discussions. Anyone can sign up for access with their favorite email address and the access code
CS473++. 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.)
- I've collected a long list of other useful resources on a separate page.
What's happening with CS x73?
For students familiar with the existing undergraduate CS curriculum: CS 374 includes about half of the material in CS 373 (which has now been retired) and about two-thirds of the material from CS 473 (which will be revised starting next semester), combined into a single four-credit 300-level course. The move from two required theory courses (373 and 473) to one (374) is part of a larger revision of the undergrad CS currculum. This particular change was motivated by several factors.
- Smaller CS core: The CS department is shrinking the core of required undergraduate courses, which is shared by all undergraduate computer science programs. (The CS department currently offers seven majors: CS Engineering, CS+Anthropology, CS+Astronomy, CS+Chemistry, CS+Linguistics, Math/CS, and Stat/CS. Several more CS+X majors are in development.)
- Earlier algorithms: The new course moves algorithms earlier in the curriculum, so that the material can be exploited in 400-level classes.
- More flexibility later: In particular, the earlier course frees the CS department to offer a broader range of 400-level elective theory courses.
- Computer engineers: The ECE department has wisely decided that all computer engineering majors need an algorithms course, but did not want to force students to take both CS 373 and CS 473.
Covering every important topic from CS 373 and CS 473 in a single course is simply impossible; we have had to make some difficult choices. The new CS 473 include all of the important topics that could not fit into CS 374, plus some others that were previously covered only in CS 573, our standard graduate algorithms class.
In light of the significant overlap between CS 573 and the revised CS 473, the fact that CS 473 is now an elective rather than a required undergraduate course, and the relatively small group of potential instructors, we have also decided to let the new CS 473 replace CS 573 as the standard algorithms course for graduate students, both within and outside computer science. Teaching the material appropriately to such a diverse audience will present a significant challenge. Thank you for agreeing to be guinea pigs.
Here is the transition timeline:
- CS 373
Old CS 473
- CS 373 (last offering)
CS 374 (first pilot, limited enrollment)
Old CS 473
- CS 374 (second pilot, limited enrollment)
Old CS 473
CS 573 (last offering)
- CS 374 (first offering at scale: 400 students)
Old CS 473 (last offering)
New CS 473 (first offering) — you are here
Every semester thereafter
- CS 374
New CS 473
Other 400- and 500-level theory courses in development