## jueves, 25 de diciembre de 2014

### Chapter #12 Solutions- Allan Weiss - Data Structures and Algorithm Analysis in Java - 3rd Edition

12.1 Prove that the amortized cost of a top-down splay is O(logN). - Get solution

12.2 Prove that there exist access sequences that require 2 logN rotations per access for bottom-up splaying. Show that a similar result holds for top-down splaying. - Get solution

12.3 Modify the splay tree to support queries for the kth smallest item. - Get solution

12.4 Compare, empirically, the simplified top-down splay with the originally described top-down splay. - Get solution

12.5 Write the deletion procedure for red-black trees. - Get solution

12.6 Prove that the height of a red-black tree is at most 2 logN, and that this bound cannot be substantially lowered. - Get solution

12.7 Show that every AVL tree can be colored as a red-black tree. Are all red-black trees AVL? - Get solution

12.8 Draw a suffix tree and show the suffix array and LCP array for the following input strings:
a. ABCABCABC
b. MISSISSIPPI - Get solution

12.9 Once the suffix array is constructed, the short routine shown in Figure 12.50 can be invoked from Figure 12.32 to create the longest common prefix array.
a. In the code, what does rank[i] represent?
b. Suppose that LCP[rank[i] ] = h. Show that LCP[rank[i+1] ] ≥ h − 1.
c. Show that the algorithm in Figure 12.50 correctly computes the LCP array.
d. Prove that the algorithm in Figure 12.50 runs in linear time.
1 /*
2 * Create the LCP array from the suffix array
3 * @param s the input array populated from 0..N-1, with available pos N
4 * @param sa the already-computed suffix array 0..N-1
5 * @param LCP the resulting LCP array 0..N-1
6 */
7 public static void makeLCPArray( int [ ] s, int [ ] sa, int [ ] LCP )
8 {
9 int N = sa.length;
10 int [ ] rank = new int[ N ];
11
12 s[ N ] = -1;
13 for( int i = 0; i < N; i++ )
14 rank[ sa[ i ] ] = i;
15
16 int h = 0;
17 for( int i = 0; i < N; i++ )
18 if( rank[ i ] > 0 )
19 {
20 int j = sa[ rank[ i ] - 1 ];
21
22 while( s[ i + h ] == s[ j + h ] )
23 h++;
24
25 LCP[ rank[ i ] ] = h;
26 if( h > 0 )
27 h--;
28 }
29 }
Get solution

12.10 Suppose that in the linear-time suffix array construction algorithm, instead of constructing three groups, we construct seven groups, using for k = 0, 1, 2, 3, 4, 5, 6 Sk = < S[7i + k]S[7i + k + 1]S[7i + k + 2] . . . S[7i + k + 6] for i = 0, 1, 2, . . . >
a. Show that with a recursive call to S3S5S6, we have enough information to sort
the other four groups S0, S1, S2, and S4.
b. Show that this partitioning leads to a linear-time algorithm. - Get solution

12.11 Implement the insertion routine for treaps nonrecursively by maintaining a stack. Is it worth the effort? - Get solution

12.12 We can make treaps self-adjusting by using the number of accesses as a priority and performing rotations as needed after each access. Compare this method with the randomized strategy. Alternatively, generate a random number each time an item X is accessed. If this number is smaller than X’s current priority, use it as X’s new priority (performing the appropriate rotation). - Get solution

12.13 Show that if the items are sorted, then a treap can be constructed in linear time, even if the priorities are not sorted. - Get solution

12.14 Implement red-black trees without using the nullNode sentinel. How much coding effort is saved by using the sentinel? - Get solution

12.15 Suppose we store, for each node, the number of null links in its subtree; call this the node’s weight. Adopt the following strategy: If the left and right subtrees have weights that are not within a factor of 2 of each other, then completely rebuild the subtree rooted at the node. Show the following:
a. We can rebuild a node in O(S), where S is the weight of the node.
b. The algorithm has amortized cost of O(logN) per insertion.
c. We can rebuild a node in a k-d tree in O(S log S) time, where S is the weight of
the node.
d. We can apply the algorithm to k-d trees, at a cost of O(log2 N) per insertion. - Get solution

12.16 Suppose we call rotateWithLeftChild on an arbitrary 2-d tree. Explain in detail all the reasons that the result is no longer a usable 2-d tree. - Get solution

12.17 Implement the insertion and range search for the k-d tree. Do not use recursion. - Get solution

12.18 Determine the time for partial match query for values of p corresponding to k = 3, 4, and 5. - Get solution

12.19 For a perfectly balanced k-d tree, derive the worst-case running time of a range query that is quoted in the text (see p. 581). - Get solution

12.20 The 2-d heap is a data structure that allows each item to have two individual keys. deleteMin can be performed with respect to either of these keys. The 2-d heap is a complete binary tree with the following order property: For any node X at even depth, the item stored at X has the smallest key #1 in its subtree, while for any node X at odd depth, the item stored at X has the smallest key #2 in its subtree.
a. Draw a possible 2-d heap for the items (1, 10), (2, 9), (3, 8), (4, 7), (5, 6).
b. How do we find the item with minimum key #1?

c. How do we find the item with minimum key #2?
d. Give an algorithm to insert a new item into the 2-d heap.
e. Give an algorithm to perform deleteMin with respect to either key.
f. Give an algorithm to perform buildHeap in linear time. - Get solution

12.21 Generalize the preceding exercise to obtain a k-d heap, in which each item can have k individual keys. You should be able to obtain the following bounds: insert in O(logN), deleteMin in O(2k logN), and buildHeap in O(kN). - Get solution

12.22 Show that the k-d heap can be used to implement a double-ended priority queue. - Get solution

12.23 Abstractly, generalize the k-d heap so that only levels that branch on key #1 have
two children (all others have one).
a. Do we need links?
b. Clearly, the basic algorithms still work; what are the new time bounds? - Get solution

12.24 Use a k-d tree to implement deleteMin. What would you expect the average running time to be for a random tree? - Get solution

12.25 Use a k-d heap to implement a double-ended queue that also supports deleteMin. - Get solution

12.26 Implement the pairing heap with a nullNode sentinel. - Get solution

12.27 Show that the amortized cost of each operation is O(logN) for the pairing heap algorithm in the text. - Get solution

12.28 An alternative method for combineSiblings is to place all of the siblings on a queue, and repeatedly dequeue and merge the first two items on the queue, placing the result at the end of the queue. Implement this variation. - Get solution

