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:


   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?