Answers to "questions1"                               Analysis of Algorithms
----------------------                                -----------------------

1. A recursive design for the merge is:

      To merge a[1]...a[i] and a[i+1]...a[n] into b[1]...b[n]
      if either sequence is exhausted, copy the other into b and return
      if a[1] < a[i+1] then
         b[1] := a[1]
         merge a[2]...a[i], a[i+1]...a[n] into b[2]...b[n]
         b[1] := a[i+1]
         merge a[1]...a[i], a[i+2]...a[n] into b[2]...b[n]

   This is followed by copying b back into a. This recursive design easily
   yields a sequential one:

      To merge a[1]...a[i] and a[i+1]...a[n] into b[1]...b[n]
      initialise x := 1, y := i+1, z := 1
      while x <= i and y <= n do
         if a[x] < a[y] then
            b[z] := a[x]
            x := x + 1
            b[z] := a[y]
            y := y + 1
         z := z + 1
      copy any remaining items into b
      copy b back to a

   The inner part of the "while" loop takes O(1) time and is repeated at most
   once for each x from 1 to i, and once for each y from i+1 to n, making n
   times in all. Thus the while loop takes O(n) time, as does the copying of
   b into a, so the total is O(n).

   If we only have b[1]...b[i], then we can use the algorithm:

      copy a[1]...a[i] into b[1]...b[i]
      merge b[1]...b[i] and a[i+1]...a[n] into a[1]...a[n]

   The merging can be done by the algorithm above. The items in a[i+1]...a[n]
   will not be over-written before they are dealt with, since if k items remain
   in a[n-k+1]...a[n], then at most n-k items have been dealt with and have
   been copied into a[1]...a[n-k]. Clearly the algorithm is still O(n).

   We can always do the merging using only b[1]...b[n/2]. If i <= n/2, then
   we can use the above method with b[1]...b[i]. If not, then a[i+1]...a[n]
   contains <= n/2 items, so we copy a[i+1]...a[n] into b[1]...b[n/2], then
   move a[1]...a[i] into a[n-i+1]...a[n], and merge b[1]...b[n/2] and
   a[n-i+1]...a[n] into a[1]...a[n] as before.

   You were not expected to
   know it, but the problem can still be solved in O(n) time without using
   b at all - if you want to find the algorithm, try it first using

2. We can set b[i] to TRUE if i is in the set, and FALSE otherwise. Thus
   for n = 9 and set {1,2,4,5,7,8,9} we have:

             1     2     3     4     5     6     7     8     9

   To insert, delete or test i for membership, the operations are:

      insert i:                   b[i] := TRUE
      delete i:                   b[i] := FALSE
      if i in set then ...:       if b[i] then ...

   which are clearly O(1). If a[1]...a[n] represents S, b[1]...b[n] represents
   T and c[1]...c[n] is to represent the union, then c is calculated by:

      To calculate union
      for i := 1 to n do
         c[i] := a[i] or b[i]

   which is O(n). Equality is tested by:

      To test equality
      for i := 1 to n do
         if not (a[i] = b[i]) then return FALSE
      return TRUE

   which is again O(n).

3. We use s as the size of the set. Then a[1]...a[s] contain a list of its
   elements in any order (with a[s+1]...a[n] arbitrary). The array b contains
   the sequence numbers of the elements in a[1]...a[s] as follows.
   If i is in the set, and appears in the list as a[k] = i, then b[i] = k.
   If i is not in the set, then b[i] is arbitrary.

   This representation can be initialised in O(1) time by setting s := 0, the
   entire contents of a and b being arbitrary. Insertion, deletion and
   membership testing can be carried out in O(1) time by the algorithms:

      To insert i
      a[s+1] := i
      b[i] := s+1
      s := s + 1

      To delete i
      k := b[i]         (find out where it is in the list)
      last := a[s]      (find last item)
      a[k] := last      (reposition last item)
      b[last] := k
      s := s - 1

      To test if i in set
      pos := b[i]               (attempt to find position in list)
      if (pos < 1) or (pos > s) (check pos was not arbitrary)
         then return FALSE
      if not (a[pos] = i)       (check pos not accidentally in range)
         then return FALSE
      return TRUE

   If we want U to be the union of sets S and T represented as above, we
   can use the algorithm:

      To form union U of S and T
      U := S
      for each item i in T do
         if i not in S then insert i in U

   The first step "U := S" can be done in time O(n), the inside of the loop
   involves membership tests and insertions as above and can be done in
   O(1) time, and thus the loop takes O(n) time. Thus the total time taken is
   O(n), and in fact is proportional to the number of items in S plus the
   number of items in T. Equality can be tested by:

      To test equality
      if sizes unequal then return FALSE
      for each item i in S do
         if i not in T then return FALSE
      return TRUE

   which similarly takes O(n) time (actually proportional to the set sizes).

