Solving Algorithms

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

The post Solving Algorithms first appeared on COMPLIANT PAPERS.