COMPUTER SCIENCE: CSIS1119A INTRODUCTION TO DATA STRUCTURES AND ALGORITHMS Solutions to Midterm Examination 1.

(a) (7%) Base on rst principle (i.e., base on the mathematical denition of O, and ), prove that 5n3 + n lg n 5 is (n3 ). Solution: Let f (n) = 5n3 + n lg n 5. If f (n) is (n3 ), then n0 > 0, c1 > 0, c2 > 0 such that n n0 : 0 c1 n3 f (n) c2 n3 . Next we will show how to pick n0 , c1 and c2 . 1) Since for n 1, lg n n, we have f (n) 5n3 + n n 5 5n3 + n3 = 6n3 for all n 1. 2) f (n) = 5n3 + n lg n 5 5n3 5 = 4n3 + (n3 5) 4n3 for all n 2. From 1) and 2), we can pick n0 = 2, c1 = 4 and c2 = 6 such that n n0 : 0 c1 n3 f (n) c2 n3 , therefore, f (n) is (n3 ). (b) (7%) Base on rst principle, show that if f1 (n) is O(g(n)) and f2 (n) is O(g(n)), then f (n) = f1 (n) + f2 (n) is also O(g(n)). Solution: If a function f1 (n) is O(g(n)), Then c1 > 0, n1 > 0 s.t. 0 f1 (n) c1 g(n) , n n1 . If a function f2 (n) is O(g(n)), Then c2 > 0, n2 > 0 s.t. 0 f (n) c2 g(n) , n n2 . Therefore, we can pick c3 = c1 + c2 , n3 = max{n1 , n2 } s.t. 0 f3 (n) = f1 (n) + f2 (n) c3 g(n) , n n3 . Therefore f3 (n) is O(g(n)). 2. You have 1M (i.e., 1,048,576) bytes of memory to store a hash table structure. Assume each element occupies 10 bytes and each pointer occupies 4 bytes. We expect that about 50,000 elements will be stored in the hash table. (a) (7%) What is the expected number of element inspection in a successful search if we use chaining? (b) (7%) What is the expected number of element inspection in a successful search if we use open addressing with double hashing? Solution: Let n denote the number of elements stored in the hash table (e.g., n = 50, 000), and mc , mo denote the size of the hash table with chaining and with open addressing respectively. Next we will show how to compute mc and mo . After obtaining them, we can get the load factors and then get the solutions. 1) Chaining: The total amount of memory used for chaining is (10 + 4)n + 4mc = 1, 048, 576. n Solving this equation, we can get mc = 87, 144. The load factor ac = mc = 50,000 . 87,144 Hence the expected number of element inspections in a successful search is 1 + ac = 2 1.287. 2) Open addressing: The total memory needed is 10mo = 1, 048, 576. Therefore mo = 104, 857. The load 50,000 n factor ao = mo = 104,857 . Hence the expected number of element inspections in a 1 1 successful search is ao ln 1ao = 1.359. 1

