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
11 if i < j 12 exchange A[i] and A[j] 13 else return j Demonstrate the operation of HOARE-PARTITION based on the string (array of 16 characters): “NTUEECSALGORITHM”, showing the values of the array and auxiliary values after each iteration of the while loop in lines 4-13. Please mark the two T’s as T1 and T2, and the two E’s as E1 and E2 according to their order in the input, and show their positions during the processing. 2. Modified Exercise 8.2-1 (page 196) Using Figure 8.2 in textbook as a model, illustrate the operation of COUNTING-SORT based on the string (array of 16 characters): “NTUEECSALGORITHM”. Please mark the two T’s as T1 and T2, and the two E’s as E1 and E2 according to their order in the input, and show their positions during the processing. Assume you have only the 26 characters: A, B, · · · , Z and thus you may work on the array of the 26 characters. 3. Exercise 8.2-4 (page 197) Describe an algorithm that, given n integers in the range 0 to k, preprocesses its input and then answers any query about how many of the n integers fall into a range [a..b] in O(1) time. Your algorithm should use Θ(n + k) preprocessing time. 4. Problem 8-4 (a), (b) (pages 206-207) Suppose that you are given n red and n blue water jugs, all of different shapes and sizes. All red jugs hold different amounts of water, as do the blue ones. Moreover, for every red jug, there is a blue jug that holds the same amount of water, and vice versa. Your task is to find a grouping of the jugs into pairs of red and blue jugs that hold the same amount of water. To do so, you may perform the following operation: pick a pair of jugs in which one is red and one is blue, fill the red jug with water, and then pour the water into the blue jug. This operation will tell you whether the red or the blue jug can hold more water, or that they have the same volume. Assume that such a comparison takes one time unit. Your goal is to find an algorithm that makes a minimum number of comparisons to determine the grouping. Remember that you may not directly compare two red jugs or two blue jugs. a. Describe a deterministic algorithm that uses Θ(n 2 ) comparisons to group the jugs into pairs. b. Prove a lower bound of Ω(n lg n) for the number of comparisons that an algorithm solving this problem must make. 5. Problem 9.1-1 (page 215) Show that the second smallest of n elements can be found with n + dlg ne − 2 comparisons in the worst case. (Hint: Also find the smallest element.) 6. Exercise 9.3-8 (page 223) Let X[1..n] and Y [1..n] be two arrays, each containing n numbers already in sorted order. Give an O(lg n)-time algorithm to find the median of all 2n elements in arrays X and Y . (No pseudo code is needed) 7. Exercise 12.2-1 (a), (b), and (d) (page 293) Suppose that we have numbers between 1 and 1000 in a binary search tree, and we want to search for the number 363. Which of the following sequences could not be the sequence of nodes examined? (a) 2, 252, 401, 398, 330, 344, 397, 363. (b) 924, 220, 911, 244, 898, 258, 362, 363. (d) 2, 399, 387, 219, 266, 382, 381, 278, 363. 8. Problem 12-2 (page 304) Given two strings a = a0a1 . . . ap and b = b0b1 . . . bq, where each ai and each bj is in some ordered set of characters, we say that string a is lexicographically less than string b if either 1. there exists an integer j , where 0 ≤ j ≤ min(p, q), such that ai = bi for all i = 0, 1, . . . , j − 1 and aj < bj , or 2. p < q and ai = bi for all i = 0, 1, . . . , p. For example, if a and b are bit strings, then 10100 < 10110 by rule 1 (letting j = 3) and 10100 < 101000 by rule 2. This ordering is similar to that used in English-language dictionaries. The radix tree data structure shown in Figure 1 stores the bit strings 1011, 10, 011, 100, and 0. When searching for a key a = a0a1 . . . ap, we go left at a node of depth i if ai = 0 and right if ai = 1. Let S be a set of distinct bit strings whose lengths sum to n. Show how to use a radix tree to sort S lexicographically in Θ(n) time. For the example in Figure 1, the output of the sort should be the sequence 0, 011, 10, 100, 1011. 9. Search trees. (a) Give the binary search tree that results from successively inserting the keys 8, 2, 1, 6, 5, 7, 9, 10 into an initially empty tree. (b) Label each node in the tree with R or B denoting the respective colors RED and BLACK so that the tree is a legal red-black tree. (c) Give the red-black tree that results from inserting the key 4 into the tree of (b). (d) Give the red-black tree that results from deleting the key 7 from the tree of (c). 2 Figure 1: A radix tree storing the bit strings 1011, 10, 011, 100, and 0. We can determine each node’s key by traversing the simple path from the root to that node. There is no need, therefore, to store the keys in the nodes; the keys appear here for illustrative purposes only. Nodes are heavily shaded if the keys corresponding to them are not in the tree; such nodes are present only to establish a path to other nodes. 10. Problem 13-2 (pages 332–333) The join operation takes two dynamic sets S1 and S2 and an element x such that for any x1 ∈ S1 and x2 ∈ S2, we have x1.key ≤ x.key ≤ x2.key. It returns a set S = S1 ∪ {x} ∪ S2. In this problem, we investigate how to implement the join operation on red-black trees. (a) Given a red-black tree T, let us store its black-height as the new attribute T.bh. Argue that RB-INSERT and RB-DELETE can maintain the bh attribute without requiring extra storage in the nodes of the tree and without increasing the asymptotic running times. Show that while descending through T, we can determine the black-height of each node we visit in O(1) time per node visited. We wish to implement the operation RB-JOIN(T1, x, T2), which destroys T1 and T2 and returns a redblack tree T = T1 ∪ {x} ∪ T2. Let n be the total number of nodes in T1 and T2. (b) Assume that T1.bh ≥ T2.bh. Describe an O(lg n)-time algorithm that finds a black node y in T1 with the largest key from among those nodes whose black-height is T2.bh. (c) Let Ty be the subtree rooted at y. Describe how Ty ∪ {x} ∪ T2 can replace Ty in O(1) time without destroying the binary-search-tree property. (d) What color should we make x so that red-black properties 1, 3, and 5 are maintained? Describe how to enforce properties 2 and 4 in O(lg n) time. (e) Argue that no generality is lost by making the assumption in part (b). Describe the symmetric situation that arises when T1.bh ≤ T2.bh. (f) Argue that the running time of RB-JOIN is O(lg n). 11. Dynamic programming implementations. (a) Find an optimal parenthesization of a matrix-chain product whose sequence of dimensions is < 3, 5, 10, 6, 8, 30 >. b) Determine an LCS of < A, B, C, D, A, B > and
< 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
complexity of your algorithm?
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