4 min read

The following theorem shows that this problem is NP-complete. Theorem: The vertex-cover problem is NP-complete. Proof We first show that VERTEX-COVER ∈ NP. Suppose we are given a graph G = (V, E) and an integer k. The certificate we choose is the vertex cover V' ⊆ V itself. The verification algorithm affirms that |V'| = k, and then it checks, for each edge (u, v) ∈ E, that u ∈ V' or v ∈ V'. This verification can be performed straightforwardly in polynomial time.

4 min read

The Bellman-Ford algorithm: The Bellman-Ford algorithm solves the single-source shortest-paths problem in the general case in which edge weights may be negative. Given a weighted, directed graph G = (V, E) with source s and weight function w : E → R, the Bellman-Ford algorithm returns a boolean value indicating whether or not there is a negative-weight cycle that is reachable from the source. If there is such a cycle, the algorithm indicates that no solution exists. If there is no such cycle, the algorithm produces the shortest paths and their weights. The algorithm uses relaxation, progressively decreasing an estimate d[v] on the weight of a shortest path from the source s to each vertex v ∈ V until it achieves the actual shortest-path weight δ(s, v). The algorithm returns TRUE if and only if the graph contains no negative-weight cycles that are reachable from the source. Figure 24.4 shows the execution of the Bellman-Ford algorithm on a graph with 5 vertices. After initializing the d and π values of all vertices in line 1, the algorithm makes |V| - 1 passes over the edges of the graph. Each pass is one iteration of the for loop of lines 2-4 and consists of relaxing each edge of the graph once. Figures 24.4(b)-(e) show the state of the algorithm after each of the four passes over the edges. After making |V|- 1 passes, lines 5-8 check for a negative-weight cycle and return the appropriate boolean value. (We'll see a little later why this check works.)

3 min read

Figure 30.1 shows this strategy graphically. One minor detail concerns degree-bounds. The product of two polynomials of degree-bound n is a polynomial of degree-bound 2n. Before evaluating the input polynomials A and B, therefore, we first double their degree-bounds to 2n by adding n high-order coefficients of 0. Because the vectors have 2n elements, we use "complex (2n)th roots of unity," which are denoted by the w_2n terms in Figure 30.1. Given the FFT, we have the following Θ(n lg n)-time procedure for multiplying two polynomials A(x) and B(x) of degree-bound n, where the input and output representations are in coefficient form. We assume that n is a power of 2; this requirement can always be met by adding high-order zero coefficients. Double degree-bound: Create coefficient representations of A(x) and B(x) as degree-bound 2n polynomials by adding n high-order zero coefficients to each.

3 min read

A sorting network We now have all the necessary tools to construct a network that can sort any input sequence. The sorting network SORTER[n] uses the merging network to implement a parallel version of merge sort from divide-and-conquer approach. The construction and operation of the sorting network are illustrated in Figure 27.12.

1 min read

Properties of Matrices: Basic properties of Matrices which are given as: 1. Zero matrix or Null matrix: A matrix whose all element equal to zero.

3 min read

Inverting matrices Although in practice we do not generally use matrix inverses to solve systems of linear equations, preferring instead to use more numerically stable techniques such as LUP decomposition, it is sometimes necessary to compute a matrix inverse. In this section, we show how LUP decomposition can be used to compute a matrix inverse. We also prove that matrix multiplication and computing the inverse of a matrix are equivalently hard problems, in that (subject to technical conditions) we can use an algorithm for one to solve the other in the same asymptotic running time. Thus, we can use Strassen's algorithm for matrix multiplication to invert a matrix. Indeed, Strassen's original paper was motivated by the problem of showing that a set of a linear equations could be solved more quickly than by the usual method. Suppose that we have an LUP decomposition of a matrix A in the form of three matrices L, U , and P such that PA = LU. Using LUP-SOLVE, we can solve an equation of the form Ax = b in time Θ(n²). Since the LUP decomposition depends on A but not b, we can run LUP-SOLVE on a second set of equations of the form Ax = b' in additional time Θ(n²). In general, once we have the LUP decomposition of A, we can solve, in time Θ(kn²), k versions of the equation Ax = b that differ only in b.

4 min read

Introduction: The straightforward method of adding two polynomials of degree n takes Θ(n) time, but the straightforward method of multiplying them takes Θ(n²) time. In this chapter, we shall show how the Fast Fourier Transform, or FFT, can reduce the time to multiply polynomials to Θ(n lg n). The most common use for Fourier Transforms, and hence the FFT, is in signal processing. A signal is given in the time domain: as a function mapping time to amplitude. Fourier analysis allows us to express the signal as a weighted sum of phase-shifted sinusoids of varying frequencies. The weights and phases associated with the frequencies characterize the signal in the frequency domain. Signal processing is a rich area for which there are several fine books; the chapter notes reference a few of them. We call the values a₀, a₁,..., a_n-1 the coefficients of the polynomial. The coefficients are drawn from a field F, typically the set C of complex numbers. A polynomial A(x) is said to have degree k if its highest nonzero coefficient is a_k. Any integer strictly greater than the degree of a polynomial is a degree-bound of that polynomial. Therefore, the degree of a polynomial of degree-bound n may be any integer between 0 and n - 1, inclusive.

3 min read

The naive string-matching algorithm The naive algorithm finds all valid shifts using a loop that checks the condition P[1 ‥ m] = T [s 1 ‥ s m] for each of the n - m 1 possible values of s. The naive string-matching procedure can be interpreted graphically as sliding a "template" containing the pattern over the text, noting for which shifts all of the characters on the template equal the corresponding characters in the text, as illustrated in Figure 32.4. The for loop beginning on line 3 considers each possible shift explicitly. The test on line 4 determines whether the current shift is valid or not; this test involves an implicit loop to check corresponding character positions until all positions match successfully or a mismatch is found. Line 5 prints out each valid shift s.

5 min read

Flow networks: In this section, a graph-theoretic definition of flow networks, discuss their properties, and define the maximum-flow problem precisely. We also introduce some helpful notation. A flow network G = (V, E) is a directed graph in which each edge (u, v) ∈E has a nonnegative capacity c(u, v) ≥ 0. If (u, v) ∉ E, we assume that c(u, v) = 0. We distinguish two vertices in a flow network: a source s and a sink t. For convenience, we assume that every vertex lies on some path from the source to the sink. That is, for every vertex v ∈ V, there is a path The graph is therefore connected, and |E| ≥ |V | - 1. Figure 26.1 shows an example of a flow network. We are now ready to define flows more formally. Let G = (V, E) be a flow network with a capacity function c. Let s be the source of the network, and let t be the sink. A flow in G is a real-valued function f : V × V → R that satisfies the following three properties:

4 min read

A bitonic sorting network The first step in our construction of an efficient sorting network is to construct a comparison network that can sort any bitonic sequence: a sequence that monotonically increases and then monotonically decreases, or can be circularly shifted to become monotonically increasing and then monotonically decreasing. For example, the sequences 〈1, 4, 6, 8, 3, 2〉, 〈6, 9, 4, 2, 3, 5〉, and 〈9, 8, 3, 2, 4, 6〉 are all bitonic. As a boundary condition, we say that any sequence of just 1 or 2 numbers is bitonic. The zero-one sequences that are bitonic have a simple structure. They have the form 0ⁱ 1^j 0^k or the form 1ⁱ 0^j 1^k, for some i, j, k ≥ 0. Note that a sequence that is either monotonically increasing or monotonically decreasing is also bitonic. The bitonic sorter that we shall construct is a comparison network that sorts bitonic sequences of 0's and 1's. Exercise 27.3-6 asks you to show that the bitonic sorter can sort bitonic sequences of arbitrary numbers.

5 min read

We next show that at most 8 points of P can reside within this δ × 2δ rectangle. Consider the δ × δ square forming the left half of this rectangle. Since all points within P_L are at least δ units apart, at most 4 points can reside within this square; Figure 33.11(b) shows how. Similarly, at most 4 points in P_R can reside within the δ × δ square forming the right half of the rectangle. Thus, at most 8 points of P can reside within the δ × 2δ rectangle. (Note that since points on line l may be in either P_L or P_R, there may be up to 4 points on l. This limit is achieved if there are two pairs of coincident points such that each pair consists of one point from P_L and one point from P_R, one pair is at the intersection of l and the top of the rectangle, and the other pair is where l intersects the bottom of the rectangle.) Having shown that at most 8 points of P can reside within the rectangle, it is easy to see that we need only check the 7 points following each point in the array Y′.Still assuming that the closest pair is p_L and p_R, let us assume without loss of generality that p_L precedes p_R in array Y′. Then, even if p_L occurs as early as possible in Y′ and p_R occurs as late as possible, p_R is in one of the 7 positions following p_L . Thus, we have shown the correctness of the closest-pair algorithm. Implementation and running time: As we have noted, our goal is to have the recurrence for the running time be T(n) = 2T(n/2) O(n), where T(n) is the running time for a set of n points. The main difficulty is in ensuring that the arrays X_L, X_R, Y_L, and Y_R, which are passed to recursive calls, are sorted by the proper coordinate and also that the array Y′ is sorted by y-coordinate. (Note that if the array X that is received by a recursive call is already sorted, then the division of set P into P_L and P_R is easily accomplished in linear time.)

5 min read

The set-covering problem: The set-covering problem is an optimization problem that models many resource-selection problems. Its corresponding decision problem generalizes the NP-complete vertex-cover problem and is therefore also NP-hard. The approximation algorithm developed to handle the vertex-cover problem doesn't apply here, however, and so we need to try other approaches. We shall examine a simple greedy heuristic with a logarithmic approximation ratio. That is, as the size of the instance gets larger, the size of the approximate solution may grow, relative to the size of an optimal solution. Because the logarithm function grows rather slowly, however, this approximation algorithm may nonetheless give useful results. An instance (X, ) of the set-covering problem consists of a finite set X and a family of subsets of X, such that every element of X belongs to at least one subset in : We say that a subset covers its elements. The problem is to find a minimum-size subset whose members cover all of X:

6 min read

String matching with finite automata Many string-matching algorithms build a finite automaton that scans the text string T for all occurrences of the pattern P. This section presents a method for building such an automaton. These string-matching automata are very efficient: they examine each text character exactly once, taking constant time per text character. The matching time used-after preprocessing the pattern to build the automaton-is therefore Θ(n). The time to build the automaton, however, can be large if Σ is large. Section 32.4 describes a clever way around this problem. We begin this section with the definition of a finite automaton. We then examine a special string-matching automaton and show how it can be used to find occurrences of a pattern in a text. This discussion includes details on how to simulate the behavior of a string-matching automaton on a given text. Finally, we shall show how to construct the string-matching automaton for a given input pattern.

4 min read

A merging network: Our sorting network will be constructed from merging networks, which are networks that can merge two sorted input sequences into one sorted output sequence. We modify BITONIC-SORTER[n] to create the merging network MERGER[n]. As with the bitonic sorter, we shall prove the correctness of the merging network only for inputs that are zero-one sequences. The merging network is based on the following intuition. Given two sorted sequences, if we reverse the order of the second sequence and then concatenate the two sequences, the resulting sequence is bitonic. For example, given the sorted zero-one sequences X = 00000111 and Y = 00001111, we reverse Y to get Y^R= 11110000. Concatenating X and Y^R yields 0000011111110000, which is bitonic. Thus, to merge the two input sequences X and Y, it suffices to perform a bitonic sort on X concatenated with Y^R. We can construct MERGER[n] by modifying the first half-cleaner of BITONIC- SORTER[n]. The key is to perform the reversal of the second half of the inputs implicitly. Given two sorted sequences 〈a₁, a₂,...,a_n/2〉 and 〈a_{n/2 1}, a_{n/2 2},..., a_n〉 to be merged, we want the effect of bitonically sorting the sequence 〈a₁, a₂,..., a_n/2, a_n, a_n-1,..., a_{n/2 1}〉. Since the first half-cleaner of BITONIC-SORTER[n] compares inputs i and n/2 i, for i = 1, 2,..., n/2, we make the first stage of the merging network compare inputs i and n - i 1. Figure 27.10 shows the correspondence. The only subtlety is that the order of the outputs from the bottom of the first stage of MERGER[n] are reversed compared with the order of outputs from an ordinary half-cleaner. Since the reversal of a bitonic sequence is bitonic.

5 min read

then we can trim L to obtain L′ = 〈10, 12, 15, 20, 23, 29〉, where the deleted value 11 is represented by 10, the deleted values 21 and 22 are represented by 20, and the deleted value 24 is represented by 23. Because every element of the trimmed version of the list is also an element of the original version of the list, trimming can dramatically decrease the number of elements kept while keeping a close (and slightly smaller) representative value in the list for each deleted element. The following procedure trims list L = 〈y₁, y₂, ..., y_m〉 in time Θ(m), given L and δ, and assuming that L is sorted into monotonically increasing order. The output of the procedure is a trimmed, sorted list.

6 min read

NP-completeness and reducibility: Perhaps the most compelling reason why theoretical computer scientists believe that P ≠ NP is the existence of the class of "NP-complete" problems. This class has the surprising property that if any NP-complete problem can be solved in polynomial time, then every problem in NP has a polynomial-time solution, that is, P = NP. Despite years of study, though, no polynomial-time algorithm has ever been discovered for any NP-complete problem. The language HAM-CYCLE is one NP-complete problem. If we could decide HAM-CYCLE in polynomial time, then we could solve every problem in NP in polynomial time. In fact, if NP - P should turn out to be nonempty, we could say with certainty that HAM-CYCLE ∈ NP - P. The NP-complete languages are, in a sense, the "hardest" languages in NP. In this section, we shall show how to compare the relative "hardness" of languages using a precise notion called "polynomial-time reducibility." Then we formally define the NP-complete languages, and we finish by sketching a proof that one such language, called CIRCUIT-SAT, is NP-complete. In NP-completeness proofs and NP-complete problems, we shall use the notion of reducibility to show that many other problems are NP-complete.

3 min read

Single-source shortest paths in directed acyclic graphs By relaxing the edges of a weighted dag (directed acyclic graph) G = (V, E) according to a topological sort of its vertices, we can compute shortest paths from a single source in Θ(V E) time. Shortest paths are always well defined in a dag, since even if there are negative-weight edges, no negative-weight cycles can exist. The algorithm starts by topologically sorting the dag to impose a linear ordering on the vertices. If there is a path from vertex u to vertex v, then u precedes v in the topological sort. We make just one pass over the vertices in the topologically sorted order. As we process each vertex, we relax each edge that leaves the vertex.

5 min read

2 min read

and E = {(v_i, v_j) : x_j - x_i ≤ b_k is a constraint} ∪{(v₀, v₁), (v₀, v₂), (v₀, v₃),..., (v₀, v_n)} . The additional vertex v₀ is incorporated, as we shall see shortly, to guarantee that every other vertex is reachable from it. Thus, the vertex set V consists of a vertex v_i for each unknown x_i , plus an additional vertex v₀. The edge set E contains an edge for each difference constraint, plus an edge (v₀, v_i) for each unknown x_i . If x_j - x_i ≤ b_k is a difference constraint, then the weight of edge (v_i , v_j) is w(v_i, v_j) = b_k. The weight of each edge leaving v₀ is 0. Figure 24.8 shows the constraint graph for the system (24.3)-(24.10) of difference constraints.

7 min read

The hamiltonian-cycle problem: We now return to the hamiltonian-cycle problem defined in Polynomial-time verification Proof We first show that HAM-CYCLE belongs to NP. Given a graph G = (V, E), our certificate is the sequence of |V| vertices that makes up the hamiltonian cycle. The verification algorithm checks that this sequence contains each vertex in V exactly once and that with the first vertex repeated at the end, it forms a cycle in G. That is, it checks that there is an edge between each pair of consecutive vertices and between the first and last vertices. This verification can be performed in polynomial time. We now prove that VERTEX-COVER ≤_P HAM-CYCLE, which shows that HAM-CYCLE is NP-complete. Given an undirected graph G = (V, E) and an integer k, we construct an undirected graph G' = (V', E') that has a hamiltonian cycle if and only if G has a vertex cover of size k.

5 min read

Shortest paths and matrix multiplication: This section presents a dynamic-programming algorithm for the all-pairs shortestpaths problem on a directed graph G = (V, E). Each major loop of the dynamic program will invoke an operation that is very similar to matrix multiplication, so that the algorithm will look like repeated matrix multiplication. We shall start by developing a Θ(V⁴)-time algorithm for the all-pairs shortest-paths problem and then improve its running time to Θ(V³ lg V). Before proceeding, let us briefly recap the steps given in Dynamic Programming for developing a dynamic-programming algorithm. Characterize the structure of an optimal solution.

5 min read

The traveling-salesman problem: In the traveling-salesman problem, which is closely related to the hamiltonian-cycle problem, a salesman must visit n cities. Modeling the problem as a complete graph with n vertices, we can say that the salesman wishes to make a tour, or hamiltonian cycle, visiting each city exactly once and finishing at the city he starts from. There is an integer cost c(i, j) to travel from city i to city j, and the salesman wishes to make the tour whose total cost is minimum, where the total cost is the sum of the individual costs along the edges of the tour. For example, in Figure 34.18, a minimum-cost tour is 〈u, w, v, x, u〉, with cost 7. The formal language for the corresponding decision problem is TSP = {〈G, c, k〉 : G = (V, E) is a complete graph, c is a function from V × V → Z, k ∈ Z, and G has a traveling-salesman tour with cost at most k}. The following theorem shows that a fast algorithm for the traveling-salesman problem is unlikely to exist.

4 min read

The code for PUSH operates as follows. Vertex u is assumed to have a positive excess e[u], and the residual capacity of (u, v) is positive. Thus, we can we increase the flow from u to v by d_f(u, v) = min(e[u], c_f (u, v)) without causing e[u] to become negative or the capacity c(u, v) to be exceeded. Line 3 computes the value d_f(u, v), and we update f in lines 4-5 and e in lines 6-7. Thus, if f is a preflow before PUSH is called, it remains a preflow afterward. Observe that nothing in the code for PUSH depends on the heights of u and v, yet we prohibit it from being invoked unless h[u] = h[v] 1. Thus, excess flow is pushed downhill only by a height differential of 1. By Lemma 26.13, no residual edges exist between two vertices whose heights differ by more than 1, and thus, as long as the attribute h is indeed a height function, there is nothing to be gained by allowing flow to be pushed downhill by a height differential of more than 1. We call the operation PUSH(u, v) a push from u to v. If a push operation applies to some edge (u, v) leaving a vertex u, we also say that the push operation applies to u. It is a saturating push if edge (u, v) becomes saturated (c_f(u, v) = 0 afterward); otherwise, it is a nonsaturating push. If an edge is saturated, it does not appear in the residual network. A simple lemma characterizes one result of a nonsaturating push.

5 min read

The relabel-to-front algorithm: The push-relabel method allows us to apply the basic operations in any order at all. By choosing the order carefully and managing the network data structure efficiently,. We shall now examine the relabel-to-front algorithm, a push-relabel algorithm whose running time is O(V³), which is asymptotically at least as good as O(V²E), and better for dense networks. The relabel-to-front algorithm maintains a list of the vertices in the network. Beginning at the front, the algorithm scans the list, repeatedly selecting an over-flowing vertex u and then "discharging" it, that is, performing push and relabel operations until u no longer has a positive excess. Whenever a vertex is relabeled, it is moved to the front of the list (hence the name "relabel-to-front") and the algorithm begins its scan anew. The correctness and analysis of the relabel-to-front algorithm depend on the notion of "admissible" edges: those edges in the residual network through which flow can be pushed. After proving some properties about the network of admissible edges, we shall investigate the discharge operation and then present and analyze the relabel-to-front algorithm itself.

6 min read

Overview Finding all occurrences of a pattern in a text is a problem that arises frequently in text-editing programs. Typically, the text is a document being edited, and the pattern searched for is a particular word supplied by the user. Efficient algorithms for this problem can greatly aid the responsiveness of the text-editing program. String-matching algorithms are also used, for example, to search for particular patterns in DNA sequences. We formalize the string-matching problem as follows. We assume that the text is an array T [1 ‥ n] of length n and that the pattern is an array P[1 ‥ m] of length m ≤ n. We further assume that the elements of P and T are characters drawn from a finite alphabet Σ. For example, we may have Σ = {0, 1} or Σ = {a, b, . . . , z}. The character arrays P and T are often called strings of characters.

7 min read

The solution of working modulo q is not perfect, however, since t_s ≡ p (mod q) does not imply that t_s = p. On the other hand, if t_s ≢ p (mod q), then we definitely have that t_s ≠ p, so that shift s is invalid. We can thus use the test t_s ≡ p (mod q) as a fast heuristic test to rule out invalid shifts s. Any shift s for which t_s ≡ p (mod q) must be tested further to see if s is really valid or we just have a spurious hit. This testing can be done by explicitly checking the condition P[1 ‥ m] = T [s 1 ‥ s m]. If q is large enough, then we can hope that spurious hits occur infrequently enough that the cost of the extra checking is low. The following procedure makes these ideas precise. The inputs to the procedure are the text T , the pattern P, the radix d to use (which is typically taken to be |Σ|), and the prime q to use. The procedure RABIN-KARP-MATCHER works as follows. All characters are interpreted as radix-d digits. The subscripts on t are provided only for clarity; the program works correctly if all the subscripts are dropped. Line 3 initializes h to the value of the high-order digit position of an m-digit window. Lines 4-8 compute p as the value of P[1 ‥ m] mod q and t₀ as the value of T [1 ‥ m] mod q. The for loop of lines 9-14 iterates through all possible shifts s, maintaining the following invariant:

7 min read

Prim's algorithm: Like Kruskal's algorithm, Prim's algorithm is a special case of the generic minimum-spanning-tree algorithm from Growing a minimum spanning tree. Prim's algorithm operates much like Dijkstra's algorithm for finding shortest paths in a graph, which we shall see in Dijkstra's algorithm. Prim's algorithm has the property that the edges in the set A always form a single tree. As is illustrated in Figure 23.5, the tree starts from an arbitrary root vertex r and grows until the tree spans all the vertices in V. At each step, a light edge is added to the tree A that connects A to an isolated vertex of G_A = (V, A). This strategy is greedy since the tree is augmented at each step with an edge that contributes the minimum amount possible to the tree's weight.

6 min read

Line-segment properties: Several of the computational-geometry algorithms in this chapter will require answers to questions about the properties of line segments. A convex combination of two distinct points p₁ = (x₁, y₁) and p₂ = (x₂, y₂) is any point p₃ = (x₃, y₃) such that for some α in the range 0 ≤ α ≤ 1, we have x₃ = αx₁ (1 - α)x₂ and y₃ = αy₁ (1 - α)y₂. We also write that p₃ = αp₁ (1 - α)p₂. Intuitively, p₃ is any point that is on the line passing through p₁ and p₂ and is on or between p₁ and p₂ on the line. Given two distinct points p₁ and p₂, the line segment is the set of convex combinations of p₁ and p₂. We call p₁ and p₂ the endpoints of segment . Sometimes the ordering of p₁ and p₂ matters, and we speak of the directed segment . If p₁ is the origin (0, 0), then we can treat the directed segment as the vector p₂. In this section, we shall explore the following questions: Given two directed segments and , is clockwise from with respect to their common endpoint p₀?

6 min read

Determining whether any pair of segments intersects This section presents an algorithm for determining whether any two line segments in a set of segments intersect. The algorithm uses a technique known as "sweeping," which is common to many computational-geometry algorithms. Moreover, as the exercises at the end of this section show, this algorithm, or simple variations of it, can be used to solve other computational-geometry problems. The algorithm runs in O(n lg n) time, where n is the number of segments we are given. It determines only whether or not any intersection exists; it does not print all the intersections.

1 min read

Thus, our understanding of the precise relationship between P and NP is woefully incomplete. Nevertheless, by exploring the theory of NP-completeness, we shall find that our disadvantage in proving problems to be intractable is, from a practical point of view, not nearly so great as we might suppose.

4 min read

Topological sort: This section shows how depth-first search can be used to perform a topological sort of a directed acyclic graph, or a "dag" as it is sometimes called. A topological sort of a dag G = (V, E) is a linear ordering of all its vertices such that if G contains an edge (u, v), then u appears before v in the ordering. (If the graph is not acyclic, then no linear ordering is possible.) A topological sort of a graph can be viewed as an ordering of its vertices along a horizontal line so that all directed edges go from left to right. Topological sorting is thus different from the usual kind of "sorting" studied in Sorting and Order Statistics. Directed acyclic graphs are used in many applications to indicate precedences among events. Figure 22.7 gives an example that arises when Professor Bumstead gets dressed in the morning. The professor must don certain garments before others (e.g., socks before shoes). Other items may be put on in any order (e.g., socks and pants). A directed edge (u, v) in the dag of Figure 22.7(a) indicates that garment u must be donned before garment v. A topological sort of this dag therefore gives an order for getting dressed. Figure 22.7(b) shows the topologically sorted dag as an ordering of vertices along a horizontal line such that all directed edges go from left to right.

6 min read

Strongly connected components: We now consider a classic application of depth-first search: decomposing a directed graph into its strongly connected components. This section shows how to do this decomposition using two depth-first searches. Many algorithms that work with directed graphs begin with such a decomposition. After decomposition, the algorithm is run separately on each strongly connected component. The solutions are then combined according to the structure of connections between components. A strongly connected component of a directed graph G = (V, E) is a maximal set of vertices C ⊆ V such that for every pair of vertices u and v in C, we have both and ; that is, vertices u and v are reachable from each other. Figure 22.9 shows an example.

4 min read

Before proving the various properties of breadth-first search, we take on the somewhat easier job of analyzing its running time on an input graph G = (V, E). We use aggregate analysis, as we saw in Aggregate analysis. After initialization, no vertex is ever whitened, and thus the test in line 13 ensures that each vertex is enqueued at most once, and hence dequeued at most once. The operations of enqueuing and dequeuing take O(1) time, so the total time devoted to queue operations is O(V). Because the adjacency list of each vertex is scanned only when the vertex is dequeued, each adjacency list is scanned at most once. Since the sum of the lengths of all the adjacency lists is Θ(E), the total time spent in scanning adjacency lists is O(E). The overhead for initialization is O(V), and thus the total running time of BFS is O(V E). Thus, breadth-first search runs in time linear in the size of the adjacency-list representation of G. At the beginning of this section, we claimed that breadth-first search finds the distance to each reachable vertex in a graph G = (V, E) from a given source vertex s ∈ V. Define the shortest-path distance δ(s, v) from s to v as the minimum number of edges in any path from vertex s to vertex v; if there is no path from s to v, then δ(s, v) = ∞. A path of length δ(s, v) from s to v is said to be a shortest path from s to v. Before showing that breadth-first search actually computes shortest-path distances, we investigate an important property of shortest-path distances. The procedure BFS builds a breadth-first tree as it searches the graph, as illustrated in Figure 22.3. The tree is represented by the π field in each vertex. More formally, for a graph G = (V, E) with source s, we define the predecessor subgraph of G as G_π = (V_π, E_π), where

3 min read

Overview: In the design of electronic circuitry, it is often necessary to make the pins of several components electrically equivalent by wiring them together. To interconnect a set of n pins, we can use an arrangement of n - 1 wires, each connecting two pins. Of all such arrangements, the one that uses the least amount of wire is usually the most desirable. We can model this wiring problem with a connected, undirected graph G = (V, E), where V is the set of pins, E is the set of possible interconnections between pairs of pins, and for each edge (u, v) ∈ E, we have a weight w(u, v) specifying the cost (amount of wire needed) to connect u and v. We then wish to find an acyclic subset T ⊆E that connects all of the vertices and whose total weight

6 min read

NP-completeness proofs: The NP-completeness of the circuit-satisfiability problem relies on a direct proof that L ≤_P CIRCUIT-SAT for every language L ∈ NP. In this section, we shall show how to prove that languages are NP-complete without directly reducing every language in NP to the given language. We shall illustrate this methodology by proving that various formula-satisfiability problems are NP-complete. NP-complete problems provides many more examples of the methodology. In other words, by reducing a known NP-complete language L′ to L, we implicitly reduce every language in NP to L. Thus, Prove L ∈ NP. Select a known NP-complete language L′.

4 min read

Reductions: The above notion of showing that one problem is no harder or no easier than another applies even when both problems are decision problems. We take advantage of this idea in almost every NP-completeness proof, as follows. Let us consider a decision problem, say A, which we would like to solve in polynomial time. We call the input to a particular problem an instance of that problem; for example, in PATH, an instance would be a particular graph G, particular vertices u and v of G, and a particular integer k. Now suppose that there is a different decision problem, say B, that we already know how to solve in polynomial time. Finally, suppose that we have a procedure that transforms any instance α of A into some instance β of B with the following characteristics: The transformation takes polynomial time. The answers are the same. That is, the answer for α is "yes" if and only if the answer for β is also "yes."

6 min read

Representations of graphs: There are two standard ways to represent a graph G = (V, E): as a collection of adjacency lists or as an adjacency matrix. Either way is applicable to both directed and undirected graphs. The adjacency-list representation is usually preferred, because it provides a compact way to represent sparse graphs-those for which |E| is much less than |V|². Most of the graph algorithms presented in this book assume that an input graph is represented in adjacency-list form. An adjacency-matrix representation may be preferred, however, when the graph is dense-|E| is close to |V|²-or when we need to be able to tell quickly if there is an edge connecting two given vertices. For example, two of the all-pairs shortest-paths algorithms presented in All-Pairs Shortest Paths assume that their input graphs are represented by adjacency matrices. The adjacency-list representation of a graph G = (V, E) consists of an array Adj of |V| lists, one for each vertex in V . For each u ∈ V, the adjacency list Adj[u] contains all the vertices v such that there is an edge (u, v) ∈ E. That is, Adj[u] consists of all the vertices adjacent to u in G. (Alternatively, it may contain pointers to these vertices.) The vertices in each adjacency list are typically stored in an arbitrary order. Figure 22.1(b) is an adjacency-list representation of the undirected graph in Figure 22.1(a). Similarly, Figure 22.2(b) is an adjacency-list representation of the directed graph in Figure 22.2(a).

5 min read

The Knuth-Morris-Pratt matching algorithm is given in pseudocode below as the procedure KMP-MATCHER. It is mostly modeled after FINITE-AUTOMATON-MATCHER, as we shall see. KMP-MATCHER calls the auxiliary procedure COMPUTE-PREFIX-FUNCTION to compute π. We begin with an analysis of the running times of these procedures. Proving these procedures correct will be more complicated. The running time of COMPUTE-PREFIX-FUNCTION is Θ(m), using the potential method of amortized analysis. We associate a potential of k with the current state k of the algorithm. This potential has an initial value of 0, by line 3. Line 6 decreases k whenever it is executed, since π[k] < k. Since π[k] ≥ 0 for all k, however, k can never become negative. The only other line that affects k is line 8, which increases k by at most one during each execution of the for loop body. Since k < q upon entering the for loop, and since q is incremented in each iteration of the for loop body, k < q always holds. (This justifies the claim that π[q] < q as well, by line 9.) We can pay for each execution of the while loop body on line 6 with the corresponding decrease in the potential function, since π[k] < k. Line 8 increases the potential function by at most one, so that the amortized cost of the loop body on lines 5-9 is O(1). Since the number of outer-loop iterations is Θ(m), and since the final potential function is at least as great as the initial potential function, the total actual worst-case running time of COMPUTE-PREFIX-FUNCTION is Θ(m).

5 min read

Approximation Algorithms Many problems of practical significance are NP-complete but are too important to abandon merely because obtaining an optimal solution is intractable. If a problem is NP-complete, we are unlikely to find a polynomial-time algorithm for solving it exactly, but even so, there may be hope. There are at least three approaches to getting around NP-completeness. First, if the actual inputs are small, an algorithm with exponential running time may be perfectly satisfactory. Second, we may be able to isolate important special cases that are solvable in polynomial time. Third, it may still be possible to find near-optimal solutions in polynomial time (either in the worst case or on average). In practice, near-optimality is often good enough. An algorithm that returns near-optimal solutions is called an approximation algorithm. This chapter presents polynomial-time approximation algorithms for several NP-complete problems. Suppose that we are working on an optimization problem in which each potential solution has a positive cost, and we wish to find a near-optimal solution. Depending on the problem, an optimal solution may be defined as one with maximum possible cost or one with minimum possible cost; that is, the problem may be either a maximization or a minimization problem.

8 min read

Polynomial time: NP-completeness problems are generally regarded as tractable, but for philosophical, not mathematical, reasons. It can offer three supporting arguments. Abstract problems: To understand the class of polynomial-time solvable problems, we must first have a formal notion of what a "problem" is. We define an abstract problem Q to be a binary relation on a set I of problem instances and a set S of problem solutions. For example, an instance for SHORTEST-PATH is a triple consisting of a graph and two vertices. A solution is a sequence of vertices in the graph, with perhaps the empty sequence denoting that no path exists. The problem SHORTEST-PATH itself is the relation that associates each instance of a graph and two vertices with a shortest path in the graph that connects the two vertices. Since shortest paths are not necessarily unique, a given problem instance may have more than one solution. This formulation of an abstract problem is more general than is required for our purposes. As we saw above, the theory of NP-completeness restricts attention to decision problems: those having a yes/no solution. In this case, we can view an abstract decision problem as a function that maps the instance set I to the solution set {0, 1}. For example, a decision problem related to SHORTEST-PATH is the problem PATH that we saw earlier. If i = 〈G, u, v, k〉 is an instance of the decision problem PATH, then PATH(i) = 1 (yes) if a shortest path from u to v has at most k edges, and PATH(i) = 0 (no) otherwise. Many abstract problems are not decision problems, but rather optimization problems, in which some value must be minimized or maximized. As we saw above, however, it is usually a simple matter to recast an optimization problem as a decision problem that is no harder.

5 min read

Depth-first search yields valuable information about the structure of a graph. Perhaps the most basic property of depth-first search is that the predecessor subgraph G_π does indeed form a forest of trees, since the structure of the depth-first trees exactly mirrors the structure of recursive calls of DFS-VISIT. That is, u = _π[v] if and only if DFS-VISIT(v) was called during a search of u's adjacency list. Additionally, vertex v is a descendant of vertex u in the depth-first forest if and only if v is discovered during the time in which u is gray. Another important property of depth-first search is that discovery and finishing times have parenthesis structure. If we represent the discovery of vertex u with a left parenthesis "(u" and represent its finishing by a right parenthesis "u)", then the history of discoveries and finishings makes a well-formed expression in the sense that the parentheses are properly nested. For example, the depth-first search of Figure 22.5(a) corresponds to the parenthesization shown in Figure 22.5(b). Another way of stating the condition of parenthesis structure is given in the following theorem.

3 min read

Under the assumption that each comparator takes unit time, we can define the "running time" of a comparison network, that is, the time it takes for all the output wires to receive their values once the input wires receive theirs. Informally, this time is the largest number of comparators that any input element can pass through as it travels from an input wire to an output wire. More formally, we define the depth of a wire as follows. An input wire of a comparison network has depth 0. Now, if a comparator has two input wires with depths d_x and d_y, then its output wires have depth max(d_x, d_y) 1. Because there are no cycles of comparators in a comparison network, the depth of a wire is well defined, and we define the depth of a comparator to be the depth of its output wires. Figure 27.2 shows comparator depths. The depth of a comparison network is the maximum depth of an output wire or, equivalently, the maximum depth of a comparator. The comparison network of Figure 27.2, for example, has depth 3 because comparator E has depth 3. If each comparator takes one time unit to produce its output value, and if network inputs appear at time 0, a comparator at depth d produces its outputs at time d; the depth of the network therefore equals the time for the network to produce values at all of its output wires. A sorting network is a comparison network for which the output sequence is monotonically increasing (that is, b₁ ≤ b₂ ≤ ··· ≤ b_n) for every input sequence. Of course, not every comparison network is a sorting network, but the network of Figure 27.2 is. To see why, observe that after time 1, the minimum of the four input values has been produced by either the top output of comparator A or the top output of comparator B. After time 2, therefore, it must be on the top output of comparator C. A symmetrical argument shows that after time 2, the maximum of the four input values has been produced by the bottom output of comparator D. All that remains is for comparator E to ensure that the middle two values occupy their correct output positions, which happens at time 3. A comparison network is like a procedure in that it specifies how comparisons are to occur, but it is unlike a procedure in that its size-the number of comparators that it contains-depends on the number of inputs and outputs. Therefore, we shall actually be describing "families" of comparison networks. For example, the goal of this chapter is to develop a family SORTER of efficient sorting networks. We specify a given network within a family by the family name and the number of inputs (which equals the number of outputs). For example, the n-input, n-output sorting network in the family SORTER is named SORTER[n].

5 min read

Growing a minimum spanning tree: Assume that we have a connected, undirected graph G = (V, E) with a weight function w : E → R, and we wish to find a minimum spanning tree for G. The two algorithms we consider in this chapter use a greedy approach to the problem, although they differ in how they apply this approach. This greedy strategy is captured by the following "generic" algorithm, which grows the minimum spanning tree one edge at a time. The algorithm manages a set of edges A, maintaining the following loop invariant: Prior to each iteration, A is a subset of some minimum spanning tree.

3 min read

Johnson's algorithm to compute all-pairs shortest paths uses the Bellman-Ford algorithm and Dijkstra's algorithm as subroutines. It assumes that the edges are stored in adjacency lists. The algorithm returns the usual |V| × |V| matrix D = d_ij, where d_ij = δ(i, j), or it reports that the input graph contains a negative-weight cycle. As is typical for an all-pairs shortest-paths algorithm, we assume that the vertices are numbered from 1 to |V|. This code simply performs the actions we specified earlier. Line 1 produces G′. Line 2 runs the Bellman-Ford algorithm on G′ with weight function w and source vertex s. If G′, and hence G, contains a negative-weight cycle, line 3 reports the problem. Lines 4-11 assume that G′ contains no negative-weight cycles. Lines 4-5 set h(v) to the shortest-path weight δ(s, v) computed by the Bellman-Ford algorithm for all v ∈ V′. Lines 6-7 compute the new weights . For each pair of vertices u, v ∈ V , the for loop of lines 8-11 computes the shortest-path weight by calling Dijkstra's algorithm once from each vertex in V. Line 11 stores in matrix entry d_uv the correct shortest-path weight δ(u, v), calculated using equation (25.10). Finally, line 12 returns the completed D matrix. Figure 25.6 shows the execution of Johnson's algorithm. If the min-priority queue in Dijkstra's algorithm is implemented by a Fibonacci heap, the running time of Johnson's algorithm is O(V² lg V V E). The simpler binary min-heap implementation yields a running time of O(V E lg V), which is still asymptotically faster than the Floyd-Warshall algorithm if the graph is sparse.

4 min read

and we wish to solve for the unknown x. The LUP decomposition is (The reader can verify that P A = LU.) Using forward substitution, we solve Ly = Pb for y:

5 min read

Augmenting paths: Given a flow network G = (V, E) and a flow f, an augmenting path p is a simple path from s to t in the residual network G_f. By the definition of the residual network, each edge (u, v) on an augmenting path admits some additional positive flow from u to v without violating the capacity constraint on the edge. The shaded path in Figure 26.3(b) is an augmenting path. Treating the residual network G_f in the figure as a flow network, we can increase the flow through each edge of this path by up to 4 units without violating a capacity constraint, since the smallest residual capacity on this path is c_f(v₂, v₃) = 4. We call the maximum amount by which we can increase the flow on each edge in an augmenting path p the residual capacity of p, given by c_f (p) = min {c_f(u, v) : (u, v) is on p}.

6 min read

5 min read

The Floyd-Warshall algorithm: In this section, we shall use a different dynamic-programming formulation to solve the all-pairs shortest-paths problem on a directed graph G = (V, E). The resulting algorithm, known as the Floyd-Warshall algorithm, runs in Θ(V³) time. As before, negative-weight edges may be present, but we assume that there are no negative-weight cycles. As in Shortest paths and matrix multiplication, we shall follow the dynamic-programming process to develop the algorithm. After studying the resulting algorithm, we shall present a similar method for finding the transitive closure of a directed graph. The structure of a shortest path: In the Floyd-Warshall algorithm, we use a different characterization of the structure of a shortest path than we used in the matrix-multiplication-based all-pairs algorithms. The algorithm considers the "intermediate" vertices of a shortest path, where an intermediate vertex of a simple path p = 〈v₁, v₂,..., v_l〉 is any vertex of p other than v₁ or v_l, that is, any vertex in the set {v₂, v₃,..., v_l-1}. The Floyd-Warshall algorithm is based on the following observation. Under our assumption that the vertices of G are V = {1, 2,..., n}, let us consider a subset {1, 2,..., k} of vertices for some k. For any pair of vertices i, j ∈ V, consider all paths from i to j whose intermediate vertices are all drawn from {1, 2,..., k}, and let p be a minimum-weight path from among them. (Path p is simple.) The Floyd-Warshall algorithm exploits a relationship between path p and shortest paths from i to j with all intermediate vertices in the set {1, 2,..., k - 1}. The relationship depends on whether or not k is an intermediate vertex of path p.

5 min read

The zero-one principle The zero-one principle says that if a sorting network works correctly when each input is drawn from the set {0, 1}, then it works correctly on arbitrary input numbers. (The numbers can be integers, reals, or, in general, any set of values from any linearly ordered set.) As we construct sorting networks and other comparison networks, the zero-one principle will allow us to focus on their operation for input sequences consisting solely of 0's and 1's. Once we have constructed a sorting network and proved that it can sort all zero-one sequences, we shall appeal to the zero-one principle to show that it properly sorts sequences of arbitrary values. The proof of the zero-one principle relies on the notion of a monotonically increasing function.

6 min read

Figure 24.7: The proof of Theorem 24.6. Set S is nonempty just before vertex u is added to it. A shortest path p from source s to vertex u can be decomposed into s , where y is the first vertex on the path that is not in S and x ∈ S immediately precedes y. Vertices x and y are distinct, but we may have s = x or y = u. Path p₂ may or may not reenter set S. We claim that d[y] = δ(s, y) when u is added to S. To prove this claim, observe that x ∈ S. Then, because u is chosen as the first vertex for which d[u] ≠ δ(s, u) when it is added to S, we had d[x] = δ(s, x) when x was added to S. Edge (x, y) was relaxed at that time, so the claim follows from the convergence property. We can now obtain a contradiction to prove that d[u] = δ(s, u). Because y occurs before u on a shortest path from s to u and all edge weights are nonnegative (notably those on path p₂), we have δ(s, y) ≤ δ(s, u), and thus

1 min read

whose pseudoinverse is Multiplying y by A , we obtain the coefficient vector which corresponds to the quadratic polynomial

3 min read

6 min read

NP-complete problems: NP-complete problems arise in diverse domains: boolean logic, graphs, arithmetic, network design, sets and partitions, storage and retrieval, sequencing and scheduling, mathematical programming, algebra and number theory, games and puzzles, automata and language theory, program optimization, biology, chemistry, physics, and more. In this section, we shall use the reduction methodology to provide NP-completeness proofs for a variety of problems drawn from graph theory and set partitioning. Figure 34.13 outlines the structure of the NP-completeness proofs in this section and NP-completeness proofs. Each language in the figure is proved NP-complete by reduction from the language that points to it. At the root is CIRCUIT-SAT, The clique problem: A clique in an undirected graph G = (V, E) is a subset V' ⊆ V of vertices, each pair of which is connected by an edge in E. In other words, a clique is a complete subgraph of G. The size of a clique is the number of vertices it contains. The clique problem is the optimization problem of finding a clique of maximum size in a graph. As a decision problem, we ask simply whether a clique of a given size k exists in the graph. The formal definition is

7 min read

Overview: A motorist wishes to find the shortest possible route from Chicago to Boston. Given a road map of the United States on which the distance between each pair of adjacent intersections is marked, how can we determine this shortest route? One possible way is to enumerate all the routes from Chicago to Boston, add up the distances on each route, and select the shortest. It is easy to see, however, that even if we disallow routes that contain cycles, there are millions of possibilities, most of which are simply not worth considering. For example, a route from Chicago to Houston to Boston is obviously a poor choice, because Houston is about a thousand miles out of the way. In this chapter and in All-Pairs Shortest Paths, we show how to solve such problems efficiently. In a shortest-paths problem, we are given a weighted, directed graph G = (V, E), with weight function w : E → R mapping edges to real-valued-weights. The weight of path p = 〈v₀, v₁, ..., v_k〉 is the sum of the weights of its constituent edges:

6 min read

How does BIT-REVERSE-COPY get the elements of the input vector a into the desired order in the array A? The order in which the leaves appear in Figure 30.4 is a bit-reversal permutation. That is, if we let rev(k) be the lg n-bit integer formed by reversing the bits of the binary representation of k, then we want to place vector element a_k in array position A[rev(k)]. In Figure 30.4, for example, the leaves appear in the order 0, 4, 2, 6, 1, 5, 3, 7; this sequence in binary is 000, 100, 010, 110, 001, 101, 011, 111, and when we reverse the bits of each value we get the sequence 000, 001, 010, 011, 100, 101, 110, 111. To see that we want a bit-reversal permutation in general, we note that at the top level of the tree, indices whose low-order bit is 0 are placed in the left subtree and indices whose low-order bit is 1 are placed in the right subtree. Stripping off the low-order bit at each level, we continue this process down the tree, until we get the order given by the bit-reversal permutation at the leaves. Since the function rev(k) is easily computed, the BIT-REVERSE-COPY procedure can be written as follows. The iterative FFT implementation runs in time Θ(n lg n). The call to BIT-REVERSE-COPY(a, A) certainly runs in O(n lg n) time, since we iterate n times and can reverse an integer between 0 and n - 1, with lg n bits, in O(lg n) time. To complete the proof that ITERATIVE-FFT runs in time Θ(n lg n), we show that L(n), the number of times the body of the innermost loop (lines 8 -13) is executed, is Θ(n lg n). The for loop of lines 6 -13 iterates n/m = n/2^s times for each value of s, and the innermost loop of lines 8 -13 iterates m/2 = 2^s-1 times. Thus,

5 min read

Informally, an algorithm is any well-defined computational procedure that takes some value, or set of values, as input and produces some value, or set of values, as output. An algorithm is thus a sequence of computational steps that transform the input into the output. We can also view an algorithm as a tool for solving a well-specified computational problem. The statement of the problem specifies in general terms the desired input/output relationship. The algorithm describes a specific computational procedure for achieving that input/output relationship. For example, one might need to sort a sequence of numbers into non-decreasing order. This problem arises frequently in practice and provides fertile ground for introducing many standard design techniques and analysis tools. Here is how we formally define the sorting problem:

5 min read

Efficiency of algorithm: Algorithms devised to solve the same problem often differ dramatically in their efficiency. These differences can be much more significant than differences due to hardware and software. The first, known as insertion sort, takes time roughly equal to c₁n² to sort n items, where c₁ is a constant that does not depend on n. That is, it takes time roughly proportional to n². The second, merge sort, takes time roughly equal to c₂n lg n, where lg n stands for log₂ n and c₂ is another constant that also does not depend on n. Insertion sort usually has a smaller constant factor than merge sort, so that c₁ < c₂. We shall see that the constant factors can be far less significant in the running time than the dependence on the input size n. Where merge sort has a factor of lg n in its running time, insertion sort has a factor of n, which is much larger. Although insertion sort is usually faster than merge sort for small input sizes, once the input size n becomes large enough, merge sort's advantage of lg n vs. n will more than compensate for the difference in constant factors. No matter how much smaller c₁ is than c₂, there will always be a crossover point beyond which merge sort is faster.

3 min read

This running time can be expressed as an b for constants a and b that depend on the statement costs c_i ; it is thus a linear function of n. If the array is in reverse sorted order-that is, in decreasing order-the worst case results. We must compare each element A[j] with each element in the entire sorted subarray A[1 ‥j - 1], and so t_j = j for j = 2, 3, . . . , n. Noting that

2 min read

Let us see how these properties hold for insertion sort.

5 min read

Line 3 chooses a random number between 1 and n³. We use a range of 1 to n³ to make it likely that all the priorities in P are unique. Let us assume that all the priorities are unique. The time-consuming step in this procedure is the sorting in line 4. After sorting, if P[i] is the jth smallest priority, then A[i] will be in position j of the output. In this manner we obtain a permutation. It remains to prove that the procedure produces a uniform random permutation, that is, that every permutation of the numbers 1 through n is equally likely to be produced. Lemma 5.4: Procedure PERMUTE-BY-SORTING produces a uniform random permutation of the input, assuming that all priorities are distinct

6 min read

The divide-and-conquer approach: Many useful algorithms are recursive in structure: to solve a given problem, they call themselves recursively one or more times to deal with closely related subproblems. These algorithms typically follow a divide-and-conquer approach: they break the problem into several subproblems that are similar to the original problem but smaller in size, solve the subproblems recursively, and then combine these solutions to create a solution to the original problem. The divide-and-conquer paradigm involves three steps at each level of the recursion: The merge sort algorithm closely follows the divide-and-conquer paradigm. Intuitively, it operates as follows.

2 min read

Randomized algorithms In order to use probabilistic analysis, we need to know something about the distribution on the inputs. In many cases, we know very little about the input distribution. Even if we do know something about the distribution, we may not be able to model this knowledge computationally. Yet we often can use probability and randomness as a tool for algorithm design and analysis, by making the behavior of part of the algorithm random. In the hiring problem, it may seem as if the candidates are being presented to us in a random order, but we have no way of knowing whether or not they really are. Thus, in order to develop a randomized algorithm for the hiring problem, we must have greater control over the order in which we interview the candidates. We will, therefore, change the model slightly. We will say that the employment agency has n candidates, and they send us a list of the candidates in advance. On each day, we choose, randomly, which candidate to interview. Although we know nothing about the candidates (besides their names), we have made a significant change. Instead of relying on a guess that the candidates will come to us in a random order, we have instead gained control of the process and enforced a random order.

6 min read

As an example, consider any quadratic function f(n) = an2 bn c, where a, b, and c are constants and a > 0. Throwing away the lower-order terms and ignoring the constant yields f(n) = Θ(n2). Formally, to show the same thing, we take the constants c1 = a/4, c2 = 7a/4, and. The reader may verify that 0 ≤ c1n2 ≤ an2 bn c ≤ c2n2 for all n ≥ n0. In general, for any polynomial, where the ai are constants and ad > 0, we have p(n) = Θ(nd) (see Problem 3-1). Since any constant is a degree-0 polynomial, we can express any constant function as Θ(n0), or Θ(1). This latter notation is a minor abuse, however, because it is not clear what variable is tending to infinity. We shall often use the notation Θ(1) to mean either a constant or a constant function with respect to some variable. O-notation: The Θ-notation asymptotically bounds a function from above and below. When we have only an asymptotic upper bound, we use O-notation. For a given function g(n), we denote by O(g(n)) (pronounced "big-oh of g of n" or sometimes just "oh of g of n") the set of functions

2 min read

and thus we see that at depth ⌊logb n⌋, the problem size is at most a constant. From Figure 4.4, we see that which is much the same as equation (4.6), except that n is an arbitrary integer and not restricted to be an exact power of b.We can now evaluate the summation

1 min read

For the recurrence T(n) = 3T(n/4) n lg n, we have a = 3, b = 4, f (n) = n lg n, and . Since

3 min read

Balls and bins: Consider the process of randomly tossing identical balls into b bins, numbered 1, 2,..., b. The tosses are independent, and on each toss the ball is equally likely to end up in any bin. The probability that a tossed ball lands in any given bin is 1/b. Thus, the ball-tossing process is a sequence of Bernoulli trials with a probability 1/b of success, where success means that the ball falls in the given bin. This model is particularly useful for analyzing hashing and we can answer a variety of interesting questions about the ball-tossing process. How many balls fall in a given bin?The number of balls that fall in a given bin follows the binomial distribution b(k; n, 1/b). If n balls are tossed, so the expected number of balls that fall in the given bin is n/b. How many balls must one toss, on the average, until a given bin contains a ball?The number of tosses until the given bin receives a ball follows the geometric distribution with probability 1/b and, the expected number of tosses until success is 1/(1/b) = b.

3 min read

Overview of Recurrences: When an algorithm contains a recursive call to itself, its running time can often be described by a recurrence. A recurrence is an equation or inequality that describes a function in terms of its value on smaller inputs. For example, we know that the worst-case running time T (n) of the MERGE-SORT procedure could be described by the recurrence whose solution was claimed to be T (n) = Θ(n lg n).

2 min read

Proof of the master theorem: This section contains a proof of the master theorem (Theorem 4.1). The proof need not be understood in order to apply the theorem. The proof is in two parts. The first part analyzes the "master" recurrence (4.5), under the simplifying assumption that T(n) is defined only on exact powers of b > 1, that is, for n = 1, b, b2, ..‥This part gives all the intuition needed to understand why the master theorem is true. The second part shows how the analysis can be extended to all positive integers n and is merely mathematical technique applied to the problem of handling floors and ceilings. In this section, we shall sometimes abuse our asymptotic notation slightly by using it to describe the behavior of functions that are defined only over exact powers of b. Recall that the definitions of asymptotic notations require that bounds be proved for all sufficiently large numbers, not just those that are powers of b. Since we could make new asymptotic notations that apply to the set {bi : i = 0, 1,...}, instead of the nonnegative integers, this abuse is minor.

4 min read

Indicator random variables: In order to analyze many algorithms, including the hiring problem, we will use indicator random variables. Indicator random variables provide a convenient method for converting between probabilities and expectations. Suppose we are given a sample space S and an event A. Then the indicator random variable I {A} associated with event A is defined as As a simple example, let us determine the expected number of heads that we obtain when flipping a fair coin. Our sample space is S = {H, T}, and we define a random variable Y which takes on the values H and T, each with probability 1/2. We can then define an indicator random variable X_H, associated with the coin coming up heads, which we can express as the event Y = H. This variable counts the number of heads obtained in this flip, and it is 1 if the coin comes up heads and 0 otherwise. We write

2 min read

Substituting this expression for the summation in equation (4.9) yields and case 2 is proved.

6 min read

Analyzing divide-and-conquer algorithms: When an algorithm contains a recursive call to itself, its running time can often be described by a recurrence equation or recurrence, which describes the overall running time on a problem of size n in terms of the running time on smaller inputs. We can then use mathematical tools to solve the recurrence and provide bounds on the performance of the algorithm. A recurrence for the running time of a divide-and-conquer algorithm is based on the three steps of the basic paradigm. As before, we let T (n) be the running time on a problem of size n. If the problem size is small enough, say n ≤ c for some constant c, the straightforward solution takes constant time, which we write as Θ(1). Suppose that our division of the problem yields a subproblems, each of which is 1/b the size of the original. (For merge sort, both a and b are 2, but we shall see many divide-and-conquer algorithms in which a ≠ b.) If we take D(n) time to divide the problem into subproblems and C(n) time to combine the solutions to the subproblems into the solution to the original problem, we get the recurrence

2 min read

Taking expectations and using linearity of expectation, we have By plugging in various values for k, we can calculate the expected number of streaks of length k. If this number is large (much greater than 1), then many streaks of length k are expected to occur and the probability that one occurs is high. If this number is small (much less than 1), then very few streaks of length k are expected to occur and the probability that one occurs is low. If k = c lg n, for some positive constant c, we obtain

3 min read

Next we determine the cost at each level of the tree. Each level has three times more nodes than the level above, and so the number of nodes at depth i is 3ⁱ. Because subproblem sizes reduce by a factor of 4 for each level we go down from the root, each node at depth i, for i = 0, 1, 2,..., log₄ n - 1, has a cost of c(n/4ⁱ)². Multiplying, we see that the total cost over all nodes at depth i, for i = 0, 1, 2,..., log₄ n - 1, is 3ⁱ c(n/4ⁱ)² = (3/16)ⁱ cn². The last level, at depth log₄ n, has nodes, each contributing cost T (1), for a total cost of , which is . Now we add up the costs over all levels to determine the cost for the entire tree:

1 min read

We approximate by integrals to bound this summation from above and below. By the inequalities (A.12), we have Evaluating these definite integrals gives us the bounds

3 min read

Thus, n! = 1 · 2 · 3 n. A weak upper bound on the factorial function is n! ≤ nⁿ, since each of the n terms in the factorial product is at most n. Stirling's approximation,

4 min read

Probabilistic analysis and further uses of indicator random variables: This advanced section further illustrates probabilistic analysis by way of four examples. The first determines the probability that in a room of k people, some pair shares the same birthday. The second example examines the random tossing of balls into bins. The third investigates "streaks" of consecutive heads in coin flipping. The final example analyzes a variant of the hiring problem in which you have to make decisions without actually interviewing all the candidates. The birthday paradox: Our first example is the birthday paradox. How many people must there be in a room before there is a 50% chance that two of them were born on the same day of the year? The answer is surprisingly few. The paradox is that it is in fact far fewer than the number of days in a year, or even half the number of days in a year, as we shall see. To answer this question, we index the people in the room with the integers 1, 2, ..., k, where k is the number of people in the room. We ignore the issue of leap years and assume that all years have n = 365 days. For i = 1, 2, ..., k, let b_i be the day of the year on which person i's birthday falls, where 1 ≤ b_i ≤ n. We also assume that birthdays are uniformly distributed across the n days of the year, so that Pr {b_i = r} = 1/n for i = 1, 2, ..., k and r = 1, 2, ..., n.

3 min read

Reflexivity: f(n) =

5 min read

The substitution method for recurrences The substitution method for solving recurrences entails two steps: The name comes from the substitution of the guessed answer for the function when the inductive hypothesis is applied to smaller values. This method is powerful, but it obviously can be applied only in cases when it is easy to guess the form of the answer.

3 min read

We need to show that this loop invariant is true prior to the first iteration, that each iteration of the loop maintains the invariant, and that the invariant provides a useful property to show correctness when the loop terminates. The final two lines of PARTITION move the pivot element into its place in the middle of the array by swapping it with the leftmost element that is greater than x.

4 min read

Heaps: The (binary) heap data structure is an array object that can be viewed as a nearly complete binary tree as shown in Figure 6.1. Each node of the tree corresponds to an element of the array that stores the value in the node. The tree is completely filled on all levels except possibly the lowest, which is filled from the left up to a point. An array A that represents a heap is an object with two attributes: length[A], which is the number of elements in the array, and heap-size[A], the number of elements in the heap stored within array A. That is, although A[1 ‥length[A]] may contain valid numbers, no element past A[heap-size[A]], where heap-size[A] ≤ length[A], is an element of the heap. The root of the tree is A[1], and given the index i of a node, the indices of its parent PARENT(i), left child LEFT(i), and right child RIGHT(i) can be computed simply: PARENT(i) return ⌊i/2⌋

1 min read

We can compute a simple upper bound on the running time of BUILD-MAX-HEAP as follows. Each call to MAX-HEAPIFY costs O(lg n) time, and there are O(n) such calls. Thus, the running time is O(n lg n). This upper bound, though correct, is not asymptotically tight. We can derive a tighter bound by observing that the time for MAX-HEAPIFY to run at a node varies with the height of the node in the tree, and the heights of most nodes are small. Our tighter analysis relies on the properties that an n-element heap has height ⌊lg n⌋ and at most ⌈n/2^{h 1}⌉nodes of any height h. The time required by MAX-HEAPIFY when called on a node of height h is O(h), so we can express the total cost of BUILD-MAX-HEAP as

6 min read

Lower bounds for sorting: In a comparison sort, we use only comparisons between elements to gain order information about an input sequence 〈a₁, a₂, . . ., a_n〉. That is, given two elements a_i and a_j, we perform one of the tests a_i < a_j, a_i ≤ a_j, a_i = a_j, a_i ≥ a_j, or a_i > a_j to determine their relative order. We may not inspect the values of the elements or gain order information about them in any other way. In this section, we assume without loss of generality that all of the input elements are distinct. Given this assumption, comparisons of the form a_i = a_j are useless, so we can assume that no comparisons of this form are made. We also note that the comparisons a_i ≤ a_j, a_i ≥ a_j, a_i > a_j, and a_i < a_j are all equivalent in that they yield identical information about the relative order of a_i and a_j. We therefore assume that all comparisons have the form a_i ≤ a_j. The decision-tree model: Comparison sorts can be viewed abstractly in terms of decision trees. A decision tree is a full binary tree that represents the comparisons between elements that are performed by a particular sorting algorithm operating on an input of a given size. Control, data movement, and all other aspects of the algorithm are ignored. Figure 8.1 shows the decision tree corresponding to the insertion sort algorithm from Section 2.1 operating on an input sequence of three elements.

2 min read

The heapsort algorithm The heapsort algorithm starts by using BUILD-MAX-HEAP to build a max-heap on the input array A[1 ‥n], where n = length[A]. Since the maximum element of the array is stored at the root A[1], it can be put into its correct final position by exchanging it with A[n]. If we now "discard" node n from the heap (by decrementing heap-size[A]), we observe that A[1 ‥(n - 1)] can easily be made into a max-heap. The children of the root remain max-heaps, but the new root element may violate the max-heap property. All that is needed to restore the max-heap property, however, is one call to MAX-HEAPIFY(A, 1), which leaves a max-heap in A[1 ‥(n - 1)]. The heapsort algorithm then repeats this process for the max-heap of size n - 1 down to a heap of size 2. HEAPSORT(A)

3 min read

Maintaining the heap property MAX-HEAPIFY is an important subroutine for manipulating max-heaps. Its inputs are an array A and an index i into the array. When MAX-HEAPIFY is called, it is assumed that the binary trees rooted at LEFT(i) and RIGHT(i) are max-heaps, but that A[i] may be smaller than its children, thus violating the max-heap property. The function of MAX-HEAPIFY is to let the value at A[i] "float down" in the max-heap so that the subtree rooted at index i becomes a max-heap. MAX-HEAPIFY(A, i)

8 min read

Radix sort is the algorithm used by the card-sorting machines you now find only in computer museums. The cards are organized into 80 columns, and in each column a hole can be punched in one of 12 places. The sorter can be mechanically "programmed" to examine a given column of each card in a deck and distribute the card into one of 12 bins depending on which place has been punched. An operator can then gather the cards bin by bin, so that cards with the first place punched are on top of cards with the second place punched, and so on. For decimal digits, only 10 places are used in each column. (The other two places are used for encoding nonnumeric characters.) A d-digit number would then occupy a field of d columns. Since the card sorter can look at only one column at a time, the problem of sorting n cards on a d-digit number requires a sorting algorithm. Intuitively, one might want to sort numbers on their most significant digit, sort each of the resulting bins recursively, and then combine the decks in order. Unfortunately, since the cards in 9 of the 10 bins must be put aside to sort each of the bins, this procedure generates many intermediate piles of cards that must be kept track of.

4 min read

Minimum and maximum: How many comparisons are necessary to determine the minimum of a set of n elements? We can easily obtain an upper bound of n - 1 comparisons: examine each element of the set in turn and keep track of the smallest element seen so far. In the following procedure, we assume that the set resides in array A, where length[A] = n. Finding the maximum can, of course, be accomplished with n - 1 comparisons as well. Is this the best we can do? Yes, since we can obtain a lower bound of n - 1 comparisons for the problem of determining the minimum. Think of any algorithm that determines the minimum as a tournament among the elements. Each comparison is a match in the tournament in which the smaller of the two elements wins. The key observation is that every element except the winner must lose at least one match. Hence, n - 1 comparisons are necessary to determine the minimum, and the algorithm MINIMUM is optimal with respect to the number of comparisons performed.

2 min read

HEAP-INCREASE-KEY(A, i, key) 1 if key < A[i] 2 then error "new key is smaller than current key"

3 min read

where we are considering whether the comparison takes place at any time during the execution of the algorithm, not just during one iteration or one call of PARTITION. Since each pair is compared at most once, we can easily characterize the total number of comparisons performed by the algorithm: Taking expectations of both sides, and then using linearity of expectation and Lemma 5.1, we obtain

2 min read

A randomized version of quicksort In exploring the average-case behavior of quicksort, we have made an assumption that all permutations of the input numbers are equally likely. In an engineering situation, however, we cannot always expect it to hold. As we can sometimes add randomization to an algorithm in order to obtain good average-case performance over all inputs. Many people regard the resulting randomized version of quicksort as the sorting algorithm of choice for large enough inputs. We randomized our algorithm by explicitly permuting the input. We could do so for quicksort also, but a different randomization technique, called random sampling, yields a simpler analysis. Instead of always using A[r] as the pivot, we will use a randomly chosen element from the subarray A[p ‥r]. We do so by exchanging element A[r] with an element chosen at random from A[p ‥r]. This modification, in which we randomly sample the range p,...,r, ensures that the pivot element x = A[r] is equally likely to be any of the r - p 1 elements in the subarray. Because the pivot element is randomly chosen, we expect the split of the input array to be reasonably well balanced on average.

2 min read

In order to apply equation, we rely on X_k and T(max(k - 1, n - k)) being independent random variables. Exercise 9.2-2 asks you to justify this assertion. Let us consider the expression max(k - 1, n - k). We have

3 min read

Figure 7.4: A recursion tree for QUICKSORT in which PARTITION always produces a 9-to-1 split, yielding a running time of O(n lg n). Nodes show subproblem sizes, with per-level costs on the right. The per-level costs include the constant c implicit in the Θ(n) term. Intuition for the average case To develop a clear notion of the average case for quicksort, we must make an assumption about how frequently we expect to encounter the various inputs. The behavior of quicksort is determined by the relative ordering of the values in the array elements given as the input, and not by the particular values in the array.

6 min read

Counting sort assumes that each of the n input elements is an integer in the range 0 to k, for some integer k. When k = O(n), the sort runs in Θ(n) time. The basic idea of counting sort is to determine, for each input element x, the number of elements less than x. This information can be used to place element x directly into its position in the output array. For example, if there are 17 elements less than x, then x belongs in output position 18. This scheme must be modified slightly to handle the situation in which several elements have the same value, since we don't want to put them all in the same position. In the code for counting sort, we assume that the input is an array A[1 ‥ n], and thus length[A] = n. We require two other arrays: the array B[1 ‥n] holds the sorted output, and the array C[0 ‥ k] provides temporary working storage.

4 min read

Bucket sort runs in linear time when the input is drawn from a uniform distribution. Like counting sort, bucket sort is fast because it assumes something about the input. Whereas counting sort assumes that the input consists of integers in a small range, bucket sort assumes that the input is generated by a random process that distributes elements uniformly over the interval [0, 1). The idea of bucket sort is to divide the interval [0, 1) into n equal-sized subintervals, or buckets, and then distribute the n input numbers into the buckets. Since the inputs are uniformly distributed over [0, 1), we don't expect many numbers to fall into each bucket. To produce the output, we simply sort the numbers in each bucket and then go through the buckets in order, listing the elements in each. Our code for bucket sort assumes that the input is an n-element array A and that each element A[i] in the array satisfies 0 ≤ A[i] < 1. The code requires an auxiliary array B[0 ‥ n - 1] of linked lists (buckets) and assumes that there is a mechanism for maintaining such lists. (Section 10.2 describes how to implement basic operations on linked lists.)

6 min read

Selection in worst-case linear time: We now examine a selection algorithm whose running time is O(n) in the worst case. Like RANDOMIZED-SELECT, the algorithm SELECT finds the desired element by recursively partitioning the input array. The idea behind the algorithm, however, is to guarantee a good split when the array is partitioned. SELECT uses the deterministic partitioning algorithm PARTITION from quicksort, modified to take the element to partition around as an input parameter. The SELECT algorithm determines the ith smallest of an input array of n > 1 elements by executing the following steps. (If n = 1, then SELECT merely returns its only input value as the ith smallest.) Divide the n elements of the input array into ⌊n/5⌋ groups of 5 elements each and at most one group made up of the remaining n mod 5 elements.

6 min read

Interval Trees: In this section, we shall augment red-black trees to support operations on dynamic sets of intervals. A closed interval is an ordered pair of real numbers [t₁, t₂], with t₁ ≤ t₂. The interval [t₁, t₂] represents the set {t ∈ R : t₁ ≤ t ≤ t₂}. Open and half-open intervals omit both or one of the endpoints from the set, respectively. In this section, we shall assume that intervals are closed; extending the results to open and half-open intervals is conceptually straightforward. Intervals are convenient for representing events that each occupy a continuous period of time. We might, for example, wish to query a database of time intervals to find out what events occurred during a given interval. The data structure in this section provides an efficient means for maintaining such an interval database. We can represent an interval [t₁, t₂] as an object i, with fields low[i] = t₁ (the low endpoint) and high[i] = t₂(the high endpoint). We say that intervals i and i' overlap if i ∩ i' ≠ ø, that is, if low[i] ≤ high[i'] and low[i'] ≤ high[i]. Any two intervals i and i' satisfy the interval trichotomy; that is, exactly one of the following three properties holds:

1 min read

In doing so, we will use the identity (Exercise 12.4-1 asks you to prove this identity.) For the base case, we verify that the bound

6 min read

Insertion and deletion: The operations of insertion and deletion cause the dynamic set represented by a binary search tree to change. The data structure must be modified to reflect this change, but in such a way that the binary-search-tree property continues to hold. As we shall see, modifying the tree to insert a new element is relatively straight-forward, but handling deletion is somewhat more intricate. To insert a new value v into a binary search tree T , we use the procedure TREE-INSERT. The procedure is passed a node z for which key[z] = v, left[z] = NIL, and right[z] = NIL. It modifies T and some of the fields of z in such a way that z is inserted into an appropriate position in the tree. Figure 12.3 shows how TREE-INSERT works. Just like the procedures TREE-SEARCH and ITERATIVE-TREE-SEARCH, TREE-INSERT begins at the root of the tree and traces a path downward. The pointer x traces the path, and the pointer y is maintained as the parent of x. After initialization, the while loop in lines 3-7 causes these two pointers to move down the tree, going left or right depending on the comparison of key[z] with key[x], until x is set to NIL. This NIL occupies the position where we wish to place the input item z. Lines 8-13 set the pointers that cause z to be inserted.

4 min read

Representing rooted trees: The methods for representing lists given in the last sessions extend to any homogeneous data structure. In this section, we look specifically at the problem of representing rooted trees by linked data structures. We first look at binary trees, and then we present a method for rooted trees in which nodes can have an arbitrary number of children. We represent each node of a tree by an object. As with linked lists, we assume that each node contains a key field. The remaining fields of interest are pointers to other nodes, and they vary according to the type of tree. As shown in Figure 10.9, we use the fields p, left, and right to store pointers to the parent, left child, and right child of each node in a binary tree T . If p[x] = NIL, then x is the root. If node x has no left child, then left[x] = NIL, and similarly for the right child. The root of the entire tree T is pointed to by the attribute root[T]. If root[T] = NIL, then the tree is empty.

6 min read

Querying a binary search tree: A common operation performed on a binary search tree is searching for a key stored in the tree. Besides the SEARCH operation, binary search trees can support such queries as MINIMUM, MAXIMUM, SUCCESSOR, and PREDECESSOR. In this section, we shall examine these operations and show that each can be supported in time O(h) on a binary search tree of height h. We use the following procedure to search for a node with a given key in a binary search tree. Given a pointer to the root of the tree and a key k, TREE-SEARCH returns a pointer to a node with key k if one exists; otherwise, it returns NIL. The procedure begins its search at the root and traces a path downward in the tree, as shown in Figure 12.2. For each node x it encounters, it compares the key k with key[x]. If the two keys are equal, the search terminates. If k is smaller than key[x], the search continues in the left subtree of x, since the binary-search-tree property implies that k could not be stored in the right subtree. Symmetrically, if k is larger than key[x], the search continues in the right subtree. The nodes encountered during the recursion form a path downward from the root of the tree, and thus the running time of TREE-SEARCH is O(h), where h is the height of the tree.

4 min read

Introduction to binary search tree: A binary search tree is organized, as the name suggests, in a binary tree, as shown in Figure 12.1. Such a tree can be represented by a linked data structure in which each node is an object. In addition to a key field and satellite data, each node contains fields left, right, and p that point to the nodes corresponding to its left child, its right child, and its parent, respectively. If a child or the parent is missing, the appropriate field contains the value NIL. The root node is the only node in the tree whose parent field is NIL. The keys in a binary search tree are always stored in such a way as to satisfy the binary-search-tree property: Let x be a node in a binary search tree. If y is a node in the left subtree of x, then key[y] ≤ key[x]. If y is a node in the right subtree of x, then key[x] ≤ key[y].

2 min read

The free list is a stack: the next object allocated is the last one freed. We can use a list implementation of the stack operations PUSH and POP to implement the procedures for allocating and freeing objects, respectively. We assume that the global variable free used in the following procedures points to the first element of the free list. The free list initially contains all n unallocated objects. When the free list has been exhausted, the ALLOCATE-OBJECT procedure signals an error. It is common to use a single free list to service several linked lists. Figure 10.8 shows two linked lists and a free list intertwined through key, next, and prev arrays.

6 min read

Deletion: Like the other basic operations on an n-node red-black tree, deletion of a node takes time O(lg n). Deleting a node from a red-black tree is only slightly more complicated than inserting a node. The procedure RB-DELETE is a minor modification of the TREE-DELETE procedure. After splicing out a node, it calls an auxiliary procedure RB-DELETE-FIXUP that changes colors and performs rotations to restore the red-black properties. There are three differences between the procedures TREE-DELETE and RB-DELETE. First, all references to NIL in TREE-DELETE are replaced by references to the sentinel nil[T ] in RB-DELETE. Second, the test for whether x is NIL in line 7 of TREE-DELETE is removed, and the assignment p[x] ← p[y] is performed unconditionally in line 7 of RB-DELETE. Thus, if x is the sentinel nil[T], its parent pointer points to the parent of the spliced-out node y. Third, a call to RB-DELETE-FIXUP is made in lines 16-17 if y is black. If y is red, the red-black properties still hold when y is spliced out, for the following reasons:

3 min read

How well does hashing with chaining perform? In particular, how long does it take to search for an element with a given key? For j = 0, 1, ..., m - 1, let us denote the length of the list T[j] by n_j, so that

2 min read

In our procedures ENQUEUE and DEQUEUE, the error checking for underflow and overflow has been omitted. (Exercise 10.1-4 asks you to supply code that checks for these two error conditions.) Figure 10.2 shows the effects of the ENQUEUE and DEQUEUE operations. Each operation takes O(1) time.

5 min read

Although this method works with any value of the constant A, it works better with some values than with others. The optimal choice depends on the characteristics of the data being hashed. Knuth [185] suggests that is likely to work reasonably well.

3 min read

Rotations: The search-tree operations TREE-INSERT and TREE-DELETE, when run on a red-black tree with n keys, take O(lg n) time. Because they modify the tree, the result may violate the red-black properties enumerated in Section 13.1. To restore these properties, we must change the colors of some of the nodes in the tree and also change the pointer structure. We change the pointer structure through rotation, which is a local operation in a search tree that preserves the binary-search-tree property. Figure 13.2 shows the two kinds of rotations: left rotations and right rotations. When we do a left rotation on a node x, we assume that its right child y is not nil[T]; x may be any node in the tree whose right child is not nil[T]. The left rotation "pivots" around the link from x to y. It makes y the new root of the subtree, with x as y's left child and y's left child as x's right child.

6 min read

red-black trees: A red-black tree is a binary search tree with one extra bit of storage per node: its color, which can be either RED or BLACK. By constraining the way nodes can be colored on any path from the root to a leaf, red-black trees ensure that no such path is more than twice as long as any other, so that the tree is approximately balanced. Each node of the tree now contains the fields color, key, left, right, and p. If a child or the parent of a node does not exist, the corresponding pointer field of the node contains the value NIL. We shall regard these NIL's as being pointers to external nodes (leaves) of the binary search tree and the normal, key-bearing nodes as being internal nodes of the tree. A binary search tree is a red-black tree if it satisfies the following red-black properties:

2 min read

Direct addressing is a simple technique that works well when the universe U of keys is reasonably small. Suppose that an application needs a dynamic set in which each element has a key drawn from the universe U = {0, 1, ..., m - 1}, where m is not too large. We shall assume that no two elements have the same key. To represent the dynamic set, we use an array, or direct-address table, denoted by T[0 ‥ m - 1], in which each position, or slot, corresponds to a key in the universe U . Figure 11.1 illustrates the approach; slot k points to an element in the set with key k. If the set contains no element with key k, then T[k] = NIL.

4 min read

Sentinels: The code for LIST-DELETE would be simpler if we could ignore the boundary conditions at the head and tail of the list. A sentinel is a dummy object that allows us to simplify boundary conditions. For example, suppose that we provide with list L an object nil[L] that represents NIL but has all the fields of the other list elements. Wherever we have a reference to NIL in list code, we replace it by a reference to the sentinel nil[L]. As shown in Figure 10.4, this turns a regular doubly linked list into a circular, doubly linked list with a sentinel, in which the sentinel nil[L] is placed between the head and tail; the field next[nil[L]] points to the head of the list, and prev[nil[L]] points to the tail. Similarly, both the next field of the tail and the prev field of the head point to nil[L]. Since next[nil[L]] points to the head, we can eliminate the attribute head[L] altogether, replacing references to it by references to next[nil[L]]. An empty list consists of just the sentinel, since both next[nil[L]] and prev[nil[L]] can be set to nil[L].

3 min read

Perfect hashing: Although hashing is most often used for its excellent expected performance, hashing can be used to obtain excellent worst-case performance when the set of keys is static: once the keys are stored in the table, the set of keys never changes. Some applications naturally have static sets of keys: consider the set of reserved words in a programming language, or the set of file names on a CD-ROM. We call a hashing technique perfect hashing if the worst-case number of memory accesses required to perform a search is O(1). The basic idea to create a perfect hashing scheme is simple. We use a two-level hashing scheme with universal hashing at each level. Figure 11.6 illustrates the approach.

6 min read

Dynamic order statistics: Data structure-such as a doubly linked list, a hash table, or a binary search tree-but many others require a dash of creativity. Only in rare situations will you need to create an entirely new type of data structure, though. More often, it will suffice to augment a textbook data structure by storing additional information in it. Specifically, the ith order statistic of a set of n elements, where i ∈ {1, 2,..., n}, is simply the element in the set with the ith smallest key. We saw that any order statistic could be retrieved in O(n) time from an unordered set. In this section, we shall see how red-black trees can be modified so that any order statistic can be determined in O(lg n) time. We shall also see how the rank of an element-its position in the linear order of the set-can likewise be determined in O(lg n) time. A data structure that can support fast order-statistic operations is shown in Figure 14.1. An order-statistic tree T is simply a red-black tree with additional information stored in each node. Besides the usual red-black tree fields key[x], color[x], p[x], left[x], and right[x] in a node x, we have another field size[x]. This field contains the number of (internal) nodes in the subtree rooted at x (including x itself), that is, the size of the subtree. If we define the sentinel's size to be 0, that is, we set size[nil[T]] to be 0, then we have the identity

6 min read

Insertion: Insertion of a node into an n-node red-black tree can be accomplished in O(lg n) time. We use a slightly modified version of the TREE-INSERT procedure to insert node z into the tree T as if it were an ordinary binary search tree, and then we color z red. To guarantee that the red-black properties are pre- served, we then call an auxiliary procedure RB-INSERT-FIXUP to recolor nodes and perform rotations. The call RB-INSERT(T, z) inserts node z, whose key field is assumed to have already been filled in, into the red-black tree T. There are four differences between the procedures TREE-INSERT and RB-INSERT. First, all instances of NIL in TREE-INSERT are replaced by nil[T]. Second, we set left[z] and right[z] to nil[T] in lines 14-15 of RB-INSERT, in order to maintain the proper tree structure. Third, we color z red in line 16. Fourth, because coloring z red may cause a violation of one of the red-black properties, we call RB-INSERT-FIXUP(T, z) in line 17 of RB-INSERT to restore the red-black properties. To understand how RB-INSERT-FIXUP works, we shall break our examination of the code into three major steps. First, we shall determine what violations of the red-black properties are introduced in RB-INSERT when the node z is inserted and colored red. Second, we shall examine the overall goal of the while loop in lines 1-15. Finally, we shall explore each of the three cases into which the while loop is broken and see how they accomplish the goal. Figure 13.4 shows how RB-INSERT-FIXUP operates on a sample red-black tree.

6 min read

Augmenting a Data Structure: The process of augmenting a basic data structure to support additional functionality occurs quite frequently in algorithm design. It will be used again in the next section to design a data structure that supports operations on intervals. In this section, we shall examine the steps involved in such augmentation. We shall also prove a theorem that allows us to augment red-black trees easily in many cases. Augmenting a data structure can be broken into four steps: choosing an underlying data structure,

5 min read

Quadratic probing uses a hash function of the form where h' is an auxiliary hash function, c₁ and c₂ ≠ 0 are auxiliary constants, and i = 0, 1, ..., m - 1. The initial position probed is T[h'(k)]; later positions probed are offset by amounts that depend in a quadratic manner on the probe number i. This method works much better than linear probing, but to make full use of the hash table, the values of c₁, c₂, and m are constrained. Also, if two keys have the same initial probe position, then their probe sequences are the same, since h(k₁, 0) = h(k₂, 0) implies h(k₁, i) = h(k₂, i). This property leads to a milder form of clustering, called secondary clustering. As in linear probing, the initial probe determines the entire sequence, so only m distinct probe sequences are used. Double hashing is one of the best methods available for open addressing because the permutations produced have many of the characteristics of randomly chosen permutations. Double hashing uses a hash function of the form

