### Final exam practise

Hello,

I would have two questions about the MCQ in the final practise exam on Moodle.
The first one is about Q9. Could you explain the answer to this questions please ? I'm not sure to understand everything !

And a second question about Q11. Is the second pass we saw in the lecture (the pass to effectively check if the remaining values appear more than $$\theta n$$ times included in the Heavy Hitters algorithm ? If yes, I don't think should be included in the answer as it appears 3 times which is less than $$0.4*9=3.6$$.

Thanks a lot for your help !
Have a nice day,
Alessio

Top comment

Hi Alessio,

In Q9, since the distribution of delays follows a powerlaw distribution, we can use the 'friendship paradox' to understand this question. The difference is that the distribution plot is about the degree in 'friendship paradox' but the delay (waiting) time here. When we wait longer, the expected waiting time is also longer. It is very similar to 'your friends have more friends than you'.

Best,
Junze

Hi Alessio,

For Q11, the heavy-hitter algorithm, you should firstly compute $$1/\theta=1/0.4=2.5$$. Then we you go through the stream, if there are three tuples ($$|K|=3\geq1/\theta=2.5$$) in the set, then you should decrease all counts by 1. For example, when you reach 'c' first time, the set is (a:2, b:1, c:1), so you should change it to (a:1). In this way, you should get (a:2, b:1) in the end.

Best,
Junze

@junze said:
Hi Alessio,

For Q11, the heavy-hitter algorithm, you should firstly compute $$1/\theta=1/0.4=2.5$$. Then we you go through the stream, if there are three tuples ($$|K|=3\geq1/\theta=2.5$$) in the set, then you should decrease all counts by 1. For example, when you reach 'c' first time, the set is (a:2, b:1, c:1), so you should change it to (a:1). In this way, you should get (a:2, b:1) in the end.

Best,
Junze

Hi, so the Heavy hitters algorithm they talk about in this question doesn't include the final pass, where we go through all the stream to select only the value that appears more than $$\theta n$$ times ?

@junze said:
Hi Alessio,

In Q9, since the distribution of delays follows a powerlaw distribution, we can use the 'friendship paradox' to understand this question. The difference is that the distribution plot is about the degree in 'friendship paradox' but the delay (waiting) time here. When we wait longer, the expected waiting time is also longer. It is very similar to 'your friends have more friends than you'.

Best,
Junze

Hi,