15-121 SPRING 2010 [CORTINA]

HOMEWORK 3 - due Tuesday, February 2

WRITTEN PROBLEMS (10 pts)

(1 pt) Assume that strings s1 and s2 have n characters each, where n ≥ 0.
1. What is the worst-case runtime complexity of the following operation in big-O notation in terms of n? Explain your answer.
```
System.out.println(s1.indexOf('a'));
```
2. What is the best-case runtime complexity of the following operation in big-O notation in terms of n? Explain your answer.
```
System.out.println(s1.equals(s2));
```

(2 pts) What is the runtime complexity of the following code fragments in big-O notation as functions of m and/or n? Explain each answer. (Your answers should represent the tightest/closest function for the code given.)

int sum = 0;
for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j+=2)
                sum += (i+j);

int sum = 0;
for (int i = 1; i <= 50; i+=2)
        for (int j = 1; j <= n; j+=3)
                sum += (i+j);

int sum = 0;
for (int i = 1; i <= m; i++)
	for (int j = 1; j <= n; j*=2)
		sum += (i+j);

int sum1 = 0;
for (int i = 1; i <= m*m; i++)
     sum1 += i;
int sum2 = 0;
for (int j = 1; j <= m; j++)
     sum2 += j;

(1 pt) Consider the following Java method that returns true if an array of n integers has two adjacent values that are the same, false otherwise:
```
public static boolean adjacentDuplicates(int[] a) {
	for (int i = 0; i < a.length-1; i++)
		if (a[i] == a[i+1])
			return true;
	return false;
}
```
1. What is the runtime complexity of this method using big-O notation in the worst case? Explain your answer.
2. What is the runtime complexity of this method using big-O notation in the best case? Explain your answer.
(1.5 pts)
1. Suppose an algorithm processes n data elements using exactly n² operations, where n = 8. If we double the number data elements, how many additional operations will the algorithm perform? Show your work.
2. Suppose an algorithm processes n data elements using exactly log₂n operations, where n = 8. If we double the number data elements, how many additional operations will the algorithm perform? Show your work.
3. Suppose an algorithm processes n data elements using exactly 2ⁿ operations, where n = 8. If we double the number data elements, how many additional operations will the algorithm perform? Show your work.
(1.5 pts) Given an array of integers in increasing order, and given a target sum, we wish to determine if the array contains two integers that can be added together to make that sum.
1. What is the worst-case runtime complexity (in big-O notation) of the following solution if the length of the array is n? Briefly explain your answer.
```
public static boolean sumInArray(int[] a, int sum) {
	//finds sum of all pairs in the array
	for (int i = 1; i < a.length; i++)
	        for (int j = 0; j < i; j++)
	                if (a[i] + a[j] == sum)
	                        return true;
	return false;
}
```
2. Describe an algorithm (or give computer code) that performs better asymptotically than the algorithm above. Determine the worst-case runtime complexity of your algorithm.
(3 pts) Given n data values, an algorithm processes these n data values with a running time given by the equation T(n) = 6n² + 15n + 75.
1. Show that T(n) = O(n²) by using the formal definition of the big O function.
2. Is T(n) = O(n³)? Explain.
3. Is T(n) = O(n)? Explain.

PROGRAMMING PROJECT (10 pts)

Let A be an array of integers (some integers can be negative). Assume that the array is of size n. The subarray A[i..j] is the part of the array that starts at index i and ends at index j, where 0 ≤ i ≤ j ≤ n-1. Let s_ij equal the sum of the integers in A[i..j].

We wish to solve the following problem:

Find the maximum value for s_ij over all subarrays in array A, where 0 ≤ i ≤ j ≤ n-1.

The three algorithms given below solve this problem. NOTE: If all of the values in the array are negative, then the maximum value for s_ij is 0 by default.

Example: If the array contains the values { -1, 12, -3, 14, -4, 3 }, then the maximum sum over all subarrays is 23 (for the subarray {12, -3, 14}). If the array contains the values { 2, -3, 5, -1, 0, 7}, then the maximum sum over all subarrays is 11 (for the subarray {5, -1, 0, 7}).

ALGORITHM 1

Start with a maximum sum of 0. Compute the sum of each 1-element subarray, then compute the sum of each 2-element subarray, then compute the sum of each 3-element subarray, etc. For each sum you compute, if it is larger than the maximum sum you've seen, then it becomes the maximum sum.

