1) If you have N numbers give a modified merge sort algorithm that divides them and collects such that. It has better than N.logn complexity. a) Write the original merge algorithm. Think how the complexity is found. b) Devise any algorithmic change to improve the complexity. Any algorithm that improves is acceptable. 2) Using splay trees sort Ngroups each have M-subgroups like (N-M) a) Write an algorithm to reach from N1(group) M1 to N2(group)M2 b) Calculate the complexity 3) 25pnt 25pnt If we have some N balls with numbers want to collect some balls with the total numbers sum is B a) Write an algorithm that searches and collects these balls from the beginning of the queue Assume the balls are in a queue. Calculate the complexity b) If balls are sorted according to the numbers 0-10, 10-20,21-30 In groups. Calculate now the complexity Example: Balls enumerated 1 to 30 but which are present is not known and the desired sum 15 43. 25 pnt 4) A data machine gives may be a CPU and cache memory) data every N seconds. Fill this incoming data into an AVL tree and rotate in maximum M cycles consider also data is still coming when rotations are done. New data is inserted similar to the usual manner(in the leaves). a) Write an algorithm for this data storage device b) Can be some improvement done if data is buffered when rotations are done 25pnt (2 points) 1. State a recurrence that gives the complexity T(n) for algorithm Foo. (2 points) 2. Find the tight complexity of algorithm Foo. Bar (A[1...n]) If n1 Then Return // nothing to do Bar (A[1...[2]]) Flash(A[1...n]) End Bar. (2 points) 3. State a recurrence that gives the complexity T(n) for algorithm Bar. (4 points) 4. Find the tight complexity of algorithm Bar.