4. Suppose the mode of a[1]...a[i-1] is a number appearing (say) 5 times.
   Then the mode of a[1]...a[i] will only be different if it contains a number
   appearing 6 times. The number must be a[i], and it must appear in the
   sequence a[i-5], a[i-4], ... , a[i]. Thus the mode changes only if
   a[i-5] = a[i]. This is one comparison. If the frequency of a[1]...a[i-1]
   was f, we test whether a[i-f] = a[i]. A recursive algorithm is thus:

      To find mode and frequency of a[1]...a[i]
      find mode m and frequency f of a[1]...a[i-1]
      if a[i-f] = a[i] then return mode a[i] and frequency f+1
      return m and f

   The time taken by the second and third lines is O(1), so if the total time
   is f(n), we have

      f(n) = f(n-1) + O(1)        =>         f(n) = O(n)

   This can be turned into a non-recursive algorithm using a loop:

      To find mode and frequency of a[1]...a[n]
      m := a[1]
      f := 1
      for i := 2 to n do
         if a[i-f+1] = a[i] then
            m := a[i]
            f := f + 1

5. If the time taken by the Fibonacci algorithm is f(n), we have:

      f(n) > f(n-1) + f(n-2)

   This shows in particular that f(n) > f(n-1), and f(n-1) > f(n-2) etc.

      f(n) > f(n-1) + f(n-2) > 2*f(n-2)

   Now applying this repeatedly gives:

     f(n) > 2*f(n-2) > 2^2 * f(n-4) > 2^3 * f(n-6) > 2^4 * f(n-8) ....

   Repeating this n/2 times gives f(n) > 2^(n/2) * f(0), i.e. f(n) is at
   least O(2^(n/2)).

   The time taken thus rises exponentially quickly, and the algorithm
   will only be of use for very small values of n. It is thus a very
   poor algorithm.

   A recursive algorithm to find both F(n) and F(n+1) is:

      To find F(n) and F(n+1)
      find F(n-1) and F(n) recursively
      calculate F(n+1) = F(n-1) + F(n)
      return F(n) and F(n+1)

   If the time for this is f(n), then f(n) = f(n-1) + O(1) giving f(n)
   is O(n). This is clearly far, far better thatn the previous algorithm.
   A non-recursive version is:

      To find F(n)
      x := F(0)
      y := F(1)
      for i := 2 to n do
         z := x + y
         x := y
         y := z
      return y

6. The letters to be permuted are held in l[1]...l[n] in alphabetical order.
   The current partial permutation is held in a[1]...a[k] and a boolean array
   b[1]...b[n] is used to indicate which letters appear in the partial
   permutation. The values b[i] are initially all FALSE. The algorithm is:

      To permute remaining k letters
      if k=0 then print out the permutation a[1]...a[n] and return
      for i := 1 to n do
         if not b[i] then
            b[i] := TRUE
            a[n-k] := l[i]
            permute remaining k-1 letters
            b[i] := FALSE

7. Note that the last permutation of a set of letters such as ACDF consists
   of those letters in reverse alphabetical order, i.e. FDCA.
   If we examine a permutation like CAFD in which the A, F and D are about to
   change to give CDAF, this is because we have reached the last permutation
   of the letters FD (they are in reverse order), but we have not reached the
   last permutation of AFD (they are not in reverse order). We can tell this
   by finding the longest "suffix" which is in reverse order. Thus given
   a permutation a[1]...a[n] we can find the following one by:

      Find permutation following a[1]...a[n]
      find longest "suffix" a[k+1]...a[n] in reverse alphabetical order
      find item a[j] among a[k+1]...a[n] which is next in order after a[k]
      swap a[j] with a[k]   (a[k+1]...a[n] will still be in reverse order)
      reverse the order of a[k+1]...a[n]

   The longest reverse suffix can be found by scanning a backwards from the
   end. The reversal in the last line can be done by swapping a[k+1] with
   a[n], a[k+2] with a[n-1] etc. Thus the whole process takes an amount of
   time proportional to the length of the suffix. The average time taken
   is the average length of the suffix.

   Now in 1/2 of all cases, the suffix will be of length 1 as a[n-1] will
   be less than a[n]. In 1/2 of the remaining cases (1/4 of the time), the
   suffix will be of length 2 as a[n-2] will be less than a[n-1].
   Thus the average length is approximately:

      1/2 * 1  +  1/4 * 2  +  1/8 * 3  + ...

      =  sum of  i/2^i

      =  O(1)

   Thus the algorithm takes an average of O(1) time on a random permutation.
   This is an improvement over the previous algorithm which takes O(n) time
   to scan the array b even when k = 1, so takes at least O(n) time per