| 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] |
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[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 = n-1; 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 != i-1 && a[c] < a[c+1]) c++;
if (x >= a[c]) break;
a[p] = a[c];
p = c;
}
a[p] = x;
}
[4 marks]
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]
int parity_split (int [ ] array)to rearrange the values in array so that
{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]
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
This is www.PaulTaylor.EU/algorithms/exam.html and it was derived from algorithms/exam.tex which was last modified on 22 July 2007.