12.29 Show that using a stack instead of a queue in the previous exercise is bad, by giving a sequence that leads to (N) cost per operation. This is the left-to-right single-pass merge. - Get solution

12.30 Without decreaseKey, we can remove parent links. How competitive is the result with the skew heap? - Get solution

12.31 Assume that each of the following is represented as a tree with child and parent references. Explain how to implement a decreaseKey operation.
a. Binary heap
b. Splay tree - Get solution

12.32 When viewed graphically, each node in a 2-d tree partitions the plane into regions.
For instance, Figure 12.51 shows the first five insertions into the 2-d tree in

Figure 12.39. The first insertion, of p1, splits the plane into a left part and a right part. The second insertion, of p2, splits the left part into a top part and a bottom part, and so on.
a. For a given set of N items, does the order of insertion affect the final partition?
b. If two different insertion sequences result in the same tree, is the same partition
produced?
c. Give a formula for the number of regions that result from the partition after N
insertions.
d. Show the final partition for the 2-d tree in Figure 12.39. - Get solution

12.33 An alternative to the 2-d tree is the quad tree. Figure 12.52 shows how a plane is partitioned by a quad tree. Initially we have a region (which is often a square, but need not be). Each region may store one point. If a second point is inserted into a region, then the region is split into four equal-sized quadrants (northeast, southeast, southwest, and northwest). If this places the points in different quadrants (aswhen p2 is inserted), we are done; otherwise, we continue splitting recursively (as is done when p5 is inserted).
a. For a given set of N items, does the order of insertion affect the final partition?
b. Show the final partition if the same elements that were in the 2-d tree in
Figure 12.39 are inserted into the quad tree. - Get solution

12.34 A tree data structure can store the quad tree. We maintain the bounds of the original region. The tree root represents the original region. Each node is either a leaf that stores an inserted item, or has exactly four children, representing four quadrants. To perform a search, we begin at the root and repeatedly branch to anappropriate quadrant until a leaf (or null entry) is reached.
a. Draw the quad tree that corresponds to Figure 12.52.
b. What factors influence how deep the (quad) tree will be?
c. Describe an algorithm that performs an orthogonal range query in a quad tree. - Get solution

### Chapter #11 Solutions- Allan Weiss - Data Structures and Algorithm Analysis in Java - 3rd Edition

11.1 When do M consecutive insertions into a binomial queue take less than 2M time units? - Get solution

11.2 Suppose a binomial queue of N = 2k − 1 elements is built. Alternately perform M insert and deleteMin pairs. Clearly, each operation takes O(logN) time. Why does this not contradict the amortized bound of O(1) for insertion? - Get solution

11.3 Show that the amortized bound of O(logN) for the skew heap operations described in the text cannot be converted to a worst-case bound, by giving a sequence of operations that lead to a merge requiring (N) time. - Get solution

11.4 Show how to merge two skew heaps with one top-down pass and reduce the merge cost to O(1) amortized time. - Get solution

11.5 Extend skew heaps to support the decreaseKey operation in O(logN) amortized time. - Get solution

11.6 Implement Fibonacci heaps and compare their performance with that of binary heaps when used in Dijkstra’s algorithm. - Get solution

11.7 A standard implementation of Fibonacci heaps requires four links per node (parent, child, and two siblings). Show how to reduce the number of links, at the cost of at most a constant factor in the running time. - Get solution

11.8 Show that the amortized time of a zig-zig splay is at most 3(Rf (X) − Ri(X)). - Get solution

11.9 By changing the potential function, it is possible to prove different bounds for splaying. Let the weight function W(i) be some function assigned to each node in the tree, and let S(i) be the sum of the weights of all the nodes in the subtree rooted at i, including i itself. The special case W(i) = 1 for all nodes corresponds to the function used in the proof of the splaying bound. Let N be the number of
nodes in the tree, and let M be the number of accesses. Prove the following two theorems:
a. The total access time is O(M + (M + N) logN).
b. If qi is the number of times that item i is accessed, and qi > 0 for all i, then the
total access time is
11.10 a. Show how to implement the merge operation on splay trees so that any sequence of N−1 merges starting from N single-element trees takes O(N log2 N) time.
b. Improve the bound to O(N logN). - Get solution

11.11 In Chapter 5, we described rehashing: When a table becomes more than half full,a new table twice as large is constructed, and the entire old table is rehashed. Give a formal amortized analysis, with potential function, to show that the amortized cost of an insertion is still O(1). - Get solution

11.12 What is the maximum depth of a Fibonacci heap? - Get solution

11.13 A deque with heap order is a data structure consisting of a list of items, on which
the following operations are possible:
push(x): Insert item x on the front end of the deque.
pop(): Remove the front item from the deque and return it.
inject(x): Insert item x on the rear end of the deque.
eject(): Remove the rear item from the deque and return it.
findMin(): Return the smallest item from the deque (breaking ties arbitrarily).
a. Describe how to support these operations in constant amortized time per
operation.
b. Describe how to support these operations in constant worst-case time per
operation. - Get solution

11.14 Show that the binomial queues actually support merging in O(1) amortized time. Define the potential of a binomial queue to be the number of trees plus the rank of the largest tree. - Get solution

11.15 Suppose that in an attempt to save time, we splay on every second tree operation.
Does the amortized cost remain logarithmic? - Get solution

11.16 Using the potential function in the proof of the splay tree bound, what is the maximum and minimum potential of a splay tree? By how much can the potential function decrease in one splay? By how much can the potential function increase in one splay? You may give Big-Oh answers. - Get solution

11.17 As a result of a splay, most of the nodes on the access path are moved halfway towards the root, while a couple of nodes on the path move down one level. This suggests using the sum over all nodes of the logarithm of each node’s depth as a potential function.
a. What is the maximum value of the potential function?
b. What is the minimum value of the potential function?
c. The difference in the answers to parts (a) and (b) gives some indication that this potential function isn’t too good. Show that a splaying operation could increase the potential by (N/ logN). - Get solution

## miércoles, 19 de febrero de 2014

### Chapter #10 Solutions- Allan Weiss - Data Structures and Algorithm Analysis in Java - 3rd Edition

Available Solutions for the following Chapter 10 exercises:

10.1 Show that the greedy algorithm to minimize the mean completion time for
multiprocessor job scheduling works. - Get solution

10.3 A file contains only colons, spaces, newlines, commas, and digits in the following
frequency: colon (100), space (605), newline (100), comma (705), 0 (431),
1 (242), 2 (176), 3 (59), 4 (185), 5 (250), 6 (174), 7 (199), 8 (205), 9 (217).
Construct the Huffman code. . - Get solution

