Data Structures and Algorithm Analysis in Java 3rd edition Mark A. Weiss - Solutions

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
Which of the two selection algorithms has the better time bound?
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
Rewrite the BinaryHeap insert method by placing a reference to the inserted item in position 0.
How many nodes are in the large heap in Figure 6.13?
a. Prove that for binary heaps, buildHeap does at most 2N−2 comparisons between elements.b. Show that a heap of eight elements can be constructed in eight comparisons between heap elements.c. Give an algorithm to build a binary heap in 13/8 N + O(logN) element comparisons.
Show that the expected depth of the kth smallest element in a large complete heap (you may assume N = 2k − 1) is bounded by log k.
Sort the sequence 3, 1, 4, 1, 5, 9, 2, 6, 5 using insertion sort.
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.
Show how heapsort processes the input 142, 543, 123, 65, 453, 879, 572, 434, 111, 242, 811, 102.
Show that there are inputs that force every percolateDown in heapsort to go all the way to a leaf.
Rewrite heapsort so that it sorts only items that are in the range low to high which are passed as additional parameters.
Sort 3, 1, 4, 1, 5, 9, 2, 6 using mergesort.
How would you implement mergesort without using recursion?
Determine the running time of mergesort for a. Sorted input b. Reverse-ordered input c. Random input
In the analysis of mergesort, constants have been disregarded. Prove that the number of comparisons used in the worst case by mergesort is N[log N] - 2[logN] + 1.
Sort 3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5 using quicksort with median-of-three partitioning and a cutoff of 3.
What is the running time of insertion sort if all elements are equal?
Using the quicksort implementation in this chapter, determine the running time of quicksort for a. Sorted input b. Reverse-ordered input c. Random input
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 In exercise Using the quicksort implementation in this chapter, determine the running time of quicksort for a. Sorted
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
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?
Construct a permutation of 20 elements that is as bad as possible for quicksort using median-of-three partitioning and a cutoff of 3.
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
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.
Solve the following recurrence:
A sorting algorithm is stable if elements with equal keys are left in the same order as they occur in the input. Which of the sorting algorithms in this chapter are stable and which are not? Why?
Suppose you are given a sorted list of N elements followed by f (N) randomly ordered elements. How would you sort the entire list if a. f (N) = O(1)? b. f (N) = O(logN)? c. f (N) = O(√N)? d. How large can f (N) be for the entire list still to be sortable in O(N) time?
Prove that any algorithm that finds an element X in a sorted list of N elements requires Ω(logN) comparisons.
Using Stirling's formula, N! ≈ (N/e)N √2πN, give a precise estimate for log(N!).
a. In how many ways can two sorted arrays of N elements be merged?b. Give a nontrivial lower bound on the number of comparisons required to merge two sorted lists of N elements, by taking the logarithm of your answer in part (a).
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,
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.
Show that the two smallest elements among N can be found in N + [logN] − 2 comparisons.
Show the result of running Shellsort on the input 9, 8, 7, 6, 5, 4, 3, 2, 1 using the increments {1, 3, 7}.
The following divide-and-conquer algorithm is proposed for finding the simultaneous maximum and minimum: If there is one item, it is the maximum and minimum, and if there are two items, then compare them and in one comparison you can find the maximum and minimum. Otherwise, split the input into two
Give a linear-time algorithm to sort N fractions, each of whose numerators and denominators are integers between 1 and N.
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.
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.
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.
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.
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.
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 runs in O(N5/3) time.c. Show that for any N, there exists a six-increment sequence such that Shellsort runs in O(N3/2) time.
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,
Prove that any comparison-based sorting algorithm requires Ω(N logN) comparisons on average.
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
Repeat Exercise 7.53 for three numbers. Try to design an O(N2) algorithm. 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
a. Prove that the running time of Shellsort is (N2) using increments of the form 1, c, c2, . . . , ci for any integer c. b. Prove that for these increments, the average running time is Θ(N3/2).
Prove that the running time of Shellsort, using the increment sequence suggested by Hibbard, is (N3/2) in the worst case. Hint: You can prove the bound by considering the special case of what Shellsort does when all elements are either 0 or 1. Set a[i] = 1 if i is expressible as a linear
Determine the running time of Shellsort for a. Sorted input b. Reverse-ordered input
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
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.
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)).
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.
Prove that if unions are done by size and path compression is performed, the worstcase running time is O(Mα(M,N)).
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
For each of the trees in the previous exercise, perform a find with path compression on the deepest node.
Show that if unions are performed by height, then the depth of any tree is O(logN).
Suppose f (N) is a nicely defined function that reduces N to a smaller integer. What is the solution to the recurrence T(N) = N/f (N) T(f (N)) + N with appropriate initial conditions?
a. Show that if M = N2, then the running time of M union/find operations is O(M).b. Show that if M = N logN, then the running time of M union/find operations is O(M).c. Suppose M = O(N log logN). What is the running time of M union/find operations?d. Suppose M = O(N log* N). What is the running
Prove that for the mazes generated by the algorithm in Section 8.7, the path from the starting to ending points is unique. α(M,N) = min{i ≥ 1| (A (i, M/N) > logN)}, where A(1, j) = 2j............................................j ≥ 1 A(i, 1) = A(i − 1, 2) .................................i
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.
Find a topological ordering for the graph in Figure 9.81.
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.
Find the maximum flow in the network of Figure 9.81.
Suppose that G = (V, E) is a tree, s is the root, and we add a vertex t and edges of infinite capacity from all leaves in G to t. Give a linear-time algorithm to find a maximum flow from s to t.
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
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
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?
Does either Prim's or Kruskal's algorithm work if there are negative edge weights?
Show that a graph of V vertices can have VV−2 minimum spanning trees.
If all the edges in a graph have weights between 1 and |E|, how fast can the minimum spanning tree be computed?
If a stack is used instead of a queue for the topological sort algorithm in Section 9.2, does a different ordering result? Why might one data structure give a "better" answer?
Give an algorithm to find a maximum spanning tree. Is this harder than finding a minimum spanning tree?
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.
Prove that the algorithm to find articulation points works.
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.
Prove that in a depth-first spanning forest of a directed graph, all cross edges go from right to left.
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.
Find the strongly connected components in the graph of Figure 9.86.
Give an algorithm that finds the strongly connected components in only one depth-first search. Use an algorithm similar to the biconnectivity algorithm.
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.
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.
Give an algorithm to find in an undirected (connected) graph a path that goes through every edge exactly once in each direction.
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
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.
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|
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?
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.
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.
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
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.
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.
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.
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.
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.
Give a linear-time algorithm to determine the longest unweighted path in an acyclic undirected graph (that is, a tree).
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
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
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?

Showing 400 - 500 of 575

Data Structures and Algorithm Analysis in Java 3rd edition Mark A. Weiss - Solutions

Step by Step Answers