Class 1 | |
| זמן: Time: Time: Time: | 19/03/2019 10:30 |
| זמן סיום: End Time: End Time: End Time: | 19/03/2019 12:30 |
|
Today we talked about: - General intro to course - Basic probability review: Markov inequality, Chebychev inequality, Union Bound - Reservoir sampling of a datastream of numbers - Counting with log log N bits - Stream frequency moments definition, algorithm for F_2 (without proof) | |
Class 2 | |
| זמן: Time: Time: Time: | 26/03/2019 10:30 |
| זמן סיום: End Time: End Time: End Time: | 26/03/2019 12:30 |
|
Today we finished describing the Tug-Of-War algorithm for F_2 estimation using logarithmic space. We described the general trick of taking "median of means" to obtain a guarantee of "at most relative eps-error, with probability at least 1-delta", with space that grows like log(1/delta)/eps^2, given an estimator that has only a Variance bound. We then talked about F_0 estimation using the Flajolet-Martin algorithm, that uses infinite precision computation. In the homework, there will be an exercise that makes this algorithm more realistic. Finally, we stated Hoeffding probability tail inequality theorem (without proof). | |
Class 3 | |
| זמן: Time: Time: Time: | 02/04/2019 10:00 |
| זמן סיום: End Time: End Time: End Time: | 02/04/2019 12:00 |
| מקום: Location: Location: Location: | טאוב Taub Taub Taub Taub Тауб Taub 7 |
| הערות: Notes: Примечания: ملاحظات: | - Martin-Flajolet algorithm for F_0 estimation - Heavy-hitters algorithm for F_infty estimation - Proof of Hoeffding inequality |