This is an exam. That means you may not speak with anybody other than me (Jeff Ondich) about its contents. You may, however, use your book, your notes, the books in the library, the Internet, and divine guidance (should any be offered to you). If you obtain information from some source other than your own brain, cite your source and use quotation marks where appropriate.
Hand in your exam on paper.
(6 points) Let's pretend I ran Insertion Sort on an array of 50,000 integers on my laptop, and it took exactly 3 seconds. Suppose further that after I sorted the integers, I ran a binary search on those integers a million times, and it took half a second.
(6 points) Consider the following method.
public static int Something( int[] a, int N ) { if( N == 1 ) return a[0]; else { int k = Something( a, N - 1 ); if( a[N-1] < k ) return a[N-1]; else return k; } }
(6 points) Write a recursive method to print a String
in reverse order. Before you try to write the Java code for such a method,
imagine a particular string--oh, I don't know, how about "moose"? How could you
break down the task "print 'moose' backwards" into something easy plus "print some
smaller string backwards"? One way to approach it would be to think of "moose" as being
composed of a head (the letter "m") and a tail (the string "oose"). To print "moose"
backwards, you might first print the tail backwards, and then print the head. That is,
first print "esoo", and then print "m".
Please use the following prototype.
public static void printBackwards( String s )
(8 points)
int N = 100000; N = N*N; System.out.println( N );
(12 points) In this problem, you will use Sorter.java to compare the performance of Selection Sort, Insertion Sort, and Merge Sort.
Selection, Insertion, and Merge Sorts are members of a class
of sorting algorithms whose performance is usually measured by
counting the number of array element comparisons that need to be done
to complete the sorting of the array. That is, we count the number
of times something like "if( a[j] < a[k] )
" gets executed
during the run of the algorithm. It would take several pages
to provide a reasonably rigorous argument that the
comparison count is a good measure of performance for these
algorithms. With a lot less rigor, we can say something like this:
by counting comparisons, we are counting the number of iterations
of the inner loop, and by counting inner loop iterations, we
are counting the most time-consuming portion of the algorithm.
So, in what follows, you're going to count comparisons
and measure running times for the three algorithms and several
values of N
. To do this, you'll need to study the algorithms
closely enough that you can insert a few lines of code to initialize a counter
to zero at the beginning, add one to the counter every time
two array elements are compared, and print the counter at the end.
N | Comp. count for Sel. Sort | Running time for Sel. Sort | Comp. count for Ins. Sort | Running time for Ins. Sort | Comp. count for Merge Sort | Running time for Merge Sort |
---|---|---|---|---|---|---|
10000 | ? | ? | ? | ? | ? | ? |
50000 | ? | ? | ? | ? | ? | ? |
100000 | ? | ? | ? | ? | ? | ? |
150000 | ? | ? | ? | ? | ? | ? |
200000 | ? | ? | ? | ? | ? | ? |
(8 points) Write a paragraph or two describing what you plan to do for your final project. After your description, provide me with your incremental development plan--that is, a list of baby steps that will take you from no program at all to a completed project. Each step should be testable independently of the others, so you can run a loop like this:
One of the lovely things about a good incremental development plan is that you can stop after any iteration of this loop and you will have a functioning program. It might not do everything you want it to do, but it compiles and it runs, and may even be useful (or even worth partial credit).