Test Date:  Thu Apr 10 and Mon Apr 14, 2003

Programming and Computer Science:  Test #2
Apr 10 and Apr 14, 2003

•  You may use JCreator both sections of this test.

• Once you begin Part II, you may not return to Part I, even to check your answers.

• Good luck!

Part I:  Sorting

Question 1:  Match the Sort.  This half of the test is only one question, though a rather hefty one. Your task is to read in an unsorted array, plus the first k swaps, and to identify which sorting algorithm is being used to sort it.  To do this, read in the following, in order:

• An integer N -- the size of the unsorted array

• N more integers -- the elements of the array

• An integer K -- the number of swaps (K in [1,20])

• The first K swaps, each as two indices -- i j -- meaning a swap from a[i] to a[j]. 

You should output one of the following: bubblesort, selectionsort, insertionsort, mergesort, quicksort, or unknownsort. 

Note that mergesort does not call swap, at least not as we write it. So what to do? Well, further note that in the merge step of mergesort, you repeatedly copy a value from somewhere in the unsorted array (which we call leftIndex or rightIndex, depending) into the next location in the merged array (which we typically call copyIndex). For this problem, consider this to be a swap, from the source index (leftIndex or rightIndex, accordingly) 
to the destination index (copyIndex).

HINT: You may include additional output prior to your answer, and in fact it is a very good idea to do this. In particular, for each sort, print out the first k swaps for that sort. This will help you solve the problem, and in any case, it will at least help guarantee considerable partial credit. 

Part II:  Strings, Doubles, Monte Carlo, and Such

Question 2:  Simple Code.  For this problem, you will read in a lowercase word that is in code, and you will print out the uncoded word.  Before you read in the word, you will first read in an integer N.  For each letter in the uncoded word, the coded version uses the letter N places beyond the uncoded letter in the alphabet (wrapping around as needed).  So if N==2, "a" is coded as "c", and if N==4, "a" is coded as "e".  Hint: to convert an integer holding an ASCII value to the equivalent character, do the following:

 int capitalAinAscii = 65; // this is capital A in ASCII
 char capitalA = (char) capitalAinAscii; // convert to a char
 s += capitalA; // add to a string

Hint: lowercase 'a' is 97 in ASCII.

Question 3:  Sentence Analysis.  Write a Java program which reads in a sentence, and prints out the following information:

• total number of words

• total number of vowels

• average number of letters per word, rounded to exactly one decimal place (so, say, if the average is 3.582, you should display 3.6)

You should read the sentence in one word at a time using readString().  Note that some words will have punctuation before or after them -- do NOT count the punctuation as a letter!  Also, you will know when you are done when a word ends with a period ('.') or an exclamation point ('!').

Sample input:  He said, "I see," and I thought perhaps not.

Sample output:  9 words, 13 vowels, 3.4 letters per word

Question 4:  Approximating Pi.  The following formula demonstrates one way to approximate Pi:

    Pi = 4 - 4/3 + 4/5 - 4/7 + 4/9 - ...

Write a Java program which uses this technique to compute the value of Pi, stopping when the next term to be added or subtracted is smaller than 0.00001.  Print your final answer, then use Math.PI to print out how far from the real value your answer lies.

Question 5:  Colliding Darts.  Imagine you throw a dart randomly at a round dartboard whose center is at (0,0) and whose radius is 1.  Now you randomly throw a second such dart, without removing the first.  There is some chance that the two darts collide.  To keep it simple, we'll say that two darts collide if they are within 0.1 of each other.  You are to write a Java program which reads in a non-negative integer D and uses Monte Carlo techniques to estimate the average number of darts which will collide when D darts are thrown randomly into such a dartboard.  Note that even if a dart collides with more than one dart on the board, you should only count that once.  Further, since there are no darts on the board when the first dart is thrown, it can never count as a collision, even if future darts collide with it.  For this problem, you should run 100,000 experiments, and simply return the average value of those experiments.

See Course Home Page.