===========================================================================
CSC 373                     Homework Exercise 4                   Fall 2008
===========================================================================

Due: by 6pm on Tue 21 Oct
Worth: 1.5%

For each question, please write up detailed answers carefully: make sure
that you use notation and terminology correctly, and that you explain and
justify what you are doing.  Marks *will* be deducted for incorrect or
ambiguous use of notation and terminology, and for making incorrect,
unjustified, ambiguous, or vague claims in your solutions.


1.  Given an unsorted list of n >= 3 distinct numbers, we wish to find the
    three smallest numbers (in order).  The obvious algorithm first finds
    the smallest element by making n-1 comparisons, then finds the smallest
    of the remaining elements by making n-2 comparisons, and then finds the
    smallest of the rest by making n-3 comparisons; this algorithm makes
    3n - 6 comparisons in total, and we would like to do better.

    Suppose that you have access to the following subroutines.

        # Returns (min(a,b),max(a,b)), using 1 comparison.
        minmax(a,b):
            if a < b:  return (a,b)
            else:      return (b,a)

        # Returns the three smallest of a,b,c, in order,
        # using no more than 3 comparisons.
        solve_three(a,b,c):
            (a,c) = minmax(a,c)  # after this, a < c
            (b,c) = minmax(b,c)  # after this, b < c
            (a,b) = minmax(a,b)  # after this, a < b
            return (a,b,c)  # at this point, a < b < c

        # Returns the three smallest of a,b,c,d, in order,
        # using no more than 5 comparisons.
        solve_four(a,b,c,d):
            # code omitted

        # Returns the three smallest of a,b,c,d,e, in order,
        # using no more than 7 comparisons.
        solve_five(a,b,c,d,e):
            # code omitted

    Give a divide-and-conquer algorithm that takes a list of n distinct
    elements (n >= 3) and returns the three smallest elements (in order).
    Your algorithm may make calls to any of the subroutines defined above.
    Moreover, if C(n) is the maximum possible number of comparisons that
    your algorithm makes when working on n input elements, then C should
    satisfy the following recurrence relation:

        C(3) <= 3,
        C(4) <= 5,
        C(5) <= 7,
        C(n) <= C(|_n/2_|) + C(|^n/2^|) + 3, for all n >= 6.

    You should write your algorithm in pseudo-code (in a style similar to
    the subroutines above) together with a /short/ English description of
    how your algorithm works, as a justification that it is correct.  Then,
    to conclude that this is better than the obvious algorithm, prove that
    for all n >= 3, C(n) <= 2n - 3.

    *Hint:*  Notice that the form of the recurrence relation satisfied by C
    dictates the way in which the algorithm must work.


2.  [*BONUS!*]
    Give algorithms for solve_four() and solve_five(), that use the correct
    number of comparisons, and justify briefly that your algorithms are
    correct -- you may make calls to subroutine minmax() in your answers.