Introduction to Algorithms: Exam
Paul Taylor
May 2001
The rubric on the front of the exam paper reads:
 DCS/127 INTRODUCTION TO ALGORITHMS
 Time allowed: TWO AND A HALF HOURS.
 Answer FOUR questions.
There are eight questions altogether;
they carry equal weight (30 marks).
Question 8 is an essay that itself has three options,
but you may only choose one of these.
 Calculators are NOT allowed.
1 Complexity
This option is made up of two groups of questions; you must answer both.
First group
The HewlettPackard HP9810A programmable desk calculator cost $2960 in 1971
and could perform about 100 instructions per second.
Below is a table showing the sizes of the largest problems
that it could solve in one minute.
For less than this price, you can now buy a computer that is
10^{6} ≈ 2^{20} times as fast.
State the worstcase time complexity of each algorithm in the form
"O(…)" and then estimate the size of the largest problem
that the modern computer could solve
in the same amount of time (one minute).
All numbers must be expressed in standard decimal ("Arabic")
notation: no marks will be given for formulae or exponential notation.
 algorithm 
largest problem size in 1971  marks 
(a)  Multiplying two n×n matrices 
 by the naïve algorithm.  n=6  [3] 
(b)  Heap sort on an array of n integers.  n=32  [5] 
(c)  Selection sort on an array of n integers.  n=32  [3] 
(d)  Looking for a "true" line in the truth table 
 for a propositional formula involving 
 (∧, ∨, ∼ , ⇒, T, ⊥ and) n variables.  n=6  [5] 
(e)  Linear search on an array of n integers.  n=200  [2]

