Algorithms for Massive Data
Fall 2021
Announcements
[2/11] Homework 2 posted! Deadline is 24/11, which is also the day of our final exam.
[26/10] You can find the subject of the final exam from the last two years here and here.
[29/9] First class. Welcome! The class will take place over four day-long sessions. Hopefully, we will be able to meet physically at Dauphine, barring a sudden deterioration of the covid-19 situation. Please remain vigilant, wear masks, and follow all precautions while in class!
General Information
Course name: Algorithms for Massive Data
Course Instructor: Michail
Lampis.
Email: michail.lampis AT dauphine.fr
This is a course on advanced algorithmic topics with an emphasis on a
fine-grained complexity analysis. Our motivation is that when the input
consists of a huge data set, we cannot afford to blur the difference between
algorithms that take, say, linear and quadratic time. We will therefore look at
various techniques that allow us to obtain faster algorithms. Our emphasis will
be on performance guarantees, that is, mathematical proofs that our algorithms
work as intended. Topics that will be covered include: randomized algorithms
and advanced dynamic programming techniques.
More information on the topics to be covered will appear in the schedule below (which will be updated during the
semester).
As part of the course, students will be expected to complete a number of
homework assignments.
The homeworks assigned will count for 30% of the final grade. The
final exam counts for the remaining 70%.
Homework Assignments
General policy: Students must work on their assignments individually. You are allowed to discuss with your classmates, but not to copy their solutions.
Assignments must be turned in, via email to the instructor, on the day of the deadline before the start of class (because the solutions
may be discussed in class).
| Homework |
Topic |
Link |
Deadline |
Solutions |
| 1 |
Randomized Algorithms and Probabilities |
hw1 |
3/11 |
hw1 |
| 2 |
Divide and Conquer, Dynamic Programming |
hw2 |
24/11 |
|
- Recommended Algorithms textbook by Dasgupta, Papadimitriou, Vazirani link
- Recommended Randomized Algorithms textbook "Probability and Computing" by Mitzenmacher and Upfal.
TD Schedule
| TD No. |
Date |
Topic |
Notes |
| 1 |
Wed 29/9 (morning) |
Introduction, Randomized Algorithms |
slides, exercises,solutions |
| 2 |
Wed 29/9 (afternoon) |
Probability Review |
slides, exercises, solutions |
| 3 |
Wed 6/10 (morning) |
Sampling algorithms for the median |
slides |
| 4 |
Wed 6/10 (afternoon) |
Secretary Problem, More Randomized Algorithm Exercises. |
exercises, solutions |
| 5 |
Wed 3/11 (morning) |
Divide and Conquer |
slides |
| 6 |
Wed 3/11 (afternoon) |
Dynamic Programming, Divide and Conquer |
slides, exercises, solutions |
| 7 |
Wed 10/11 (morning) |
Dynamic Programming |
exercises, solutions |
| 8 |
Wed 10/11 (afternoon) |
More Dynamic Programming |
|