Introduction to Algorithms: Test

Paul Taylor

26 February 2001

You have 90 minutes.
Calculators are NOT allowed.
There are rather a lot of questions on this test paper, and you are not expected to be able to do all of them. Just do as many as you can.
The later parts ((f), (g), (h), ...) of each section (1, 2, 3, ...) are more difficult than the earlier ones. If you get stuck, move on to the next section.
Full credit (15/15) will be awarded for considerably less than the entire paper, depending on the distribution of marks from the whole class.
Warning: The "dry run" questions (where you are asked to simulate the algorithm on paper) will take you quite a long time, but not gain you marks in proportion to this time. You should read quickly through the other questions before starting these, and skip them if you feel reasonably confident of scoring marks elsewhere.

1  Sorting algorithms in general

(a) In order to justify calling a method a "sorting" algorithm, its result or output must, of course, be in (non-strictly) ascending order. What other property must the method satisfy? Write your answer in English, not formal logical, mathematical or programming language; there is one significant word.
(b) Briefly describe in English a method whose output is in ascending order, but which fails this condition and is therefore not a sorting algorithm. Make it as simple as possible.
(c) List the sorting algorithms that have been discussed during the course, in order of the time that they take to sort large arrays, fastest first.
(d) Based on your observations during labs of the algorithms built in to the TESTER, what is the largest unsorted array of integers that the fastest of the algorithms could sort in one minute. Your answer should be a power of 10: 10, 100, 1000, ...
(e) What is the largest unsorted array that the slowest algorithm could sort in one minute?
(f) What is the largest unsorted array that the fastest algorithm could sort in 100 minutes? Your answer will be judged by whether it is consistent with your answer to (d).
(g) What is the largest unsorted array that the slowest algorithm could sort in 100 minutes? Again, it is consistency with (e) that matters.
(h) Most of the algorithms work in place, i.e. by rearranging the given array without using additional scratch space. Which one does need additional scratch space, and why?
(i) You have found on the Internet a JAVA method that begins 
    public int[] hp_srt (int [] A) {
       ...
    }
so you try it out on some arrays of length 1000, 2000, 3000, 4000 filled with random numbers. Repeating the test many times with new random numbers, you find that it consistently returns in 1, 2, 3 and 4 milliseconds respectively. Without looking at either the code or its output, on what basis can you deduce that hp_srt is almost certainly not a sorting algorithm?

2  Insertion sort and bubble sort on almost sorted data

Be careful to emphasise the distinctions between your answers to parts (a) and (f), and also amongst (e), (f), (h) and (i).
(a) State, in one English sentence, the idea of insertion sort.
(b) Insertion sort takes about 150 microseconds to sort a random array of length 100. How long would you expect it to take to sort into ascending order an array of length 100 that was reverse sorted, i.e. given in descending order?
(c) How many seconds would you expect it to take to sort a random array of length 10000?
(d) Suppose that insertion sort is given the following array
1, 2, 4, 5, 6, 7, 8, 3, 9
which has one small value out of place amongst otherwise sorted data.
Describe the steps that insertion sort executes on this array, using the notation: State how many comparisons and assignments are made.
(e) Using the same notation, describe what insertion sort does with
1, 2, 8, 3, 4, 5, 6, 7, 9
where there is just one large value that is mis-placed among the small ones.
(f) State, in one English sentence, the idea of bubble sort.
(g) What does bubble sort do with the following array?
1, 2, 4, 5, 6, 7, 8, 3, 9
Use the following notation: State the total number of comparisons and assignments.
(h) Using the same notation as in (g), describe what bubble sort does with the following array?
1, 2, 8, 3, 4, 5, 6, 7, 9
(i) Insertion sort is very fast when it is given an array that is already sorted in ascending order but contains repeated values. What design decision must be made in its implementation to reduce to the absolute minimum the work that it does in this case?
(j) In what way does the time taken by insertion sort to sort an almost sorted array depend on the number or the percentage of displaced values? Explain these result in the light of the answers to the questions above.

3  Binary search

