COMP 410, Fall 2012 Sample problems for Midterm Exam 1 (more to come, these are a start, will add at the end) 1) (a) Given an array A of integers, sorted into ascending order, design an efficient algorithm for finding is there is any array subscript i where A[i] == i. What is the worst case run time of your algorithm (in "Big-Oh" notation)? Answer: Here we have numbers that can be negative and positive, and they are sorted. We binary search on the array, looking for A[i]==i we can use the fact that they are sorted to decide which half to throw away each test. This approach works if we allow duplicates, or if all elements are unique values. O(log N) for N elements in the array (b) Do the same for an array A of non-negative integers, sorted in ascending order. What is the worst case run time of your algorithm (in "Big-Oh" notation)? Answer: We have two situations. First assume there are no duplicates. We now have sorted unique integers and the smallest possible element is 0. So we check to see if A[0]==0. If so, then there is some A[i]==i (at least 0, possibly more but we did not need to find them all... we just need to answer "is there some i". If A[0] is not 0 then there can be no other A[i]==i. O(1) worst case complexity. Second situation: if there are duplicates allowed Here we have 0 as the lowest possible element, but we can also have sequences of the same element in places in the array. Now, checking simply for A[0]==0 is not enough... for example, if all elements in the array are 7, then A[0] is not 0, but A[7] is 7. So we are back to doing binary search to find the answer. O(log N) wirst case. 2) Prove by induction (make sure to show the base case, the inductive hypothesis, and all steps in the proof) Sum (from k=1 to N) of k is less than N^2 for all N >= 2 Answer: base case is N=2. Sum is 1+2=3. Is 3 < 2^2? 3 < 4? yes inductive hypothesis: lets assume an M such that Sum(from k=1 to M) of k < M^2, M > 2. Now show that sum(k=1 to M+1) of k < (M+1)^2 sum(k=1 to M+1) of k is sum(k=1 to M) of k + (M+1) is sum(k=1 to M) of k + (M+1) < (M+1)^2 ? is sum(k=1 to M) of k + (M+1) < M^2 +2M +1 ? by inductive hypo. we know sum(k=1 to M) of k < M^2 we know that if a < b and c < d then a+c < b+d (rules of algebra) so can we show that (M+1) < 2M + 1 ? M < 2M ? yes if M > 0 and inductive hypo says M > 2 3) (a) Show the result of inserting these integers (in this order) into an initially empty AVL tree: 2, 1, 4, 5, 9, 3, 6, 7 Make sure to show the tree after each insertion. I can give partial credit is you give good detail. You might consider showing the patterns we used to define the various insertion situations that are possible. (b) Show the tree after doing delete 4 on the result from (a) (c) Show the tree after doing delete 9 on the result from (b) Answer: Can't easily draw it here. You can use one of the animations to check your work 4) The height of a tree that is only one node (no children) is zero. Given this, work these problems (BST is Binary Search Tree): (a) In a BST with N nodes, the maximum height is what? (in terms of N) Answer: N-1 (b) In a BST of N nodes, the minimum height is what? Answer: floor(log N) (c) In an AVL tree of 12 nodes, the maximum height is what? Answer: 4 here is one example: 12 nodes, height 4, meets AVL conditions 19 . . . . 7 31 . . . . . . . . 3 11 17 43 . . . . . . . . 2 14 34 55 . . 77 (d) In an AVL tree of 12 nodes, the minimum height is what? Answer: 3 This is the same as the height of a complete binary tree with 12 nodes. 5) Consider this algorithm: Take a complete binary tree T. We dont know anything about it except that it meets the requirements to be a complete binary tree. Start at the root. Select at random one of the children and go to that child; count that path as length 1. Select at random one of the children of this child. Go to that child and increase the path length to 2. Continue to select random children and counting the path length until you hit a leaf (node with no children). This means that if you come to a node with one child, you will take the path to that child. Lets say when we are done the path length we found is K. Using this number K give bounds on the number of nodes in this tree. Answer: TBD 6) We have a tree with the following properties: (a) It is a binary tree. (b) For each node R, all values in the subtree rooted at R's left child are smaller than the value of R; all values stored in the subtree rooted at R's right subchild are greater than R's value. This tree is a (circle one): Binary Search Tree, AVL Tree, Left-Right Topo Tree, Binary Heap Splay Tree, not something we have studied Answer: BST, AVL, SPlay all work here 7) We have a tree with the following properties: (a) It is a binary tree. (b) For any two paths P1 and P2 that go from root to a leaf, the AbsoluteValue(length(P1)-length(p2)) is either 0 or 1. This tree is a (circle one): Binary Search Tree, AVL Tree, Left-Right Topo Tree, Binary Heap Splay Tree, not something we have studied Answer: binary heap (but we are not doing binary heaps on this exam); a binary heap is structurally a complete binary tree, which has the specified property. None of the other structures given will always have the property. BTW, there is no such thing as a left-right topo tree (not that I know or anyway). 8) (a) Take an initially empty BST and show the tree after doing these insertions in this order: 2, 1, 4, 5, 9, 3, 6, 7 Show your work, show the intermediate trees so I can give partial credit in case your final tree is incorrect. (b) Show the tree you get when you do delete(4) starting with the result of (a) (c) Show the tree you get when you do delete(9) starting with the result of (b) Answer: Can't easily draw it here. You can use one of the animations to check your work 9) Take the axioms defining the STACK that we studied in class. Let's add some new behavior to get a new type we will call SWAPSTACK. We want to keep the operations we have (push, pop, top, size, empty), but we want to add this operation: swap: SWAPSTACK --> SWAPSTACK It will take a stack, and swap the top two elements. This means that if 12 is on top the initial stack, and 6 is the second element, then the resulting stack will have 6 on top, and 12 as the second element. Be careful to consider what swap does if you call it on a stack that does not contain at least two elements. Answer: None of the axioms for a normal stack will change. The "swap" operation is not canonical, so all we need to do is add axioms for how swap does on new, and how it does on push. one way: swap(new) = new swap(push(new,e)) = push(new,e) swap(push(push(S,e),f)) = push(push(S,f),e) another way: swap(new) = new swap(push(S,e)) = if empty(S) then push(S,e) else push(push(pop(S),e),top(S)) 10) Describe a data structure that will support the stack operations push, pop, top, empty, and size, as well as these two additional operations: findMax findMin These will return the largest (smallest) value stored in the stack regardless of where they are in the element order. Your data structure must allow each operation to be performed in worst-case constant time. Answer: Use a normal stack (we can use an array) and add to it two more stacks: one for min, one for max. When we push an item we not only change the top pointer, we check to see if the item pushed is larger than the item pointed to by the top of the max stack (smaller than the top of the min stack). If it is we push the array subscript of the item pushed onto the max stack (push the item location onto the min stack). When we pop, we check to see if we are popping the item that is max (top max stack); also check min. If we are then pop the max stack (min stack). All stack ops are contant time so the getMax is as well (since it is a top operation on a stack). We cannot do this simply with min and max pointers like we do top. If we pop the item that is currrent max, say, we have to find the next max by scanning the stack, which is O(N) for stack size N. 11) Consider the following data structure operations and their worst case run times. Fill in the table with numbers to demonstrate their relative efficiencies. What I want is for you to replace the ? with a number that gives the worst case run time of the algorithm on the problem size at the top of the column. If you need details to help explain your answer, you may add footnotes. Use scientific notation to help with any larger numbers. N: 4 1024 1,073,741,824 (2^30) bubble sort list of length N ? ? ? Answer: O(N^2) 16 2^20 2^60 insert in AVL tree of N nodes ? ? ? Answer: O(log N) 2 10 30 push on a stack of size N ? ? ? Answer: O(1) 1 1 1 remove from queue of length N ? ? ? Answer: O(1) 1 1 1 find in BST with ? ? ? N nodes Answer: O(N) worst case 4 1024 2^30 in-order traversal on ? ? ? a BST with N nodes Answer: O(N) 4 1024 2^30 building a BST with ? ? ? N nodes Answer: O(N^2) 16 2^20 2^60 locate item in ordered ? ? ? list of length N Answer: O(log N) binary search 2 10 30 find in splay tree with ? ? ? N nodes (remember the splay op) Answer: 2N which is O(N) 4 1024 2^30 (worst) O(log N) amortized 2 10 30 12) (a) Below are two hash tables. The left one will use linear probing to resolve collisions. The right one will hash into lists to resolve collisions. Fill in each table with the following input items in the order given left to right: alpha beta gamma delta epsilon zeta eta theta iota kappa lambda Use this hash function: take the position in the alphabet of the first third letters, add them; then multiply by the length of the word; then mod the result by 13. Example: alpha a is 1, p is 16, sum 17. 17*5 is 85. 85 mod 13 is 7 so alpha hashes to slot 7. an alphabet, with ordinal positions, for your viewing pleasure A B C D E F G H I J K L M N O P Q R S T U V W X Y Z 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 Answer: linear hash into lists probing 0: iota 0: _____ 1: _________ 1: _____ 2: delta 2: _____ --> zeta --> delta 3: zeta 3: _____ 4: _________ 4: _____ 5: eta 5: _____--> kappa --> eta 6: kappa 6: _____ 7: alpha 7: _____ --> lambda --> alpha 8: theta 8: _____ --> theta 9: gamma 9: _____ --> gamma 10: beta 10: _____ --> beta 11: lambda 11: _____ 12: epsilon 12: _____ --> iota --> epsilon (b) We ended up storing 11 items in the tables, and let's say we expected to have 11 items for storage. Was the choice of 13 for table size a good one for the linear probing table? If so, cool... if not, what size would have been better? Answer: 13 is too small, we want a load of 1/2 so we need twice as many slots as items stored... so we expected 11 so we need a prime larger than 22.. so 23 is better. We would adjust the hash function to mod 23 Same question for the hash-into-lists table... was 13 a good size? If so, cool, ... if not, what size would have been better? Answer: 13 is ok here. We want a load of 1, so with 11 items, we could do with 11 slots (11 is prime)... but 13 is prime and close to 11 so its ok too. 13) Consider this BST: gamma . . . . beta rho . . . . . . . . alpha delta kappa theta . . . . . . . . . . eta iota omicron sigma zeta . . lambda (a) list the node values in the order given by a pre-order traversal Answer: gamma beta alpha delta eta rho kappa iota omicron lambda theta sigma zeta (b) list the node values in the order given by an in-order traversal Answer: alpha beta delta eta gamma iota kappa lambda omicron rho sigma theta zeta (c) list the node values in the order given by a post-order traversal Answer: alpha eta delta beta iota lambda omicron kappa sigma zeta theta rho gamma