22C:21: Computer Science II: Data Structures

## Homework 1: Due October 22, 2004

1. Let A be an array of integers. We say that A is bitonic if the elements of A are first strictly increasing and after reaching a maximum value, they are strictly decreasing. More precisely, suppose that A has n elements. Then for some index j, 0 ≤ jn-1, the array A is strictly increasing up to element A[j], that is,
```	A[0] < A[1] < ... A[j]
```
and is strictly decreasing after that, meaning
```	A[j] > A[j+1] > ... > A[n-1].
```
Note that j could be 0 or n-1. Write a recursive java function called findMax that takes a bitonic integer array of size n and returns the maximum element. The function header should be
```	int findMax(int[] A, int n)
```
In the above, n refers to the size of A. The function is required to run in O(log(n)) time, which means you cannot just scan the entire array. Instead, you should mimic the binary search algorithm.

What to submit: A printout of just the function findMax.

2. This problem relates to the "Computing Change in Postage Stamps" (pages 86-88 in your textbook). Take the efficient solution to this problem (bottom of page 87 and top of page 88) and extend it to return the actual smallest change, rather than just the size of the smallest change. Here are some hints on how to do this. Currently, the function uses an int array answer so that answer[i] contains the size of the smallest change for the integer i. Change this, so that answer[i] is itself an int array of size 3 so that

• answer[i][0] contains the number of pennies used to make smallest change for i,
• answer[i][1] contains the number of 21 cent coins used to make smallest change for i, and
• answer[i][2] contains the number of 37 cent coins used to make smallest change for i.

This also implies that the last line of code on page 87 should now be

```		return stampCount(amount, new int[amount+1][3]);
```
and the function header at the beginning of the next page should be
```		protected static int stampCount(int amount, int[][] answer)
```
Use the above function to compute smallest change for 1000.

What to submit: A printout of the two modified functions, both called stampCount. Also, the smallest change for 1000.

3. Our goal in this problem is to design and implement a class called IntMultiSet, whose objects can be used to store multi-sets of non-negative integers. A multi-set is a collection of items that may contain multiple copies of the same item, supporting the following operations:

1. A.isMemberOf(int x): returns true if x is a member of the multi-set A; false otherwise.
2. A.Union(IntMultiSet B): returns the union of multi-sets A and B.
3. A.Intersection(IntMultiSet B): returns the intersection of multi-sets A and B.
4. A.addElement(int x): returns the multi-set obtained by adding the element x to A.

For example, suppose that A is {1, 2, 2, 2, 3, 7, 10, 10} and B is {2, 2, 4, 4, 4, 7, 7, 9, 9}. Then the functon call A.isMemberOf(i) would return true for values of i equal to 1, 2, 3, 7, or 10 and would return false for every other value of i. The function call A.Union(B) returns {1, 2, 2, 2, 2, 2, 3, 4, 4, 4, 7, 7, 7, 9, 9, 10, 10} and the function call A.Intersection(B) returns {2, 2, 7}. The function call A.addElement(7) returns {1, 2, 2, 2, 3, 7, 7, 10, 10}. Let us now suppose that when a user constructs a multi-set she knows the largest integer the multi-set can ever contain. Given this assumption, we can simply use an int array, let us call it count, to represent a multi-set with the understanding that count[i] tells us how many copies of i there are in the multi-set. The size of count is simply 1 plus the largest integer the multi-set can ever contain. Implement the IntMultiSet class consisting of the following 6 methods:

1. IntMultiSet(int n): a constructor that constructs an empty multi-set, such that n is the largest integer it can ever contain. The pre-condition is that n is positive.
2. int size(): returns the number of elements in the multi-set.
3. boolean isMemberOf(int x): returns true if x is a member of the multi-set; false otherwise.
4. IntMultiSet Union(IntMultiSet B): returns the union of multi-set B with this multi-set. The pre-condition is that the largest element that either set can contain is identical.
5. IntMultiSet Intersection(IntMultiSet B): returns the intersection of multi-set B with this multi-set. The pre-condition is that the largest element that either set can contain is identical.
6. IntMultiSet addElement(int x): returns the multi-set obtained by adding the element x to this set. The pre-condition is that x is non-negative and is no greater than the largest element that the multi-set can contain.

What to submit: A printout of the entire IntMultiSet class.

4. Extend the class IntMultiSet to MultiSet so that a user can construct arbitrary multi-sets rather than just multi-sets of non-negative integers. We start by assuming that when a user constructs a MultiSet object, she provides the universal set, that is the set of all items that may ever end up in the multi-set. Given this assumption, IntMultiSet can be extended to MultiSet by adding an array called Map as a field to the MultiSet class. The array Map simply contains the universal set. Then the meaning of values in the array count is the following: count[i] tells us the number of copies of the object Map[i] that the multi-set contains. Implement the MultiSet class consisting of the following 6 methods. These are the same as those in the IntMultiSet class. I am describing these again for the sake of completeness.

1. MultiSet(Object[] universalSet): a constructor that constructs an empty multi-set, such that any elements the multi-set can ever contain are in universalSet.
2. int size(): returns the number of elements in the multi-set.
3. boolean isMemberOf(Object x): returns true if x is a member of the multi-set; false otherwise.
4. MultiSet Union(MultiSet B): returns the union of multi-set B with this multi-set. The pre-condition is that the universal sets of B and this set are identical.
5. MultiSet Intersection(MultiSet B): returns the intersection of multi-set B with this multi-set. The pre-condition is that the universal sets of B and this set are identical.
6. MultiSet addElement(Object x): returns the multi-set obtained by adding the element x to this set. The pre-condition is that x belongs to the universal set of this multi-set.

