Note. When you are asked about the time complexity of an algorithm, the best (tightest) characterization of the order of the time complexity is implied. For example, it is correct to say that the time complexity fLS(n) of binary search is O(n). However, even though fLS(n) is also O(n 2 ), you should not say that the time complexity of linear search is O(n 2 ).

1. Three programs P1, P2, and P3 have time complexities f1(n), f2(n), and f3(n), respectively, such that f1(n) is O(f2(n)), f2(n) is O(f1(n)), f1(n) is O(f3(n)), and f3(n) is not O(f1(n)). Which of the following statements is true? (A) Program P1 is faster than P2 and P3 for very large size inputs. (B) Program P2 is faster than P1 and P3 for very large size inputs. (C) Program P3 is faster than P1 and P2 for very large inputs. (D) Program P3 is slower than P1 and P2 for very large inputs. (E) Program P1 must have the exact same running time as P2.

2. Consider the following pairs of functions: f(n), g(n). For which pair, the functions are such that f(n) is O(g(n)) and g(n) is not O(f(n))? (A) f(n) = n 2 , g(n) = 2n 2 + 7 (B) f(n) = log n, g(n) = log(n 2 ) (C) f(n) = 17, g(n) = n + 1 (D) f(n) = n, g(n) = 3000n + 1 (E) f(n) = log n, g(n) = 1/n

3. Consider a hash table of size M that initially stores n keys. Assume that the hash function maps keys uniformly across the entire table and that separate chaining is used to resolve collisions. What is the worst case time complexity of the find(k) algorithm invoked on this hash table when its parameter is a key k that is not in the table? Assume that n is much bigger than M. (A) O(1) time (B) O(n) time (C) O(M) time (D) O(n/M) time (E) O(log n) time 2

4. Consider the following algorithms, where A is an array storing n positive integer values. Algorithm foo(A, n) Input: Array A of size n for k 0 to n 1 do { if A[k] > 0 then foofoo(A, n) else A[k] A[k] 1 } Algorithm foofoo(A, n) Input: Array A of size n i 0 while i < n do { for j 0 to n 1 do { A[j] A[j] + 1 i i + 1 } } What is the worst case time complexity of algorithm foo? (A) O(n) (B) O(nk) (C) O(n 2 ) (D) O(n 2 i) (E) O(n 3 )

5. Let T be a proper binary tree with root r. Consider the following algorithm. Algorithm traverse(r) Input: Root r of a proper binary tree. if r is a leaf then return 0 else { t traverse(left child of r) s traverse(right child of r) return s + t + 1 } What does the algorithm do? (A) It computes the height of the tree. (B) It computes the number of nodes in the tree. (C) It computes the number of nodes in the tree plus 1. (D) It computes the number of leaves in the tree. (E) It computes the number of internal nodes in the tree. 3

6. The following algorithm performs a traversal of a binary tree and returns some value based on the keys stored in the nodes. Algorithm traverse2(r) Input: Root r of a binary tree. if r is a leaf then return key stored at r else { a traverse2(left child of r) if a > key stored in r then a key stored in r b traverse2(right child of r) return a b } Let the algorithm traverse2 be executed on the following tree. What is the value returned by the algorithm? (A) 3 (B) 2 (C) 0 (D) 2 (E) 5 3 2 4 6 4 r 5 1 1 2

7. A set of n keys: {k1, . . . , kn} is to be stored in an initially empty binary search tree. Which of the following statements is always true? (A) The resulting binary search tree has the same height, regardless of the order in which the keys are inserted in the tree. (B) If ki is the largest key, then in every binary search tree storing the above set of keys, the right child of the node storing ki is a leaf. (C) A preorder traversal of the tree visits the keys in increasing order of value. (D) After inserting the keys, the key stored at the root of the tree is the same regardless of the order in which the keys are inserted. (E) None of the above statements is always true.

8. Let T be a proper binary tree with 7 nodes: a, b, c, d, e, f, g. A preorder traversal of T visits the nodes in this order: b, g, d, a, c, f, e. An inorder traversal of T visits the nodes in this order: d, g, c, a, f, b, e. Which node is at distance 3 from the root of T? (Hint. In tree T, node a is the right child of node g.) (A) a (B) c (C) d (E) e (F) g 4 Part 2: Written Answers Write your answers directly on these sheets. You might find these facts useful: In a proper binary tree with n nodes the number of leaves is (n + 1)/2 and the number of internal nodes is (n 1)/2.

9. [14 marks] Write in pseudocode an algorithm that receives as input the root of a tree and it returns true if the tree is a proper binary tree (i.e. each internal node has 2 children) and false otherwise. Assume that r.children is the number of children of a node r. For example, for the tree below with root A the algorithm must return the value true, and for the tree with root B it must return the value false. B A

10. [3 marks] Compute the time complexity of the above algorithm in the worst case as a function of the number n of nodes and give its order. [4 marks] Explain what the worst case for the algorithm is and how you computed the time complexity. 5

11. [14 marks] Given an array A storing m integer values and an array B storing n integer values, write in pseudocode an algorithm subarray(A, B, m, n) that returns the value true if A is a sub-array of B and it returns false otherwise. A is a sub-array of B if there is a value 0 j n m such that A[0] = B[j], A[1] = B[j + 1], , A[m] = B[j + m 1], i.e., if the values of A appear in consecutive positions of B. For example, for the arrays A and B shown below the algorithm must return the value true, but for the arrays A and B, the algorithm must return the value false. A 8 4 7 B 1 4 7 5 8 4 7 1 5 5 A 1 5 8

12. [3 marks] Compute the worst case time complexity of the above algorithm as a function of m and n and give its order. [3 marks] Explain what the worst case of the algorithm is and how you computed the time complexity. 6

13. Consider the following algorithm. A is an array of size n. Algorithm rec(n) In: Integer value n. if n = 0 then return 1 else { i rec(n 1) A[n] i return i } [6 marks] Write a recurrence equation for the time complexity of this algorithm. [6 marks] Solve the above recurrence equation by repeated substitution and give the order of the time complexity. 7

14. Consider a hash table of size 7 with hash function h(k) = k mod 7. Draw the hash table after inserting in it, in the given order, the following values into the table: 14, 28, 2, 26, and 70: [3 marks] (a) when linear probing is used to resolve collisions [7 marks] (b) when double hashing with secondary hash function h (k) = 5(k mod 5) is used to resolve collisions. 0 1 2 3 4 5 6 Linear probing 0 1 2 3 4 5 6 Double hashing

15. [3 marks] Consider the following binary search tree. Insert the keys 15 and 10 (in that order) into the tree and show the resulting tree. You must use the algorithms described in class for inserting data into a binary search tree. 21 34 3 9 17 11 8

16. [6 marks] Consider the following binary search tree. Remove the key 13 from the tree and draw the resulting tree. Then remove the key 5 from this new tree and show the final tree (so in the final tree both keys, 13 and 5, have been removed). You must use the algorithms described in class for removing data from a binary search tree. 2 21 11 17 5 4 7 13 3 9 18 9