7 min read

A task-scheduling problem An interesting problem that can be solved using matroids is the problem of optimally scheduling unit-time tasks on a single processor, where each task has a deadline, along with a penalty that must be paid if the deadline is missed. The problem looks complicated, but it can be solved in a surprisingly simple manner using a greedy algorithm. A unit-time task is a job, such as a program to be run on a computer, that requires exactly one unit of time to complete. Given a finite set S of unit-time tasks, a schedule for S is a permutation of S specifying the order in which these tasks are to be performed. The first task in the schedule begins at time 0 and finishes at time 1, the second task begins at time 1 and finishes at time 2, and so on.

4 min read

Bounding the maximum degree: To prove that the amortized time of FIB-HEAP-EXTRACT-MIN and FIB-HEAP-DELETE is O(lg n), we must show that the upper bound D(n) on the degree of any node of an n-node Fibonacci heap is O(lg n). The cuts that occur in FIB-HEAP-DECREASE-KEY, however, may cause trees within the Fibonacci heap to violate the unordered binomial tree properties. In this section, we shall show that because we cut a node from its parent as soon as it loses two children, D(n) is O(lg n). In particular, we shall show that D(n) ≤ ⌊log_φn⌋, where . The key to the analysis is as follows. For each node x within a Fibonacci heap, define size(x) to be the number of nodes, including x itself, in the subtree rooted at x. (Note that x need not be in the root list-it can be any node at all.) We shall show that size(x) is exponential in degree[x]. Bear in mind that degree[x] is always maintained as an accurate count of the degree of x. Let x be any node in a Fibonacci heap, and suppose that degree[x] = k. Let y₁, y₂, . . . , y_k denote the children of x in the order in which they were linked to x, from the earliest to the latest. Then, degree[y₁] ≥ 0 and degree[y_i] ≥ i - 2 for i = 2, 3, . . . , k.