10.4 Part of the encoded file must be a header indicating the Huffman code. Give
a method for constructing the header of size at most O(N) (in addition to the
symbols), where N is the number of symbols.. - Get solution

10.5 Complete the proof that Huffman’s algorithm generates an optimal prefix code.. - Get solution

10.6 Show that if the symbols are sorted by frequency, Huffman’s algorithm can be implemented in linear time. . - Get solution

10.10 Explain how to implement first fit and best fit in O(N logN) time.. - Get solution

10.11 Show the operation of all the bin-packing strategies discussed in Section 10.1.3 on the input 0.42, 0.25, 0.27, 0.07, 0.72, 0.86, 0.09, 0.44, 0.50, 0.68, 0.73, 0.31,0.78, 0.17, 0.79, 0.37, 0.73, 0.23, 0.30. . - Get solution

10.13 Prove Theorem 10.7. . - Get solution

10.14 Prove Theorem 10.8.. - Get solution

10.15 N points are placed in a unit square. Show that the distance between the closest pair is O(N−1/2). . - Get solution

10.16 Argue that for the closest-points algorithm, the average number of points in the strip is O(√ N). (Hint: Use the result of the previous exercise.). - Get solution

10.18 What is the asymptotic running time of quickselect, using a median-of-medianof-three partitioning strategy? . - Get solution

10.19 Show that quickselect with median-of-median-of-seven partitioning is linear.Why is median-of-median-of-seven partitioning not used in the proof? . - Get solution

10.22 Complete the analysis of the sampling algorithm described at the end of Section 10.2.3, and explain how the values of δ and s are chosen. . - Get solution

10.23 Show how the recursive multiplication algorithm computes XY, where X = 1234 and Y = 4321. Include all recursive computations.. - Get solution

10.24 Show how to multiply two complex numbers X = a + bi and Y = c + di using
only three multiplications. . - Get solution

10.25 a. Show that
XLYR + XRYL = (XL + XR)(YL + YR) − XLYL − XRYR
b. This gives an O(N1.59) algorithm to multiply N-bit numbers. Compare this
method to the solution in the text. . - Get solution

10.27 Why is it important that Strassen’s algorithm does not use commutativity in the
multiplication of 2 × 2 matrices? . - Get solution

10.28 Two 70×70 matrices can be multiplied using 143,640 multiplications. Show how
this can be used to improve the bound given by Strassen’s algorithm. . - Get solution

10.29 What is the optimal way to compute A1A2A3A4A5A6, where the dimensions of
the matrices are A1 : 10 × 20, A2 : 20 × 1, A3 : 1 × 40, A4 : 40 × 5, A5 : 5 × 30,
A6: 30 × 15? . - Get solution

10.30 Show that none of the following greedy algorithms for chained matrix multiplication
work. At each step
a. Compute the cheapest multiplication.
b. Compute the most expensive multiplication.
c. Compute the multiplication between the two matrices Mi and Mi+1, such that
the number of columns in Mi is minimized (breaking ties by one of the rules
above). . - Get solution

10.32 Show the optimal binary search tree for the following words, where the frequency
of occurrence is in parentheses: a (0.18), and (0.19), I (0.23), it (0.21), or (0.19). - Get solution

10.35 Write a routine to reconstruct the shortest paths from the algorithm in Section 10.3.4. . - Get solution

10.39 Figure 10.75 shows a routine to flip a coin, assuming that random returns an integer (which is prevalent in many systems). What is the expected performance of the skip list algorithms if the random number generator uses a modulus of the form M = 2B (which is unfortunately prevalent on many systems)? . - Get solution

10.40 a. Use the exponentiation algorithm to prove that 2340 ≡ 1 (mod 341).
b. Show how the randomized primality test works for N = 561 with several choices of A. . - Get solution

10.42 Two point sets are homometric if they yield the same distance set and are not rotations of each other. The following distance set gives two distinct point sets:
{ 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 16, 17 }. Find the two point sets.. - Get solution

10.43 Extend the reconstruction algorithm to find all homometric point sets given a distance set. . - Get solution

10.44 Show the result of α–β pruning of the tree in Figure 10.76. . - Get solution

10.47 The one-dimensional circle packing problem is as follows: You have N circles of radii r1, r2, . . . , rN. These circles are packed in a box such that each circle is tangent to the bottom of the box and are arranged in the original order. The problem is to find the width of the minimum-sized box. Figure 10.77 shows an example with circles of radii 2, 1, 2 respectively. The minimum-sized box has width
4 + 4√ 2. . - Get solution

10.48 Suppose that the edges in an undirected graph G satisfy the triangle inequality:
cu,v + cv,w ≥ cu,w. Show how to compute a traveling salesman tour of cost at most twice optimal. (Hint: Construct a minimum spanning tree.). - Get solution

10.49 You are a tournament director and need to arrange a round robin tournament among N = 2k players. In this tournament, everyone plays exactly one game each day; after N − 1 days, a match has occurred between every pair of players. Give a recursive algorithm to do this. . - Get solution

10.50 a. Prove that in a round robin tournament it is always possible to arrange the players in an order pi1 , pi2 , . . . , piN such that for all 1 ≤ j < N, pij has won the match against pij+1 .
b. Give an O(N logN) algorithm to find one such arrangement. Your algorithm
may serve as a proof for part (a). . - Get solution

10.52 A convex polygon is a polygon with the property that any line segment whose endpoints are on the polygon lies entirely within the polygon. The convex hull

problem consists of finding the smallest (area) convex polygon that encloses a set of points in the plane. Figure 10.79 shows the convex hull for a set of 40 points. Give an O(N logN) algorithm to find the convex hull. . - Get solution

10.53 Consider the problem of right-justifying a paragraph. The paragraph contains a sequence of words w1, w2, . . . , wN of length a1, a2, . . . , aN, which we wish to break into lines of length L. Words are separated by blanks whose ideal length is b (millimeters), but blanks can stretch or shrink as necessary (but must be >0), so that a line wiwi+1 . . . wj has length exactly L. However, for each blank b we charge |b − b| ugliness points. The exception to this is the last line, for which we charge only if b < b (in other words, we charge only for shrinking), since the last line does not need to be justified. Thus, if bi is the length of the blank between ai and ai+1, then the ugliness of setting any line (but the last) wiwi+1 . . . wj for j > i is
j−1
k=i
|bk − b| = (j − i)|b − b|, where b is the average size of a blank on this line.
This is true of the last line only if b < b, otherwise the last line is not ugly at all.

