Practice Problems with Sample Solutions ---------------- 1. Consider the following class structure for (unbalanced) binary trees of integers. interface node { boolean empty(); //... } class nil implements node { public boolean empty() {return true;} //... } class vertex implements node { int item; node left, right; vertex(int h) {item=h; left=right=new nil();} // usually, only one nil is needed vertex(int h, node l, node r) {item=h; left=l; right=r;} public boolean empty() {return false;} public boolean leaf() { return left.empty() && right.empty();} ... } // 1a Write a function to return the total number of nodes in the tree. add it to the interface and both subclasses. What is its average case time complexity? in interface, add: int size(); in class nil, add: int size() {return 0;} in class vertex, add: int size() {return 1+ left.size() + right.size();} Average complexity: T(n)=2*T(n/2)+1 has O(n) solution Worst-case complexity: T(n) = T(n-1)+1, also has O(n) solution, but recursion shouldn't be used because worst case means tree is imbalanced. *** NOTE THAT FOR THIS EXAM YOU WILL NOT BE REQUIRED TO USE RECURRENCE RELATIONS IN YOUR SOLUTIONS BUT KNOWING THEM MAY WILL BE HELPFUL. They provide the best answers to the "explain why" parts of some questions. *** // 1b Write a function to search for a value in a binary search tree // Determine also its average time // complexity class by writing a recurrence relation in interface node, add: boolean search(int x); in class nil: public boolean search(int x) {return false;} in class vertex: public boolean search(int x) { return x==item || (xitem && right.search(x)); /* In case of a generic type T extends Comparable: int comp = head.compareTo(x); return comp==0 || ((comp<0 && left.search(x)) || (comp>0 && right.search(x))); Or: if (comp<0) return left.search(x); else if (comp>0) return right.search(x); else return 0; Or: node current = this; while (!current.empty()) { vertex cv = (vertex)current; if (xcv.item) current = cv.right; else return true; }//while return false; // returns false if reached nil node. */ } // or: if (comp==0) return true; else if (comp<0) return left.search(x); // else return right.search(x); T(n) = T(n/2) + 1 has O(log n) average complexity. In the case of a worst case tree, it would be T(n)=T(n-1)+1 which is O(n). 2. Given the above class for trees, consider the following code: node A = new vertex(6, new vertex(4), new nil()); Explain if the following lines of code are valid, and if not valid, whether it will cause a compiler error or runtime error: 2a. node i = A.left; compiler error: A's static type is node, not vertex 2b. node i = ((vertex)A).right; this is ok because of the type cast. 2c. int x = ((vertex)i).item; // where i is from above this will compile, but since i's dynamic type is nil, there will be a runtime type-casting exception. 4. What is the worst-case time complexity of the following operations: a. inserting into priority heap. O(log n) b. searching for a value in a priority heap. O(n) c. searching for a value in a hash table. O(n) in case of a really bad hash function. d. searching for a value in an AVL binary search tree. O(log n) e. mergesort. O(n log n). Note: mergesort can be applied to both arrays and linked lists. f. removing a value from an AVL tree. g. removing a value from the end of a circular queue. O(1). (this is an advantage of circular queues over singly linked lists). 3. Show how to augment (edit) the existing interface classes to implement an operation on trees that determines if x is an item in the tree: boolean search(int x) in node: add boolean search(int x); in nil: add public boolean search(int x) { return false; } in vertex: add public boolean search(int x) {return x==item || (xitem && right.search(x));} 3b. What are the average and worst case complexity classes of your program. Average case O(log n) because T(n)=T(n/2)+1 Worst case O(n) because T(n)=T(n-1)+1 Warning: for some functions such as size(), which must traverse the entire tree, both the average (T(n)=2T(n/2)+1) and worst (T(n)=T(n-1)+1) are O(n). But you shouldn't use recursion unless the worst case is also T(n)=2T(n/2)+1 because T(n/2) means that the depth of recursion is log(n). 3c. Given the following tree: 5 / \ 2 7 / \ / \ 1 4 6 8 \ 9 What order will the values be printed using an INORDER, PREORDER and POSTORDER traversal. INORDER (left-item-right): 1 2 4 5 6 7 8 9 (sorted order) PREORDER (item-left-right): 5 2 1 4 7 6 8 9 POSTODER (right-left-item): 9 8 6 7 4 1 2 5 (inverse of PREORDER) 4. What are the *worst-case* time complexities of the following operations: a. inserting into priority heap O(log n) b. searching for a value in a priority heap O(n) c. searching for a value in a hash table O(n) this is the absolute worst case where every value results in a hash collision. usually hash tables give O(1) search time. d. searching for a value in an AVL binary search tree: O(log n) e. Dijkstra's algorithm in general O(n*n) where n is the number of nodes, because in the worst case each node can have a direct edge to every other node. f. removing a value from an AVL tree: O(log n) g. removing a value from the end of a cicular queue: O(1) h. an in-order traversal on an AVL tree. O(n). No matter the structure, a traversal has to visit every node in the tree, and therefore will be at least O(n). To be more precise, the traversal function has time complexity approximated by the recurrence relation T(n) = 2T(n/2)+1, which has solution T(n)=2n-1. 5. Consider the following recursive function: int bif(int n) { if (n<2) return n; else return bif(n-1) * bif(n-2); } 5b. Rewrite the program using a dynamic programming matrix. This function only take one variable, so we only need a 1D array: int bif2(int n) // bottom-up solution { int[] M = new int[n+1]; // why is it n+1? M[1] = 1; // M[0] is already 0 when created for (int i=2;i<=n;i++) M[i] = M[i-1] * M[i-2]; return M[n]; } or: (top-down solution, sometimes called "memoization") Within the same class: int[] M; public int dbif(int n)// public interface function, inits matrix { M = new int[n+1]; M[1] = 1; return rbif(n); } protected int rbif(int n) { if (n>1 && M[n]==0) M[n] = rbif(n-1) * rbif(n-2); return M[n]; } // this problem has a special case for M[0]. We're using 0 for "no value", // but 0 is also the correct answer for bif(0), so we need to be specific // about when this special case applies in the code. 5c. Do the same for this: int k(int n, int c) { if (n<1 || c<2) return 0; return Math.max(k(n-1,c), k(n-1,c-2)+2); } // top down: int[][] M; // external, belongs to same class public int k(int n, int c) { M = new int[n+1][c+1]; // initialize all values to -1, which means "no value present": for(int i=0;i<=n;i++) for(int k=0;k<=c;k++) M[i][k] = -1; return ktd(n,c); } public int ktd(int n, int c) { if (M[n][c]<0) { if (n<1 || c<2) M[n][c] = 0; else M[n][c] = Math.max(ktd(n-1,c), ktd(n-1,c-2)+2); } return M[n][c]; } // note that, unlike some other DP problems, we can't use the default // value of 0 to represent "no answer present", so we had to initialized // the array to -1. // bottom-up public int kbu(int n, int c) { int[][]M = new int[n+1][c+1]; for(int i=1;i<=n;i++) for(int k=2;k<=c;k+=1) // note k+=2 each time { M[i][k] = Math.max(M[i-1][k],M[i-1][k-2]+2); } return M[n][c]; } 6. Explain the difference between nodes in the closed/interior and nodes on the open/frontier in Dijkstra's algorithm. The interior contains all nodes that we've already found the best path to. The frontier are nodes we've visited, but for which better routes may still exist. The most important step of the algorithm is to select the minimum-cost value from the frontier. 7. Insert the following nodes into an AVL tree. show when a rotation is required. 2 8 6 1 3 9. Insert additional nodes (make up your numbers) so that all 4 rotations are used. 2 \ 8 / 6 need RL rotation: 6 / \ 2 8 then: 6 / \ 2 8 / \ \ 1 3 9 now insert: 6 / \ 2 8 / \ \ 1 3 9 \ 10 this requires a RR rotation on the 8 6 / \ 2 9 / \ / \ 1 3 8 10 As a general hint: whatever tree you construct, ALWAYS make sure that it's still a binary search tree. 8. If I ask this, it would be considered one of the harder questions. Give a specific example of deleting from an AVL tree where more than one rotation is required to balance the tree. There are four distinct rotations: LL, RR, RL and LR, the rotations "RL" and "LR" should be counted as ONE rotation, not two. 8 / \ / \ 5 15 / \ / \ 3 6 10 18 / / \ / \ 1 9 12 16 20 \ 13 This is an AVL tree as the balance property is satisfied at every node But deleting the 6 will first cause a LL rotation on the left subtree, which will then decrease the height of left subtree by one, causing a new imbalance to be detected at the root node, An RL rotation centered on 8 is then needed to balance the tree. 9. Assume that you need to record the transcripts of many students. You want to be able search quickly for a student by their ID number, and you want to be able to look up the student with the highest GPA. What kind of data structure(s) would you choose to write this program with? Justify your answer. You need to search by two different criteria so two data structures with pointers to the same objects can be used. One possibility is to use a hash table to search by ID, and use a heap to search by highest GPA. A hash table has average case O(1) lookup time, but in extreme situations (worst case) it could degenerate to O(n), although as long as the IDs are not all similar, this would not happen. You can also use an AVL tree to search by ID, which would be average and worst case O(log n), but you can't use an AVL tree to search for the highest GPA since two students can have the same GPA. An answer such as "use an AVL tree" is not enough because you have to be clear as to what .compareTo is comparing. 10. Assume that you want to represent a SET of integers (these integers can, for example, index some values in an array). You want to be able to insert, delete and search for values in the set with maximum efficiency. Furthermore, you also want to be able to determine quickly both the smallest and the largest index of the "set". For example, if the set consists of {3,2,6,1,8,7}, you want to be able to determine quickly that the smallest value of the set is 1 and that the largest is 8, as well as be able to search/insert/delete other values. What kind of data structure would you use and WHY? Use a balanced binary search tree such as an AVL tree (or "red-black" tree). All described operations are worst-case log(n) time. Search for the smallest (largest) value by following the left (right) branch to the end. Because we're representing a SET, there need not be duplicates, which is one problem for balanced binary search trees. 11. In a closed hashmap, which uses a rehash function, when a value is deleted from the table the key is kept (Values[hash(key)] is set to null but not Keys[hash(key)]). Explain why? The reason is to distinguish bewteen a slot that's currently empty from a slot that was never occupied before. If we inserted: mary larz narx, all of which has the same hash value, then we deleted mary, the fact that mary's key is still in the table means that we won't quit if we're looking for larz or narx. On the other hand, if no key or value is present, then we know that nothing had ever occupied this slot (index), and therefore nothing could have been rehashed from here because of hash collision. 12. Given Optional Aopt; String A; a. Write code to print the string inside the optional if it exists Aopt.ifPresent(x -> System.out.print(x)); b. Assign A to the string inside Aopt if it exists, and to "" if it doesn't A = Aopt.orElse(""); Under no circumstances can your code throw an exception. 13. Assume: class A { public void f() {} } class B extends A { public void g() {} } ... A m = new A(); A n = new B(); // determine if there's an error in the following code, and whether // it's a compiler or runtime error: a. n = m; This is fine. the static types of n and m are both A. The pointer to the B object is changed to a pointer to the A object. b. n.f(); This calls the f() inherited from A by B c. n.g(); this is a compiler error: the static type of n is A, which doesn't have g d. ((B)n).g(); this is OK. The type cast is legal at compile-time and runtime e. ((B)m).g(); This is a runtime error. The type cast is legal at compile time but not at runtime. f. (extra) ((String)n).length()); This will not compile because String and A are unrelated classes (neither is a subclass of the other). 14. Does the following class always define a binary tree in Java? It doesn't have to be a binary "search" tree. Just a binary tree that uses null pointers to represent the empty tree. class tree { T item; tree left; tree right; } If the answer is no, give a specific example of this structure that would not be a tree. : The answer is no, because this can happen: tree t = new tree; t.item = 5; t.left = t; t.right = t.left; 15. Explain how Dijkstra's algorithm avoids cycles. : by ignoring nodes already on the interior. 15b. What is the absolute worst case time complexity of Dijkstra's algorithm in terms of the number of possible nodes (vertices) in graph. : O(n*n) (n-squared), because in the worst case there could be a direct edge from every node to every other node: the inner loop of the algorithm "for each neighbor" will therefore also run O(n) times. 15c. Given the following weighted graph A ----4----> B ----1----> F | | | 8 2 3 | | | | | | v v v C <----3---- D ----3----> E Apply Dijkstra' single-source shortest path algorithm to source node A Apply Dijkstra' single-source shortest path algorithm to source node B For A, order of nodes in interior Interior | Frontier order taken from frontier ------------------- (A,0,_) | (A,0,_) 1 (B,4,A) | (B,4,A) 2 | (C,9,A) * (replaced by better node) | (D,6,B) 4 (F,5,B) | (F,5,B) 3 | (E,8,F) 5 (D,6,B | (C,8,D) 6 (E,8,F) (C,8,D) 16. Apply the Needle-Wunsch algorithm to the following sequences: A= .ATGACTG B= .TGATGC with the following scoring scheme: int score(int i, int k) { if (A.charAt(i)==B.charAt(k)) return 1; else return 0; } int w() {return 0;} Show the matrix generated by the algorithm. Display one optimal alignment (traceback) (without the . at the front) ATGACTG- ||| || -TGA-TGC Alignment score: 5 . T G A T G C . 0 0 0 0 0 0 0 A 0 0 0 1 1 1 1 T 0 1 1 1 2 2 2 G 0 1 2 2 2 3 3 A 0 1 2 3 3 3 3 C 0 1 2 3 3 3 4 T 0 1 2 3 4 4 4 G 0 1 2 3 4 5 5 How about under the following Scheme: int score(int i, int k) { if (A.charAt(i) == B.charAt(k)) return 2; else return -1; } int W() { return -1; } ATGACTG- ||| || -TGA-TGC Alignment score: 7 . T G A T G C . 0 -1 -2 -3 -4 -5 -6 A -1 -1 -2 0 -1 -2 -3 T -2 1 0 -1 2 1 0 G -3 0 3 2 1 4 3 A -4 -1 2 5 4 3 3 C -5 -2 1 4 4 3 5 T -6 -3 0 3 6 5 4 G -7 -4 -1 2 5 8 7