7 min read

Dynamic tables: In some applications, we do not know in advance how many objects will be stored in a table. We might allocate space for a table, only to find out later that it is not enough. The table must then be reallocated with a larger size, and all objects stored in the original table must be copied over into the new, larger table. Similarly, if many objects have been deleted from the table, it may be worthwhile to reallocate the table with a smaller size. In this section, we study this problem of dynamically expanding and contracting a table. Using amortized analysis, we shall show that the amortized cost of insertion and deletion is only O(1), even though the actual cost of an operation is large when it triggers an expansion or a contraction. Moreover, we shall see how to guarantee that the unused space in a dynamic table never exceeds a constant fraction of the total space. We assume that the dynamic table supports the operations TABLE-INSERT and TABLE-DELETE. TABLE-INSERT inserts into the table an item that occupies a single slot, that is, a space for one item. Likewise, TABLE-DELETE can be thought of as removing an item from the table, thereby freeing a slot. The details of the data-structuring method used to organize the table are unimportant; we might use a stack, a heap, or a hash table. We might also use an array or collection of arrays to implement object storage, as we did in. We shall find it convenient to use a concept introduced in our analysis of hashing. We define the load factor α (T) of a nonempty table T to be the number of items stored in the table divided by the size (number of slots) of the table. We assign an empty table (one with no items) size 0, and we define its load factor to be 1. If the load factor of a dynamic table is bounded below by a constant, the unused space in the table is never more than a constant fraction of the total amount of space.

