Description

This course covers the design and analysis of algorithms. An algorithm is a set of steps  used to solve a particular problem. We’ll cover classical concepts in algorithm  analysis  (such as Big-O notation and NP-Completeness) as well as important  categories of algorithms (graph algorithms, greedy algorithms, randomized algorithms, streaming) and some key application areas (federated learning, differential privacy) if time permits.  This class will focus on rigorous proofs of correctness and reasoning about running time.

Instructors:

Vladimir Braverman ([email protected]). Office hours are Friday noon-1pm in Duncan

2068.

Prerequisite: Students  should have some mathematical background and ability to write rigorous mathematical proofs.

Textbook

About 60% of the course’s lectures will closely follow the material in Introduction to Algorithms, 3rd Edition (The MIT Press). This is also known as the CLRS book.

Some of the material covered in class will not be covered in that book (specifically, streaming algorithms, federated learning) but.  CLRS is available online at Fondren Library and the links can be found on Canvas:

https://canvas.rice.edu/courses/54528/pages/useful-links

Lectures, Meeting Times and Locations

Class will be held Monday, Wednesday, Friday from 11am-11.50am in DH 1042.

Registration

You’re responsible for registering for COMP 582 with the university registrar.

Communication

The class will have a Piazza forum for all day-to-day communication:

piazza.com/rice/spring2023/comp582

Assignment handouts and submissions, as well as your grades, will be on Canvas. Everything else will be on Piazza.

Schedule

The Tentative Schedule is available on Canvas:

https://canvas.rice.edu/courses/54528/pages/tentative-schedule

Lecture Attendance Policy

Lectures will be on slides and the whiteboard. Lecture attendance is not required, but you’ll find it to be very useful. Slides and lecture notes are available for most lectures on

Canvas/Modules:

https://canvas.rice.edu/courses/54528/modules

Grading and Evaluation

There will be 12 homeworks, roughly one homework each week, with each homework being 3% of your grade. Thus the homework will be 36% of your grade in total.

All homeworks must be typed using Latex and submitted on Gradescope (see the link on Canvas).

There are three examinations. These will be held in person, during one of the classes. See the Schedule for the exact dates. The first two exams are worth 21% of your grade and the last exam is worth 22%.

Final grades are based on the percent of the total points you receive, where 90-100 is an A, 80-89 is a B, and so forth. We reserve the right to apply a “curve” to change this, but only for the better. That is, if you’ve gotten 90%, you’re guaranteed at least an A- for your final grade, but you might do better.

Lateness and Missed Assignments