About This Course

Syllabus

The course covers a wide range of algorithm design and analysis techniques. Precise coverage varies from semester to semester, but usually includes a large subset of 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

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 a strong 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 or Makrand as soon as possible.

• Finally, if you want an easy A, you are probably in the wrong place.

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!

Postrequisites

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

• CS 574: Randomized Algorithms
• CS 580: Algorithmic Game Theory
• CS 583: Approximation Algorithms
• Algorithmic sections of CS 598

Coursework

Grades are based on weekly written homeworks, two midterm exams, and a final exam. See the grading policies for more information about how each type of coursework contributes to the final course grade.

Degree Requirements

This course is required for the following degree programs:

• MS in Applied Mathematics, Optimization and Algorithms option
• MS in Bioinformatics, all options
  ⚠️ Many MS Bioinformatics students have little or no undergraduate background in computer science; historically these students seriously struggle in CS 473. The CS Department approved removing this degree requirement aver a year ago; however, campus-level approval is still pending. We strongly recommend that MS Bioinformatics students speak with Jeff and/or one of the graduate advisors in the CS Academic Office early in the semester about having this degree requirement waived.

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

• “Mere” 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!

Reading

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 revised and updated as the semester progresses. (The book web site also contains homeworks, lab handouts, and exams (but no solutions) from Jeff's past algorithms classes.)

Videos

We plan to record all lectures, as in past semesters. Lecture videos should appear on MediaSpace at most a day after each lecture. Lecture videos from several past semesters of CS 473 are linked from a separate page.

Gradescope

We are using Gradescope for submission and grading of both homeworks and exams. Everyone who registered for CS 374 before the semester started should already have access to the CS 473 Gradescope site. Students who add the course later can enroll themselves using the self-enrollment code 5KKB3X.

Ed Discussion

We are using Ed Discussion for online questions and announcements. Anyone can join the Ed site; no access code is required. Please post questions on any course-related topic to Ed rather than emailing the course staff. You can even post your questions and answers anonymously.

Caveats

The university does not have a contract with Ed; we cannot enroll students automatically, and we must allow you to enroll anonymously (using pseudonyms and non-university email addresses). Campus administration strongly encourage instructors to use CampusWire for online discussion and Canvas for everything else, but we prefer to use tools that actually work.

As a matter of course policy, course staff will wait a minimum of three hours before answering any online question about the course material—except for questions about lecture material on the day of the the lecture—so that other students have an opportunity to answer first. (We will answer administrative questions as quickly as we can.)

Etc.

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