What to submit: A printout of the entire MultiSet class.

5. Given that we know how to implement a MultiSet class, let us revisit Problem 2. The reason for revisiting Problem 2 is that change for a number can naturally be represented as a multi-set, whose universal set is the set of all denominations. Rewrite the two stampCount functions from Problem 2, letting each answer[i] be a multi-set with universal set {1, 21, 37}.

What to submit: A printout of the two modified functions, both called stampCount.

6. In this problem you are asked to perform experiments to compare the performance of quickSort and randomizedQuickSort. The difference between quickSort and randomizedQuickSort is that quickSort uses the function partition, whereas randomizedQuickSort uses the function randomizedPartition. To perform the experiments, generate for each value of n, 10 integer arrays of size n, run both quickSort and randomizedQuickSort on each of the 10 arrays, time each run, and report the mean running time (taken over the 10 runs) for quickSort and for randomizedQuickSort. Do this for the following values of n: 1000, 2000, 3000, ..., 10,000 and make a plot of running times, one for quickSort and another for randomizedQuickSort. Write 4-5 sentences summarizing your observations, based on these plots. Consider the following questions:

• Which implementation is faster?
• How does the running time seem to grow, as a function of n, for each implementation?

Generate each size-n integer array in the following manner. Start by assigning the integer i to slot i in the array. Thus the array starts off with entries 0, 1, 2, ..., n-1 in that order. Then do the following 20 times: pick a pair of indices i and j, at random, in the range [0, n-1], and swap the elements in slots i and j. After this is done, we may no longer have a sorted array, but the array will still be "almost sorted''. Our expectation for "almost sorted'' inputs is that quickSort should run in O(n^2) and will clearly be slower than randomizedQuickSort, which runs in O(n log(n)) time, on an average, independent of the type of input.

What to submit: A printout of the two plots and the summary of your observations.

7. What is the running time of the following code fragment as a function of n? Express your answer in the Big-Oh notation. Show all the steps you took in coming up with your answer.
```	int i = n;
int j;
while(i >= 10)
{
i = i/3;
for(j = 0; j < n; j++)
System.out.println("In the inner loop");
}
```

What to submit: Your derivation of the running time of the above code fragment.

8. In Bailey's Vector class, the add functions have the responsibility of expanding the Vector, whenever capacity is reached. The expansion of the Vector is done by calling the function ensureCapacity. This function takes an int argument called minCapacity and makes sure that the Vector has capacity, at least minCapacity. However, the remove functions in the Vector class do not "shrink" the Vector when the size of the Vector becomes too small as compared to its capacity. Write a Vector class public method called ensureMaxCapacity that takes an int argument called maxCapacity and makes sure that the Vector has capacity, at most maxCapacity. The shrinking of the Vector should be roughly opposite to how the expansion is done:

• If capacityIncrement is 0, then the Vector is halved repeatedly, until its capacity is at most maxCapacity.
• If capacityIncrement is positive, then the capacity of the Vector is repeatedly decreased by capacityIncrement, until the capacity is at most maxCapacity.

Now modify the remove function in the Vector class (given at the bottom of page 52 in the textbook), so that it shrinks the Vector by calling ensureMaxCapacity. The remove function must shrink the Vector as soon as the capacity becomes "too large" as compared to the size, but it should also ensure that no data is lost during the shrinking.

What to submit: Two functions, ensureMaxCapacity and remove.

9. Exercise 4.2 (page 77) in your textbook. Also, provide a 3-4 sentence argument for why the running time of your function if O(n log(n)).

Hint: It is shown in the textbook that the size of the table being constructed is O(n log(n)). However, the solution in the textbook runs in O(n^2) time. Your solution should take O(1) time for every new entry in the table. The way to do achieve this is not by finding factors of an int i, but by noting that i is a factor of all of its multiples.

What to submit: The function factTable justification for why this function runs in O(n log(n)) time.

10. This problem involves writing a portion of the set method for the SparseMatrix class from Project 1. For those of you who have successfully written this method for your project, solving this problem may simply mean cutting and pasting some code from your submitted project.

Write a protected method of the SparseMatrix class called locate that has the following function header:

```		int locate(int i, int j)
```
If the (i, j) element in the matrix is non-zero, then locate returns the position of this element in the Vector values. Otherwise, if the (i, j) element in the matrix is zero, then locate returns the position of where this element would be located in the Vector values if it were to be inserted. Assume that the following two "helper" functions already exist (you don't have to write them).

1. int locateNonNegative(Vector data, int left, int right): This function searches the sub-Vector data[left..right] for a non-negative integer and returns an index i of the first non-negative integer found. If data[left..right] contains no non-negative integer, it returns right + 1.

2. int locateNoSmaller(Vector data, int left, int right, int x): This function assumes that the sub-Vector data[left..right] is sorted in increasing order and searches this sub-Vector for for an integer at least as large as x and returns an index i of the first integer at least as large as x. If data[left..right] contains no such integer, it returns right + 1.

If you make appropriate calls to the above two functions from locate, then it should take at most 10 lines of code to complete locate.

What to submit: The function locate.