a. Give a dynamic programming algorithm to find the least ugly setting of w1, w2, . . . , wN into lines of length L. (Hint: For i = N, N − 1, . . . , 1, compute the best way to set wi, wi+1, . . . , wN.)
b. Give the time and space complexities for your algorithm (as a function of the number of words, N).
c. Consider the special case where we are using a fixed-width font, and assume the optimal value of b is 1 (space). In this case, no shrinking of blanks is allowed, since the next smallest blank space would be 0. Give a linear-time algorithm to generate the least ugly setting for this case. . - Get solution

10.54 The longest increasing subsequence problem is as follows: Given numbers a1, a2, . . . , aN, find the maximum value of k such that ai1 < ai2 < · · · < aik, and i1 < i2 < · · · < ik. As an example, if the input is 3, 1, 4, 1, 5, 9, 2, 6, 5, the maximum increasing subsequence has length four (1, 4, 5, 9 among others). Give an O(N2) algorithm to solve the longest increasing subsequence problem. . - Get solution

10.55 The longest common subsequence problem is as follows: Given two sequences A = a1, a2, . . . , aM, and B = b1, b2, . . . , bN, find the length, k, of the longest sequence C = c1, c2, . . . , ck such that C is a subsequence (not necessarily continguous) of both A and B. As an example, if A = d,y,n,a,m,i,c
and B = p,r,o,g,r,a,m,m,i,n,g, then the longest common subsequence is a,m,i and has length 3. Give an algorithm to solve the longest common subsequence problem. Your algorithm should run in O(MN) time. . - Get solution

10.57 One form of the knapsack problem is as follows: We are given a set of integers A = a1, a2, . . . , aN and an integer K. Is there a subset of A whose sum is exactly K?
a. Give an algorithm that solves the knapsack problem in O(NK) time.
b. Why does this not show that P = NP? . - Get solution

10.58 You are given a currency system with coins of (decreasing) value c1, c2, . . . , cN cents.
a. Give an algorithm that computes the minimum number of coins required to give K cents in change.
b. Give an algorithm that computes the number of different ways to give K cents in change. . - Get solution

10.59 Consider the problem of placing eight queens on an (eight-by-eight) chess board.
Two queens are said to attack each other if they are on the same row, column, or
(not necessarily main) diagonal.
a. Give a randomized algorithm to place eight nonattacking queens on the board.
b. Give a backtracking algorithm to solve the same problem.
c. Implement both algorithms and compare the running time. . - Get solution

a. Why does this algorithm not work for general graphs?
b. Prove that this algorithm terminates for acyclic graphs.
c. What is the worst-case running time of the algorithm? . - Get solution

10.62 Let A be an N-by-N matrix of zeros and ones. A submatrix S of A is any group of contiguous entries that forms a square.
a. Design an O(N2) algorithm that determines the size of the largest submatrix of ones in A. For instance, in the matrix that follows, the largest submatrix is a
4-by-4 square.
10111000
00010100
00111000
00111010
00111111
01011110
01011110
00011110
b. Repeat part (a) if S is allowed to be a rectangle instead of a square. Largest is measured by area.

10.67 Othello played on a 6-by-6 board is a forced win for black. Prove this by writing
a program. What is the final score if play on both sides is optimal? . - Get solution

### Chapter #9 Solutions- Allan Weiss - Data Structures and Algorithm Analysis in Java - 3rd Edition

Available Solutions for the following Chapter 9 exercises:

9.4 An adjacency matrix requires O(|V|2) merely to initialize using a standard double loop. Propose a method that stores a graph in an adjacency matrix (so that testing for the existence of an edge is O(1)) but avoids the quadratic running time. - Get solution

9.5 a. Find the shortest path from A to all other vertices for the graph in Figure 9.82.
b. Find the shortest unweighted path from B to all other vertices for the graph in Figure 9.82. - Get solution

9.6 What is the worst-case running time of Dijkstra’s algorithm when implemented with d-heaps (Section 6.5)? - Get solution

9.7 a. Give an example where Dijkstra’s algorithm gives the wrong answer in the presence of a negative edge but no negative-cost cycle.
b. Show that the weighted shortest-path algorithm suggested in Section 9.3.3 works if there are negative-weight edges, but no negative-cost cycles, and that the running time of this algorithm is O(|E| · |V|). - Get solution

9.8 Suppose all the edge weights in a graph are integers between 1 and |E|. How fast can Dijkstra’s algorithm be implemented? - Get solution

9.10 a. Explain how to modify Dijkstra’s algorithm to produce a count of the number of different minimum paths from v to w.
b. Explain how to modify Dijkstra’s algorithm so that if there is more than one
minimum path from v to w, a path with the fewest number of edges is chosen. - Get solution

9.11 Find the maximum flow in the network of Figure 9.81. - Get solution

9.12 Suppose that G = (V, E) is a tree, s is the root, and we add a vertex t and edgesof infinite capacity from all leaves in G to t. Give a linear-time algorithm to find a maximum flow from s to t. - Get solution

9.13 A bipartite graph, G = (V, E), is a graph such that V can be partitioned into two subsets V1 and V2 and no edge has both its vertices in the same subset.
a. Give a linear algorithm to determine whether a graph is bipartite.
b. The bipartite matching problem is to find the largest subset E of E such that no vertex is included in more than one edge. A matching of four edges (indicated by dashed edges) is shown in Figure 9.83. There is a matching of five edges, which is maximum.
Show how the bipartite matching problem can be used to solve the following problem:
We have a set of instructors, a set of courses, and a list of courses that each instructor is qualified to teach. If no instructor is required to teach more than one course, and only one instructor may teach a given course, what is the maximum number of courses that can be offered?
c. Show that the network flow problem can be used to solve the bipartite matching
problem.
d. What is the time complexity of your solution to part (b)? - Get solution

9.14 a. Give an algorithm to find an augmenting path that permits the maximum flow.
b. Let f be the amount of flow remaining in the residual graph. Show that the
augmenting path produced by the algorithm in part (a) admits a path of capacity f/|E|.
c. Show that after |E| consecutive iterations, the total flow remaining in the residual graph is reduced from f to at most f /e, where e ≈ 2.71828.
d. Show that |E| ln f iterations suffice to produce the maximum flow. - Get solution

9.15 a. Find a minimum spanning tree for the graph in Figure 9.84 using both Prim’s and Kruskal’s algorithms.

b. Is this minimum spanning tree unique? Why? - Get solution

9.16 Does either Prim’s or Kruskal’s algorithm work if there are negative edge weights? - Get solution

