(10 points) This question is about the Misra-Gries algorithm. The elements in the stream come from...

 

Transcribed Image Text:

(10 points) This question is about the Misra-Gries algorithm. The elements in the stream come from the range [1,8]. Use k = 5. Run the Misra-Gries algorithm on the following stream (in left-to-right order). 7, 3, 1, 1, 5, 2, 7, 5, 3, 5, 8, 1, 5, 4, 4, 2, 1, 6, 8, 7, 6, 8, 7, 5, 7, 2, 5, 4, 5, 8, 4, 5, 1, 1, 5, 2, 7, 1, 2, 1, 3, 4 (a) Draw the table A and show its current content (including the elements in the table and their counts) after seeing each element in the stream. (b) Draw a table that shows the true frequencies and estimated frequencies (according to the Misra- Gries algorithm) of the values in the range [1,8]. Your table should be updated after seeing each element in the stream. (10 points) This question is about the Misra-Gries algorithm. The elements in the stream come from the range [1,8]. Use k = 5. Run the Misra-Gries algorithm on the following stream (in left-to-right order). 7, 3, 1, 1, 5, 2, 7, 5, 3, 5, 8, 1, 5, 4, 4, 2, 1, 6, 8, 7, 6, 8, 7, 5, 7, 2, 5, 4, 5, 8, 4, 5, 1, 1, 5, 2, 7, 1, 2, 1, 3, 4 (a) Draw the table A and show its current content (including the elements in the table and their counts) after seeing each element in the stream. (b) Draw a table that shows the true frequencies and estimated frequencies (according to the Misra- Gries algorithm) of the values in the range [1,8]. Your table should be updated after seeing each element in the stream.

Answer rating: 100% (QA)

Sure lets start with part a by drawing the table A and updating it after seeing each el... View the full answer