4 min read

We start in line 1 by saving a pointer z to the minimum node; this pointer is returned at the end. If z = NIL, then Fibonacci heap H is already empty and we are done. Otherwise, as in the BINOMIAL-HEAP-EXTRACT-MIN procedure, we delete node z from H by making all of z's children roots of H in lines 3-5 (putting them into the root list) and removing z from the root list in line 6. If z = right[z] after line 6, then z was the only node on the root list and it had no children, so all that remains is to make the Fibonacci heap empty in line 8 before returning z. Otherwise, we set the pointer min[H] into the root list to point to a node other than z (in this case, right[z]), which is not necessarily going to be the new minimum node when FIB-HEAP-EXTRACT-MIN is done. Figure 20.3(b) shows the Fibonacci heap of Figure 20.3(a) after line 9 has been performed.

6 min read

We use optimal substructure to show that we can construct an optimal solution to a problem from optimal solutions to subproblems. For assembly-line scheduling, we reason as follows. If we look at a fastest way through station S_1,j, it must go through station j - 1 on either line 1 or line 2. Thus, the fastest way through station S_1,j is either the fastest way through station S_1,j-1 and then directly through station S_1,j, or the fastest way through station S_2,j-1, a transfer from line 2 to line 1, and then through station S_1,j.

5 min read

