CS 117
Midterm 2
Ondich
Due 11:10AM, Monday, June 2, 1997
This is an open-book, open-computer exam.
You may use your textbook, your notes, your programs,
and whatever information you find on
the course Web page. You may not consult other books
or on-line resources.
Do not discuss this exam with people
other than Jeff Ondich, who will be glad to answer
your questions if he feels it appropriate to do so.
If you have questions, ask them. It's not noble to suffer needlessly.
Please submit your exam on paper.
Stay cool, and have fun.
- (10 points) Numbers and characters.
- (10 points) The program
liststrings.p contains
several procedures for manipulating linked lists of characters.
Write a non-recursive function
function StringLength( str : nodePtr ) : integer;
to return the number of character nodes in the linked list
pointed to by str.
- (10 points) Write a recursive version of
StringLength from the previous problem.
- (3 points) Tell me a joke, please.
- (15 points) This problem uses the program
midtermsort.p.
- If you compile and run midtermsort.p as is,
it will generate a random shuffling of the integers 1 through 10,
sort those numbers, and quit without producing any output.
If you remove the comment braces on the lines labeled ****,
the resulting program will print out the contents of the array
before sorting begins, and after each pass of the selection
sort algorithm. Try running the program this way.
Now, explain in one or two sentences the strategy employed
by the selection sort algorithm. (The output in the previous
step may tell you what you need to know, but you might want
to take a look at the code for SelectionSort all the same.)
Finally, give a formula in terms of the parameter N
for the number of times the comparison
num[j] < num[indexOfMin] is performed when
you run SelectionSort.
- Next, comment out all calls to PrintList, and set
the constant maxIntarraySize to 1000. Recompile and
then time the program using the Unix command
time midtermsort. The timing number you want to record
is the far left one (something like "3.8u", which means your
program spent 3.8 seconds actually computing stuff as opposed to
waiting around).
Try this a couple of times to make
sure you get consistent timing data.
Time the program for maxIntarraySize
equal to 1000, 2000, 3000,...,8000. Are the times you get
consistent with what you would expect given the formula
you derived in the previous part?
- Go down to the main program, comment out the call
to SelectionSort, and uncomment the call to
MergeSort. Set maxIntarraySize back to 10.
Make sure the call to PrintList
in MergeSort is uncommented so you'll get some output.
Run the program this way to see how the array looks after
each call to Merge.
Explain in one or two sentences the strategy employed
by the merge sort algorithm.
- As you did with selection sort, time merge sort for maxIntarraySize
equal to 1000, 2000, 3000,...,8000.
- If you were to derive a formula for the number of operations
performed by MergeSort on an N-item array,
your formula's highest-order term would be some constant times
N*log(N). Based on this information and your timing
data, approximately how long would you expect MergeSort to take
to sort 1,000,000 items? How long would you expect
SelectionSort to take to sort 1,000,000 items?