The rest of the questions on this test paper are based on the following (correct) JAVA code for binary search. Notice that one of the lines is "commented out"; it will be discussed in Question 5. 
   int search (int[] array, int seek) {
      int bot = -1;
      int top = size;
      while (top - bot > 1) {
         int mid = (top + bot)/2;
         // if (array[mid] == seek) return mid;
         if (array[mid] < seek) bot = mid;
         else                   top = mid;
      }
      return top;
   }
In this question, array is of length 15 and contains the values
1, 3, 4, 6, 6, 6, 8, 8, 8, 10, 12, 14, 14, 14, 15
(a) Do a "dry run" to find out what result the method returns when it is asked to search for 6. Indicate clearly when assignments to the program variables take place, and what numbers are assigned to them.
(b) Does the result returned indicate the leftmost, rightmost or just some occurrence of the value seek, assuming that it is present?
(c) Without doing a "dry run", what number would be returned given seek=8?
(d) Do another "dry run" to find out what the method returns when it is asked to search for 13.
(e) When the value seek is absent, should it be inserted before or after the position that the method returns?
(f) Without doing a "dry run", what number would this method return given seek=0 or seek=16?
(g) List clearly and explicitly the lines of code that are executed if this method is instead given an array of length 0.
(h) What number does the method return in this case?
(i) Explain why it does not throw ArrayIndexOutOfBoundsException.

4  Complexity and pre-conditions

(a) How much time does it take this method take to execute, as a function of the size of the array?
(b) What special requirement (pre-condition) must the array satisfy for the method to be able to work?
(c) Write this in logical notation (using ∀, ⇒ etc..).
(d) Write a JAVA program
boolean ok (int[ ] array) { ... }
to find out whether or not the array satisfies this requirement.
(e) What does binary search do if the pre-condition is not satisfied?
(f) Should the code for binary search be altered to check the pre-condition before proceeding with the search? Give your reasons.

5  Early exit

Now consider the version of binary search where the line 
   if (array[mid] == seek) return mid;
(which was "commented out" before) is now included.
(a) If the value seek occurs several times in the array, does this altered code find the leftmost, rightmost or just some occurrence?
(b) If the value seek does not occur at all in the array, should it be inserted before or after the position that the altered code returns?
(c) Why might this alteration to the code make it faster?
(d) Why, on the other hand, might the alteration make it slower?
(e) Is it, in fact, faster or slower than the original code?
(f) Suppose that the value seek does occur exactly once in the array, which is of length n=2k−1. How many times does the unaltered code go round its loop?
(g) On average, how many fewer times does the altered code execute the loop? Explain your answers by drawing a binary tree.
(h) Suppose that you were instead searching a String[] array, using the JAVA library method
int comparison = string1.compareTo (string2);
which returns −1, 0 or +1 according as string1 comes before, at the same place as or after string2 in the dictionary. Would you expect the analogous code with or without the alteration to be faster. Why?
(i) Again, suppose that you were using the COMP instruction in SF4 machine code (from the CS1 course) to compare integers. Which would you expect to be faster now, and why?

6  Other alterations

The purpose of this question is to get you to appreciate that each symbol in a program has a meaning, and affects the program as a whole.
The alterations to the code are to be taken individually: you have to "change it back" when you move on to the next part.
If something goes wrong, state clearly whether it is always or sometimes incorrect in the way that you describe.
If it only sometimes goes wrong, try to give an example of a value of seek (in the array used in Question 3, or in some other array that you describe) where this incorrect behaviour would occur. Say what value the method returns, or, if it throws an ArrayIndexOutOfBoundsException, what position it illegally tries to access.
(a) What happens if you initialise bot=0 instead?
(b) What happens if you initialise bot=-2 instead?
(c) How could you alter the code to search the segment array[3] to array[13] inclusive of the array (so it is allowed access array[3] and array[13] but not array[2] or array[14])?
(d) What happens if you change the loop condition to this?
while (top > bot) { ... }
(e) What happens if you change the loop condition to this?
while (top - bot > 2) { ... }
You will only be able to answer the final two parts if you have done the experiments in the lab (or can do the mathematical analysis).
(f) What happens if you change the calculation of mid to this?
int mid = (top + bot - 1) / 2;
(g) What happens if you make both of the changes in (e) and (f)?

This is www.PaulTaylor.EU/algorithms/test26feb.html and it was derived from algorithms/test26feb.tex which was last modified on 21 July 2007.