CSCI 570 – Summer 2020 – HW 3
Due July 24th
Note:
• It is recommended that you read chapters 4 and 5 from Klienberg and
Tardos.
• The homework covers Divide and conquer algorithms and recurrence re-
lations. 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 Kleinberg and Tardos.
• It also covers Dynamic programming. It is recommended that you read
chapter 6.1 to 6.4 from Klienberg and Tardos.
1 Graded Problems
1. The recurrence T (n) = 7T (n/2) + n2 describes the running time of an
algorithm ALG. A competing algorithm ALG
′
has a running time of
T
′
(n) = aT
′
(n/4) + n2 log n. What is the largest value of a such that
ALG
′
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) + n2 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)
1
(g) T (n) = 2T (n/2)−
√
n
3. 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.
5. Solve Kleinberg and Tardos, Chapter 5, Exercise 3.
6. Solve Kleinberg and Tardos, Chapter 5, Exercise 6.
7. 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 al-
gorithm is allowed to make at most O(log n) pairwise comparisons
between elements of A.
8. 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 ver-
tex 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.
2
(b) Give a divide and conquer algorithm to find the vertex with the
largest y coordinate in O(log n) time.
9. 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
′
= [3, 5, 7, 11, 1], after second ro-
tation A
′′
= [5, 7, 11, 1, 3].
10. From the lecture, you know how to use dynamic programming to solve
the 0-1 knapsack problem where each item is unique and only one of each
kind is available. Now let us consider knapsack problem where you have
infinitely many items of each kind. Namely, there are n different types of
items. All the items of the same type i have equal size wi and value vi.
You are offered with infinitely many items of each type. Design a dynamic
programming algorithm to compute the optimal value you can get from a
knapsack with capacity W .
11. Given a non-empty string s and a dictionary containing a list of unique
words, design a dynamic programming algorithm to determine if s can
be segmented into a space-separated sequence of one or more dictionary
words. If s=“algorithmdesign” and your dictionary contains “algorithm”
and “design”. Your algorithm should answer Yes as s can be segmented
as “algorithmdesign”.
12. Given n balloons, indexed from 0 to n − 1. Each balloon is painted with
a number on it represented by array nums. You are asked to burst all the
balloons. If the you burst balloon i you will get nums[left] ∗ nums[i] ∗
nums[right] coins. Here left and right are adjacent indices of i. After
the burst, the left and right then becomes adjacent. You may assume
nums[−1] = nums[n] = 1 and they are not real therefore you can not
burst them. Design an dynamic programming algorithm to find the max-
imum coins you can collect by bursting the balloons wisely. Analyze the
running time of your algorithm.
Here is an example. If you have the nums arrays equals [3, 1, 5, 8]. The
optimal solution would be 167, where you burst balloons in the order of
1, 5 3 and 8. The left balloons after each step is:
[3, 1, 5, 8]→ [3, 5, 8]→ [3, 8]→ [8]→ []
And the coins you get equals:
167 = 3 ∗ 1 ∗ 5 + 3 ∗ 5 ∗ 8 + 1 ∗ 3 ∗ 8 + 1 ∗ 8 ∗ 1.
3
13. Solve Kleinberg and Tardos, Chapter 6, Exercise 5.
2 Practice Problems
1. Solve Kleinberg and Tardos, Chapter 6, Exercise 6.
2. Solve Kleinberg and Tardos, Chapter 6, Exercise 10.
3. Solve Kleinberg and Tardos, Chapter 6, Exercise 24.
4