
Recent Posts
Archives
Categories
Meta
Monthly Archives: January 2012
Lecture 8: Compressed Sensing
1. Compressed Sensing Let be some unknown vector. We can learn information about through the following “measurement” operation: we can choose a vector and we are told the value of . We would like to minimize the number of measurements … Continue reading
Posted in Uncategorized
Leave a comment
Lecture 7: Streaming Algorithms, Nearest Neighbor
In this lecture we will see two applications of the JohnsonLindenstrauss lemma. 1. Streaming Algorithms In 1996, Alon, Matias and Szegedy introduced the streaming model of computation. Given that they all were at AT&T Labs at the time, their work … Continue reading
Posted in Uncategorized
Leave a comment
Lecture 6: Dimensionality Reduction by the JohnsonLindenstrauss Lemma
Dimensionality reduction is the process of mapping a high dimensional dataset to a lower dimensional space, while preserving much of the important structure. In statistics and machine learning, this often refers to the process of finding a few directions in … Continue reading
Posted in Uncategorized
2 Comments
Lecture 5: SkipNet Analysis, Consistent Hashing
In this lecture we continue to discuss applications of randomized algorithms in computer networking. 1. Analysis of SkipNet Routing Last time we introduced the SkipNet peertopeer system and we discussed its routing protocol. Recall that every node has a string … Continue reading
Posted in Uncategorized
Leave a comment
Lecture 4: Quicksort, SkipNet
In today’s lecture we will see two applications of negative binomially distributed random variables. 1. Example: Quicksort Quicksort is one of the most famous algorithms for sorting an array of comparable elements. (We assume for simplicity that the array has … Continue reading
Posted in Uncategorized
Leave a comment
Lecture 3: Balls and Bins, Congestion Minimization, Quicksort
1. Example: Balls and Bins Last time we proved the Chernoff bound, the most useful analysis tool we will encounter in this course. Today we illustrate the power of the Chernoff bound by using it to analyze a fundamental ballsandbins … Continue reading
Posted in Uncategorized
Leave a comment
Notes on Convexity Inequalities
In the analysis of randomized algorithms, we frequently use various inequalities to simplify expressions or make them easier to work with. These inequalities are usually obvious by plotting them, and proving them just uses basic calculus. 1. Facts from Convex … Continue reading
Posted in Uncategorized
3 Comments