Streaming

Question 1

what are the performance metric considered for the streaming model

Answer 1

size of working memory, sequential passes over the stream, processing time per item

Question 2

majority problem

Question 3

Boyer-Moore algorithm pseudocode + description

Question 4

Prove the correctness of the Boyer-Moore algorithm

Question 5

What is a m-sample of a set X

Question 6

what is a m-sample of a streaming

Question 7

Prof of the correctness of the reservoir sampling

Question 7

Reservoir sampling pseudo

Question 8

Describe the frequent items problem

Question 9

Describe the e approximate frequent items problem

Question 9

Describe sticky sampling + pseudo + analysis of the performance + prove the correctness of the algorithm

Question 10

Prove the working memory of the sticky sampling

Question 11

Prove the correctness of the sticky sampling

Question 12

formula of the frequency of moments Fk (what are F0, F1 AND etc)

Question 13

Probabilistic counting algorithm elements + prof

Question 14

Count min sketch elements + pseudo

Question 15

Count min sketch analysis (formula/relation + dim)

Question 16

Count sketch ingredients + pseudo

Question 17

Prove that count sketch is an unbiased estimator

Question 18

Bloom filter (description + ingredients + pseudo)

Question 19

False positive rate of the bloom filter + prof