Homework Exercise 4

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 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.