# Algorithms Homework #2 solved

\$35.00

Category:

## Description

1. Modified Problem 7-1(a) (page 185)
The version of PARTITION given in Pages 171–174 of the textbook is not the original partitioning
algorithm. Here is the original partition algorithm, which is due to C. A. R. Hoare:
HOARE-PARTITION(A, p, r)
1 x = A[p]
2 i = p − 1
3 j = r + 1
4 while TRUE
5 repeat
6 j = j − 1
7 until A[j] ≤ x
8 repeat
9 i = i + 1
10 until A[i] ≥ x
< B, D, A, C, D, B >. (c) Determine the cost and structure of an optimal binary search tree for a set of
n = 6 keys with the following probabilities: pi = 0.07, 0.09, 0.10, 0.04, 0.12, 0.14, i = 1, .., , 6, respectively,
and qi = 0.04, 0.06, 0.07, 0.09, 0.08, 0.07, 0.03, i = 0, …, 6, respectively.
12. Given a log of wood of length k, Woody the woodcutter will cut it once, in any place you choose, for
the price of k dollars. Suppose you have a log of length L, marked to be cut in n different locations
labeled 1, 2, . . . , n. For simplicity, let indices 0 and n + 1 denote the left and right endpoints of the
original log of length L. Let the distance of mark i from the left end of the log be di
, and assume that
0 = d0 < d1 < d2 < . . . < dn < dn+1 = L. The wood-cutting problem is the problem of determining the sequence of cuts to the log that will (1) cut the log at all the marked places, and (2) minimize your total payment to Woody. (a) Give an example with L = 4 illustrating that two different sequences of cuts to the same marked log can result in two different costs. 3 (b) Let c(i, j) be the minimum cost of cutting a log with left endpoint i and right endpoint j at all its marked locations. Suppose the log is cut at position m, somewhere between i and j. Define the recurrence of c(i, j) in terms of i, m, j, di , and dj . Briefly justify your answer. (c) Using part (b), give an efficient algorithm to solve the wood-cutting problem. Use a table C of size (n + 1) × (n + 1) to hold the values C[i][j] = c(i, j). What is the running time of your algorithm? 13. You are given a sequence of n circuit cells C =< c1, c2, . . . , cn > in a single row with the fixed cell order
from left to right, c1c2 . . . cn, each cell ci with its bottom-left coordinate xi and the width wi
, and the
minimum spacing φci,cj
for a pair of cells ci and cj , i 6= j. For example, Figure 2(a) shows an initial
placement of four circuit cells.
You are ask to minimize the total length of placing the n cells, flipping or not flipping each cell. That
is, cell ci can have two orientations, not flipped (unflipped) and flipped, denoted by c
p
i
and c
r
i
,
respectively. A cell flipping graph can be constructed to visualize the cell flipping problem, as shown in
Figure 2(b) where the nodes f
p
i
and f
r
i
respectively represent the two orientations c
p
i
and c
r
i
of the cell
ci
, and the number beside each edge between two nodes (i.e., edge weight) denotes the minimum spacing
of the two corresponding cell boundaries.
(a) For the example shown in Figure 2, the initial unflipped cell placement gives the total row length
of 40, with w1 = 6, w2 = 5, w3 = 8, and w4 = 9, and the minimum spacing φc
p
1
,c
p
2
= 3, φc
p
1
,cr
2
= 2,
and so on. Find the optimal cell flipping with the minimum total row length for these four cells
c1, c2, c3, and c4. What is the optimal row length? Which cell(s) should be flipped to achieve the
optimal solution?
(b) This problem exhibits the optimal substructure with overlapping subproblems. Explain the properties of (1) the optimal substructure, and (2) overlapping subproblems.
(c) Let f
∗ denote the optimal cell flipping, and T denote the cost function of the nodes f
p
i
, f
r
i
, and f

;
i.e., T(f
p
i
) gives the x-coordinate of the unflipped cell i. Find the recurrences for T(f
α
i
), α ∈ {p, r},
and T(f

). (Hint: in terms of xi, wi, T(f
α
i
), φc
α
i
,cα
j
, etc., with appropriate indices.)
(d) Give a dynamic programming algorithm for solving this problem. What are the time and space
1
4 5
𝑓ଵ

𝑓ଵ

𝑓ଶ

𝑓ଶ

𝑓ଷ

𝑓ଷ

3 2
2
1
2
3
2 𝑓∗
𝑓ସ

𝑓ସ

6
3
4
𝑤ଵ ൌ6 𝑤ଶ ൌ5 𝑤ଷ ൌ 8 𝑤ସ ൌ 9
(a)
𝑐ଵ
௣ 𝑐ଶ
௣ 𝑐ଷ
௣ 𝑐ସ

0 40
(b)
unflipped
edge node
flipped edge
edge weight
coordinate of c1
Figure 2: (a) An initial placement without any cell being flipped. (b) Cell flipping graph.
14. (DIY Problem) For this problem, you are asked to design a problem set related to Chapter(s) 6–9, 12,
13, and/or 15 and give a sample solution to your problem set. Grading on this problem will be based
upon the quality of the designed problem as well as the correctness of your sample solution.
4