This homework has two parts: a written section and a programming section.
For the written section of this assignment, type up your answers and submit a computer based document to us. You can submit MS Word doc files, pdf files, or txt files.
1. Weiss, Exercise 2.1
Order the following functions by growth rate: N, square root of N, N^1.5, n^2, N Log N, N log log N, N log^2 N, N log(n^2), 2/N, 2^N, 2^N/2, 37, N^2 log N, N^3. Indicate which functions grow at the same rate.
2. Weiss, Exercise 2.6
In a recent course case, a judge cited a city for contempt and ordered a fine of $2 for the first day. Each subsequent day, until the day followed the judge's order, the fine was squared (that is, the fine progressed as follows: $2, $4, $16, $256, $65, 536, ...).
a. What would be the fine on day N?
b. How many days would it take the fine to reach D dollars? (A Big-Oh answer will do.)
3. Give an analysis of the BigOh running time for each of the following program fragments:
a. int sum = 0;
for ( int i = 0; i < 23; i ++)
for ( int j = 0; j < n ; j ++)
sum = sum + 1;
b. int sum = 0;
for ( int i = 0; i < n ; i ++)
for ( int k = i ; k < n ; k ++)
sum = sum + 1;
c. public int foo(int n, int k) {
if(n<=k)
return 1;
else
return foo(n/k,k) + 1;
4. Weiss, Exercise 2.11
An algorithm takes 0.5 ms for input size 100. How long will it take for input size 500 if the running time is the following (assume low-order terms are negligible):
a. linear
b. O(N log N)
c. quadratic
d. cubic
5. Weiss, Exercise 2.15
Give an efficient algorithm to determine if there exists an integer i such that Ai = i in an array of integers A1 < A2 < A3 < ... < An. What is the running time of your algorithm?
For the programming portion of the assignment, please submit only your .java files and your README.txt. Your code should be well commented. In addition please include a detailed README.txt file which indicates exactly what files you are submitting, what problem they solve, and how to compile and run them.
1. Define a rectangle class that provides a getLength method and and a getWidth method. Rectangle should also implement the Comparable class it should compare by perimeter. Create another class called Problem1 that has the findMax routine (included below) and add a main method that creates an array of Rectangle objects and finds the largest Rectangle on the bases of its perimeter.
public static < AnyType extends Comparable< AnyType>> AnyType findMax(AnyType[] arr) {
int maxIndex = 0;
for (int i = 1; i < arr.length; i++)
if ( arr[i].compareTo(arr[maxIndex]) > 0 )
maxIndex = i;
return arr[maxIndex];
}
2. In Problem2.java Implement a static method with the signature:
public static < AnyType extends Comparable< AnyType>>
int binarySearch(AnyType[] a, AnyType x);
This method should then search the array recursively for the value x. Create a main method that builds an array of rectangles (use your class from problem 1) and then sort that array with Arrays.sort. Demonstrate your recursive binarySearch method on this array.
3. In Problem3.java, implement the three code fragments from written problem 3. Have your code repeatedly run each fragment on various values of n. Time each run and see if the progression of timings as n increases matches the predicted run times from your written assignment.
By default the java virtual machine uses a feature called the JustInTime (JIT) compiler that actually compiles the java bytecode down to native machine code for the computer on which you're running. The use of the JIT generally speeds up execution of code, but in this case will cause the run times to not follow the pattern you would expect since it does some onthespot optimizations. Therefore, you must disable the JIT to do this problem. If you are running java from the command line, you can disable the JIT for a single run by using the command line argument: Xint. So if you want to run your class Problem 3 with the JIT turned off:
java Xint Problem3
If you want to run your code from Eclipse, you will need to modify the VM args in the run configuration menu. Here (http://www.cs.colostate.edu/helpdocs/eclipseCommLineArgs.html) is an explanation of how to access the run configuration window. The link talks about changing the command line arguments, but if you look at that window, you will see a second field called "VM args." In the "VM args" place the Xint, and then the program like you normally would in Eclipse.
Place the results of your timing and your explanation in a file called Problem3.txt. For the third fragment, set k equal to 2 for all of your testing. The easiest way to time your run is to execute the following code before each fragment:
int starTime = System.currentTimeMillis();
then after each fragment place:
endTime = System.currentTimeMillis()
The elapsed time is the difference between these two variables.