Tu/Th 9-10:15 pm, Krannert Building G007
Instructor
Elena Grigorescu, elena-g purdue.edu
TA: Abram Magner, anmagner purdue.edu
Office Hours: upon appointment.
Announcements
Welcome to CS590 Sublinear algorithms!
Please sign up on Piazza. The lecture notes and other resources will be posted there.
Course description
Sublinear time algorithms allow one to read only a small fraction of the input. They play an important role in the design of algorithms for big data and are typically randomized algorithms generating approximate solutions. This course will introduce techniques for designing and analyzing sublinear time algorithms including combinatorial and graph algorithms, and algorithms for error-correcting codes and other algebraic objects. These algorithms provide extremely fast approximations for classical optimization problems and also for decision problems studied in the so-called property testing model.
Prerequisites: A course on discrete math and undergraduate algorithms.
Grading
- 30% for class discussions and participation
- 70% for the project (Instructions)