9.17 Show that a graph of V vertices can have VV−2 minimum spanning trees. - Get solution

9.19 If all the edges in a graph have weights between 1 and |E|, how fast can the minimum spanning tree be computed? - Get solution

9.20 Give an algorithm to find a maximum spanning tree. Is this harder than finding a minimum spanning tree? - Get solution

9.21 Find all the articulation points in the graph in Figure 9.85. Show the depth-first spanning tree and the values of Num and Low for each vertex. - Get solution

9.22 Prove that the algorithm to find articulation points works. - Get solution

9.23 a. Give an algorithm to find the minimum number of edges that need to be removed from an undirected graph so that the resulting graph is acyclic.
b. Show that this problem is NP-complete for directed graphs. - Get solution

9.24 Prove that in a depth-first spanning forest of a directed graph, all cross edges go from right to left. - Get solution

9.25 Give an algorithm to decide whether an edge (v, w) in a depth-first spanning forest of a directed graph is a tree, back, cross, or forward edge. - Get solution

9.26 Find the strongly connected components in the graph of Figure 9.86. - Get solution

9.28 Give an algorithm that finds the strongly connected components in only one depthfirst search. Use an algorithm similar to the biconnectivity algorithm. - Get solution

9.29 The biconnected components of a graph G is a partition of the edges into sets such that the graph formed by each set of edges is biconnected. Modify the algorithm in Figure 9.69 to find the  biconnected components instead of the articulation points. - Get solution

9.30 Suppose we perform a breadth-first search of an undirected graph and build a breadth-first  spanning tree. Show that all edges in the tree are either tree edges or cross edges. - Get solution

9.31 Give an algorithm to find in an undirected (connected) graph a path that goes through every edge exactly once in each direction. - Get solution

9.33 An Euler circuit in a directed graph is a cycle in which every edge is visited exactly once.
a. Prove that a directed graph has an Euler circuit if and only if it is strongly connected and every vertex has equal indegree and outdegree.
b. Give a linear-time algorithm to find an Euler circuit in a directed graph where one exists. - Get solution

9.34 a. Consider the following solution to the Euler circuit problem: Assume that the graph is biconnected. Perform a depth-first search, taking back edges only as a last resort. If the graph is not biconnected, apply the algorithm recursively on the biconnected components. Does this algorithm work?
b. Suppose that when taking back edges, we take the back edge to the nearest ancestor. Does the algorithm work? - Get solution

9.35 A planar graph is a graph that can be drawn in a plane without any two edges intersecting.
a. Show that neither of the graphs in Figure 9.87 is planar.
b. Show that in a planar graph, there must exist some vertex which is connected to no more than five nodes.
c. Show that in a planar graph, |E| ≤ 3|V| − 6. - Get solution

9.36 A multigraph is a graph in which multiple edges are allowed between pairs of vertices. Which of the algorithms in this chapter work without modification for multigraphs? What modifications need to be done for the others? - Get solution

9.37 Let G = (V, E) be an undirected graph. Use depth-first search to design a linear algorithm to convert each edge in G to a directed edge such that the resulting graph is strongly connected, or determine that this is not possible. - Get solution

9.38 You are given a set of N sticks, which are lying on top of each other in some configuration.
Each stick is specified by its two endpoints; each endpoint is an ordered triple giving its x, y, and z coordinates; no stick is vertical. A stick may be picked up only if there is no stick on top of it.
a. Explain how to write a routine that takes two sticks a and b and reports whether a is above, below, or unrelated to b. (This has nothing to do with graph theory.)
b. Give an algorithm that determines whether it is possible to pick up all the sticks, and if so, provides a sequence of stick pickups that accomplishes this. - Get solution

9.39 A graph is k-colorable if each vertex can be given one of k colors, and no edge connects identically colored vertices. Give a linear-time algorithm to test a graph for two-colorability. Assume graphs are stored in adjacency list format; you must specify any additional data structures that are needed. - Get solution

9.40 Give a polynomial-time algorithm that finds V/2 vertices that collectively cover at least three-fourths (3/4) of the edges in an arbitrary undirected graph. - Get solution

9.41 Show how to modify the topological sort algorithm so that if the graph is not acyclic, the algorithm will print out some cycle. You may not use depth-first search. - Get solution

9.42 Let G be a directed graph with N vertices. A vertex s is called a sink if, for every v in V such that s = v, there is an edge (v, s), and there are no edges of the form (s, v). Give an O(N) algorithm to determine whether or not G has a sink, assuming that G is given by its N × N adjacency matrix. - Get solution

9.43 When a vertex and its incident edges are removed from a tree, a collection of subtrees remains. Give a linear-time algorithm that finds a vertex whose removal from an N vertex tree leaves no  subtree with more than N/2 vertices. - Get solution

9.44 Give a linear-time algorithm to determine the longest unweighted path in an acyclic undirected graph (that is, a tree). - Get solution

9.45 Consider an N-by-N grid in which some squares are occupied by black circles. Two squares belong to the same group if they share a common edge. In Figure 9.88, there is one group of four occupied squares, three groups of two occupied squares, and two individual occupied squares. Assume that the grid is represented by a two-dimensional array. Write a program that does the following:
a. Computes the size of a group when a square in the group is given.
b. Computes the number of different groups.
c. Lists all groups. - Get solution

9.46 Section 8.7 described the generating of mazes. Suppose we want to output the path in the maze. Assume that the maze is represented as a matrix; each cell in the matrix stores information about what walls are present (or absent).
a. Write a program that computes enough information to output a path in the maze. Give output in the form SEN... (representing go south, then east, then north, etc.).
b. Write a program that draws the maze and, at the press of a button, draws the path. -

Solution clue: This is a single source unweighted shortest path problem.

9.47 Suppose that walls in the maze can be knocked down, with a penalty of P squares.
P is specified as a parameter to the algorithm. (If the penalty is 0, then the problem is trivial.) Describe an algorithm to solve this version of the problem. What is the running time of your algorithm? - Get solution

9.48 Suppose that the maze may or may not have a solution.
a. Describe a linear-time algorithm that determines the minimum number of walls that need to be knocked down to create a solution. (Hint: Use a double-ended queue.)
b. Describe an algorithm (not necessarily linear-time) that finds a shortest path after knocking down the minimum number of walls. Note that the solution to part
(a) would give no information about which walls would be the best to knock down. (Hint: Use Exercise 9.47.) - Get solution

