Lecture 2 whiteboard + addition to lecture 1 | |
|
Dear students, The whiteboard from yesterday's lecture (Lecture 2) was uploaded. Thanks to the students who attended and participated, and thanks for the votes on preferred proofs of Lemma 1. For Lecture 1, the construction of k-wise independent hash functions presented was insufficient for our needs, since we require to map elements in [m] to a much smaller range [2/eps] (thanks Michael for pointing this out!) The fix is fairly simple, and effectively boils down to taking remainders modulo the size of the smaller range. See the updated slides (especially the text in blue). For those who haven't checked this out yet, I remind you that the end of Lecture 1's slides have a numeric example to provide some explanation of why these kind of sketching algorithms are so popular in practice. (In short: these algorithms provide savings of several orders of magnitude in space!) Best, David |
| עדכון אחרון ב-20/11/2024, 13:12:58 Last updated on 20/11/2024, 13:12:58 Последняя модификация20/11/2024, 13:12:58 تمت الحتلنة الأخيرة ب-20/11/2024, 13:12:58 |
Lecture 2 notes | |
|
Dear students, The notes for today's lecture have been updated (minor change of flow of the lecture). If you use the notes during class, do make sure to download the most recent notes. See you soon, David |
| פורסם ב-19/11/2024, 09:24:40 Created on 19/11/2024, 09:24:40 Создано19/11/2024, 09:24:40 تم النشر ب-19/11/2024, 09:24:40 |
Lecture 1 notes | |
|
Dear students, Please note that the notes for Lecture 1 now include: (1) a discussion of the Reservoir Sampling algorithm we saw in the last ten minutes of class. (2) a quick numerical example and discussion explaining the popularity in practice of streaming algorithms. (Thanks for Adar for pointing out that (1) wasn't actually uploaded, and asking about (2).) Best, David |
| עדכון אחרון ב-14/11/2024, 15:44:11 Last updated on 14/11/2024, 15:44:11 Последняя модификация14/11/2024, 15:44:11 تمت الحتلنة الأخيرة ب-14/11/2024, 15:44:11 |
Extra office hours to questions regarding the first lecture | |
|
Dear students, To help students who missed the first lecture and were worried about making up the missed material, I will hold an exceptional extra office hour this week on Thursday 11:00-12:00 for clarification questions regarding the first lecture (see course material). If you cannot attend this extra office hour and missed the first lesson, you are strongly recommended to attend my office hour next Tuesday an hour after class. (Email me if meeting over Zoom for the office hour is easier.) As a reminder: for the second lecture, make sure to go over HW0 for a probability refresher. Best, David |
| עדכון אחרון ב-13/11/2024, 10:58:19 Last updated on 13/11/2024, 10:58:19 Последняя модификация13/11/2024, 10:58:19 تمت الحتلنة الأخيرة ب-13/11/2024, 10:58:19 |
Lecture 1 summary: | |
|
Dear Students, Thanks to the students who came to the first lecture and contributed to an interactive and engaging lesson. I hope you enjoyed the discussion. Following the lesson, I uploaded the lecture whiteboard and updated the notes to include an appendix on Reservoir Sampling. Looking forward to seeing you in the next lectures. (To best prepare: please finish HW0 and go over Lecture 1, especially if you missed it.) Best, David |
| עדכון אחרון ב-12/11/2024, 14:33:00 Last updated on 12/11/2024, 14:33:00 Последняя модификация12/11/2024, 14:33:00 تمت الحتلنة الأخيرة ب-12/11/2024, 14:33:00 |
Welcome to Foundations of Algorithms for Massive Datasets! | |
|
Dear students, Welcome to the course. I'm looking forward to discussing some elegant algorithms (and lower bounds) for massive data. See the course syllabus for tentative topics. We may cover these in less detail and also cover other topics. As per current Technion regulations, we will have our classes *over zoom*. See course syllabus for the zoom room link and some tips and requests to make lectures as interactive (and effective) as possible given the circumstances. To prepare for the first few lessons, I uploaded a *non-mandatory HW0*. This homework is intended as a reminder of some basic probabilistic tools that you have seen before and we will use in the course. It is recommended you do at least parts (a) and (b) before the first lecture, and the other parts before Lecture 2. Looking forward to seeing you in (virtual) class, and wishing us all a productive and quiet semester! Best, David |
| עדכון אחרון ב-6/11/2024, 18:35:23 Last updated on 6/11/2024, 18:35:23 Последняя модификация6/11/2024, 18:35:23 تمت الحتلنة الأخيرة ب-6/11/2024, 18:35:23 |