Question 4.[6+2=8 points] Part a. [6 points] Ahmed wants to store some integers in a hash-table Tl of size 13 . He wants to try out some hash functions to see if they would ensure uniform distribution of the data. The following functions are available f(x),g(x) and h(x). f(x)=x%5,g(x)=(x2)%11,h(x)=(x%6)2. Insert the following data in the hash table: 3,15,17,22,19,16,27,35,46,8. Assume that collisions are resolved using linear-probing method; compute the number of collisions and probes/displacement for each of the hash functions. Part b. [2 points] For the information provided in part(a); select the best hash function. Using this hash function, insert the same data (as in part a) into the hash tables T2 of size 17. Number of collisions in T2 Number of probes/displacements in T2 Did the number of collisions and displacements decrease as the size of the table increase? Explain Question 2. [4+3+3=10 points] Part a. [4 points] Sort the elements of the following array using quick-sort approach. Show all operations (pivot positions etc.). Assume the array is already shuffled. Always choose the first element as nivnt Show all nnerations Part b. [ 3 points] Circle the correct answer Part c. [ 3 points] Heaps are an important data structure and have many applications. Assume that an array of integers is given; insert the following data in a MAX-heap (read left to right). Show all sink (heap-down) and swim (heap-up) operations for each insertion. Question 3. [ 3+3+3+3=12 points ] Part a. [ 3 points] A web-browser such as Google-Chrome, opens web-pages as you click on different links on a web-site. A stack is maintained in the browser to store the URL for all pages visited. The back-button, if pressed, would take the user to the most recent previously visited web-page. Write a method in java that returns a String array of URL links for all the pages visited by the user. The method receives a Stack of type String where each String is a URL link. The first element in the returned array should contain the most recently visited URL. NOTE: You don't want to destroy the Chrome Stack! publio string [] URL (Staok Chromestaok) Part b. [3 points] A Binary Search Tree (BST) stores keys/values following the Symmetric-order, i.e., all values smaller than a key go left, all values larger than a key go right. Write the insert method for a BST that stores integers as keys. Assume duplicates (equal keys) are not allowed. publio void insert (Node N ) \{ Part c. [3 points] In an AVL Tree, if a node to-be-deleted has two children, a candidate node needs to be found in the sub-tree. Assume an AVL Tree T that stores integers as keys, is given. Write a method that returns the candidate node in the sub-tree T. publio Node returnCandidate (AVL T) \{ Part d. [3 points] Given an adjacency-list A for a directed Graph G, write a method remove that takes an edge (v,w) as a parameter and removes this edge from the adjacency-list. It returns true if successful, false otherwise. The following is an adjacency-list for the given directed graph. Hint: The adjacency-list is an array sLL of singly-linked-lists. The array sLL position [0] is left blank intentionally; the first vertex 1 is stored at SLL[1], the next is SLL[2] and so on. publio boolean remove (int v, int w ) \{ Question 4.[6+2=8 points] Part a. [6 points] Ahmed wants to store some integers in a hash-table Tl of size 13 . He wants to try out some hash functions to see if they would ensure uniform distribution of the data. The following functions are available f(x),g(x) and h(x). f(x)=x%5,g(x)=(x2)%11,h(x)=(x%6)2. Insert the following data in the hash table: 3,15,17,22,19,16,27,35,46,8. Assume that collisions are resolved using linear-probing method; compute the number of collisions and probes/displacement for each of the hash functions. Question 1. [ 3+2+2+3=10 points] Part a. [3 points] Draw a directed weighted graph for the following edge-list. Do a BFS and DFS run starting at 0, considering the lowest weighted edge for choosing the next vertex. Part b. [2 points] Given the Alg2 method, show the recursion trace for Alg2 (0,32) call. Give the estimated run-time as a function of time T(n) and Big-Oh. public static int Alg2(int m,, int n) \{ if ( n=1) return m; else return m+Alg2(m,n/2); Part c. [2 points] Give the best Big- 0 characterization for each of the following running time estimates (where n is the size of the invut problem). Part d. [ 3 points] The following AVL tree of integer keys is given. Execute the following insertion and deletion calls on this tree. Show all rotations that apply. (i) Apply delete(28) on the given tree (ii) Apply delete(6) on the resulting tree from (i) (iii) Apply insert(17) on the resulting tree from (ii)