9.49 Write a program to compute word ladders where single-character substitutions have a cost of 1, and single-character additions or deletions have a cost of p > 0, specified by the user. As mentioned at the end of Section 9.3.6, this is essentially a weighted shortest-path problem.
Explain how each of the following problems (Exercises 9.50–9.53) can be solved by applying a
shortest-path algorithm. Then design a mechanism for representing an input, and write a program
that solves the problem. - Get solution

9.50 The input is a list of league game scores (and there are no ties). If all teams have at least one win and a loss, we can generally prove, by a silly transitivity argument, that any team is better than any other. For instance, in the six-team league where everyone plays three games, suppose we have the following results: A beat B and C; B beat C and F; C beat D; D beat E; E beat A; F beat D and E. Then we can prove that A is better than F, because A beat B, who in turn beat F. Similarly, we can prove that F is better than A because F beat E and E beat A. Given a list of game scores and two teams X and Y, either find a proof (if one exists) that X is better than Y, or indicate that no proof of this form can be found. - Get solution

9.51 The input is a collection of currencies and their exchange rates. Is there a sequence of exchanges that makes money instantly? For instance, if the currencies are X, Y, and Z and the exchange rate is 1 X equals 2 Ys, 1 Y equals 2 Zs, and 1 X equals 3 Zs, then 300 Zs will buy 100 Xs, which in turn will buy 200 Ys, which in turn will buy 400 Zs. We have thus made a profit of 33 percent. - Get solution

9.52 A student needs to take a certain number of courses to graduate, and these courses have prerequisites that must be followed. Assume that all courses are offered every semester and that the student can take an unlimited number of courses. Given a list of courses and their prerequisites, compute a schedule that requires the minimum number of semesters. - Get solution

9.53 The object of the Kevin Bacon Game is to link a movie actor to Kevin Bacon via shared movie roles. The minimum number of links is an actor’s Bacon number. For instance, Tom Hanks has a Bacon number of 1; he was in Apollo 13 with Kevin Bacon. Sally Field has a Bacon number of 2, because she was in Forrest Gump with Tom Hanks, who was in Apollo 13 with Kevin Bacon. Almost all well-known actors have a Bacon number of 1 or 2. Assume that you have a comprehensive list of
actors, with roles,3 and do the following:
a. Explain how to find an actor’s Bacon number.
b. Explain how to find the actor with the highest Bacon number.
c. Explain how to find the minimum number of links between two arbitrary actors. - Get solution

9.54 The clique problem can be stated as follows: Given an undirected graph G = (V, E) and an  integer K, does G contain a complete subgraph of at least K vertices?
The vertex cover problem can be stated as follows: Given an undirected graph G = (V, E) and an integer K, does G contain a subset V ⊂ V such that |V | ≤ K and every edge in G has a vertex in V ? Show that the clique problem is polynomially reducible to vertex cover. - Get solution

9.55 Assume that the Hamiltonian cycle problem is NP-complete for undirected graphs.
a. Prove that the Hamiltonian cycle problem is NP-complete for directed graphs.
b. Prove that the unweighted simple longest-path problem is NP-complete for directed graphs. - Get solution

9.56 The baseball card collector problem is as follows: Given packets P1, P2, . . . , PM, each
of which contains a subset of the year’s baseball cards, and an integer K, is it possible to collect all the baseball cards by choosing ≤ K packets? Show that the baseball card collector problem is NP-complete. - Get solution

### Chapter #8 Solutions- Allan Weiss - Data Structures and Algorithm Analysis in Java - 3rd Edition

Available Solutions for the following Chapter 7 exercises:

8.1 Show the result of the following sequence of instructions: union(1,2), union(3,4),
union(3,5), union(1,7), union(3,6), union(8,9), union(1,8), union(3,10),
union (3,11), union(3,12), union(3,13), union(14,15), union(16,0), union(14,16),
union (1,3), union(1, 14) when the unions are:
a. Performed arbitrarily.
b. Performed by height.
c. Performed by size. - Get solution

8.2 For each of the trees in the previous exercise, perform a find with path compression
on the deepest node. - Get solution

8.4 Show that if unions are performed by height, then the depth of any tree is O(logN). - Get solution

8.8 Prove that for the mazes generated by the algorithm in Section 8.7, the path from
the starting to ending points is unique. - Get solution

8.9 Design an algorithm that generates a maze that contains no path from start to finish
but has the property that the removal of a prespecified wall creates a unique path. - Get solution

8.10 Suppose we want to add an extra operation, deunion, which undoes the last union operation that has not been already undone.
a. Show that if we do union-by-height and finds without path compression, then
deunion is easy and a sequence of M union, find, and deunion operations takes
O(MlogN) time.
b. Why does path compression make deunion hard?
c. Show how to implement all three operations so that the sequence of M
operations takes O(M logN/log logN) time. - Get solution

8.11 Suppose we want to add an extra operation, remove(x), which removes x from its current set and places it in its own. Show how to modify the union/find algorithm so that the running time of a sequence of M union, find, and remove operations is O(Mα(M,N)). - Get solution

8.12 Show that if all of the unions precede the finds, then the disjoint set algorithm with path compression requires linear time, even if the unions are done arbitrarily. - Get solution

8.14 Prove that if unions are done by size and path compression is performed, the worstcase
running time is O(Mα(M,N)). - Get solution

8.16 Suppose we implement partial path compression on find(i) by making every other node on the path from i to the root link to its grandparent (where this makes sense).
This is known as path halving.
a. Write a procedure to do this.
b. Prove that if path halving is performed on the finds and either union-by-height
or union-by-size is used, the worst-case running time is O(Mα(M,N)). - Get solution

## miércoles, 12 de febrero de 2014

### Chapter #7 Solutions- Allan Weiss - Data Structures and Algorithm Analysis in Java - 3rd Edition

7.1 Sort the sequence 3, 1, 4, 1, 5, 9, 2, 6, 5 using insertion sort. - Get solution

7.2 What is the running time of insertion sort if all elements are equal? - Get solution

7.3 Suppose we exchange elements a[i] and a[i+k], which were originally out of order.
Prove that at least 1 and at most 2k − 1 inversions are removed. - Get solution

7.4 Show the result of running Shellsort on the input 9, 8, 7, 6, 5, 4, 3, 2, 1 using the increments {1, 3, 7}. - Get solution

7.5 a. What is the running time of Shellsort using the two-increment sequence {1, 2}?
b. Show that for any N, there exists a three-increment sequence such that Shellsort - Get solution

7.7 Prove that if a k-sorted file is then h-sorted, it remains k-sorted. - Sol. Not available

