Streaming exercise
Here is an (HW?) exercise in streaming algorithm design.
Given a stream of items a_1,...,a_n, a_i \in [1,u], find the average of items below the median or the median of items below the average.
There is previous work on finding the median (or more generally, the quantiles) and the kth frequency moments \sum_i f_i^k, where f_i is the frequency of i (k=1 is the average). The exercise here is an example of cascaded aggregation: computing the kth frequency moment following a quantile computation.
As is standard in streaming algorithms, one has to use space and per-item update time of polylog(n,u) and obtain reasonable approximation.
Given a stream of items a_1,...,a_n, a_i \in [1,u], find the average of items below the median or the median of items below the average.
There is previous work on finding the median (or more generally, the quantiles) and the kth frequency moments \sum_i f_i^k, where f_i is the frequency of i (k=1 is the average). The exercise here is an example of cascaded aggregation: computing the kth frequency moment following a quantile computation.
As is standard in streaming algorithms, one has to use space and per-item update time of polylog(n,u) and obtain reasonable approximation.
posted by metoo at 6:57 AM
9 Comments:
low calorie diet Having problems with weight loss? To achieve lasting weight loss requires some knowledge and a little work. Your food intake must consist of the right amounts of protein carbohydrate and fat. (or it won�t work!) And you need proper exercise intensity, frequency and duration (not what you think). To get more info. please visit low calorie diet
weight loss calories Looking for the right diet? To help you choose we have reviewed the top diet plans available today. Simply fill out a free profile and choose one you�re most comfortable with. Please visit weight loss calories
diet programs Having problems with weight loss? To achieve lasting weight loss requires some knowledge and a little work. Your food intake must consist of the right amounts of protein carbohydrate and fat. (or it won�t work!) And you need proper exercise intensity, frequency and duration (not what you think). To get more info. please visit diet programs
weight loss calories How many calories do you need per day? Learn more. Please visit weight loss calories
Once an individual suffers from obesity or overweight, it becomes highly important for him to trigger off weight loss and altogether weight loss is necessary to keep a whole lot of obesity induced disorders, namely, diabetes, arthritis, high blood pressure et al at bay. Dieting and regular physical exercises can help in achieving weight loss and altogether the “weight loss” section of the website http://www.pill-care.com informs you that weight loss medicines such as Phentermine, Xenical etc can also help you trigger off instant weight loss if taken in accordance with the instructions of the doctor.
If you have fallen prey to obesity and would like to trigger off weight loss as soon as possible, then you should opt for diet pills such as Phentermine and Adipex that are extremely popular for inducing rapid weight loss among people across the world. You will find the relevant details of weight loss pills at http://www.weight-loss-truths.com that inform you that Phentermine is to be taken only after procuring a Phentermine prescription and also in accordance with the instructions of the doctor. So, get hold of a Phentermine prescription, administer the drug properly and transform your weight loss dreams into reality.
Nice blog. :)
Natural weight loss
[url=http://www.review6.com]Website Review Evaluation[/url]
Post a Comment
<< Home