ANNOUNCEMENTS

• 2020-08-31: Office hours have been posted.

ABOUT

Class: This class will be fully online. Asynchronous lecture videos will be posted to the calendar WF5.

Instructors:

• Prof. Michael A. Forbes (miforbes)
• Prof. Chandra Chekuri (chekuri)

Teaching Assistants:

• Robert Andrews (rgandre2)
• Calvin Beideman (calvinb2)
• Zander Kelley (awk2)

Graders:

• Joe  Carolan
• Binghui Cheng
• Rishub Podar
• Tianyi Wang

Office Hours (on Zoom (id: 995 3201 9818, access code)):

• Zander: Tuesday 1pm
• Robert: Wednesday 9am
• Calvin: Thursday 1pm

Logistics and Policies

• Problem Set and Exam Policies
• Grading
• Academic integrity

RESOURCES

CALENDAR

The calendar lists lecture topics, associated lecture materials, and auxilary reading. It also lists the problem sets with release- and due-dates, as well as listing the exam schedule.

PIAZZA

The class has a Piazza page (access code), which will serve two purposes. The first is for course announcements. The second is to host a discussion forum where students can (anonymously or otherwise) ask questions of their co-students. Such discussion is highly encouraged, subject to policies on academic integrity. We strongly recommend that any questions directed at the course staff to be posted on Piazza, and not sent as email, as this ensures a faster and more consistent response. Please sign-up!

GRADESCOPE

We will use Gradescope (access code) for all problem set submissions and grading. See the pset policies for more.

DESCRIPTION

cs473 is an algorithms course aimed at advanced undergraduates and graduate students in computer science and related disciplines.

Prerequisites: cs374 or equivalent, or graduate standing. In particular, students are assumed to have mastered the material taught in cs173 (discrete mathematics) and cs225 (basic algorithms and data structures). We emphasize that "mastery" is not the same as "exposure" or even "a good grade"; hence, problem set 0. Programming experience is helpful; a strong mathematics background is even more helpful.

Coursework: Course grades are based on weekly problem sets (25% total), two midterm exams (22.5% each), and a final exam (30%). All problem set and exam grades will be posted on Gradescope. See the grading policies for more details.

Postrequisites: Taking this course prepares you for various other theoretical computer science courses at UIUC. We list some semi-regularly offered courses below.

• cs583: Approximation Algorithms
• cs574: Randomized Algorithms
• cs579: Computational Complexity

REFERENCES

The main materials for the class are the lecture notes, to be posted on the calendar as the semester progresses. Auxiliary materials will also be listed, but may not follow the presentation given during lecture. Common sources of these materials include:

• Algorithms, by Jeff Erickson
• Lecture notes by Sariel Har-Peled
• Algorithm Design by Jon Kleinberg and Éva Tardos
• Algorithms by Sanjoy Dasgupta, Christos Papadimitriou, and Umesh Vazirani (draft pdf)
• Introduction to Algorithms by Thomas H. Cormen, Charles Leiserson, Ronald L. Rivest, and Clifford Stein

Past versions of thise course (2018-09, 2019-09, 2020-01) are also a rich source of different perspectives on the same material.

For those seeking review materials, either consult past versions of cs374 (2019-09, 2020-01), or the following textbooks:

• Building Blocks for Theoretical Computer Science by Margaret Fleck.
• Mathematics for Computer Science by Eric Lehman, Tom Leighton, and Albert Meyer.
• Open Data Structures by Pat Morin