7.9 Determine the running time of Shellsort for
a. sorted input
b. reverse-ordered input - Get solution

7.10 Do either of the following modifications to the Shellsort routine coded in Figure 7.4
affect the worst-case running time?
a. Before line 11, subtract one from gap if it is even.
b. Before line 11, add one to gap if it is even. - Get solution

7.11 Show how heapsort processes the input 142, 543, 123, 65, 453, 879, 572, 434,
111, 242, 811, 102. - Get solution

7.13 Show that there are inputs that force every percolateDown in heapsort to go all the
way to a leaf. (Hint: Work backward.) - Get solution

7.14 Rewrite heapsort so that it sorts only items that are in the range low to high which
are passed as additional parameters.
Solution: If the root is stored in position low, then the left child of node i is stored at position 2i + 1 - low. This requires a small change to the heapsort code.

7.15 Sort 3, 1, 4, 1, 5, 9, 2, 6 using mergesort. - Get solution

7.16 How would you implement mergesort without using recursion? - Get solution

7.17 Determine the running time of mergesort for
a. sorted input
b. reverse-ordered input
c. random input - Get solution

7.18 Sol. Not available

7.19 Sort 3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5 using quicksort with median-of-three partitioning
and a cutoff of 3. - Get solution

7.20 Using the quicksort implementation in this chapter, determine the running time of
quicksort for
a. sorted input
b. reverse-ordered input
c. random input - Get solution

7.21 Repeat Exercise 7.20 when the pivot is chosen as
a. the first element
b. the larger of the first two distinct elements
c. a random element
d. the average of all elements in the set - Get solution

7.22 a. For the quicksort implementation in this chapter, what is the running time when
all keys are equal?
b. Suppose we change the partitioning strategy so that neither i nor j stops when
an element with the same key as the pivot is found. What fixes need to be made
in the code to guarantee that quicksort works, and what is the running time,
when all keys are equal?
c. Suppose we change the partitioning strategy so that i stops at an element with
the same key as the pivot, but j does not stop in a similar case. What fixes need
to be made in the code to guarantee that quicksort works, and when all keys are
equal, what is the running time of quicksort? - Get solution

7.23 Suppose we choose the element in the middle position of the array as the pivot.
Does this make it unlikely that quicksort will require quadratic time? - Get solution

7.24 Construct a permutation of 20 elements that is as bad as possible for quicksort using median-of-three partitioning and a cutoff of 3. - Get solution

7.26 Continuing from Exercise 7.25, after part (a),
a. Perform a test so that the smaller subarray is processed by the first recursive call,
while the larger subarray is processed by the second recursive call.
b. Remove the tail recursion by writing a while loop and altering left or right, as
necessary.
c. Prove that the number of recursive calls is logarithmic in the worst case. - Get solution

7.27 Suppose the recursive quicksort receives an int parameter, depth, from the driver
that is initially approximately 2 logN.
a. Modify the recursive quicksort to call heapsort on its current subarray if the level
of recursion has reached depth. (Hint: Decrement depth as you make recursive
calls; when it is 0, switch to heapsort.)
b. Prove that the worst-case running time of this algorithm is O(N logN).
c. Conduct experiments to determine how often heapsort gets called.
d. Implement this technique in conjunction with tail-recursion removal in Exercise 7.25.
e. Explain why the technique in Exercise 7.26 would no longer be needed. - Sol. 7.27 Not available

7.28 When implementing quicksort, if the array contains lots of duplicates, it may be better to perform a three-way partition (into elements less than, equal to, and greater than the pivot), to make smaller recursive calls. Assume three-way comparisons, as provided by the compareTo method.
a. Give an algorithm that performs a three-way in-place partition of an N-element subarray using only N − 1 three-way comparisons. If there are d items equal to the pivot, you may use d additional Comparable swaps, above and beyond the two-way partitioning algorithm. (Hint: As i and j move toward each other, maintain five groups of elements as shown below):
EQUAL SMALL UNKNOWN LARGE EQUAL
i j
b. Prove that using the algorithm above, sorting an N-element array that contains
only d different values, takes O(dN) time. - Get 7.28a Solution / Sol. 7.28. b. Not available

7.37 Consider the following algorithm for sorting six numbers:
Sort the first three numbers using Algorithm A.
Sort the second three numbers using Algorithm B.
Merge the two sorted groups using Algorithm C.
Show that this algorithm is suboptimal, regardless of the choices for Algorithms A,
B, and C. - Get solution

7.38 Write a program that reads N points in a plane and outputs any group of four
or more colinear points (i.e., points on the same line). The obvious brute-force
algorithm requires O(N4) time. However, there is a better algorithm that makes use
of sorting and runs in O(N2 logN) time. - Get solution

7.42 Give a linear-time algorithm to sort N fractions, each of whose numerators and denominators are integers between 1 and N. - Get solution

7.43 Suppose arrays A and B are both sorted and both contain N elements. Give an O(logN) algorithm to find the median of A ∪ B. - Get solution

7.44 Suppose you have an array of N elements containing only two distinct keys, true and false. Give an O(N) algorithm to rearrange the list so that all false elements precede the true elements. You may use only constant extra space. - Get solution

7.45 Suppose you have an array of N elements, containing three distinct keys, true, false, and maybe. Give an O(N) algorithm to rearrange the list so that all false elements precede maybe elements, which in turn precede true elements. You may use only constant extra space. - Get solution

7.46 a. Prove that any comparison-based algorithm to sort 4 elements requires 5 comparisons.
b. Give an algorithm to sort 4 elements in 5 comparisons. - Get solution

7.47 a. Prove that 7 comparisons are required to sort 5 elements using any comparison based
algorithm.
b. Give an algorithm to sort 5 elements with 7 comparisons. - Get solution

7.51 Suppose we implement the median of three routine as follows: Find the median of a[left], a[center], a[right], and swap it with a[right]. Proceed with the normal partitioning step starting i at left and j at right-1 (instead of left+1 and right-2).
a. Suppose the input is 2, 3, 4, . . . ,N −1,N, 1. For this input, what is the running time of this version of quicksort?
b. Suppose the input is in reverse order. For this input, what is the running time of this version of quicksort? - Get solution

7.52 Prove that any comparison-based sorting algorithm requires (N logN) comparisons on average. - Get solution

7.53 We are given an array that contains N numbers. We want to determine if there are two numbers whose sum equals a given number K. For instance, if the input is 8, 4, 1, 6, and K is 10, then the answer is yes (4 and 6). A number may be used twice.
Do the following:
a. Give an O(N2) algorithm to solve this problem.
b. Give an O(N logN) algorithm to solve this problem. (Hint: Sort the items first.
After that is done, you can solve the problem in linear time.)
c. Code both solutions and compare the running times of your algorithms. - Get solution