3. (14%) The idea of recursion is to solve a larger problem by combining the solutions of problems of smaller sizes. Consider the following two recursive algorithms for solving a problem P . (a) Algorithm A solves P of size n by recursively solving two sub-problems of P of size n/2, and then combining the solutions in linear (i.e., O(n)) time. Solution: Let T (n) denote the time consumption for algorithm A solving P of size n. Then we have c1 for n = 1; T (n) = (1) 2T ( n ) + O(n) 2T ( n ) + c2 n for n 2. 2 2 Assume that n is a power of 2. i.e., n = 2k . Then we have T (n) = T (2k ) 2T (2k1 ) + c2 2k 2(2T (2k2 ) + c2 2k1 ) + c2 2k = 22 T (2k2 ) + c2 (2 2k ) ... 2i T (2ki ) + c2 (i 2k ) ... 2k T (20 ) + c2 (k 2k ) = c1 n + c2 n log2 n (c1 + c2 )n log2 n (for all n 2). Hence, we can conclude that T (n) is O(n log2 n). (b) Algorithm B solves P of size n by recursively solving two sub-problems of P of size n 1, and then combining the solutions in constant time. Solution: Let T (n) denote the time consumption for algorithm A solving P of size n. Then we have c1 for n = 1; T (n) = (2) 2T (n 1) + c2 for n 2. By telescoping, we get T (n) = 2T (n 1) + c2 = 2(2T (n 2) + c2 ) + c2 = 22 T (n 2) + c2 (2 + 1) = = 2i T (n i) + c2 (2i1 + 2i2 + + 1) = = 2n1 T (1) + c2 (2n2 + 2n3 + + 1) = c1 2n1 + c2 (2n1 1) = (c1 + c2 )2n1 c2 (c1 + c2 )2n (for all n 1). Hence, we can conclude that T (n) is O(2n ). 4. (a) (5%) Give an algorithm TREE HEIGHT(T ) to compute the height of a binary tree whose root is pointed to by T . You can assume that a node is dened with the following structure: struct tree_node { int key; int parent; /* key value */ /* parent pointer */ 2

tree_node *left; tree_node *right; }

/* left child pointer */ /* right child pointer */

(b) (12%) Give an algorithm that prints out a longest path of a tree. For example, the tree shown in Figure 1 has a height of 5 and a longest path would be A B F I J K
A

