Problem Set 7. Posted 3/31. Due on 4/6.

1. Let n be a positive integer. An integer partition of n is a sequence of positive integers in non-increasing order that add up to n. For example, (2, 2, 1, 1) is an integer partition of 6. Write a recursive function that generates all integer partitions of a given positive integer n. For example, if n = 6, the function should generate:

   (6)
   (5, 1)
   (4, 2)
   (4, 1, 1)
   (3, 3)
   (3, 2, 1)
   (3, 1, 1, 1)
   (2, 2, 2)
   (2, 2, 1, 1)
   (2, 1, 1, 1, 1)
   (1, 1, 1, 1, 1, 1)
   

   The generated partitions should be stored in a 2-dimensional integer array and that should be returned. Use the following function call:

   	int[][] generatePartitions(int n)
   

2. In a Java program (or a C program or a C++ program), multiple functions can be active at the same time. For example, suppose main calls f, which in turn calls g. Then while g is executing, main, f, and g are all active. Each active function has an activation record, a chunk of computer memory which holds the arguments and local variables of the function. Another widely-used term for activation record is "stack frame". The activation records for all of the active functions are stored in the region of computer memory called the system stack. A good way to remember this is to think of the stack as ``the region of memory where all the activation records are stacked''. The activation record lives just long enough to allow a function to do its job. it is pushed onto the system stack when the function is called (becomes active) and it is popped when the function returns (becomes inactive). Once an activation record is deallocated, the memory it occupied is available for use when new activation records are created.
   1. Show how the system stack grows and shrinks when the simple recursive fibonacci function is called with n = 6.
   2. Write a version of the fibonacci function that simulates the system stack explicitly (using an implementation of the stack ADT).

3. You are given a collection with 6 items. The priorities of these items are shown below:

   1 10 25 30 40 55
   

   1. Draw all possible max-heaps (as binary trees) for this collection of items.
   2. Start with the max-heap (55, 30, 40, 25, 1, 10). Perform the following sequence of operations on this max-heap:

      Insert(45)
      Insert(35)
      Delete()
      Delete()
      

      Show the max-heap after each operation.
   3. Answer in a sentence or two: Given a max-heap can you find the item with 2nd highest priority in O(1) time? Explain your answer.
   4. Answer in a sentence or two: Given a max-heap can you find the item with smallest priority in O(1) time? Explain your answer.