Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: daixieit

CS430 Midterm Version B

1.     We have 6 algorithms  ,  ,  ,  ,  ,  for the same problem with following exact running times (in terms of the input size ):  3, 48, 2 lg  , log4  , 32  and  3  milliseconds, respectively. Right now, with different input       sizes, all 6 algorithms finish their jobs using exactly 64 milliseconds. And then, the input size of each algorithm becomes halved. Order these 6 algorithms, in non-decreasing order, based on how much time each of them     needs to finish its job (after the input size is halved). Show your work.

2.    Assume that you are given an algorithm TWO-THIRDS([ ]) that returns the  of the ⌈ (which is about 2/3 of the subarray size) smallest element in subarray [ ] in linear time.

a.     Given an array of size  , present pseudo code of a simple, efficient algorithm that uses this algorithm TWO-THIRDS([ ]) to find the  ℎ  smallest element in the array. Note that, do not use the    algorithm SELECT(. ) that we learned in class.

b.    Analyze the worst-case time complexity of your algorithm.

 

3.     Remind that, given a node  in a binary search tree  , we define ’s successor as the next node to visit in an       inorder tree walk in  . Now, instead of an inorder tree walk, we re-define ’s successor as the next node to visit in a    in  .

a.     Given a node  in a binary search tree  , present pseudocode of an efficient algorithm POST- SUCCESSOR() that finds the ’s successor using the new definition .

b.     Given a binary search tree  with  nodes, show that 1 call to TREE-MINIMUM() following by  − 1 calls to POST-SUCCESSOR(. ) run in Θ() time.

4.     Professor invented a data structure called    () . It is maintained on a complete binary tree. In each node  , as usual, there is a pointer to its parent and two pointers to its children; however, there    store two number attributes:  .  and  .  . A  behaves like a min binary heap with regard to all the ’s in    the structure, and it behaves like a binary search tree with regard to all the ’s in the structure.

a.     Given a  with  nodes, present an algorithm that finds the node  with the minimum  .  +  .  value in Θ(lg ) time.

b.     Proof that your algorithm gives the expected result within required time in a few sentences.