You are advised to write down the mathematical equation that needs to be
solved before you do any arithmetic, and set out your rough calculations
as clearly as possible.
Alternatively, you should be able to guess the answers on the basis
of your own experience of running test programs in the lab sessions,
without doing any arithmetic.
It is enough to give orderofmagnitude answers,
so long as they correctly indicate the relative values.
Second group
For each of the three fragments of code,
what is its worstcase time complexity,
in the form "O(…)".
(f) Given an array A of appropriate size,
what is the complexity in terms of n?
int i=n, x=0;
while (i>0) {
i;
x += A[i][ni];
}
[2 marks]
(g) Given three 2dimensional arrays A, B, C
of appropriate sizes,
what is the complexity in terms of n, m and p?
for (int i=0; i<n; i++) {
for (int k=0; k<p; k++) {
int x=0;
for (int j=0; j<m; j++) {
x += A[i][j] * B[j][k];
}
C[i][k] = x;
}
}
[2 marks]
(h) Given int x and an array of appropriate size,
what is the complexity in terms of n?
int p = 1;
int q = n;
while (p+1 < q) {
int m = (p+q)/2;
if (A[m] < x) { p=m; }
else /* A[m] >= x */ { q=m; }
}
[2 marks]
(i) Given an array of appropriate size,
what is the complexity in terms of n?
int m = A[0];
for (int i=1; i<n; i++) { if (A[i] > m) m = A[i]; }
int k = 0;
for (int i=0; i<n; i++) { if (A[i] == m) k++; }
[2 marks]
(j) Given an array of appropriate size,
what is the complexity in terms of n?
for (int i = n1; i > 0; i) {
int x = a[i];
a[i] = a[0];
int p = 0;
while (true) {
int c = 2*p+1;
if (c >= i) break;
if (c != i1 && a[c] < a[c+1]) c++;
if (x >= a[c]) break;
a[p] = a[c];
p = c;
}
a[p] = x;
}
[4 marks]
2 Specifications
(a) What are meant by the terms precondition and postcondition?
[4 marks]
(b) Explain how these two conditions
provide a right (or guarantee) for the user of a method and
impose a duty on its programmer, or vice versa.
[3 marks]
(c) Very briefly, state the postcondition of one method
that you have implemented during this course.
[1 mark]
(d) Name one method that you have implemented for which you did not need
to state any precondition.
[1 mark]
(e) Does a specification determine the way in which the method
is to be implemented?
Give an example to explain your answer:
no marks will be given for "yes" or "no" alone.
[3 marks]
(f) What is the precondition for the following method?
void shift (int array[ ], int src, int dest, int len) {
if (src > dest) {
int j=0;
while (j < len) {
array [dest + j] = array [src + j];
j++;
} }
else {
int j=len;
while (j > 0) {
j;
array [dest + j] = array [src + j];
} } }
[3 marks]
(g) Can this condition be verified in an acceptable number of operations?
[1 mark]
(h) What would happen in JAVA if this method were to proceed
with its execution when the precondition was not satisfied?
What would happen in C? Does this matter?
[3 marks]
(i) What is the precondition for binary search?
[1 mark]
(j) Can this condition be verified in an acceptable number of operations?
[2 marks]
(k) What would happen if this method were to proceed
with its execution when the precondition was not satisfied?
Does this matter?
[2 marks]
(l) You were told to implement insertion sort
using a separate search method.
Your insertion sort method is therefore a user of the search method,
in the sense of part (b) above.
What is the specification of the search method,
if it is to be used for this purpose?
[2 marks]
(m) How does insertion sort make use of this property to conform
to its own specification?
[4 marks]
3 Merge sort
(a) What is the idea of merge sort?
Make sure that your description applies unambiguously
to merge sort and not to quick sort.
[4 marks]
(b) Suppose that recursive merge sort is called with an array of length 16.
Draw a tree to show how many recursive calls are made,
labelling the root "M(16)" and each of the other nodes
"M(size)"
in the same way to show the sizes of the arrays
that they are each required to sort.
[3 marks]
(c) In general, how many method calls does recursive merge sort make
when sorting an array of length n, assuming that n=2^{k}?
[2 marks]
(d) Each of the recursive calls to mergesort has to merge two arrays into one,
which involves a certain number of assignment operations.
How many such assignments are made altogether?
Annotate your tree with the total number that are made at each level.
[2 marks]
(e) In general, how many such assignments does recursive merge sort make
when sorting an array of length n, assuming that n=2^{k}?
[2 marks]
(f) It is possible to make a hybrid of insertion sort and merge sort
that sorts large arrays faster than pure merge sort itself.
You are not required to write out the code.
Instead, draw a tree similar to that in (b)
and explain in one English sentence how the hybrid
differs from pure merge sort.
Annotate the nodes of your tree with "I(s)" where you want
to call insertion sort on an array of size s.
Choose the size of the original array appropriately (say, 128 or 256)
to illustrate the design decision that you are making.
[6 marks]
(g) How many method calls does your hybrid algorithm make for
an array of size n=2^{k}?
[2 marks]
(h) How many assignments does insertion sort make, on average,
when sorting an array of length s?
[1 mark]
(i) How many assignments does your hybrid algorithm make for
an array of size n=2^{k}?
[4 marks]
(j) How long do the pure and hybrid mergesort methods take to sort
an array of length n, as a function of n?
It is the form of the function that is required:
you are not required to give numerical time values for the coefficients.
Which part of this mathematical expression is different for the hybrid?
[4 marks]
4 Quick sort
(a) Given an array of numbers, what is meant by their mean,
mode, average and median values?
[4 marks]
(b) One of these values (mean, mode, average or median) is very easy
to calculate. Which one?
Write (the significant part of) the JAVA code to do it.
[2 marks]
(c) In a single English sentence, what is the idea
of quick sort?
Make sure that your description applies unambiguously
to quick sort and not to merge sort.
[3 marks]
(d) What is the bestcase time complexity of quick sort?
[1 mark]
(e) What is meant by the pivot in quick sort?
[2 marks]
(f) Which of the values in (a) (mean, mode, average or median) would you
ideally use for the pivot?
[1 mark]
(g) What would the depth of the recursion be if this ideal choice
were used to sort an array of length n=2^{k}? Explain why this is.
[4 marks]
(h) Explain how this ideal choice would result in the time complexity
that you have stated in (d).
[2 marks]
(i) What is the worstcase time complexity of quick sort?
[1 mark]
(j) Describe briefly what quick sort does with sorted data
if the first value is used for the pivot.
[1 mark]
(k) Why does this result in worstcase complexity?
[3 marks]
(l) What is meant by the median of three method of choosing the pivot?
[2 marks]
(m) On what kind of almost sorted data does this method of choosing the pivot
still result in worstcase time complexity?
Describe what happens.
[4 marks]
5 Programming Split
This question guides you through the design of a method
int parity_split (int [ ] array)
to rearrange the values in array so that
 the odd numbers come first (in any order, not necessarily sorted),
 followed by the even numbers (also any order),
 returning the position of the first even number.
