- 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 ≤ j ≤ n-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.
-
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.
-
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:
- A.isMemberOf(int x): returns true if x is a member of the multi-set
A; false otherwise.
- A.Union(IntMultiSet B): returns the union of multi-sets A and B.
- A.Intersection(IntMultiSet B): returns the intersection of multi-sets A
and B.
- 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:
- 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.
- int size(): returns the number of elements in the multi-set.
- boolean isMemberOf(int x): returns true if x is a member of the
multi-set; false otherwise.
- 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.
- 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.
- 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.
- 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.
- MultiSet(Object[] universalSet): a constructor that constructs
an empty multi-set, such that any elements the multi-set can ever contain
are in universalSet.
- int size(): returns the number of elements in the multi-set.
- boolean isMemberOf(Object x): returns true if x is a member of the
multi-set; false otherwise.
- 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.
- 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.
- 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.
- 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.
-
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.
-
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.
-
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.
-
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.
-
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).
- 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.
- 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.