4. DGIM Algorithm Based on Exercise 4.6.1: Suppose the window is as shown in Fig. 4.2. (5 points) (a) Compute DGIM estimated number of 1's the last k positions, k=5. Show all calculations, explain each step. (5 points) (b) Compute DGIM estimated number of 1's the last k positions, k=15. Show all calculations, explain each step. (5 points) (c) In each case, how far off the exact value is your estimate? Explain why the estimation can be closer or farther from the exact value. Figure 4.2: A bit-stream divided into buckets following the DGIM rules (10 points) See Section 4.6.7. Show how to extend the DGIM algorithm to count the sum of integers in the window of last N integers. Use the book as a starting point, but show detailed explanations, use hand drawings if they help you explain. Use your own words. Here your stream contains integers, not just bits. Assume that all integers are in the range between 1 and 2m so that you need m bits to represent each integer. Recall the binary representations of integers: 0001 is 2 to the zero power, or 1 0010 is 2 to the 1st power, or 2 0101=0+4+0+1=5 0100 is 2 to the 2nd power, or 4 1010=8+0+2+0=10 0111=0+4+2+1=7 Recall that the sum of integers in the bit representation is computed as Sum(x1,..,xn)=j=1:ni=mbj(i)2i=i=1:nc(i)2i