Question.1 (10): Imagine we have an n-bit counter that is incremented m times. The counter starts at 0 and at each step it is incremented by 1. The cost to change the k th bit (from the right end) of the counter is 2 k . As an example, the cost of the increment 001011 => 001100 is 7. Here, the 0 th , 1 st and 2 nd bits got changed and so the cost is 2 0+2 1+2 2 = 1 + 2 + 4 =7. What is the smallest amortized cost of an increment? Use the aggregate method to derive your answer. (Hint: The amortized cost of an increment is a function of the number of increments m) Each increment changes bit 0 and cost to change the 0 th bit = 2 0 . m/2 increments change bit 1 and cost to change the 1 st bit = 2 1 m/4 increments change bit 2 and cost to change the 2 nd bit = 2 2 . m/8 increments change bit 3 and cost to change the 3 rd bit = 2 3 . So, the cost of m increments is m. 2 0 + m/2 . 2 1 + m/4. 2 2 + .... 4 points = m + m + m + …. 2 points = m . log (m) 2 points Amortized cost of an increment is m .log (m) /m = log (m). 2 points Following is also an accepted solution. m . 2 0 + floor(m/2) . 2 1 + floor(m/4) 2 2 + .... <= m + m + m + …. = m . ( log (m)+1) Amortized cost of an increment is = m . ( log (m)+1) /m = log (m) +1. Page 2 of 17 Question 2 (12): You are given n=1000 records to be sorted on a computer with a memory capacity of S=100 records. Assume that the entire S-record capacity may be used for input/output buffers, i.e. you have extra memory for a k-way loser tree. The input is on disk and consists of m runs. Assume that you use 2k buffers for input and 2 for output. Also assume that each time a disk access is made, the seek time is ts=10ms and the latency time is tl=5ms. The transmission time is tt=0.5ms per record transmitted. (a)(6) What is the buffer size, b, and the total input time for phase two of external sorting, merging, if a k-way merge scheme is used? What is the better k with respect to the total input time for phase two? Consider only k=4 and 9. (b)(4) Assume that it takes 0.5 ms to merge 10 records. Compute the total time for the phase two of external sorting, taken when k=9, i.e. compute the total time taken for input, merging and output. (c)(2) We can use either a winner tree or loser tree for the second phase of external sort. Which is expected to run faster in practice? Why? S=100 records n=1000 records m runs ts = 10 ms tl = 5 ms tt = 0.5 ms / record (a) (1) b = floor( S / (2k+2) ) = floor ( 100/ (2k+2) ) : 2 points (2) time to read a buffer = ( 10 + 5 + (1)*0.5 ) ms : 0.5 points (3) # of buffers per pass = ceiling( n / b ) = ceiling( 810 / (1) ) : 0.5 points (4) input time per pass = (2) * (3) (5) # of passes = ceiling( log m base k) : 0.5 points (6) total input time : 0.5 points = (4) * (5) k=4 : 1 point k=9 : 1 point (1) 100/10 = 10 100/20 = 5 Page 3 of 17 (2) 10+5+10*0.5 = 20 ms 10+5+0.5*5 = 17.5 ms (3) 1000/10 = 100 1000/5 = 200 (4) 20*100 = 2000 ms 17.5*200 = 3500 ms (5) log m base 4 log m base 9 (6) 2000* log m base 4 3500 * log m base 9 2000 log m base 4 / 3500 log m base 9 = 0.571 * log 9 base 4 = 0.571 * 1.585 = 0.91 k=4 is better (b) Total input time = 3500 * log m base 9 : 1 point Total output time = 3500 * log m base 9 Total merge time = (100*0.5) * log m base 9 : 2 points Thus (2*3500 + 50) * log m base 9 ms : 1 point (c) In winner tree, each node stores the winner of its two children. When the next match is to be played again between its two children, you have to find the loser of the previous match. Thus, some time is wasted. In loser tree, the loser is stored instead at each node, so the search is avoided, thus resulting a better performance in practice. Question 3 (14): a. (6) Perform insert 13 . Show the steps. b. (4) Perform delete Min from the original tree. Show the steps. c. (2) Mention the complexity for the insert, delete in a min leftist tree with n elements. d. (2) Give 1 main advantage