Linked-list representation of disjoint sets: A simple way to implement a disjoint-set data structure is to represent each set by a linked list. The first object in each linked list serves as its set's representative. Each object in the linked list contains a set member, a pointer to the object containing the next set member, and a pointer back to the representative. Each list maintains pointers head, to the representative, and tail, to the last object in the list. Figure 21.2(a) shows two sets. Within each linked list, the objects may appear in any order (subject to our assumption that the first object in each list is the representative). With this linked-list representation, both MAKE-SET and FIND-SET are easy, requiring O(1) time. To carry out MAKE-SET(x), we create a new linked list whose only object is x. For FIND-SET(x), we just return the pointer from x back to the representative.

5 min read

Because the optimal-substructure property is exploited by both the greedy and dynamic-programming strategies, one might be tempted to generate a dynamic-programming solution to a problem when a greedy solution suffices, or one might mistakenly think that a greedy solution works when in fact a dynamic-programming solution is required. To illustrate the subtleties between the two techniques, let us investigate two variants of a classical optimization problem. The 0-1 knapsack problem is posed as follows. A thief robbing a store finds n items; the ith item is worth v_i dollars and weighs w_i pounds, where v_i and w_i are integers. He wants to take as valuable a load as possible, but he can carry at most W pounds in his knapsack for some integer W. Which items should he take? (This is called the 0-1 knapsack problem because each item must either be taken or left behind; the thief cannot take a fractional amount of an item or take an item more than once.) In the fractional knapsack problem, the setup is the same, but the thief can take fractions of items, rather than having to make a binary (0-1) choice for each item. You can think of an item in the 0-1 knapsack problem as being like a gold ingot, while an item in the fractional knapsack problem is more like gold dust.

