# Introduction to Algorithms: Exam

### 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 Hewlett-Packard 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 106220 times as fast.
State the worst-case 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  (b) Heap sort on an array of n integers. n=32  (c) Selection sort on an array of n integers. n=32  (d) Looking for a "true" line in the truth table for a propositional formula involving (∧, ∨,  ∼ , ⇒, T, ⊥ and) n variables. n=6  (e) Linear search on an array of n integers. n=200 
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 order-of-magnitude answers, so long as they correctly indicate the relative values.

### Second group

For each of the three fragments of code, what is its worst-case 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][n-i];
}
```
[2 marks]
(g) Given three 2-dimensional 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;
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 = n-1; i > 0; i--) {
int x = a[i];
a[i]  = a;
int p = 0;
while (true) {
int c  = 2*p+1;
if (c >= i) break;
if (c != i-1 && 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 pre-condition and post-condition?       [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 post-condition 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 pre-condition.       [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 pre-condition 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 pre-condition 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=2k?       [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=2k?       [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=2k?       [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=2k?       [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 best-case 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=2k? 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 worst-case 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 worst-case 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 worst-case 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 left-hand 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 right-hand 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[bot-1]?       [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[top-1] 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 right-most 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.