CS 473: About This Course

• About this course
• Class resources

About This Course

What is this?

CS 473 is an algorithms course aimed at advanced undergraduates and graduate students in computer science and related disciplines. The course is officially cross-listed as Math 473 and CSE 414.

Syllabus

The course covers 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

Coursework

Grades will be based on weekly written homeworks (30% total), two midterms (20% each), and a final exam (30%). See the grading policies for more details.

Prerequisites

CS/ECE 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, especially recursion and graphs). 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!
• 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.

Postrequisites

This course is a recommended prerequisite for all 500-level algorithms courses, in particular:

• CS 574: Randomized Algorithms
• CS 583: Approximation Algorithms
• CS 598 RM: Algorithmic Game Theory
• Other algorithmic sections of CS 598

Degree Requirements

This course is required for the following degree programs:

• MS in Applied Mathematics, Optimization and Algorithms option
• MS in Bioinformatics

This course also satifies requirements in each of the following degree programs:

• Engineering CS majors: Technical elective in the Algorithms and Models of Computation focus area.
• Math&CS majors: Group V (logic and computation) requirement.
• EE and CE majors: Approved technical elective.
• All CS master's programs (MS, MCS, BS/MS, and BS/MCS): Theoretical Computer Science breadth requirement.
• CS PhD program: Any Program of Study that includes CS 473.

However, because this is a 400-level course, it does not count toward the requirement in all graduate programs for 500-level credits.

Class Resources

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

There is no required textbook. A significant fraction of the class will follow Jeff's Algorithms textbook and related course notes, which are freely available online. Lecture notes / book chapters for all lecture topics are available on the schedule page; these will be revise and updates as the semester progresses. (The book web site also contains homeworks, lab handouts, and exams (but no solutions) from Jeff's past algorithms classes.)

The book and lecture notes have bugs. We will award extra credit to any student who identifies a mistake and offers a suitable correction on Ed Discussion. Yes, typos and spellign mistaks count.

Videos

We plan to record all lectures, as in past semesters. Lecture videos should appear on a separate page a few hours after each lecture. We may also add links to (self-recorded) lecture videos to the schedule web page as the semester progresses.

Videos of Jeff's lectures from some past semesters are also available; stay tuned for links.

Gradescope

We will use Gradescope for homework submission and grading. Everyone registered or the class will be enrolled automatically at the start of the semester.

Ed Discussion

We are planning to use Ed for online discussions. Anyone with an illinois.edu email address can join by following this link. We strongly encourage posting questions on any course-related topic to Ed 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.)

Etc.

I've collected a long list of other useful resources on a separate page.