Analysis Of Algorithms
----------------------
Questions 1
-----------
Answers to these questions will appear in "~ian/algorithms" in due course. The
questions include some of the previous exam questions for the course. Starred
questions are harder than you would expect in the exam.
1. Suppose we have an array of numbers a[1]...a[n] in which the first i numbers
a[1]...a[i] have been sorted into ascending order, and the remaining numbers
a[i+1]...a[n] have also been sorted into ascending order. The aim is to sort
the entire array into ascending order. Design an algorithm which merges
the two sorted lists into a second array b[1]...b[n] and copies the result
back into a.
Prove that the algorithm takes time O(n).
Design an algorithm which does the same job using only b[1]...b[i] for
temporary storage, and which also takes O(n) time. What do you think is the
minimum temporary storage (as a function of n) needed to solve this problem
in time O(n)?
2 Show how a boolean array b[1]...b[n] can be used to represent a set of
numbers taken from 1...n. What does b contain if n=9 and the set is
{1, 2, 4, 5, 7, 8, 9} ? Show that inserting a number into the set, deleting
a number from the set, and testing a number for membership in the set are
all O(1) operations. How long does it take to find the union of two sets or
to test them for equality? (This is the representation used in most versions
of pascal for "set" variables).
3 One disadvantage of the above representation is that initialising the set
to be empty takes O(n) time. Find a representation in which initialisation
is O(1) as well as insertion, deletion and membership testing. It can be
done using a variable s giving the set size, an array a[1]...a[n] of set
elements and an array b[1]...b[n] of sequence numbers. Only s needs to be
initialised; a and b are assumed to contain random data initially. How long
does it take to find the union of two sets represented this way, or to
test them for equality? (This is the basis of "memory marking" algorithms
in operating systems).
4 Consider the problem of finding the mode (most frequent item) and its
frequency in a sorted array of numbers. For example
1, 3, 3, 6, 6, 6, 6, 7, 8, 8, 8, 9, 9
has mode 6 with frequency 4 since 6 occurs more times (4) than anything
else. Suppose that you know the mode and frequency of a[1]...a[i-1]. Show
that with only a single comparison you can tell whether the mode and
frequency of a[1]...a[i] is different. Use this to design a recursive
algorithm for finding the mode and frequency. Estimate the time it takes.
Turn the recursive algorithm into a non-recursive one (perhaps by examining
the sequence of operations performed by the recursive one).
5 The following recursive algorithm calculates the n'th Fibonacci number,
i.e. the n'th number in the sequence 1, 2, 3, 5, 8, 13, ... in which each
number is the sum of the previous two.
Find n'th Fibonacci number F(n)
-------------------------------
if n <= 2 then return n
return F(n-1) + F(n-2)
Show that it takes time at least O(2^(n/2)). Would you rate it as a good
algorithm? Design another recursive algorithm for the problem which returns
both F(n) and F(n+1), and only does one recursive call. Estimate the time it
takes. How does it compare to the above algorithm? Turn this second
algorithm into a non-recursive one.
6 One way to produce all the permutations of a collection of (say) n letters
is to use the following rough algorithm.
To permute a set of letters (e.g. CADF)
---------------------------
for each letter in alphabetical order (A,C,D,F)
put that letter first (say A)
(recursively) permute the remaining letters (CDF)
For the letters CADF this produces the permutations:
ACDF, ACFD, ADCF, ADFC, AFCD, AFDC, CADF, CAFD, CDAF, CDFA, CFAD, CFDA,
DACF, DAFC, DCAF, DCFA, DFAC, DFCA, FACD, FADC, FCAD, FCDA, FDAC, FDCA
Assume that the letters are held in an array a[1]...a[n].
Make this algorithm more precise, using an array of markers, one for
each letter, to indicate whether the letter has been considered yet.
7* Design an algorithm which will examine a particular permutation of n letters
(in an array a[1]..a[n]) and will change it into the FOLLOWING permutation,
(in the order of the previous question). For example if the algorithm is
presented with CAFD it will swap A, F and D to produce CDAF.
Prove that the algorithm takes O(1) time on average (assuming all the
permutations are equally likely). Does this provide a better algorithm
than the previous question?