5 min read

Decreasing a key and deleting a node: In this section, we show how to decrease the key of a node in a Fibonacci heap in O(1) amortized time and how to delete any node from an n-node Fibonacci heap in O(D(n)) amortized time. These operations do not preserve the property that all trees in the Fibonacci heap are unordered binomial trees. They are close enough, however, that we can bound the maximum degree D(n) by O(lg n). In the following pseudocode for the operation FIB-HEAP-DECREASE-KEY, we assume as before that removing a node from a linked list does not change any of the structural fields in the removed node. The FIB-HEAP-DECREASE-KEY procedure works as follows. Lines 1-3 ensure that the new key is no greater than the current key of x and then assign the new key to x. If x is a root or if key[x] ≥ key[y], where y is x's parent, then no structural changes need occur, since min-heap order has not been violated. Lines 4-5 test for this condition.

2 min read

which is the estimated number of atoms in the observable universe. We define the inverse of the function A_k (n), for integer n ≥ 0, by α(n) = min {k : A_k(1) = n} .

2 min read

If c_i[x] has only t - 1 keys but has an immediate sibling with at least t keys, give c_i[x] an extra key by moving a key from x down into c_i[x], moving a key from c_i[x]'s immediate left or right sibling up into x, and moving the appropriate child pointer from the sibling into c_i[x]. If c_i[x] and both of c_i[x]'s immediate siblings have t - 1 keys, merge c_i[x] with one sibling, which involves moving a key from x down into the new merged node to become the median key for that node. Since most of the keys in a B-tree are in the leaves, we may expect that in practice, deletion operations are most often used to delete keys from leaves. The B-TREE-DELETE procedure then acts in one downward pass through the tree, without having to back up. When deleting a key in an internal node, however, the procedure makes a downward pass through the tree but may have to return to the node from which the key was deleted to replace the key with its predecessor or successor (cases 2a and 2b).

