Laboratory Analysis

  1. (Total: 8 pts) A grad student comes up with the following algorithm to sort an array A[1..n] that
    works by first sorting the first 2/3rds of the array, then sorting the last 2/3rds of the (resulting) array,
    and finally sorting the first 2/3rds of the new array.
    1: function G-SORT(A, n) . takes as input an array of n numbers, A[1..n]
    2: G-sort-recurse(A, 1, n)
    3: end function
    4: function G-SORT-RECURSE(A, , u) 5: if u − ≤ 0 then
    6: return . 1 or fewer elements already sorted
    7: else if u − = 1 then . 2 elements 8: if A[u] < A[] then . swap values
    9: temp ← A[u]
    10: A[u] ← A[] 11: A[] ← temp
    12: end if
    13: else . 3 or more elements
    14: size ← u − + 1 15: twothirds ← d(2 ∗ size)/3e 16: G-sort-recurse(A,, + twothirds − 1) 17: G-sort-recurse(A, u − twothirds + 1, u) 18: G-sort-recurse(A,, ` + twothirds − 1)
    19: end if
    20: end function
    1
    a (4 pts). First, prove that the algorithm correctly sorts the numbers in the array (in increasing order).
    After showing that it correctly sorts 1 and 2 element intervals, you may make the (incorrect) assumption that the number of elements being passed to G-sort-recurse is always a multiple of 3 to simplify
    the notation (and drop the floors/ceilings).
    Solution.
    2
    b (1 pts). Next, Derive a recurrence for the algorithm’s running time (or number of comparisons
    made).
    Solution.
    3
    c (3 pts). Finally, obtain a good asymptotic upper bound (big-O) for your recurrence.
    Solution.
    4
  2. (Total: 3 pts) Least counterexample: Give a proof by contradiction using the least counterexample
    method that:
    Xn
    i=0
    i =
    n(n + 1)
    2
    for all n ≥ 0.
    Solution.
    5
  3. (Total: 8 pts) Define the sequence Tn = (n − 1) + n−1
    n2 ·
    Pn−1
    k=1 Tk. Prove, by induction, for all n ≥ 1,
    that Tn ≤ 2n.
    Solution.
    6
  4. (Total: 14 pts) Let S(n) be defined, for n ≥ 2, as S(n) = 2S(d
    n
    2
    e) + nlog2
    (n). For n = 1, the value
    is S(n) = 1.
    (a) (4 pts) Can you apply Master Theorem on S(n)? If no, precisely state why not. If yes, apply the
    theorem and derive the bound.
    Solution.
    7
    (b) (10 pts) Now use a method, besides Master Theorem, to prove that S(n) ∈ O(n(log2n)
    2
    ).
    Solution.
    8
  5. (5 points) You are presented with two sorting algorithms. You have to select one of them. The
    documentation provided states that both of these algorithms perform Ω(n
    3
    ) comparisons in the worst
    case. You want to build a fast program and therefore want to optimise speed. Does it matter which
    algorithm you select? How would you make the decision?
    Solution.
    9
  6. (Total: 12 pts)You are interested in building a coffeeshop and charging station beside a freeway running between two cities. Let n be the number of interchanges between the cities, and number them
    consecutively so that interchange 0 is at the first city, 1 is the next interchange, and so on, with n − 1
    being the interchange at the other city. We say each interchange i is adjacent to interchanges i−1 and
    i + 1 (only).
    Each interchange i has a cost c(i) to construct a coffee shop/charging station. Call an interchange
    i a local minimum if (and only if) the cost of building there is less than the costs of building at the
    adjacent interchanges, i.e. both c(i) < c(i + 1) and c(i) < c(i − 1). You want to ensure that you
    build at a local minimum so that no one can build a coffeeshop/charging station more cheaply at an
    adjacent interchange.
    You can assume that:
    • n ≥ 3, so there is at least one interchange between the cities.
    • The costs at the cities c(0) and c(n−1) are both known to be the same large number (say 100n).
    • The other costs are all different and are all strictly less than c(0) (and thus also less than c(n−1)).
    The difficulty is that the c(i) values are not known ahead of time (except for c(0) and c(n − 1)) and it
    is expensive to determine the cost of building at any interchange.
    The goal is to create a divide and conquer algorithm that finds any interchange k that is a local
    minimum while examining relatively few of the c(i) values. Although there may be many local
    minimums, your algorithm need only find one of them.
    (a) (2 points) First, prove that a local minimum exists.
    Solution.
    10
    (b) (5 points) Clearly describe a divide and conquer algorithm for the problem.
    Two pages have been left blank for this question. If you do not need both the page, please leave
    the second page blank.
    Solution.
    11
    12
    (c) (3 points) Prove that your algorithm is correct.
    Solution.
    13
    (d) (2 points) Analyze the (worst case) number of interchange costs (i.e. c(i) values) examined by
    your algorithm as a function of n.
    Solution.
find the cost of your paper