COMP 410 (updated Fall 2015) Sample problems for Midterm Exam 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)? (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)? 2) (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) 3) 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) (b) In a BST of N nodes, the minimum height is what? (c) In an AVL tree of 12 nodes, the maximum height is what? (d) In an AVL tree of 12 nodes, the minimum height is what? 4) Consider this algorithm: Take a Complete Binary Tree T. We dont know anything about it except that it meets the requirements to be a BST. 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. 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. 5) 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 or more): Binary Search Tree, AVL Tree, Left-Right Topo Tree, Binary Heap Splay Tree, not something we have studied 6) 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 or more): Binary Search Tree, AVL Tree, Left-Right Topo Tree, Binary Heap Splay Tree, not something we have studied 7) (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) 8) 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. 9) 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. 10) 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 ? ? ? insert in AVL tree of N nodes ? ? ? push on a stack of size N ? ? ? remove from queue of length N ? ? ? find in BST with ? ? ? N nodes in-order traversal on ? ? ? a BST with N nodes building a BST with ? ? ? N nodes locate item in ordered ? ? ? list of length N find in splay tree with ? ? ? N nodes (remember the splay op) 11) 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 (b) list the node values in the order given by an in-order traversal (c) list the node values in the order given by a post-order traversal 12)(a) Show the result of inserting these integers (in this order) into an initially empty Splay tree: 8, 1, 4, 2, 5, 15, 7, 3, 6 Make sure to show the tree after each insertion. I can give partial credit if 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 7 on the result from (b) (d) Show the tree after doing find 2 on the result from (c) (e) Show the tree after doing find 6 on the result from (d) 13) a) Take the following numbers and show the Binary Heap that results from build it by 13 inserts (in the order shown) (draw it as a tree) 12, 3, 17, 45, 0, 1, 14, 9, 55, 73, 5, 21, 34 b) Take the same numbers and show the heap that results from O(N) direct build method (draw as a tree) c) Show the array that represents the heap tree from part (b) 14) Give a tight big-Oh run-time analysis in terms of N for each of the following code fragments. a) public static long A (int N) { if (N <= 1) return 1; return N * (N-1) * A (N - 1); } b) sum = 0; for (int i = 0; i < N; i++) for (int j = 0; j < i; j++) sum++; c) sum = 0; for (int i = 0; i < N; i++) for (int j = 0; j < i*i; j++) for (k=0; k < j*j; k++) sum++; 15) a) For the following minimum binary heap (drawn as a complete binary tree) fill the items into the array below in the correct positions for the way a binary heap is normally represented with an array. 4 . . . . . . 11 6 . . . . . . . . . . . . 13 21 8 23 . . . . . . . . . . . . 27 14 29 33 12 19 _______________________________________________________________ | | | | | | | | | | | | | | | | | array: |___|___|___|___|___|___|___|___|___|___|___|___|___|___|___|___| 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 b) Using this array representation, show the subscript calculations needed to find the children of the node with value "13" c) Using this array representation, show the subscript calculations needed to find the parent of the node with value "33" 16) For the heap in problem (15), show the heap that results after doing a single removeMin operation. Show the steps involved in rearranging the heap elements so that the new minimum ends up at the root. Show the head both in the binary tree representation and in the array implementation. 17) For the following items in the order given, construct a minimum binary heap. Use the O(N) "build" algorithm we studied. Show the steps in your work. 6, 3, 29, 21, 7, 2, 19, 24, 8, 4, 61, 16, 9 18) a) Do the same as problem (16) for the heap built in problem (17). b) Starting with the heap built in (17) show the heap that results from doing insert(11). Show both the tree and the array.