5 min read

Operations on binomial heaps: In this section, we show how to perform operations on binomial heaps in the time bounds shown in Figure 19.1. Creating a new binomial heap: To make an empty binomial heap, the MAKE-BINOMIAL-HEAP procedure simply allocates and returns an object H , where head[H ] = NIL. The running time is Θ(1). The procedure BINOMIAL-HEAP-MINIMUM returns a pointer to the node with the minimum key in an n-node binomial heap H. This implementation assumes that there are no keys with value ∞.

3 min read

The auxiliary recursive procedure B-TREE-INSERT-NONFULL inserts key k into node x, which is assumed to be nonfull when the procedure is called. The operation of B-TREE-INSERT and the recursive operation of B-TREE-INSERT-NONFULL guarantee that this assumption is true. The B-TREE-INSERT-NONFULL procedure works as follows. Lines 3-8 handle the case in which x is a leaf node by inserting key k into x. If x is not a leaf node, then we must insert k into the appropriate leaf node in the subtree rooted at internal node x. In this case, lines 9-11 determine the child of x to which the recursion descends. Line 13 detects whether the recursion would descend to a full child, in which case line 14 uses B-TREE-SPLIT-CHILD to split that child into two nonfull children, and lines 15-16 determine which of the two children is now the correct one to descend to. (Note that there is no need for a DISK-READ(c_i [x]) after line 16 increments i, since the recursion will descend in this case to a child that was just created by B-TREE-SPLIT-CHILD.) The net effect of lines 13-16 is thus to guarantee that the procedure never recurses to a full node. Line 17 then recurses to insert k into the appropriate subtree. Figure 18.7 illustrates the various cases of inserting into a B-tree.

5 min read

Disjoint-set operations: A disjoint-set data structure maintains a collection of disjoint dynamic sets. Each set is identified by a representative, which is some member of the set. In some applications, it doesn't matter which member is used as the representative; we only care that if we ask for the representative of a dynamic set twice without modifying the set between the requests, we get the same answer both times. In other applications, there may be a prespecified rule for choosing the representative, such as choosing the smallest member in the set (assuming, of course, that the elements can be ordered). As in the other dynamic-set implementations we have studied, each element of a set is represented by an object. Letting x denote an object, we wish to support the following operations: MAKE-SET(x) creates a new set whose only member (and thus representative) is x. Since the sets are disjoint, we require that x not already be in some other set.

7 min read

Theoretical foundations for greedy methods There is a beautiful theory about greedy algorithms, which we sketch in this section. This theory is useful in determining when the greedy method yields optimal solutions. It involves combinatorial structures known as "matroids." Although this theory does not cover all cases for which a greedy method applies (for example, it does not cover the activity-selection problem of Section 16.1 or the Huffman coding problem of Section 16.3), it does cover many cases of practical interest. Furthermore, this theory is being rapidly developed and extended to cover many more applications; see the notes at the end of this chapter for references. S is a finite nonempty set.

