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 Johnson-Lindenstrauss 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 Johnson-Lindenstrauss 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 peer-to-peer 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 balls-and-bins … 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