CS 473: About This Course
About This Course
- What is this?
CS 473 (officially "CS 498 DL1") is an algorithms course aimed at advanced undergraduates and graduate students in computer science and related disciplines. When the course is finally approved, it will be cross-listed as Math 473 and CSE 414.
- 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
- NP-hardness and related lower bounds
- 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 who has taken CS 374, you are in the right place! Welcome!
- If you are an undergraduate who has not taken CS 374 or an equivalent course, you are in the wrong place. You really do need to take CS 374 first.
- 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 still be in the right place. Welcome! Past experience suggests that a strong background in proof-based mathematics is more important for success in this class than programming experience. If you have any concerns, please talk to Jeff as soon as possible.
- The department is considering developing an outward-facing 400-level course in algorithms and data structures, aimed at students outside computer science. Please let Jeff know if you or your students would be interested in such a course.
- 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, in particular:
- Degree Requirements
This course is not specifically required for any program on campus, but it has been approved to satisfy requirements in each of the following programs:
However, because this is a 400-level course, it does not count toward the requirement in all graduate programs for 500-level credits.
- Web site
- All course materials—announcements, course policies, detailed schedule, lecture notes, lecture videos, homeworks, homework and exam solutions—can be found here. Hey, look! You found it!
- Lecture notes
Jeff's algorithms lecture notes are the primary reference for this class. Jeff will post revisions and new notes to the lecture page as the semester progresses. The lecture notes site also contains homeworks and exams from several of 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.
We plan to record all lectures, as in past semesters. Lecture videos should appear automatically on a separate page a few hours after each lecture. We will also add links to lecture videos to the schedule web page as the semester progresses. Videos of Jeff's lectures from several past semesters are also available; Jeff has asked the college to maintain these videos permanently.
- We will use Gradescope for homework submission and grading. Anyone can sign up for access to the CS 473 Gradescope site with their favorite alias and email address, using the self-enrollment code M54G49. We will separately ask you for your alias, so that we can map your homework grades to you.
- 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.)
- We're going to try using Gradescope to score exams as well as homework, but if that doesn't work out, we'll use Moodle as a fallback. We will not use Moodle for anything else. If you do not already have access, you can enroll yourself with the code CS473. (Sorry, Illinois students only.)
- I've collected a long list of other useful resources on a separate page.