ALGORITHM 2

Start with a maximum sum of 0. Compute the sum of each subarray that starts at index 0, then compute the sum of each subarray that starts at index 1, then compute the sum of each subarray that starts at index 2, etc. For each sum you compute, if it is larger than the maximum sum you've seen, then it becomes the maximum sum.
EFFICIENCY NOTE: Once you compute the sum of the subarray from A[i] to A[j], the sum of the subarray from A[i] to A[j+1] is just the previous sum you computed plus A[j+1]. Don't add up all of the previous values all over again.

ALGORITHM 3

Start with a maximum sum of 0. Compute the sum of all subarrays starting from index 0. Use the efficiency note from Algorithm 2. If the sum you compute is negative, start computing the sum of all subarrays starting from the next index in the array. Repeat this special rule if necessary. For each sum you compute, if it is larger than the maximum sum you've seen, then it becomes the maximum sum.
For example, as you compute the sum of all subarrays starting from index 0, if you find the sum of the integers in A[0..5] is negative, then compute the sum of all subarrays starting from index 6 next. If the sum of the integers from A[6..14] is negative, then compute the sum of all subarrays starting from index 15, Etc.

You are to write a Java program that determines the amount of work each of these algorithms does to compute its answer for arrays of various sizes. Using this data, you are to determine the runtime complexity of each algorithm.

Programming Requirements

Write a class MethodTester that contains a main method and three static helper methods, one to implement each algorithm above. Your main method should test your methods with small arrays (like the ones in the examples above) so you know they work correctly before moving on.
Once you know the algorithms work correctly, write another class named RuntimeAnalyzer that contains the same helper methods. Modify each helper method so that it returns the number of assignment statements that it performs rather than the maximum sum over all subarrays. Do this by adding a counter to each algorithm that starts at 0 and increments each time you do an assignment statement. You should decide what qualifies as an assignment statement. Be consistent across algorithms so you can compare the algorithms against each other.
NOTE CORRECTION IN RED: Write your main method for this class so it will run your algorithms for randomly generated arrays of size 5, 10, 15, ..., up to 50. Each array should have random values between -10 and 99, inclusive, and you can have duplicates. (To generate a random number between x and y, use the following Java expression: (int)(Math.random()*(y-x+1) + x).) For each array size, generate 2000 arrays (one at a time) and run the algorithms with each array, averaging the returned number of assignment statements executed for each algorithm separately.
Your program should output your results in tabular format, as shown below (XXXX indicates where your results will be, display integers only, no floating point values):
```
AVERAGE NUMBER OF ASSIGNMENT STATEMENTS
EXECUTED OVER 2000 TRIALS:

size	Alg1	Alg2	Alg3
5	XXXX	XXXX	XXXX
10	XXXX	XXXX	XXXX
15	XXXX	XXXX	XXXX
20	XXXX	XXXX	XXXX
25	XXXX	XXXX	XXXX
30	XXXX	XXXX	XXXX
35	XXXX	XXXX	XXXX
40	XXXX	XXXX	XXXX
45	XXXX	XXXX	XXXX
50	XXXX	XXXX	XXXX
```
Once you complete your second program and generate your final data, enter the data into a spreadsheet and plot one graph for each algorithm, comparing the number of data values in the array (n) along the x-axis against the number of assignment statements computed along the y-axis.
Based on the curves, determine the runtime complexity (in big O notation) of each algorithm. Enter your answers in a comment at the beginning of each helper method of the RuntimeAnalyzer class. Your answer should include the runtime complexity and a short explanation of why you believe your answer is correct based on the algorithm given.

Hand-In Instructions & Late Submissions

Your submitted zip file should include your Java source code, and an Excel spreadsheet that includes the data you collected when you ran the program along with the associated graphs.

See the course website for instructions on how to hand in your program and the policy for late submissions.

15-121 SPRING 2010 [CORTINA]

HOMEWORK 3 - due Tuesday, February 2

WRITTEN PROBLEMS (10 pts)

PROGRAMMING PROJECT (10 pts)

Find the maximum value for sij over all subarrays in array A, where 0 ≤ i ≤ j ≤ n-1.

ALGORITHM 1

ALGORITHM 2

ALGORITHM 3

Programming Requirements

Hand-In Instructions & Late Submissions

Find the maximum value for s_ij over all subarrays in array A, where 0 ≤ i ≤ j ≤ n-1.