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 Klienberg 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?
Solution: We shall use Master Theorem to evaluate the running time of
the algorithms.
(a) For T (n), setting 0 < � < log2 7−2 ≈ 0.81 we have n2 = O(nlog2 7−�).
Hence T (n) = Θ(nlog2 7).
(b) For T
′
(n), if log4 a > 2 then setting 0 < δ < log4 a − 2 implies
n2 log n = O(nlog4 a−δ) and hence T
′
(n) = Θ(nlog4 a).
To have T
′
(n) asymptotically faster than T (n), we need T
′
(n) = O(T (n)),
which implies nlog4 a = O(nlog2 7) and therefore log4 a < log2 7 =⇒ a <
49. Since other expressions for run time of ALG
′
require log4 a ≤ 2 =⇒
a ≤ 16 < 49, the largest possible integer value of a such that ALG
′
is
asymptotically faster than ALG is a = 48.
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
1
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)
(g) T (n) = 2T (n/2)−
√
n
Solution: In some cases, we shall need to invoke the Master Theorem with
one generalization as described next. If the recurrence T (n) = aT (n/b) +
f(n) is satisfied with f(n) = Θ(nlogb a logk n) for some k ≥ 0, then T (n) =
Θ(nlogb a logk+1 n).
(a) Observe that f(n) = n2 log n and nlogb a = n2, so applying the gen-
eralized Master’s theorem, T (n) = Θ(n2 log2 n).
(b) Observe thatnlogb a = nlog6 8 and f(n) = n log n = O(nlog6 8−�) for
any 0 < � < log6 8 − 1. Thus, invoking Master’s Theorem gives
T (n) = Θ(n logb a) = Θ(n
log6 8).
(c) We have nlogb a = nlog2
√
6006 = n0.5 log2 6006 = O(n0.5 log2 8192) =
O(n13/2) and f(n) = n
√
6006 = Ω(n
√
4900) = Ω(n70) = Ω(n13/2+�) for
any 0 < � < 63.5. Thus from Master’s Theorem T (n) = Θ(f(n)) =
Θ(n
√
6006).
(d) We have nlog−ba = nlog210 and f(n) = 2n = Ω(nlog2 10+�) for any � >
0. Therefore Master’s Theorem implies T (n) = Θ(f(n)) = Θ(2n).
(e) Use the change of variables n = 2m to get T (2m) = 2T2m/2 + m.
Next, denoting S(m) = T (2m) implies that we have the recurrence
S(m) = 2S(m/2) + m. Note that S(·) is a positive function due to
the monotonicity of the increasing map x7 → 2x and the positivity
of T (·). All conditions for applicability of Master’s Theorem are
satisfied and using the generalized version gives S(m) = Θ(mlogm)
on observing that f(m) = m and m logb a = m. We express the
solution in terms of T (n) by
T (n) = T (2m) = S(m) = (m logm) = (log2 n log log2 n)
, for large enough n so that the growth expression above is positive.
(f) Owing to the unusual nature of this recurrence, we’ll try to be a little
descriptive in the solution since applicability of Master’s Theorem is
2
not foreseeable. Since T (n) is positive for every n > 0, dividing the
given recurrence by T (n)T (n/2) gives
T (n)
T (n/2)
=
T (2n)
T (n)
− 1
. Setting S(n) = T (2n)/T (n) for n ≥ 2, we get the recurrence
S(n/2) = S(n)1 which is equivalent to S(n) = S(n/2) + 1. Positivity
of T (·) implies positivity of S(·) and a step-by-step solution of the
recurrence gives
S(n) = S(n/2) + 1 = S(n/4) + 2 = · · · = S(
n
2k−1
+ k − 1)
, where k = log2 n and
S(
n
2k−1
) = S(
2n
2log 2n
) = S(2) =
T (4)
T (2)
= c0
. From the recurrence relation for T (n), we have T (4) = 2T (2) + 2,
so that c0 = T (4)/T (2) = 2 + 2/T (2) > 2. Furthermore, (1) amounts
to S(n) = log2 n+ c01. Using this expression for S(n), we have
T (n) =S(
n
2
)T (
n
2
) (1a)
=(log2
n
2
+ c0 − 1)T (
n
2
) (1b)
=(log2
n
2
+ c0 − 1)(log2
n
4
+ c0 − 1)T (
n
4
) (1c)
= · · ·
=(log2
n
2
+ c0 − 1)(log2
n
4
+ c0 − 1) · · · (log2
n
2k−1
+ c0 − 1)T (
n
2k−1
)
(1d)
=T (2)
k−1∏
l=1
(log2
n
2l
+ c0 − 1) (1e)
=T (2)
k−1∏
l=1
(log2 n+ c0 − l − 1) (1f)
=T (2)
log2 n−2∏
p=0
(c0 + p) (1g)
=Θ((log2 n+ c0 − 2)!) (1h)
where (1b) uses the definition of S(n), (1d) is the fully expanded
expression for the recurrence on T (n), (1g) employed the substitution
p = log2nl1, and (1h) assumed that c0 + log2 n is an integer. If
you want to be more precise, you can use the function to write
3
T (n) = Θ(Γ(log2 n + c01)) even when c0 + log2 n is not an integer,
but this is not mandatory.
Next we shall employ Stirling’s approximation to dispense with the
factorial in (1h). Recall that Stirling’s approximation implies
m! = Θ(mm+0.5e−m)
. Setting c0 − 2 = d, we have
Θ((log2 n+ c0 − 2)!) =Θ((d+ log2 n)
d+0.5+log2 ne−d−log2 n) (2a)
=Θ((1 +
d
log2 n
)d+0.5+log2 n(log2 n)
d+0.5+log2 ne−d−log2 n)
(2b)
=Θ((log2 n)
c0−1.5+log2 nn− log2 �) (2c)
where we have used the constant upper and lower bounds (for log2 n ≥
1)
(1 +
d
log2 n
)d+0.5+log2 n = exp[(d+ 0.5 + log2 n) log(1 +
d
log2 n
)]
= exp[(
d+ 0.5
log2 n
+ 1)
log(1 + d
log2 n
)
d/ log2 n
]
≤ exp[(
d+ 0.5
1
+ 1)]
and
(1 +
d
log2 n
)d+0.5+log2 n ≥ 1d+0.5+log2 n = 1
Our final answer is essentially (2c) which gives
T (n) = Θ(n− log2 e(log2 n)
c0−1.5+log2 n)
(g) For this recurrence, we cannot apply Master’s Theorem since pattern
matching with the template recurrence relation T (n) = aT (n/b) +
f(n) gives the f(n) term as negative. We have,
T (n) =2T (n/2)−
√
n (3a)
=2(2T (n/4)−
√
n/2)−
√
n = 22T (n/22)−
√
n(1 +
√
2) (3b)
=22(2T (n/23)−
√
n/22)−
√
n(1 +
√
2) = 23T (n/23)−
√
n(1 +
√
2 +
√
22)
(3c)
= · · · = 2k−1T (n/2k−1)−
√
n(1 +
√
n+
√
22 + · · ·+
√
2k−2)
(3d)
=2k−1T (n/2k−1)−
√
n(
√
2k−1 − 1
√
2− 1
) (3e)
4
where k = log2n, (3d) represents the fully expanded form of the
recurrence for T (n) and (3e) was obtained using the formula for sum
of a geometric progression. Further simplification of (3e) gives
T (n) =
2log2 n
2
T (
2n
2log2 n
)−
√
n(
√
2log2 n −
√
2
2−
√
2
) (4a)
=
n
2
T (2)−
√
n(
√
n−
√
2
2−
√
2
) (4b)
=n(
T (2)
2
−
1
2−
√
2
+
√
2n
2−
√
2
(4c)
resulting in the following tow cases:
Case 1. If T (2) >
√
2/(
√
2 − 1), then the coefficient of n in (4c) is
positive and therefore T (n) = Θ(n).
Case 2: If T (2) =
√
2/(
√
2 − 1), then the coefficient of n in (4c) is
zero and thus, T (n) = Θ(
√
n).
Note that T (2) <
√
2/(
√
2−1) is not possible, since that would imply
that T (n) is asymptotically negative which contradicts the premise
of the question as T (n) denotes running time of an algorithm.
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).
Solution: Suppose that A has n elements. Then steps (c), (d) and (f)
can take up to O(n) time, step (a) takes constant time and step (e) takes
2T (n/2) time. Step (b), when implemented in the way described above,
takes Θ(n2) time since each scan of A takes Θ(n) time and the scan is
repeated for each of the n elements of A. Counting times taken for all the
steps, we have
T (n) = 2T (n/2) +O(n) + Θ(n2) +O(1) = 2T (n/2) + Θ(n2)
5
Comparing the above recurrence with T (n) = aT (n/b) + f(n) we have
f(n) = Θ(n2) and nlogb a = n so that Master’s Theorem gives T (n) =
Θ(n2).
Note: Although steps (b) and (c) together can be implemented more
efficiently by sorting A (or finding the median of A) first, the question
specifically asks for the running time of the given implementation without
any further optimizations.
4. Solve Kleinberg and Tardos, Chapter 5, Exercise 1.
Solution: Ideas and Notation: Let us denote the combined set of ele-
ments as A
⋃
B. The core idea behind the solution to this problem is to
recursively discard from consideration, an equal number of elements from
the left and right of the median of A
⋃
B (so that the median of the re-
duced set is the same as the median of the original set), until we are left
with only two elements for which the median can be explicitly computed.
Let A2 and Bs respectively represent the arrays A and B sorted in as-
cending order. For any 1 ≤ i ≤ n, the design of the databases implies that
As[i] and Bs[i] can be obtained by one query to their respective databases.
Furthermore, we will work with the definition that the median for a set
of m distinct elements is the dm/2eth element when all the elements are
sorted in ascending order.
Algorithm: We recursively define the procedure median(l, a, b) below such
that it returns the median of the set As[a + 1 : a + l]
⋃
Bs[b + 1 : b + l].
Then the answer we seek will be the return value of the function call
median(n, 0, 0).
1: function MEDIAN(l, a, b)
2: if l = 1 then
3: return min(As[a+ 1], B2[b+ 1])
4: end if
5: k ← dl/2e
6: if As[a+ k] < Bs[b+ k] then
7: return MEDIAN(k, a+ bl/2c, b)
8: else
9: return MEDIAN(k, a, b+ bl/2c)
10: end if
11: end function
Query Complexity : Assuming that A and B had n elements each, let
T (n) denote the number of database queries made by the function call
median(n, 0, 0). For l = 1, median(l, a, b) executes line 3 using 2 database
queries, regardless of values of a and b, implying T (1) = 2. For l > 1, line
6 requires 2 explicit database queries and exactly one of lines 7 or ??
is executed, amounting to T (dn/2e) implicit queries. Therefore, T (n) =
T (dn/2e) + 2. One can either assume n to be a power of 2 to get the
6
simplified recurrence relation T (n) = T (n/2) + 2 and invoke Master’s
Theorem to arrive at T (n) = Θ(log n), or solve the original recurrence
from first principles (as below) to arrive at T (n) ≤ 2dlog2 ne+ 2.
T (n) =T (2log2 n)
≤T (2dlog2 ne)
=T (2dlog2 ne−1) + 2
=T (2dlog2 ne−2) + 4
= · · · = T (20) + 2dlog2 ne
=2dlog2 ne+ 2
Proof of Correctness: We need to show that for any l ∈ {1, 2, · · · , n} and
any valid indices a, b ∈ {0, 1, · · · , n1}, median(l, a, b) correctly finds the
median of As[a + 1 : a + l]
⋃
Bs[b + 1 : b + l]. We switch to relative
indexing for convenience, i.e. let Asa[1 : l] = A
s[a + 1 : a + l] and Bsb [1 :
l] = Bs[b+1 : b+ l]. Also, let (Asa
⋃
Bsb )
s denote the array Asa
⋃
Bsb sorted
in ascending order. For l = 1, line 3 correctly returns the median of 2
elements as per our working definition of the median. For l > 1, we have
a total of 2l elements and utilizing the fact that all elements across A and
B are distinct, we have two cases.
(a) Let Asa[k] < B
s
b [k] so that line 7 is executed. Then the k elements
in Asa[1 : k] are all less than B
s
b [k]. Furthermore, the k1 elements in
Bsb [1 : k1] are also less than B
s
b [k] so that there are at least 2k =
2dl/2e ≥ l elements less than or equal to Bsb [k] in A
s
a
⋃
Bsb . Since the
median of Asa
⋃
Bsb is the l-th element when sorted in ascending order,
it must be less than or equal to Bsb [k] implying that the elements in
Bsb [k + 1 : l] are strictly to the right of the median in (A
s
a
⋃
Bsb )
s.
Similarly, we note that the lk+ 1 elements in Bsb [k : l] are all greater
than Asa[k]. Moreover, the k elements in A
s
a[lk+1 : l] are greater than
or equal to Asa[k] (since lk+ 1 = ldl/2e+ 1 = dl/2e+ 1 ≥ dl/2e = k),
so that there are at least (lk + 1) + k = l + 1 elements greater than
or equal to Asa[k] in A
s
a
⋃
Bsb . Since there are exactly l + 1 elements
greater than or equal to the median in Asa
⋃
Bsb , the elements in
Asa[1 : lk] are strictly to the left of the median in (A
s
a
⋃
Bsb )
s. Line 7
finds the median of Asa[dl/2e + 1 : dl/2e + k]
⋃
Bsb [1 : k]. Observing
that dl/2e = ldl/2e = lk, line 7 is finding the median of Asa[lk + 1 :
l]
⋃
Bsb [1 : k] and thus is discarding exactly lk elements to the left as
well as to the right of the original median median(l, a, b) in the new
function call median(k, a+ bl/2c, b). This is correct since discarding
an equal number of elements from either side of the median does not
change the median element.
(b) If Asa[k] > B
s
b [k], then line 9 is executed. To prove correctness,
the preceding argument can be repeated with the roles of A and B
7
reversed. So we shall have the elements Asa[k + 1 : l] strictly to
the right of the median and the elements Bsb [1 : lk] strictly to the
left of the median, and all of these elements are discarded in the
line 9 function call median(k, a, b+ dl/2e) which finds the median of
Asa[1 : k]
⋃
Bsb [lk + 1 : l].
5. Solve Kleinberg and Tardos, Chapter 5, Exercise 3.
Solution: Let us call a card to be a majority card if it belongs to a
set of equivalent cards encompassing at least half of the total number of
cards to be tested, i.e. for a total of n cards, if there is a set of more
than n/2 cards that are all equivalent to each other, then any one of these
equivalent cards constitutes a majority card. To keep the conquer step
as simple as possible, we shall require the algorithm to return a majority
card if one exists and return nothing if no majority card exists (this can
be implemented by indexing the cards from 1 to n and a return value of
0 could correspond to returning nothing). Then the algorithm consists of
the following steps, with S denoting the set of cards being tested by the
algorithm and |S| denoting its cardinality.
(a) If |S| = 1 then return the card.
(b) If |S| = 2 then test whether the cards are equivalent. If they are
equivalent then return either card, else return nothing.
(c) If |S| > 2 then arbitrarily divide the set S into two disjoint subsets
S1 and S2 such that |S1| = b|S|/2c and |S2| = d|S|/2e.
(d) Call the algorithm recursively on the set of cards S1.
(e) If a majority card is returned (call it card m1), then test it for equiv-
alence against all cards in S {m1}. If m1 is equivalent to at least
b|S|/2c other cards in S, then return card m1.
(f) If m1 is not equivalent to at least b|S|/2c other cards in S, OR if no
majority card was returned by the recursive call on S1, then call the
algorithm recursively on the set of cards S2.
(g) If a majority card is returned (call it card m2), then test it for equiva-
lence against all cards in S m2. If m2 is equivalent to at least b|S|/2c
other cards in S, then return card m2.
(h) If m2 is not equivalent to at least b|S|/2c other cards in S, OR if no
majority card was returned by the recursive call on S2, then return
nothing.
Complexity: Let T (n) be the number of equivalence tests performed by the
algorithm on a set of n cards. We have T (2) = 1 from step (b). Steps (d)
and (f) can incur a total of T (bn/2c)+T (dn/2e) equivalence tests whereas
steps (e) and (g) could require up to 2(n1) equivalence tests. Therefore,
we have the recurrence T (n) ≤ T (bn/2c) + T (dn/2e) + 2n2, which can
8
be solved from first principles like in (6). Alternatively, the recurrence
simplifies to T (n) ≤ 2T (n/2) + 2n2 on assuming n to be a power of 2.
The simplified recurrence can be solved using Master’s Theorem to yield
T (n) = O(n log n).
Proof of Correctness: We need to show that the algorithm returns the
correct answer in both cases, viz. majority card present and majority
card absent. If |S| = 1 then this single card forms a majority by our
definition and is correctly returned by step (a). If |S| = 2 then either
card is a majority card if both cards are equivalent and neither card is
a majority card if they are not equivalent. Clearly, step (b) implements
exactly this criterion. For steps (d)-(h) we consider what happens when a
majority card is present or absent.
(a) Majority card present: If a majority card is present (say m), then at
least one of the subsets S1 or S2 must have m as a majority card. It
is simple to see this by contradiction since if neither S1 nor S2 have
a majority card (or if m is not a mojority card in either subset) then
necessarily the number of equivalent cards (or cards equivalent to m,
including m) is upper bounded by 0.5b|S|/2c + 0.5d|S|/2e = 0.5|S|
which immediately implies the absence of any majority card in S.
Thus, at least one of m 1 (in step (e)) or m2 (in step (g)) will be
returned and at least one of these will be equivalent to m. Since
steps (e) and (g) respectively test m1 and m2 against all other cards,
the algorithm will necessarily find one of them to be equivalent to m
and hence also as a majority card (since the set of majority cards is
necessarily unique) and would return the same.
(b) Majority card absent: There are multiple possibilities in this scenario.
If neither S1 nor S2 returns a majority card then clearly there is no
majority card, and the algorithm terminates at step (h) returning
nothing. If m1 or m2 or both are returned as valid majority cards
then they would be respectively discarded as candidates in steps (e)
and (g) when checked against all other cards in S as they are not truly
in majority on the set S. Thus the algorithm correctly terminates in
step (h) returning nothing.
Note: There are a lot of repeated equivalence tests in the algorithm
described above, primarily because we are solving the problem in a top-
down manner. Can you think of a bottom-up approach to solving this
problem with potentially fewer equivalence tests? Hint: It is possible
to achieve O(n) complexity in terms of the number of equivalence tests
required.
6. Solve Kleinberg and Tardos, Chapter 5, Exercise 6.
Solution: For simplicity, we shall identify a binary tree by its root node.
Let us denote the values at the root node (level 1), the left child node (level
9
2) and the right child node (level 2) respectively by R, l and r. Consider
the following algorithm with a complete binary tree as the input.
(a) If both left and right subtrees are empty, then return root node.
(b) If R < l and R < r then return root node.
(c) If l < R < r then call the algorithm recursively on the left subtree
rooted at the left child node.
(d) If r < R < l then call the algorithm recursively on the right subtree
rooted at the right child node.
Complexity: A complete binary tree with n nodes has a depth d such that
n = 2d1. In each function call, exactly one of the steps (a)-(d) will be
executed. Moreover, step (a) or (b) is only executed in the last function
call whereas every other function call executes either step (c) or step (d).
It is clear that execution of either step (c) or step (d) has the effect of
descending one level on the binary tree (either the left or the right subtree
is the next function call argument), so that the algorithm has to terminate
after at most d = log2(n + 1) recursive calls. Each function call involves
at most 3 probes, viz. values at the root node, the left child node and the
right child node, and therefore a total of at most 3 log2(n+ 1) = O(log n)
probes are executed.
Proof of Correctness: It is clear that the algorithm terminates in either
step (a) or step (b).
(a) If the algorithm terminates in step (b) then a node x with value R is
returned such that R < l and R < r are satisfied, i.e. the returned
node has smaller value than both of its children. Since the tree rooted
at x was passed as input to this final function call, it had to have
originated in either step (c) or step (d) of the penultimate recursive
function call. If the origin was step (c) of the penultimate call then
node x was the left child node with value less than its parent node.
If the origin was step (d) of the penultimate call then node x was the
right child node with value less than its parent node. In either case,
node x has value less than its parent node. Since node x has value
less than its parent node as well as its children nodes, it is a local
minimum and hence a correct solution.
(b) If the algorithm terminates in step (a) then a leaf node x is returned.
We can repeat the foregoing argument to establish that node x has
a value less than its parent node. Since node x has no children, it
therefore is a local minimum and hence a correct solution.
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.
10
(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.
Solution: We prove the existence of a local minimum by induction. For
n = 3, we have A[1] ≥ A[2] and A[3] ≥ A[2] by the premise of the question
and therefore A[2] is a local minimum. Let A[1 : n] admit a local minimum
for n = k. We shall show that A[1 : k+1] also admits a local minimum. If
we assume that A[2] A[3] then A[2] is a local minimum for A[1 : k+1] since
A[1] ≥ A[2] by premise of the question. So let us assume A[2] > A[3]. In
this case, the k length array A[2 : k+ 1] = A′[1 : k] satisfies the induction
hypothesis (A′[1] = A[2] ≥ A[3] = A′[2] and A′[k1] = A[k] ≥ A[k + 1] =
A′[k]) and hence admits a local minimum. This is also a local minimum
for A[1 : k + 1]. Hence, proof by induction is complete.
Consider the following algorithm with array A of length n as the input,
and return value as a local minimum element.
(a) If n = 3, return A[2].
(b) If n > 3,
i. k ← bn/2c.
ii. If A[k] ≤ A[k1] and A[k] ≤ A[k + 1] then return A[k].
iii. If A[k] > A[k1] then call the algorithm recursively on A[1 : k],
else call the algorithm recursively on A[k : n].
Complexity: If the running time of the algorithm on an input of size n is
T (n), then it involves a constant number of comparisons and assignments
and a recursive function call on either A[1 : bn/2c] (size = bn/2c) or
A[bn/2c : n] (size = nbn/2c = dn/2e). Therefore, T (n) ≤ T (dn/2e) +
Θ(1). Assuming n to be a power of 2, this recurrence simplifies to T (n) ≤
T (n/2) + Θ(1) and invoking Master’s Theorem gives T (n) = O(log n).
Proof of Correctness: We employ induction. For n = 3 it is clear that
step (a) returns a local minimum using the premise of the question that
A[1] ≥ A[2] and A[3] ≥ A[2]. Let us assume that the algorithm correctly
finds a local minimum for all n m and consider an input of size m + 1.
Then k = b(m + 1)/2c. If step (b)(ii) returns, then a local minimum is
found by definition and the algorithm gives the correct output. Otherwise,
step (b)(iii) is executed since one of A[k] > A[k1] or A[k] > A[k+ 1] must
be true for step (b)(ii) to not return. If A[k] > A[k1], then A[1 : k] must
admit a local minimum by the first part of the question and the given
algorithm can find it correctly if k ≤ m, using the induction hypothesis on
the correctness of the algorithm for inputs of size up to m. This holds if
b(m+ 1)/2c ≤ m which is true for all m ≥ 1. Similarly, if A[k] > A[k+ 1],
then A[k : m + 1] must admit a local minimum by the first part of the
question and the given algorithm can find it correctly if mk+2 ≤ m, using
the induction hypothesis on the correctness of the algorithm for inputs of
11
size up to m. This holds if k ≥ 2 or equivalently b(m + 1)/2c ≥ 2 which
holds for all m ≥ 3. Therefore, the algorithm gives the correct output for
inputs of size m+ 1 and the proof is complete by induction.
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.
(b) Give a divide and conquer algorithm to find the vertex with the
largest y coordinate in O(log n) time.
Solution: Since V [1] is known to be the vertex with the minimum x-
coordinate (leftmost point), moving counter-clockwise to complete a cycle
must first increase the x-coordinates and then after reaching a maximum
(rightmost point), should decrease the x-coordinate back to that of V [1].
To see this more formally, we claim that there cannot be two distinct local
maxima in the x-axis projection of the counter-clockwise tour. For the sake
of contradiction, assume otherwise. Then there exists a vertical line that
would intersect the boundary of the polygon at more than two points.
This is impossible by convexity of the polygon since the line segments
between the intersection points must lie completely in the interior of the
polygon, thus contradicting our assumption. Thus, Vx[1 : n] is a unimodal
array, and the first part of this question is synonymous with detecting the
location of the maximum element in this array.
Consider the following algorithm:
(a) If n = 1, return Vx[1].
(b) If n = 2, return max{Vx[1], Vx[2]}.
(c) k ← dn/2e.
(d) If Vx[k] > Vx[k1] and Vx[k] > Vx[k + 1], then return Vx[k].
(e) If Vx[k] < Vx[k1] then call the algorithm recursively on Vx[1 : k1],
else call the algorithm recursively on Vx[k + 1 : n].
Complexity: If T (n) is the running time on an input of size n, then beside
a constant number of comparisons, the algorithm is called recursively on
at most one of Vx[1 : k1] (size = k1 = dn/2e1 ≤ bn/2c) or Vx[k+1 : n] (size
= nk = ndn/2e = bn/2c). Therefore, T (n) ≤ T (bn/2c) + Θ(1). Assuming
n to be a power of 2, this recurrence simplifies to T (n) ≤ T (n/2) + Θ(1)
and invoking Master’s Theorem gives T (n) = O(log n).
12
Proof of Correctness: Proof is very similar to the last question and hence
is omitted. For the second part of this question, let p denote the in-
dex at which the x-coordinate was maximized. Observe that joining V [1]
and V [p] by a straight line divides the polygon into an upper half and a
lower half and the the vertex achieving the maximum y-coordinate must
lie above this line. Once again invoking convexity of the polygon, it can
be shown in a manner analogous to the first part of the question, that
the counter-clockwise traversal Vy[p] → Vy[p + 1] → · · · → Vy[n] → Vy[1]
is unimodal and we need to detect the location of the maximum element
of this array. So, considering the same algorithm as above with this new
array [Vy[p], Vy[p+1], · · · , Vy[n], Vy[1]] will return the vertex with the max-
imum y-coordinate. The running time is still O(log n) as the algorithm is
unchanged and the problem size is no bigger.
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].
Solution: There are many different ways to solve this problem. Here, we
shall consider reusing well known algorithms and algorithms developed
in other questions on this homework as building blocks. Consider the
following approach.
(a) Compute the rotation index p, i.e. find the minimum p such that
A[1 : p] and A[p+ 1 : n] are both sorted arrays in ascending order (if
there is no rotation, then return p = 0).
(b) If p 6= 0, run binary search on A[1 : p] to find the element. Return
success if found.
(c) If not found, then run binary search on A[p + 1 : n] to find the
element. Return success if found and failure if not found.
Correctness of the algorithm is obvious. The two binary searches can be
accomplished in O(log n) time each. Hence, if we can accomplish step (a)
in O(log n) time then the problem is solved.
If there is no rotation, it can be confirmed by testing whether A[1] < A[n]
is true in constant time. In the presence of rotations it is necessarily true
that A[1] > A[n]. If rotations are present then to find the rotation index
p, we recall the algorithm in question 7, to find the local minimum in an
array, and assume that all elements in A are distinct. Using the definitions
in question 7, it is straightforward to see that A[p + 1] is the only local
minimum if there exists a non-zero rotation p and thus finding the local
minimum index is equivalent to finding the rotation index. In particular,
we have A[1] < A[2] < · · · < A[p], A[p + 1] < A[p + 2] < · · · < A[n] and
A[p] > A[p + 1]. Thus, the rotation index p can be found in O(log n)
13
time from the complexity analysis in question 7, and this completes our
solution.
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 .
Solution: Similar to what is taught in the lecture, let OPT (k,w) be the
maximum value achievable using a knapsack of capacity 0 ≤ w ≤ W and
with k types of items 1 ≤ k ≤ n. We find the recurrence relation of
OPT (k,w) as follows. Since we have infinitely many items of each type,
we choose between the following two cases:
• We include another item of type k and solve the sub-problemOPT (k,w−
vk).
• We do not include any item of type k and move to consider next type
of item this solving the sub-problem OPT (k − 1, w).
Therefore, we have
OPT (k,w) = max{OPT (k − 1, w), OPT (k,w − wk) + vk}.
Moreover, we have the initial condition OPT (0, 0) = 0.
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”.
Solution: Let si,k denote the substring sisi+1 . . . sk. Let Opt(k) denote
whether the substring s1,k can be segmented using the words in the dictio-
nary, namely OPT (k) = 1 if the segmentation is possible and 0 otherwise.
A segmentation of this substring s1,k is possible if only the last word (say
si . . . sk) is in the dictionary the remaining substring s1,i can be segmented.
Therefore,we have equation:
Opt(k) = max
0
Suppose the first k words are put in the first line, then the number of extra
space characters is
s(i, k) := L− k + 1−
i+k−1∑
t=i
ct
So we have the recurrence
Opt(i) =
{
0 if p ≥ n− i+ 1
min1≤k≤p{(s(i, k))2 +Opt(i+ k)} if p < n− i+ 1
Trace back the value of k for which Opt(i) is minimized to get the number
of words to be printed on each line. We need to compute Opt(i) for n
different values of i. At each step p may be asymptotically as big as L.
Thus the total running time is O(nL).
2. Solve Kleinberg and Tardos, Chapter 6, Exercise 10.
Solution:
16
(a) Consider the following example: there are totally 4 minutes, the
numbers of steps that can be done respectively on the two machines
in the 4 minutes are listed as follows (in time order):
• Machine A: 2, 1, 1, 200
• Machine B: 1, 1, 20, 100
The given algorithm will choose A then move, then stay on B for
the final two steps. The optimal solution will stay on A for the four
steps.
(b) An observation is that, in the optimal solution for the time interval
from minute 1 to minute i, you should not move in minute i, because
otherwise, you can keep staying on the machine where you are and
get a better solution (ai > 0 and bi > 0). For the time interval
from minute 1 to minute i, consider that if you are on machine A in
minute i, you either (i) stay on machine A in minute i−1 or (ii) are in
the process of moving from machine B to A in minute i− 1. Now let
OPTA(i) represent the maximum value of a plan in minute 1 through
i that ends on machine A, and define OPTB(i) analogously for B. If
case (i) is the best action to make for minute i1, we have OPTA(i) =
ai +OPTA(i− 1); otherwise, we have OPTA(i) = ai +OPTB(i− 2).
In sum, we have
OPTA(i) = ai + max{OPTA(i− 1), OPTB(i− 2)} :
Similarly, we get the recursive relation for OPTB(i):
OPTB(i) = bi + max{OPTB(i− 1), OPTA(i− 2)} :
The algorithm initializes OPTA(0) = 0, OPTB(0) = 0, OPTA(1) =
a1 and OPTB(1) = b1. Then the algorithm can be written as follows:
[width=]q6.png
It takes O(1) time to complete the operations in each iteration; there
are O(n) iterations; the tracing backs takes O(n) time. Thus, the
overall complexity is O(n).
3. Solve Kleinberg and Tardos, Chapter 6, Exercise 24.
Solution: The basic idea is to ask: How should we gerrymander precincts
1 through j, for each j? To make this work, though, we have to keep track
of a few extra things, by adding some variables. For brevity, we say that
A-votes in a precinct are the voters for part A and B-voter are the votes
for part B. We keep track of the following information about a partial
solution.
• How many precincts have been assigned to district 1 so far?
17
• How many A-votes are in district 1 so far?
• How many A-votes are in district 2 so far?
So let M [j, p, x, y] = true if it is possible to achieve at least x A-votes
in distance 1 and y A-votes in district 2, while allocating p of the first
j precincts to district 1. Now suppose precinct j + 1 has z A-votes. To
compute M [j+1, p, x, y], you either put precinct j+1 in district 1 (in which
case you check the results of sub-problem M [j, p−1, x−z, y]) or in district
2 (in which case you check the results of sub-problem M [j, p, x, y − z]).
Now to decide if there’s a solution to the while problem, you scan the
entire table at the end, looking for a value of true in any entry from
M [n, n/2, x, y] where each of x and y is greater than mn/4. (Since each
district gets mn/2 votes total).
We can build this up in the order of increasing j, and each sub-problem
takes constant time to compute, using the values of smaller sub-problems.
Since there are n2,m2 sub-problems, the running time is O(n2m2).
18