This is a written assignment (so late homework is not accepted); there is no electronic turn-in. The textbook problem numbers below are the same for the Java and C++ versions of the textbook.

Total: 80 points

1. (10 points) Problem 1.8 in the text, parts (a), (b)
2. (10 points) Problem 1.12 in the text, parts (a) and (b). Hint: For (b), use induction (also possible with (a)).
3. (10 points) Simplify the following expressions as much as possible using the Big-Oh notation (express each as big-oh of some function of N e.g. 3 N + log N = O(N)). You don't need to give the constants c and n₀ for this problem, but for practice, try finding them for some of your answers.

     a.) N3 + 100 N
   
     b.) 100 N4 + N log N
   
     c.) 2 N2 + N + 2100
   
     d.) 3 log log N + log2 N
   
     e.) log log (N2) + 3 log2 (N2)
   
     f.) 10 N2 + 5 N + N3 log N
   
     g.) 2.5N + N100
   

4. (10 points) Problem 2.7. Lucky for you, however, you only have to do part (a), and even that just for fragments (1) to (4). Justify your answers.
5. (10 points) Estimate the running times of the following functions using the Big-Oh notation (write your answer as big-oh of some function of N):

   int fun_a(int N) {
     if (N<=1) return 100;
     else return 2*fun_a(N-1);
   }
   
   int fun_b(int N) {
     if (N<=1) return 100;
     else return fun_b(N/2) * fun_b(N/2 - 1);
   }
   

6. (15 points total) Problem 2.20, all parts (a)-(f). For part (a), write your program as a method, similar to the example in Section 2.4.1 of the text.
   (Note: A number N is prime if the only positive integers that divide N (with remainder 0) are 1 and N itself. For example, 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, etc., are prime.)
7. (10 points) For a binary heap stored in an array, the root is stored in position 1, the parent of node i is stored in position floor(i/2), the left child is in position 2i, and the right child is in position 2i+1. What about a d-heap stored in an array? In what positions are the children and parent of node i stored? [Hint: to start, assume that the root is at position 0. Then modify your results to work with the root at position 1]
8. (5 points) The picture below is an example of a min-max heap, a data structure used to implement a double-ended priority queue. A min-max heap is a variation on the normal binary heap data structure. Like a normal binary heap, a min-max heap has the structure property that it must be a complete binary tree. However, the heap order property is a bit different for min-max heaps: every node at an even depth in the tree is smaller than its parent but larger than its grandparent, and every node at an odd depth in the tree is larger than its parent but smaller than its grandparent. A min-max heap supports the insert, deleteMin, and deleteMax operations in O(log(N)) time.
   • a.) Where is the node with the minimum priority located in the tree? Where is the node with maximum priority located?
   • b.) Extra credit: Give algorithms for the min-max heap deleteMin and deleteMax operations.