Description
SHomework Problems
1. (25 points) Give an algorithm that takes as input a tree on n nodes and determines whether
it has a perfect matching.
A perfect matching is a subset of the edges of the tree where every node appears exactly
once; for example, if T is a tree with 4 nodes and edges (v1, v2), (v2, v3), (v3, v4), then
M = {(v1, v2),(v3, v4)} is a perfect matching.
2. (25 points) Let S, S0 be two sequences of symbols from some alphabet with lengths n, m
respectively.
Give an efficient algorithm that decides whether S
0
is a subsequence of S. A subsequence of a
sequence S = s1s2 . . . sn is any subset of the symbols in S taken in order, that is, it has the
form si1
si2
. . . sik
, where 1 ≤ i1 < i2 < . . . < ik ≤ n.
(For example, S
0 = ABC is a subsequence of S = ACACBBCB.)
3. (25 points) In Internet routing, there are delays on lines but also, delays at routers. This
motivates us to consider graphs that, on top of non-negative edge weights we > 0 for all edges
e ∈ E, also have non-negative vertex costs cv > 0 for all v ∈ V . We now define the weight of
a path to be the sum of its edge weights, plus the costs of all vertices on the path (including
the endpoints).
Give an efficient algorithm that on input a directed graph with node costs and edge weights
G = (V, E, w, c) and an origin vertex s ∈ V outputs an array dist such that for every vertex
u, dist[u] is the minimum weight of any path from s to u (e.g., dist[s] = cs). Thus dist[u]
is the weight of the shortest s-u path under the modified definition for the weight of a path
given above.
4. (30 points) You are given a line L that represents a long hallway in an art gallery and a
sorted set X = {x1, x2, . . . , xn} of real numbers that specify the positions of paintings in this
hallway. Suppose that a guard can protect all the paintings within distance at most 1 of their
position on both sides.
Give an efficient algorithm that returns
(a) the minimum number of guards to protect all the paintings; and
(b) a placement of the guards that achieves this minimum number.
5. (30 points) There are n libraries L1, L2, . . . , Ln. We want to store copies of a book in some
libraries. Storing a copy at Li
incurs a purchase cost ci (assume integer ci > 0). A copy of
the book is always stored at Ln. If a user requests the book from Li and Li does not have it,
then Li+1, Li+2, . . . are searched sequentially until a copy of the book is found at Lj for some
j > i. This results in a user delay of j − i. (Note that, in this case, no library Lk with an
index k smaller than i is searched; also, if the user finds the book at Li
, then the user delay
is 0.)
We define the total cost as the sum of the purchase costs and the user delays associated with
all n servers. For example, if there are 4 libraries, and copies of the book are stored at L1
and L4, the total cost is c1 + c4 + 2 + 1.
Give an efficient algorithm that returns
(a) the minimum total cost; and
(b) a set of libraries where copies of the books must be placed to achieve the minimum total
cost.
RECOMMENDED exercises: do NOT return, they will not be graded.
1. Give an efficient algorithm to compute the length of the longest increasing subsequence of a
sequence of numbers a1, . . . , an. A subsequence is any subset of these numbers taken in order,
of the form ai1
, ai2
, . . . , aik where 1 ≤ i1 < i2 < . . . < ik ≤ n and an increasing subsequence
is one in which the numbers are getting strictly larger.
For example, the longest increasing subsequence of 5, 2, 8, 6, 3, 6, 7 is 2, 3, 6, 7 and its
length is 4.
2. Consider an array A with n numbers, some of which (but not all) may be negative. We wish
to find indices i and j such that
X
j
k=i
A[k]
is maximized. Give an efficient algorithm for this problem.
3. Problem 16.1 from your textbook (pp. 446-447).
