Questions and Answers of Algorithms

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
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
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
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
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
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
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
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
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
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
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,
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
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
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
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
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
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
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
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
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),
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,
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
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.
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).
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) =
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
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
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
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
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
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
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
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
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
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
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
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
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
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)
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
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
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
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

Showing 400 - 500 of 575