cs473: ALGORITHMS (FALL 2019)

ANNOUNCEMENTS

- 2019-09-03: For students waiting to enroll, please post a private note in piazza with your name, netid, and major by the evening of
*this Thursday*. We may have some spots in the online section but need an estimate of demand before enrolling more students.

ABOUT

**Class:** TR2:00-3:15 DCL 1310

- Prof. Michael A. Forbes
*(miforbes)* - Prof. Chandra Chekuri
*(chekuri)*

- Shant Boodaghians
*(boodagh2)* - Mitchell Jones
*(mfjones2)* - Yipu Wang
*(ywang298)*

- Yipu: M3
- Shant: M5
- Mitchell: T12:30
- Michael: T3:30
- Chandra: F1

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 *cs473*), which will serve two purposes. The first is for course announcements, which will also be posted on this website. 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 *MZJ326*) 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 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.

**Am I in the right place?** Well, that depends.

- If you are an undergraduate who has taken cs374, you are in the right place! Welcome!
- If you are an undergraduate who has not taken cs374 or an equivalent course, you are in the wrong place. You really do need to take cs374 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 "cs573", 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 the instructors as soon as possible.
- Finally, if you want an easy A, you are probably in the wrong place.

**Postrequisites:** This course replaces cs573 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:

**Engineering CS majors:**Technical elective in the Algorithms and Models of Computation focus area**Math/CS majors:**400-level logic/computation requirement**EE and CE majors:**Approved technical elective**All CS masters programs**(MS, MCS, BS/MS, and BS/MCS): Theoretical Computer Science breadth requirement, replacing cs573.**MS program in Bioinformatics:**Computer Science and Informatics requirement.**CS PhD program:**Any Program of Study for cs473 or cs573.

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

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
(2017-01,
2017-09,
2018-01,
2018-09)
are also a rich source of different perspectives on the same material (often with *video*).

For those seeking review materials, either consult past versions of cs374 (2018-09, 2019-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