New Semester Started Get 50% OFF Study Help! --h --m --s Claim Now

Question Answers

Textbooks

Find textbooks, questions and answers

Oops, something went wrong!

Change your search query and then try again

Result Not Found

Books FREE
Study Help
Tutors
AI Study Planner NEW
Sell Books

Search
Sign In
Register

study help
computer science
introduction to algorithms

Introduction to Algorithms 3rd edition Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest - Solutions

Give an efficient push-relabel algorithm to find a maximum matching in a bipartite graph. Analyze your algorithm.
Suppose that each source si in a flow network with multiple sources and sinks produces exactly pi units of flow, so that ∑ν∈v f(si, v)= Pi. Suppose also that each sink tj consumes exactly qj units, so that that ∑ν∈v f(ν, tj) = qj, where ∑i Pi = ∑j qj. Show how to
Suppose that all edge capacities in a flow network G = (V, E) are in the set |1, 2, . . . ,k}.Analyze the running time of the generic push-relabel algorithm in terms of |V|, |E|, and k. How many times can each edge support a nonsaturating push before it becomes saturated?
Let ıf (u, ν) be the distance (number of edges) from u to ν in the residual network Gf. Show that the GENERIC-PUSH-RELABEL procedure maintains the properties that u.h < |V| implies u.h ≤ δf (u, t) and
As in the previous exercise, let δf (u, ν) be the distance from u to ν in the residual network Gf. Show how to modify the generic push-relabel algorithm to maintain the property that u.h < |V| implies u.h = δf (u,
Show how to find a maximum flow in a network G = (V, E) by a sequence of at most |E| augmenting paths. Determine the paths after finding the maximum flow.
Show that the number of nonsaturating pushes executed by the GENERIC-PUSH-RELABEL procedure on a flow network G = (V, E) is at most 4 |V|2 |E| for |V| ≥ 4.
Explain how to coarsen the base case of P-MERGE.
Draw the computation dag for computing P-SQUARE-MATRIX-MULTIPLY on 2 × 2 matrices, labeling how the vertices in your diagram correspond to strands in the execution of the algorithm. Use the convention that spawn and call edges point downward, continuation edges point horizontally to the right, and
Draw the computation dag that results from executing P-FIB(5). Assuming that each strand in the computation takes unit time, what are the work, span, and parallelism of the computation? Show how to schedule the dag on 3 processors using greedy scheduling by labeling each strand with the time step
Construct a computation dag for which one execution of a greedy scheduler can take nearly twice the time of another execution of a greedy scheduler on the same number of processors. Describe how the two executions would proceed.
Solve the equation by using forward substitution. 1 0 0 4 1 0 -6 5 1 X1 3 X2 14 X3 -7
Prove that every diagonal element of a symmetric positive-definite matrix is positive.
Consider the tridiagonal matrix a. Find an LU decomposition of A. b.?Solve the equation?Ax?=(1 1 1 1 1)T by using forward and back substitution. c.?Find the inverse of?A. d.?Show how, for any?n?נn?symmetric positive-definite, tridiagonal matrix?A?and any?n-vector?b, to solve the
Find an LU decomposition of the matrix? Figure 28.2?The operation of LUP-DECOMPOSITION. (a) The input matrix A with the identity permutation of the rows on the left. The first step of the algorithm determines that the element 5 in the black circle in the third row is the pivot for the first
Let M(n) be the time to multiply two n × n matrices, and let L(n) be the time to compute the LUP decomposition of an n × n matrix( Show that multiplying matrices and computing LUP decompositions of matrices have essentially the same difficulty: an M(n)-time matrix-multiplication algorithm implies
A practical method for interpolating a set of points with a curve is to use cubic splines. We are given a set {(xi, yi) : i = 0, 1, . . . , n} of n + 1 point-value pairs, where x01 n. We wish to fit a piecewise-cubic curve (spline) f (x) to the points. That is, the curve f (x) is made up of n cubic
Solve the equation by using an LUP decomposition. 15 4 2 0 3 X1 12 X2 5 8 2 X3 5
Let M(n) be the time to multiply two n × n matrices, and let D(n) denote the time required to find the determinant of an n × n matrix. Show that multiplying matrices and computing the determinant have essentially the same difficulty: an M(n)-time matrix-multiplication algorithm implies an
Prove that the maximum element in a symmetric positive-definite matrix lies on the diagonal.
Describe the LUP decomposition of a diagonal matrix.
Prove that the determinant of each leading submatrix of a symmetric positive definite matrix is positive.
Describe the LUP decomposition of a permutation matrix A, and prove that it is unique.
Let Ak denote the kth leading submatrix of a symmetric positive-definite matrix A. Prove that det (Ak)/ det(Ak-1) is the kth pivot during LU decomposition, where, by convention, det(A′) = 1.
Show that for all n ≥ 1, there exists a singular n × n matrix that has an LU decomposition.
Find the function of the form that is the best least-squares fit to the data points (1, 1), (2, 1), (3, 3), (4, 8) .
Let M (n) be the time to multiply two n × n matrices, and let S (n) denote the time required to square an n × n matrix. Show that multiplying and squaring matrices have essentially the same difficulty: an M(n)-time matrix-multiplication algorithm implies an O(M (n))-time squaring algorithm, and
In LU-DECOMPOSITION, is it necessary to perform the outermost for loop iteration when k = n? How about in LUP-DECOMPOSITION?
Show that the pseudoinverse A+ satisfies the following four equations: AA* A А, A+ AA+ A+ , (AA*)" (A* A)™ AA+ A A. || || ||
Given a set of m linear inequalities on n variables x1, x2, . . . ,xn, the linearin equality feasibility problem asks whether there is a setting of the variables that simultaneously satisfies each of the inequalities.a. Show that if we have an algorithm for linear programming, we can use it to
Show that the call to PIVOT in line 12 of SIMPLEX never decreases the value of ν.
Suppose that we have a linear program that is not in standard form. We could produce the dual by first converting it to standard form, and then taking the dual. It would be more convenient, however, to be able to produce the dual directly. Explain how we can directly take the dual of an arbitrary
Show that when the main loop of SIMPLEX is run by INITIALIZE-SIMPLEX, it can never return “unbounded.”
Complementary slackness describes a relationship between the values of primal variables and dual constraints and between the values of dual variables and primal constraints. Let x? be a feasible solution to the primal linear program given in (29.16)-(29.18), and let y? be a feasible solution to the
For the slack form in (29.38)–(29.41), what are N, B, A, b, c, and ν?
In the single-source shortest-paths problem, we want to find the shortest-path weights from a source vertex s to all vertices ν ∈ V. Given a graph G, write a linear program for which the solution has the property that dν is the shortest-path weight from s to ν for each vertex ν ∈ V.
Prove that the slack form given to the PIVOT procedure and the slack form that the procedure returns are equivalent.
Suppose that we are given a linear program L in standard form, and suppose that for both L and the dual of L, the basic solutions associated with the initial slack forms are feasible. Show that the optimal objective value of L is 0.
An integer linear-programming problem is a linear-programming problem with the additional constraint that the variables x must take on integral values. Exercise 34.5-3 shows that just determining whether an integer linear program has a feasible solution is NP-hard, which means that there is no
Convert the following linear program into standard form: minimize 2x, + 7x2 + X3 subject to X1 X3 7 3x1 + X2 2 24 X2 X3 0 . || AL AL VI
Suppose we convert a linear program (A, b, c) in standard form to slack form. Show that the basic solution is feasible if and only if bi ≥ 0 for i = 1, 2, . . . ,m.
Suppose that we allow strict inequalities in a linear program. Show that in this case, the fundamental theorem of linear programming does not hold.
Let A be an m ? n matrix and c be an n-vector. Then Farkas?s lemma states that exactly one of the systems and 0 " style="" class="fr-fic fr-dib"> is solvable, where x is an n-vector and y is an m-vector. Prove Farkas?s lemma. A"y У> 0
Let bn denote the number of different binary trees with?n?nodes. In this problem, you will find a formula for?bn, as well as an asymptotic estimate. a.?Show that?b0 =?1?and that, for?n???1, b. Referring to Problem 4-4 for the definition of a generating function, let B(x) be the generating
Suppose you are given a set S = {a1, a2, . . . ,an} of tasks, where task ai requires pi units of processing time to complete, once it has started. You have one computer on which to run these tasks, and the computer can run only one task at a time. Let ci be the completion time of task ai,
What is an optimal Huffman code for the following set of frequencies, based on the first 8 Fibonacci numbers?a:1 b:1 c:2 d:3 e:5 f:8 g:13 h:21 Can you generalize your answer to find the optimal code when the frequencies are the first n Fibonacci numbers?
Explain how to find the minimum key stored in a B-tree and how to find the predecessor of a given key stored in a B-tree.
Show all legal B-trees of minimum degree 2 that represent {1, 2, 3, 4, 5}.
The join operation takes two dynamic sets S′ and S′′ and an element x such that for any x′ ∈ S′ and x′′ ∈ S′′, we have x′.key < x.key < x′′.key. It returns a set S = S′ ⋃ {x} ⋃ S′′. The split operation is like an "inverse" join: given a dynamic set S and
Explain under what circumstances, if any, redundant DISK-READ or DISK-WRITE operations occur during the course of executing a call to B-TREE-INSERT. (A redundant DISK-READ is a DISK-READ for a page that is already in memory. A redundant DISK-WRITE writes to disk a page of information that is
For what values of t is the tree of Figure 18.1 a legal B-tree? Figure 18 T.root D,H 2,T X В С F G ЈK L N P R S V W Y Z
Consider implementing a stack in a computer that has a relatively small amount of fast primary memory and a relatively large amount of slower disk storage. The operations PUSH and POP work on single-word values. The stack we wish to support can grow to be much larger than can fit in memory, and
Show the results of inserting the keys F, S, Q, K, C, L, H, T, V, W, M, R, N, P, A, B, X, Y, D, Z, E in order into an empty B-tree with minimum degree 2. Draw only the configurations of the tree just before some node must split, and also draw the final configuration.
Why don’t we allow a minimum degree of t = 1?
Design a data structure to support the following two operations for a dynamic multiset S of integers, which allows duplicate values:INSERT (S, x) inserts x into S.DELETE-LARGER-HALF(S) deletes the largest ⌈|S|/2⌉ elements from S.Explain how to implement this data
Show how to implement a queue with two ordinary stacks (Exercise 10.1-6) so that the amortized cost of each ENQUEUE and each DEQUEUE operation is O(1).
Suppose that a counter begins at a number with b 1s in its binary representation, rather than at 0. Show that the cost of performing n INCREMENT operations is O(n) if n = Ω(b). (Do not assume that b is constant.)
A self-organizing list is a linked list of n elements, in which each element has a unique key. When we search for an element in the list, we are given a key, and we want to find an element with that key. A self-organizing list has two important properties. 1. To find an element in the list, given
What is the total cost of executing n of the stack operations PUSH, POP, and MULTIPOP, assuming that the stack begins with s0 objects and finishes with sn objects?
Suppose that instead of contracting a table by halving its size when its load factor drops below 1/4, we contract it by multiplying its size by 2/3 when its load factor drops below 1/3. Using the potential function show that the amortized cost of a TABLE-DELETE that uses this strategy is bounded
Consider an ordinary binary search tree augmented by adding to each node x the attribute x.size giving the number of keys stored in the subtree rooted at x. Let ? be a constant in the range 1/2 ? ? a.?A?1/2-balanced tree is, in a sense, as balanced as it can be. Given a node?x?in an arbitrary
Show that if a DECREMENT operation were included in the k-bit counter example, n operations could cost as much as Θ(nk) time.
Chapter 30 examines an important algorithm called the fast Fourier transform, or FFT. The first step of the FFT algorithm performs a bit-reversal permutation on an input array A[0 . . n - 1] whose length is n = 2k for some nonnegative integer?k. This permutation swaps elements whose indices have
If the set of stack operations included a MULTI-PUSH operation, which pushes k items onto the stack, would the O(1) bound on the amortized cost of stack operations continue to hold?
Suppose that we wish to implement a dynamic, open-address hash table. Why might we consider the table to be full when its load factor reaches some value α that is strictly less than 1? Describe briefly how to make insertion into a dynamic, open-address hash table run in such a way that the
Suppose we have a potential function Φ such that Φ(Di)≥ Φ(D0) for all i, but Φ(D0) ≠ 0. Show that there exists a potential function Φ′ such that Φ′(D0) = 0, Φ′(Di ) ≥ 0 for all i ≥ 1, and the amortized costs using Φ′ are the same as
Show that no compression scheme can expect to compress a file of randomly chosen 8-bit characters by even a single bit.
Suppose that a data file contains a sequence of 8-bit characters such that all 256 characters are about equally common: the maximum character frequency is less than twice the minimum character frequency. Prove that Huffman coding in this case is no more efficient than using an ordinary 8-bit
Generalize Huffman's algorithm to ternary codewords (i.e., codewords using the symbols 0, 1, and 2), and prove that it yields optimal ternary codes.
Suppose we have an optimal prefix code on a set C = {0, 1, . . . n – 1} of characters and we wish to transmit this code using as few bits as possible. Show how to represent any optimal prefix code on C using only 2n - 1 + n ⌈lg n⌋ bits.
Prove that if we order the characters in an alphabet so that their frequencies are monotonically decreasing, then there exists an optimal code whose codeword lengths are monotonically increasing.
Describe an efficient algorithm that, given a set 〈x1, x2, . . . ,xn〉 of points on the real line, determines the smallest set of unit-length closed intervals that contains all of the given points. Argue that your algorithm is correct.
Show how to transform the weight function of a weighted matroid problem, where the desired optimal solution is a minimum-weight maximal independent subset, to make it a standard weighted-matroid problem. Argue carefully that your transformation is correct.
Prove that we can also express the total cost of a tree for a code as the sum, over all internal nodes, of the combined frequencies of the two children of the node.
Let S be a finite set and let S1, S2, . . . ,Sk be a partition of S into nonempty disjoint subsets. Define the structure (S, I) by the condition that I = {A : |A ⋂ Si | ≤ 1 for i = 1, 2, . . . ,k}. Show that (S, I) is a matroid. That is,
Suppose that in a 0-1 knapsack problem, the order of the items when sorted by increasing weight is the same as their order when sorted by decreasing value. Give an efficient algorithm to find an optimal solution to this variant of the knapsack problem, and argue that your algorithm is correct.
Show how to use property 2 of Lemma 16.12 to determine in time O(|A|) whether or not a given set A of tasks is independent.Lemma 16.12For any set of tasks A, the following statements are equivalent.1. The set A is independent.2. For t = 0, 1, 2, . . . , n, we have Nt(A) ≤ t.3. If the tasks in A
Prove that a binary tree that is not full cannot correspond to an optimal prefix code.
Solve the instance of the scheduling problem given in Figure 16.7, but with each penalty wi replaced by 80 ? wi . Figure 16.7 Task ai 1 4 5 6 7 di 4 4 3 1 4 6. Wi 70 60 50 40 30 20 10 3. 2. 2.
Prove that the fractional knapsack problem has the greedy-choice property.
Show that (S, Ik) is a matroid, where S is any finite set and Ik is the set of all subsets of S of size at most k, where k ≤ |S|.
Your knowledge of algorithms helps you obtain an exciting job with the Acme Computer Company, along with a $10,000 signing bonus. You decide to invest this money with the goal of maximizing your return at the end of 10 years. You decide to use the Amalgamated Investment Company to manage your
Show that a full parenthesization of an n-element expression has exactly n – 1 pairs of parentheses.
Give an O(n lg n)-time algorithm to find the longest monotonically increasing subsequence of a sequence of n numbers. Observe that the last element of a candidate subsequence of length i is at least as large as the last element of a candidate subsequence of length i - 1. Maintain candidate
We can use dynamic programming on a directed graph G = (V, E) for speech recognition. Each edge (u, ν) ∈ E is labeled with a sound σ (u, ν) from a finite set ∑ of sounds. The labeled graph is a formal model of a person speaking a restricted language. Each path in the graph starting from a
Professor Stewart is consulting for the president of a corporation that is planning a company party. The company has a hierarchical structure, that is, the supervisor relation forms a tree rooted at the president. The personnel office has ranked each employee with a conviviality rating, which is a
Give an O(n2)-time algorithm to find the longest monotonically increasing subsequence of a sequence of n numbers.
As stated, in dynamic programming we first solve the subproblems and then choose which of them to use in an optimal solution to the problem. Professor Capulet claims that we do not always need to solve all the subproblems in order to find an optimal solution. She suggests that we can find an
Knuth [212] has shown that there are always roots of optimal subtrees such that root[I, j – 1] ≤ root[I, j] ≤ root[i + 1, j] for all 1 ≤ i < j ≤ n. Use this fact to modify the OPTIMAL-BST procedure to run in Θ(n2) time.
Consider a variant of the matrix-chain multiplication problem in which the goal is to parenthesize the sequence of matrices so as to maximize, rather than minimize, the number of scalar multiplications. Does this problem exhibit optimal substructure?
Suppose that instead of maintaining the table w[I, j], we computed the value of w(I, j) directly from equation (15.12) in line 9 of OPTIMAL-BST and used this computed value in line 11. How would this change affect the asymptotic running time of OPTIMAL-BST? (15.12) w(i, j) = Pi +E 1=i 1=i-1
Give a recursive algorithm MATRIX-CHAIN-MULTIPLY (A, s, i, j) that actually performs the optimal matrix-chain multiplication, given the sequence of matrice 〈A1, A2, . . . ,An〉, the s table computed by MATRIX-CHAIN-ORDER, and the indices i and j. (The initial call would be
Give pseudocode to reconstruct an LCS from the completed c table and the original sequences X = 〈x1, x2, . . . , xm〉 and Y = 〈y1, y2, . . , yn〉 in O(m + n) time, without using the b table.
Find an optimal parenthesization of a matrix-chain product whose sequence of dimensions is 〈5, 10, 3, 12, 5, 50, 6〉.
Determine the cost and structure of an optimal binary search tree for a set of n = 7 keys with the following probabilities: 1 0.04 0.06 i 3 4 5 6. 7 Pi 0.08 0.02 0.10 0.12 0.14 0.06 0.06 0.06 0.06 0.05 0.05 0.05 0.05
Write pseudocode for the procedure CONSTRUCT-OPTIMAL-BST(root) which, given the table root, outputs the structure of an optimal binary search tree. For the example in Figure 15.10, your procedure should print out the structure Figure 15.10 k2 is the root k1 is the left child of?k2 d0 is the left
Determine an LCS of 〈1, 0, 0, 1, 0, 1, 0, 1〉 and 〈0, 1, 0, 1, 1, 0, 1, 1, 0〉.
Consider n chords on a circle, each defined by its endpoints. Describe an O(n lg n)- time algorithm to determine the number of pairs of chords that intersect inside the circle. (For example, if the n chords are all diameters that meet at the center, then the correct answer is (n2).) Assume that no
Suggest modifications to the interval-tree procedures to support the new operation INTERVAL-SEARCH-EXACTLY (T, i), where T is an interval tree and i is an interval. The operation should return a pointer to a node x in T such that x.int.low = i.low and x.int.high = i.high, or T.nil if T contains no
Given an interval tree T and an interval i, describe how to list all intervals in T that overlap i in O(min(n, k lg n)) time, where k is the number of intervals in the output list. One simple method makes several queries, modifying the tree between queries. A slightly more complicated method does

Showing 800 - 900 of 1549

First
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

Step by Step Answers

Services

Sitemap
Fun
Definitions
Become Tutor
Used Textbooks
Study Help Categories
Recent Questions
Expert Questions
Campus Wear
Sell Your Books

Company Info

Security
Copyrights
Privacy Policy
Terms & Conditions
SolutionInn Fee
Scholarship
Online Quiz
Give Feedback, Get Rewards

Get In Touch

About Us
Contact Us
Career
Jobs
FAQ
Student Discount
Campus Ambassador

Secure Payment

Download Our App

© 2026 SolutionInn. All Rights Reserved