So, for example,
{1,0,8,7,5,3,9,6,2,7,4} might become {1,7,9,7,5,3,8,6,2,0,4}
and the value 7 (the new position of 8) is returned.
This is similar to the split method used in quicksort.
You must not allocate a new array inside your method.
In the typical situation during the execution of the loop inside your method,
there are some odd numbers on the left, some even numbers on the right
and a mixture of odd and even numbers that have not yet been considered
in the middle.
(a) Draw a diagram to illustrate the typical situation as just described,
and the way in which program variables will be used as pointers into
the array during the execution of the loop.
[4 marks]
(b) What are the initial values of the pointers?
[2 marks]
(c) Under what condition can you simply increment the lefthand pointer,
without altering the values in the array?
[2 marks]
(d) Write the JAVA code to do this as much as possible.
[2 marks]
(e) Similarly, write the JAVA code to move the righthand pointer
as far left as possible.
[2 marks]
(f) After you have moved the pointers together like this,
what can you deduce about the values near the pointers in the diagram?
Describe the situation in English or JAVA, and also indicate it on your
diagram in (a).
[3 marks]
(g) What operation can you now perform on the values in the array,
after which you may advance both pointers?
[3 marks]
(h) When does the algorithm terminate, and what value does it return?
Write it in JAVA as if (...) return ...;
[2 marks]
(h) Now write the complete method.
[10 marks]
6 Heap sort
(a) Considering it as a tree,
explain what is meant by a heap.
Draw an example.
[4 marks]
(b) How can a heap be represented as an array? In particular, what array
represents your example?
[2 marks]
(c) How do you calculate the positions of the parent and
children of a particular node in this representation?
[3 marks]
(d) Describe how to insert a new value in the heap.
Draw an example.
[4 marks]
(e) What significance does position 0 have in the tree representation,
and what property does the value there have?
[2 marks]
(f) Describe how to delete the value at position 0 from the heap.
Draw an example.
[4 marks]
(g) If the heap has n elements, what is the (worst case) time complexity
for insertion and for deletion?
[1 mark]
(h) Suppose you have a random array of n elements that you want to
rearrange into a heap. One way to do this is by inserting the
elements (using (e)) one by one. What is the (worst case) time complexity
of doing this?
[2 marks]
(i) Describe a faster way to heapify an array, and state its
time complexity.
[5 marks]
(j) Explain how to use a heap to sort an array, and state its
time complexity.
[3 marks]
7 Correctness of binary search
This question guides you through the proof of correctness of the following
binary search method:
int search (int[] array, int seek) {
int bot = 0;
int top = size;
while (top > bot) {
int mid = (top + bot  1)/2;
if (array[mid] <= seek) bot = mid + 1;
else /* array[mid] > seek */ top = mid;
}
return ??;
}
Notice that the return value is missing.
(a) After the assignment bot=mid+1 has been made,
what can you say about array[bot1]?
[2 marks]
(b) Suppose instead that the assignment top=mid
has just been executed. What can you say about array[top]?
[2 marks]
(c) What do (a) and (b) tell you about other values in the array,
and why?
[2 marks]
(d) Draw a diagram to illustrate these statements, indicating the positions
of the bot and top pointers,
and the properties of the segments that they delimit.
[5 marks]
(e) Are the two logical statements in (a) and (b)
valid just before the loop is entered?
If so, why? If not, what similar statements are in fact valid, and why?
[2 marks]
(f) Suppose that the logical statement in (a) happened to be valid
just inside the beginning of the body of the loop,
but that the else branch
(including assignment top=mid) is executed.
Is (a) still valid at the end of the body of the loop? Why?
[2 marks]
(g) What may you therefore conclude is true on exit from the loop,
assuming that it does terminate?
[1 mark]
(h) Suppose that the assignment bot=mid+1 has just been executed.
Show that the variable bot is increased by at least 1.
Be careful to distinguish between the original and new values of bot.
[3 marks]
(i) What logical statement is true on exit from the loop,
simply by virtue of having just come out of the loop?
[2 marks]
(j) What can you deduce about the relationship among seek,
array[top1] and array[top] on exit from the loop?
[3 marks]
(k) Deduce the value that the method must return,
if it is required to point to some occurrence of seek if there is one.
[2 marks]
(l) Is this the left or rightmost occurrence, or just some occurrence?
[1 mark]
(m) What does the result returned by the method mean in the situation
where the value seek does not occur in the array?
[1 mark]
(n) What would happen if you changed the loop condition to
while (top >= bot)
and ran the program?
Explain this in terms of the calculation in (h).
[2 marks]
8 Essay
Write an essay about one of the following topics. [30 marks]
Your answer should include a selection
of the most important parts of the code:
do not include JAVA declarations unless they illustrate some aspect
of the algorithm.
Explain the main points in proving correctness and
state the main facts about complexity.
 Sorting a list of names that fits on disk but not in RAM.
 Hash tables for creating, accessing and updating dictionaries.
 Finding a path through a network.
This is
www.PaulTaylor.EU/algorithms/exam.html
and it was derived from algorithms/exam.tex
which was last modified on 22 July 2007.