Figure 1: A tree Solution: The height of the tree is the length of the longest path from the root to a node. A longest path is a path from the root to a deepest node (whose depth is the largest). Therefore, this problem can be solved if we can get the depth of each node. The basic property is that the depth of a child node is larger than that of its parent node by 1. If the tree can be traversed in a order such that a node is visited always after its parent is visited, we can then get the depth for each node. The pre-order traversal can satisfy this requirement. The following code shows how to get the depth for each node using pre-order traversal. deepest_node is used to track the node whose depth is the largest. tree_height is used to track the length of the path from the root to deepest_node. int tree_height = 0; tree_node* deepest_node = NULL; void get_depth(tree_node* root) { if (root == NULL) { return; } if (root->parent == NULL) { //root has no parent depth(root) = 0; } else { depth(root) = depth(root->parent) + 1; } if (depth(root) > tree_height) { //track the deepest node tree_height = depth(root); deepest_node = root; } get_depth(root->left); get_depth(root->right); } 3

The height of the tree is then tree_height=depth(deepest_node). The path from the root to deepest_node is a longest path. To print it, we can rst get the path from deepest_node to the root (walking from a child node to its parent), and then reversing the path using a stack. The following procedure shows the process. void print_longest_path() { stack st; tree_node* pnode = deepest_node; while (pnode) { st.push(pnode); pnode = pnode->parent; } while (st is not empty) { tree_node* current_node = st.top(); st.pop(); print current_node->key; } } 5. Consider the following two algorithms for computing the n-th Fibonacci number. (Assume n 0.) Fib1(n) { //1 condition checking if (n <= 1) return(1); else //1 addition return(Fib1(n-1) + Fib1(n-2)); } Fib2(n) { //2 assignments previous = present = 1; //repeat n - 1 times for (i=2; i<=n; i++) { //the following code has 3 assignments and 1 addition past = previous; previous = present; present = past + previous; } return(present); } (a) (7%) What are the complexities of the algorithms? Solution: 1) Fib1 Let T (n) denote the total number of condition checking (if (n<=1)) and additions

(Fib(n-1) + Fib1(n-2)). The we can get the following recursive equation: T (n) = 1 if n = 0, 1; 2 + T (n 1) + T (n 2) if n 2.
n n

(3)

In fact, we could show that for n > 0, T (n) = ( 5 )(c1 + c2 ) c3 , where

1+ 5 1 2 , = . T (n) = (( 1+2 5 )n ).

(Please refer to Chapter 2: algorithms, slides 90-91). Hence Each condition checking or addition takes (1) time, so the

time complexity is also (( 1+2 5 )n ). 2) Fib2 The total number of variable assignments is 2 + 3(n 1) = 3n 1, and the total number of additions is n 1. They are both (n). Since each assignment or addition takes (1) time, so the time complexity is (n). (b) (6%) You will nd the complexity of Fib1 much larger than that of Fib2. Explain why Fib1 is so inecient. Solution: The reason is that when we want to compute Fib1(n), function Fib1(i) is called many times(where 1 i n 2). Take Fib1(1) as an example. Let f (n) denote the number of times Fib1(1) is called to compute Fib1(n). Then we have for n = 0 0 f (n) = 1 for n = 1 (4) f (n) + f (n 1) for n 2 We can show that f (n) is (( 1+2 5 )n ). (Please refer to Chapter 2: algorithms, slides 90-91).

6. You have m dollars to be invested in n projects, P1 , . . . , Pn . For project Pi , if your investment is x dollars, your return is fi (x) dollars. For simplicity, let us assume that all investments are in integral amounts. Let F be a two-dimensional array such that F [i][x] (for 1 i n and 0 x m) stores the value fi (x). Dene R(n, m) as the maximum return that can be obtained by investing m dollars among the projects P1 , . . . , Pn . (a) (4%) Argue that R(n, m) = max0xm {F [n][x] + R(n 1, m x)}1 . Solution: For project Pn , suppose the investment is x dollars. Then the return from Pn is F [n][x]. Now we have m x dollars left to invest on P1 , P2 , . . . , Pn1 . The maximum return that can be obtained from P1 , . . . , Pn1 is then R(n 1, m x). Therefore, the total return we can get is F [n][x] + R(n 1, m x). Since x can be 0, 1, . . . , m, the maximum return we can get is then max0xm {F [n][x] + R(n 1, m x)}. (b) (14%) Write a non-recursive algorithm that determines R(n, m). (Hint: consider using an n by (m + 1) matrix as an auxiliary data structure.) Solution: We can use an n (m + 1) matrix to store R. We use R[i][j] to denote the entry in the matrix that stores R(i, j) where 1 i n and 0 j m. Then from (a) we know that R[i][j] = max0xj {F [i][x] + R[i 1][j x]}. To compute R[i][j], we
1

The notation maxs(x) {g(x)} refers to the maximum value of g(x) such that the condition s(x) is satised.

need to ensure R[i 1][j x] is computed, where 0 j x j. Therefore, we should compute R row by row, and from the rst row to the last row. For the rst row, R[1][j] is equal to F [1][j] where 0 j m. For the other rows, we can use the formula R[i][j] = max0xj {F [i][x] + R[i 1][j x]} to compute. The following shows the algorithm. 00 void computeR() { 01 for (j = 0; j <= m; j++) { 02 R[1][j] = F[1][j]; 03 } 04 05 for (i = 2; i <= n; i++) { 06 for (j = 0; j <= m; j++) { 07 R[i][j] = 0; 08 for (x = 0; x <= j; x++) { 09 if (F[i][x] + R[i - 1][j - x] > R[i][j]) { 10 R[i][j] = F[i][x] + R[i - 1][j - x]; 11 } 12 } 13 } 14 } 15 } (c) (5%) What is the time complexity of your algorithm? Justify your answer. Solution: Line 02 is executed (m + 1) times. Line 07 is executed (n 1)(m + 1) times. For the for-loop for (j = 0; j <= m; j++), Line 09 is executed m (j +1) = (m+2)(m+1) j=0 2 times. The for-loop is repeated n 1 times, so totally Line 09 is executed (n 1) (m+2)(m+1) times. Then the time complexity is (nm2 ). 2 (d) (5%) What is the space complexity of your algorithm? Justify your answer. Solution: The space is used to store R. Since there are n(m + 1) elements in R, the space complexity is (nm). The END