7.55 Repeat Exercise 7.53 for three numbers. Try to design an O(N2) algorithm. - Get solution

### Chapter #6 Solutions - Allan Weiss - Data Structures and Algorithm Analysis in Java - 3rd Edition

Available Solutions for the following Chapter 6 exercises:

6.1 Can both insert and findMin be implemented in constant time? - Get solution

6.2 a. Show the result of inserting 10, 12, 1, 14, 6, 5, 8, 15, 3, 9, 7, 4, 11, 13, and 2, one at a time, into an initially empty binary heap.
b. Show the result of using the linear-time algorithm to build a binary heap using the same input. - Get solution

6.3 Show the result of performing three deleteMin operations in the heap of the previous exercise. - Get solution

6.4 A complete binary tree of N elements uses array positions 1 to N. Suppose we try
to use an array representation of a binary tree that is not complete. Determine how
large the array must be for the following:
a. a binary tree that has two extra levels (that is, it is very slightly unbalanced)
b. a binary tree that has a deepest node at depth 2 logN
c. a binary tree that has a deepest node at depth 4.1 logN
d. the worst-case binary tree  - Get solution

6.5 Rewrite the BinaryHeap insert method by placing a reference to the inserted item in
position 0. - Get solution

6.6 How many nodes are in the large heap in Figure 6.13?  - Get solution

6.10 a. Give an algorithm to find all nodes less than some value, X, in a binary heap.
Your algorithm should run in O(K), where K is the number of nodes output.
b. Does your algorithm extend to any of the other heap structures discussed in this chapter?
c. Give an algorithm that finds an - Get solution

6.12 Write a program to take N elements and do the following:
a. Insert them into a heap one by one.
b. Build a heap in linear time. - Get solution

Compare the running time of both algorithms for sorted, reverse-ordered, and
random inputs.

6.13 Each deleteMin operation uses 2 logN comparisons in the worst case.
a. Propose a scheme so that the deleteMin operation uses only logN + log logN +
O(1) comparisons between elements. This need not imply less data movement.
b. Extend your scheme in part (a) so that only logN + log log logN + O(1)
comparisons are performed.
c. How far can you take this idea?
d. Do the savings in comparisons compensate for the increased complexity of your algorithm?  - Get solution

6.14 If a d-heap is stored as an array, for an entry located in position i, where are the parents and children? - Get solution

6.15 Suppose we need to perform M percolateUps and N deleteMins on a d-heap that initially has N elements.
a. What is the total running time of all operations in terms of M, N, and d?
b. If d = 2, what is the running time of all heap operations?
c. If d = (N), what is the total running time?
d. What choice of d minimizes the total running time? - Get solution

6.16 Suppose that binary heaps are represented using explicit links. Give a simple algorithm to find the tree node that is at implicit position i. - Get solution

6.17 Suppose that binary heaps are represented using explicit links. Consider the problem of merging binary heap lhs with rhs. Assume both heaps are perfect binary
trees, containing 2l − 1 and 2r − 1 nodes, respectively.
a. Give an O(logN) algorithm to merge the two heaps if l = r.
b. Give an O(logN) algorithm to merge the two heaps if |l − r| = 1.
c. Give an O(log2 N) algorithm to merge the two heaps regardless of l and r. - Get solution

6.19 Merge the two leftist heaps in Figure 6.58. - Get solution

6.20 Show the result of inserting keys 1 to 15 in order into an initially empty leftist heap. - Get solution

6.21 Prove or disprove: A perfectly balanced tree forms if keys 1 to 2k − 1 are inserted in order into an initially empty leftist heap. - Get solution

6.22 Give an example of input that generates the best leftist heap. - Get solution

6.23 a. Can leftist heaps efficiently support decreaseKey?
b. What changes, if any (if possible), are required to do this? - Get solution

6.24 One way to delete nodes from a known position in a leftist heap is to use a lazy strategy. To delete a node, merely mark it deleted. When a findMin or deleteMin is performed, there is a potential problem if the root is marked deleted, since then the node has to be actually deleted and the real minimum needs to be found, which may involve deleting other marked nodes. In this strategy, deletes cost one unit, but the cost of a deleteMin or findMin depends on the number of nodes that are marked deleted. Suppose that after a deleteMin or findMin there are k fewer marked nodes than before the operation.
a. Show how to perform the deleteMin in O(k logN) time.
b. Propose an implementation, with an analysis to show that the time to perform the deleteMin is O(k log(2N/k)). - Get solution

6.25 We can perform buildHeap in linear time for leftist heaps by considering each
element as a one-node leftist heap, placing all these heaps on a queue, and performing
the following step: Until only one heap is on the queue, dequeue two
heaps, merge them, and enqueue the result.
a. Prove that this algorithm is O(N) in the worst case.
b. Why might this algorithm be preferable to the algorithm described in the text? - Get solution

6.26 Merge the two skew heaps in Figure 6.58. - Get solution

6.27 Show the result of inserting keys 1 to 15 in order into a skew heap. - Get solution

6.28 Prove or disprove: A perfectly balanced tree forms if the keys 1 to 2k−1 are inserted in order into an initially empty skew heap. - Get solution

6.29 A skew heap of N elements can be built using the standard binary heap algorithm.
Can we use the same merging strategy described in Exercise 6.25 for skew heaps to get an O(N) running time? - Get solution

6.30 Prove that a binomial tree Bk has binomial trees B0, B1, . . . , Bk−1 as children of the
root. - Get solution

6.31 Prove that a binomial tree of height k has kd nodes at depth d. - Get solution

6.32 Merge the two binomial queues in Figure 6.59. - Get solution

6.33 a. Show that N inserts into an initially empty binomial queue takes O(N) time in the worst case.
b. Give an algorithm to build a binomial queue of N elements, using at most N−1 comparisons between elements.
c. Propose an algorithm to insert M nodes into a binomial queue of N elements in O(M + logN) worst-case time. Prove your bound. - Get solution

6.38 Suppose we want to add the decreaseAllKeys() operation to the heap repertoire.
The result of this operation is that all keys in the heap have their value decreased by an amount. For the heap implementation of your choice, explain the necessary modifications so that all other  operations retain their running times and decreaseAllKeys runs in O(1). - Get solution

6.39 Which of the two selection algorithms has the better time bound? - Get solution