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
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'.
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.
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 ?
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'.
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
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
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 ?
Hi,
Ok I see, thanks a lot for your answers !
Yes, I think the output means the final set in this question. Just like the example in the lecture (page 10).
Add comment