[SOLVED] Csci570 hw5 this homework assignment covers divide and conquer algorithms and recurrence relations.

CSCI570 HW5This homework assignment covers divide and conquer algorithms and recurrence relations. It is
recommended that you read all of chapter 5 from Klienberg and Tardos, the Master Theorem from
the lecture notes, and be familiar with the asymptotic notation from chapter 2 in Klienberg and
Tardos.1. The recurrence T(n) = 7T(n/2) + n
2 describes the running time of an algorithm ALG. A
competing algorithm ALG0
has a running time of T
0
(n) = aT0
(n/4) + n
2
log n. What is the
largest value of a such that ALG0
is asymptotically faster than ALG?2. Solve the following recurrences by giving tight Θ-notation bounds in terms of n for sufficiently
large n. Assume that T(·) represents the running time of an algorithm, i.e. T(n) is positive
and non-decreasing function of n and for small constants c independent of n, T(c) is also a
constant independent of n. Note that some of these recurrences might be a little challenging
to think about at first.(a) T(n) = 4T(n/2) + n
2
log n
(b) T(n) = 8T(n/6) + n log n
(c) T(n) = √
6006T(n/2) + n
√
6006(d) T(n) = 10T(n/2) + 2n
(e) T(n) = 2T(
√
n) + log2n
(f) T
2
(n) = T(n/2)T(2n) − T(n)T(n/2)
(g) T(n) = 2T(n/2) −
√
n3. Consider the following algorithm StrangeSort which sorts n distinct items in a list A.
(a) If n ≤ 1, return A unchanged.
(b) For each item x ∈ A, scan A and count how many other items in A are less than x.
(c) Put the items with count less than n/2 in a list B.(d) Put the other items in a list C.
(e) Recursively sort lists B and C using StrangeSort.
(f) Append the sorted list C to the sorted list B and return the result.Formulate a recurrence relation for the running time T(n) of StrangeSort on a input list of
size n. Solve this recurrence to get the best possible O(·) bound on T(n).4. Solve Kleinberg and Tardos, Chapter 5, Exercise 1.2 Practice Problems
1. Solve Kleinberg and Tardos, Chapter 5, Exercise 3.
2. Solve Kleinberg and Tardos, Chapter 5, Exercise 6.
3. Consider an array A of n numbers with the assurance that n > 2, A[1] ≥ A[2] and A[n] ≥
A[n − 1]. An index i is said to be a local minimum of the array A if it satisfies 1 < i < n,
A[i − 1] ≥ A[i] and A[i + 1] ≥ A[i].
(a) Prove that there always exists a local minimum for A.
(b) Design an algorithm to compute a local minimum of A. Your algorithm is allowed to
make at most O(log n) pairwise comparisons between elements of A.4. A polygon is called convex if all of its internal angles are less than 180◦
and none of the edges
cross each other. We represent a convex polygon as an array V with n elements, where each
element represents a vertex of the polygon in the form of a coordinate pair (x, y). We are told
that V [1] is the vertex with the least x coordinate and that the vertices V [1], V [2], · · · , V [n]
are ordered counter-clockwise. Assuming that the x coordinates (and the y coordinates) of the
vertices are all distinct, do the following.(a) Give a divide and conquer algorithm to find the vertex with the largest x coordinate in
O(log n) time.
(b) Give a divide and conquer algorithm to find the vertex with the largest y coordinate in
O(log n) time.5. Given a sorted array of n integers that has been rotated an unknown number of times, give
an O(log n) algorithm that finds an element in the array. An example of array rotation is as
follows: original sorted array A = [1, 3, 5, 7, 11], after first rotation A
0
= [3, 5, 7, 11, 1], after
second rotation A
00 = [5, 7, 11, 1, 3].