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:
- write out the data shown above so that it takes the full width of the
page, with plenty of space between the digits;
- allow one line per iteration of the main loop;
- underline ( )
each position with which a comparison is made;
- write each number that is assigned to cells in the
array, carefully aligning it with the numbers above to make its position
in the array clear;
if no assignment is made, leave the column blank;
- do not indicate temporary storage.
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:
- underline each pair of numbers that are are compared;
- rewrite the numbers only when they are swapped.
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=2^{k}−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.