CS 117 Late-term Exam

Due 9:50AM Monday, November 14, 2005

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.

1. (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.

   • If I increased the size of the array to 200,000, approximately how long would the Insertion Sort take? Why?
   • If I increased the size of the array to 200,000, approximately how long would it take to perform the million binary searches? Why?

2. (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; } }

   • What task does Something accomplish?
   • Change the names of Something and k to names that are more descriptive.
   • It's possible to pass Something parameters that would cause it to crash your program. Explain.

3. (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 )

4. (8 points)

   • How many different 8-bit patterns are there?
   • If you consider the 8-bit pattern 01000101 to be an integer, what integer is it? (Give your answer in base ten.)
   • If you consider the 8-bit pattern 01000101 to be an ASCII character, what character is it?
   • What output does the following code produce, and why?

     int N = 100000; N = N*N; System.out.println( N );

5. (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.

   • Fill in the following chart.

     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	?	?	?	?	?	?

   • Describe any patterns you see in the data you collected to fill in the chart above.
   • Is the comparison count for Selection Sort dependent on the initial data? (For example, if you run Selection Sort several different times on different randomly generated arrays of 10000 items, is the comparison count the same every time?) How about Insertion Sort? Merge Sort?
   • Under what conditions would you choose to use Merge Sort instead of Insertion Sort and Selection Sort? When would you choose Insertion Sort? When would you choose Selection Sort?
6. (2 points) We had a little conversation a few days ago about the coolest things you have seen a computer do, and I still promise to discuss my list of coolest things before the end of the term. In the meantime, tell me the coolest or most interesting or most impressive thing you have seen a computer do.
7. (3 points) Briefly describe the significance of Alan Turing to the history of computer science.

8. (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:

   • Complete a step on the incremental development plan list.
   • Compile the program.
   • Test the program to make sure your new additions work, and that they didn't break previously completed features.
   • SAVE A COPY OF THE WORKING CODE AND NEVER TOUCH IT AGAIN.
   • Repeat.

   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).