6 min read

Aggregate analysis: In aggregate analysis, we show that for all n, a sequence of n operations takes worst-case time T (n) in total. In the worst case, the average cost, or amortized cost, per operation is therefore T (n)/n. Note that this amortized cost applies to each operation, even when there are several types of operations in the sequence. The other two methods we shall study in this chapter, the accounting method and the potential method, may assign different amortized costs to different types of operations. Stack operations: In our first example of aggregate analysis, we analyze stacks that have been augmented with a new operation. Section 10.1 presented the two fundamental stack operations, each of which takes O(1) time: PUSH(S, x) pushes object x onto stack S.

4 min read

Binomial heaps: A binomial heap H is a set of binomial trees that satisfies the following binomial-heap properties. Each binomial tree in H obeys the min-heap property: the key of a node is greater than or equal to the key of its parent. We say that each such tree is min-heap-ordered. For any nonnegative integer k, there is at most one binomial tree in H whose root has degree k.

5 min read

Suppose that the ith operation on the stack is MULTIPOP(S, k) and that ′ = min(k, s) objects are popped off the stack. The actual cost of the operation is ′, and the potential difference is Φ(D_i) - Φ(D_i-1) - -′. Thus, the amortized cost of the MULTIPOP operation is

5 min read

Definition of B-trees: To keep things simple, we assume, as we have for binary search trees and red-black trees, that any "satellite information" associated with a key is stored in the same node as the key. In practice, one might actually store with each key just a pointer to another disk page containing the satellite information for that key. The pseudocode in this chapter implicitly assumes that the satellite information associated with a key, or the pointer to such satellite information, travels with the key whenever the key is moved from node to node. A common variant on a B-tree, known as a B - tree, stores all the satellite information in the leaves and stores only keys and child pointers in the internal nodes, thus maximizing the branching factor of the internal nodes. A B-tree T is a rooted tree (whose root is root[T]) having the following properties: Every node x has the following fields:

8 min read

Longest common subsequence In biological applications, we often want to compare the DNA of two (or more) different organisms. A strand of DNA consists of a string of molecules called bases, where the possible bases are adenine, guanine, cytosine, and thymine. Representing each of these bases by their initial letters, a strand of DNA can be expressed as a string over the finite set {A, C, G, T}. For example, the DNA of one organism may be S₁= ACCGGTCGAGTGCGCGGAAGCCGGCCGAA, while the DNA of another organism may be S₂ = GTCGTTCGGAATGCCGTTGCTCTGTAAA. One goal of comparing two strands of DNA is to determine how "similar" the two strands are, as some measure of how closely related the two organisms are. Similarity can be and is defined in many different ways. For example, we can say that two DNA strands are similar if one is a substring of the other. In our example, neither S₁ nor S₂ is a substring of the other. Alternatively, we could say that two strands are similar if the number of changes needed to turn one into the other is small. Yet another way to measure the similarity of strands S₁ and S₂ is by finding a third strand S₃ in which the bases in S₃ appear in each of S₁ and S₂; these bases must appear in the same order, but not necessarily consecutively. The longer the strand S₃ we can find, the more similar S₁ and S₂ are. In our example, the longest strand S₃ is GTCGTCGGAAGCCGGCCGAA. We formalize this last notion of similarity as the longest-common-subsequence problem. A subsequence of a given sequence is just the given sequence with zero or more elements left out. Formally, given a sequence X = 〈x₁, x₂, ..., x_m〉, another sequence Z = 〈z₁, z₂, ..., z_k〉 is a subsequence of X if there exists a strictly increasing sequence 〈i₁,i₂, ..., i_k〉 of indices of X such that for all j = 1, 2, ..., k, we have x_ij = z_j . For example, Z = 〈B, C, D, B〉 is a subsequence of X = 〈A, B, C, B, D, A, B〉 with corresponding index sequence 〈2, 3, 5, 7〉.

3 min read

We easily can convert our recursive procedure to an iterative one. The procedure RECURSIVE-ACTIVITY-SELECTOR is almost "tail recursive" : it ends with a recursive call to itself followed by a union operation. It is usually a straightforward task to transform a tail-recursive procedure to an iterative form; in fact, some compilers for certain programming languages perform this task automatically. As written, RECURSIVE-ACTIVITY-SELECTOR works for any subproblem S_ij, but we have seen that we need to consider only subproblems for which j = n 1, i.e., subproblems that consist of the last activities to finish. The procedure GREEDY-ACTIVITY-SELECTOR is an iterative version of the procedure RECURSIVE-ACTIVITY-SELECTOR. It also assumes that the input activities are ordered by monotonically increasing finish time. It collects selected activities into a set A and returns this set when it is done. The procedure works as follows. The variable i indexes the most recent addition to A, corresponding to the activity a_i in the recursive version. Since the activities are considered in order of monotonically increasing finish time, f_i is always the maximum finish time of any activity in A. That is,

2 min read

Overview of Dynamic Programming Dynamic programming, like the divide-and-conquer method, solves problems by combining the solutions to subproblems. ("Programming" in this context refers to a tabular method, not to writing computer code.) As we saw in divide-and-conquer algorithms partition the problem into independent subproblems, solve the subproblems recursively, and then combine their solutions to solve the original problem. In contrast, dynamic programming is applicable when the subproblems are not independent, that is, when subproblems share subsubproblems. In this context, a divide-and-conquer algorithm does more work than necessary, repeatedly solving the common subsubproblems. A dynamic-programming algorithm solves every subsubproblem just once and then saves its answer in a table, thereby avoiding the work of recomputing the answer every time the subsubproblem is encountered. Dynamic programming is typically applied to optimization problems. In such problems there can be many possible solutions. Each solution has a value, and we wish to find a solution with the optimal (minimum or maximum) value. We call such a solution an optimal solution to the problem, as opposed to the optimal solution, since there may be several solutions that achieve the optimal value.

4 min read

The second ingredient that an optimization problem must have for dynamic programming to be applicable is that the space of subproblems must be "small" in the sense that a recursive algorithm for the problem solves the same subproblems over and over, rather than always generating new subproblems. Typically, the total number of distinct subproblems is a polynomial in the input size. When a recursive algorithm revisits the same problem over and over again, we say that the optimization problem has overlapping subproblems. In contrast, a problem for which a divide-and-conquer approach is suitable usually generates brand-new problems at each step of the recursion. Dynamic-programming algorithms typically take advantage of overlapping subproblems by solving each subproblem once and then storing the solution in a table where it can be looked up when needed, using constant time per lookup. To illustrate the overlapping-subproblems property in greater detail, let us reexamine the matrix-chain multiplication problem. Referring back to Figure 15.3, observe that MATRIX-CHAIN-ORDER repeatedly looks up the solution to subproblems in lower rows when solving subproblems in higher rows. For example, entry m[3, 4] is referenced 4 times: during the computations of m[2, 4], m[1, 4], m[3, 5], and m[3, 6]. If m[3, 4] were recomputed each time, rather than just being looked up, the increase in running time would be dramatic. To see this, consider the following (inefficient) recursive procedure that determines m[i, j], the minimum number of scalar multiplications needed to compute the matrix-chain product A_i‥j = A_iA_{i 1} ··· A_j. The procedure is based directly on the recurrence (15.12). Figure 15.5 shows the recursion tree produced by the call RECURSIVE-MATRIX-CHAIN(p, 1, 4). Each node is labeled by the values of the parameters i and j. Observe that some pairs of values occur many times.

6 min read

Matrix-chain multiplication: Our next example of dynamic programming is an algorithm that solves the problem of matrix-chain multiplication. We are given a sequence (chain) 〈A₁, A₂, ..., A_n〉 of n matrices to be multiplied, and we wish to compute the product We can evaluate the expression (15.10) using the standard algorithm for multiplying pairs of matrices as a subroutine once we have parenthesized it to resolve all ambiguities in how the matrices are multiplied together. A product of matrices is fully parenthesized if it is either a single matrix or the product of two fully parenthesized matrix products, surrounded by parentheses. Matrix multiplication is associative, and so all parenthesizations yield the same product. For example, if the chain of matrices is 〈A₁, A₂, A₃, A₄〉, the product A₁ A₂ A₃ A₄ can be fully parenthesized in five distinct ways:

7 min read

Overview of Fibonacci Heaps: In Binomial heaps, we saw how binomial heaps support in O(lg n) worst-case time the mergeable-heap operations INSERT, MINIMUM, EXTRACT-MIN, and UNION, plus the operations DECREASE-KEY and DELETE. In this chapter, we shall examine Fibonacci heaps, which support the same operations but have the advantage that operations that do not involve deleting an element run in O(1) amortized time. Structure of Fibonacci heaps: Like a binomial heap, a Fibonacci heap is a collection of min-heap-ordered trees. The trees in a Fibonacci heap are not constrained to be binomial trees, however. Figure 20.1(a) shows an example of a Fibonacci heap.

6 min read

Huffman codes: Huffman codes are a widely used and very effective technique for compressing data; savings of 20% to 90% are typical, depending on the characteristics of the data being compressed. We consider the data to be a sequence of characters. Huffman's greedy algorithm uses a table of the frequencies of occurrence of the characters to build up an optimal way of representing each character as a binary string. Suppose we have a 100,000-character data file that we wish to store compactly. We observe that the characters in the file occur with the frequencies given by Figure 16.3. That is, only six different characters appear, and the character a occurs 45,000 times. There are many ways to represent such a file of information. We consider the problem of designing a binary character code (or code for short) wherein each character is represented by a unique binary string. If we use a fixed-length code, we need 3 bits to represent six characters: a = 000, b = 001, ..., f = 101. This method requires 300,000 bits to code the entire file. Can we do better?

4 min read

hus, we can compute the Θ(n²) values of w[i, j] in Θ(1) time each. The pseudocode that follows takes as inputs the probabilities p₁, ..., p_n and q₀, ..., q_n and the size n, and it returns the tables e and root. From the description above and the similarity to the MATRIX-CHAIN-ORDER procedure in Section 15.2, the operation of this procedure should be fairly straightforward. The for loop of lines 1-3 initializes the values of e[i, i - 1] and w[i, i - 1]. The for loop of lines 4-13 then uses the recurrences (15.19) and (15.20) to compute e[i, j] and w[i, j] for all 1 ≤ i ≤ j ≤ n. In the first iteration, when l = 1, the loop computes e[i, i] and w[i, i] for i = 1, 2, ..., n. The second iteration, with l = 2, computes e[i, i 1] and w[i, i 1] for i = 1, 2, ..., n - 1, and so forth. The innermost for loop, in lines 9-13, tries each candidate index r to determine which key k_r to use as the root of an optimal binary search tree containing keys k_i, ..., k_j. This for loop saves the current value of the index r in root[i, j] whenever it finds a better key to use as the root.

7 min read

The accounting method: In the accounting method of amortized analysis, we assign differing charges to different operations, with some operations charged more or less than they actually cost. The amount we charge an operation is called its amortized cost. When an operation's amortized cost exceeds its actual cost, the difference is assigned to specific objects in the data structure as credit. Credit can be used later on to help pay for operations whose amortized cost is less than their actual cost. Thus, one can view the amortized cost of an operation as being split between its actual cost and credit that is either deposited or used up. This method is very different from aggregate analysis, in which all operations have the same amortized cost. One must choose the amortized costs of operations carefully. If we want analysis with amortized costs to show that in the worst case the average cost per operation is small, the total amortized cost of a sequence of operations must be an upper bound on the total actual cost of the sequence. Moreover, as in aggregate analysis, this relationship must hold for all sequences of operations. If we denote the actual cost of the ith operation by c_i and the amortized cost of the ith operation by , we require

6 min read

Overview of B-trees B-trees are balanced search trees designed to work well on magnetic disks or other direct-access secondary storage devices. B-trees are similar to red-black trees, but they are better at minimizing disk I/O operations. Many database systems use B-trees, or variants of B-trees, to store information. B-trees differ from red-black trees in that B-tree nodes may have many children, from a handful to thousands. That is, the "branching factor" of a B-tree can be quite large, although it is usually determined by characteristics of the disk unit used. B-trees are similar to red-black trees in that every n-node B-tree has height O(lg n), although the height of a B-tree can be considerably less than that of a red-black tree because its branching factor can be much larger. Therefore, B-trees can also be used to implement many dynamic-set operations in time O(lg n).

3 min read

The FIND-SET procedure with path compression is quite simple. The FIND-SET procedure is a two-pass method: it makes one pass up the find path to find the root, and it makes a second pass back down the find path to update each node so that it points directly to the root. Each call of FIND-SET(x) returns p[x] in line 3. If x is the root, then line 2 is not executed and p[x] = x is returned. This is the case in which the recursion bottoms out. Otherwise, line 2 is executed, and the recursive call with parameter p[x] returns a pointer to the root. Line 2 updates node x to point directly to the root, and this pointer is returned in line 3. Separately, either union by rank or path compression improves the running time of the operations on disjoint-set forests, and the improvement is even greater when the two heuristics are used together. Alone, union by rank yields a running time of O(m lg n), and this bound is tight. Although we shall not prove it here, if there are n MAKE-SET operations (and hence at most n - 1 UNION operations) and f FIND-SET operations, the path-compression heuristic alone gives a worst-case running time of Θ (n f · (1 log_{2 f / n} n)).