Recursion and Recurrences
Introduction
The purpose of this assignment is to gain experience analyzing recursive algorithms and solving recurrences.
Exercise 1 (Solution Provided)
Take a minute to read the following class and make sure you understand how it works:
/**
* Recursive algorithm to find the largest sum of 4 consecutive elements.
*/
public class Recur1 {
/**
* Finds the largest sum of 4 consecutive elements in the entire array.
*
* @param nums the array to search
* @return the largest sum of 4 consecutive elements
* @throws IllegalArgumentException if array has fewer than 4 elements
*/
public static int largestFour(int[] nums) {
if (nums == null || nums.length < 4) {
throw new IllegalArgumentException("Array must have at least 4 elements");
}
return largestFour(nums, 0, nums.length - 1);
}
/**
* Finds the largest sum of 4 consecutive elements in the given range.
*
* @param nums the array to search
* @param start the starting index (inclusive)
* @param end the ending index (inclusive)
* @return the largest sum of 4 consecutive elements
*/
public static int largestFour(int[] nums, int start, int end) {
int size = (end - start) + 1;
if (size == 4) {
int sum = 0;
for (int i = start; i <= end; i++) {
sum += nums[i];
}
return sum;
}
int maxLeft = largestFour(nums, start, end - 1);
int maxRight = largestFour(nums, start + 1, end);
return Math.max(maxLeft, maxRight);
}
}
Our goal is to analyze the running time of this algorithm. To make things concrete, we'll select array accesses as the basic operation and develop a formula that describes the number of operations as a function of the input size.
Doing this carefully will involve completing several steps:
- Develop a recurrence relation that describes the number of steps performed by the algorithm.
- Find the closed-form solution of the recurrence relation.
- Check our solution by plugging in several values of \(n\) into the recurrence relation and the closed-form answer to make sure we get the same numbers from both. (This doesn't prove that our solution is correct, but it provides a helpful sanity check.)
- Instrument our code to empirically track the number of operations performed, and compare the results to our analytical solution. This allows us to verify that our recurrence relation correctly describes the amount of work done by the algorithm.
Go ahead and attempt to complete these steps for the code provided above. If you get stuck, we've provided solutions below. There is nothing to submit for this exercise.
Solution
-
Develop a recurrence
Initial Conditions:
\(~~~~~~T(4) = 4\)
The base case occurs when the input subarray has size four, all four array elements are accessed.
Recurrence relation:
\(~~~~~~T(n) = 2T(n-1)\)
In the recursive case, there are no array accesses, but we do make 2 recursive calls, each of which has size \(n-1\).
-
Solve the Recurrence
Perform substitutions until we find the general form:
\(i\) Substitution Simplified Form Scratch Paper 1 \(T(n) = 2T(n-1)\) \(2T(n-1)\) \(T(n-1) = 2T((n-1) -1) = 2T(n-2)\) 2 \(= 2(2T(n-2))\) \(2^2T(n-2)\) \(T(n-2) = 2T((n-2) -1) = 2T(n-3)\) 3 \(= 2^2(2T(n-3))\) \(2^3T(n-3)\) \(\vdots\) \(\vdots\) \(\vdots\) \(\vdots\) \(i\) \(2^iT(n-i)\) Solve for the number of substitutions required to reach the base case:
\(n - i = 4\)
\(i = n-4\)
Substitute \(i = n-4\) into our general form:
\(T(n) = 2^{n-4}T(n-(n-4)) = 2^{n-4}T(4) = 2^{n-4}(4) = 2^{n-4}(2^2) = 2^{n-2}\)
-
Check the solution against the recurrence
Let's verify our closed-form solution by comparing it to values computed using the recurrence relation:
n Recurrence Calculation Closed Form Match? 4 \(T(4) = 4\) (base case) \(2^{4-2} = 2^2 = 4\) ✓ 5 \(T(5) = 2T(4) = 2 \cdot 4 = 8\) \(2^{5-2} = 2^3 = 8\) ✓ 6 \(T(6) = 2T(5) = 2 \cdot 8 = 16\) \(2^{6-2} = 2^4 = 16\) ✓ The values match, providing confidence that our closed-form solution is correct.
-
Instrument the code
Now let's instrument the code so that we increment a counter every time a basic operation occurs. Newly added lines are highlighted.
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 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 | |
n = 4, Operations = 4
n = 5, Operations = 8
n = 6, Operations = 16
n = 7, Operations = 32
This matches the answers provided by our closed-form formula, which suggests that our analysis is correct.
Exercise 2
Repeat the exercise above with the following class. Once again, you should use array accesses as the basic operation. For this exercise you will submit your answers through Gradescope. Your submission should include:
- Clearly written answers for steps 1-3 above. These can be scans of neatly handwritten answers, or they may be prepared electronically. Overleaf is a good option for producing nicely formatted mathematical formulas. (You have institutional access through JMU). For full credit, you must show all steps of your solution.
- A completed version of the class below. You should add instrumentation code and complete the
closedFormmethod so that it encodes the closed-form solution you determined in steps 1-3. You should also add testing code to the main to confirm that your results match your expectations.
You may use the ArrayGenerator.java utility class to create sample arrays in your main.
public class Recur2 {
static int opCount = 0;
/**
* Adds all elements in a subarray from start to end (inclusive).
*
* @param nums the array
* @param start the starting index (inclusive)
* @param end the ending index (inclusive)
* @return the sum of elements in the range
*/
public static int addSubarray(int[] nums, int start, int end) {
int sum = 0;
for (int i = start; i <= end; i++) {
sum += nums[i];
}
return sum;
}
/**
* Finds the largest sum of 4 consecutive elements in the entire array.
*
* @param nums the array to search
* @return the largest sum of 4 consecutive elements
* @throws IllegalArgumentException if array has fewer than 4 elements
*/
public static int largestFour(int[] nums) {
if (nums == null || nums.length < 4) {
throw new IllegalArgumentException("Array must have at least 4 elements");
}
return largestFour(nums, 0);
}
/**
* Finds the largest sum of 4 consecutive elements starting from a given position.
*
* @param nums the array to search
* @param start the starting position to consider
* @return the largest sum of 4 consecutive elements
*/
public static int largestFour(int[] nums, int start) {
int size = nums.length - start;
if (size == 4) {
return addSubarray(nums, start, nums.length - 1);
}
int firstFour = addSubarray(nums, start, start + 3);
int maxRemaining = largestFour(nums, start + 1);
return Math.max(firstFour, maxRemaining);
}
/**
* Closed-form solution for the recurrence relation T(n) of the largestFour algorithm. Completing
* this method will enable the autograder to check your closed-form answer.
*
* @param n the input size (array length)
* @return the number of array access operations T(n) predicted by your closed-form solution
*/
public static int closedForm(int n) {
return -1; // TODO: Replace with your closed-form solution
}
/**
* Test method to demonstrate the largestFour algorithm.
*/
public static void main(String[] args) {
// TODO: YOUR CODE HERE
}
}
Exercise 3
Repeat the process with the class below, again using array accesses as the basic operation.
In order to simplify the analysis, we will assume for this problem that the array size is a power of two and is greater than or equal to 4.
public class Recur3 {
static int opCount = 0;
/**
* Computes a hash value for the entire array.
*
* @param arr the array to hash
* @return the computed hash value
*/
public static int computeHash(int[] arr) {
return computeHash(arr, 0, arr.length - 1);
}
/**
* Recursively computes hash for a subarray using divide-and-conquer.
*
* @param arr the array
* @param start the starting index (inclusive)
* @param end the ending index (inclusive)
* @return the computed hash value for the range
*/
private static int computeHash(int[] arr, int start, int end) {
int size = end - start + 1;
if (size <= 4) {
int h = 0x9e3779b9; // arbitrary seed
for (int i = start; i <= end; i++) {
h = h * 31 + arr[i];
}
return h;
}
int mid = (start + end) / 2;
int leftHash = computeHash(arr, start, mid);
int rightHash = computeHash(arr, mid + 1, end);
int combine = 0;
for (int i = start; i <= end; i++) {
combine += arr[i];
}
return leftHash ^ rightHash ^ combine; // arbitrary mixing
}
/**
* Closed-form solution for the recurrence relation T(n) of the computeHash algorithm. Completing
* this method will enable the autograder to check your closed-form answer.
*
* @param n the input size (array length)
* @return the number of array access operations T(n) predicted by your closed-form solution
*/
public static int closedForm(int n) {
return -1; // TODO: Replace with your closed-form solution
}
/**
* Test method to demonstrate the hash computation algorithm.
*/
public static void main(String[] args) {
// TODO: YOUR CODE HERE
}
}