All Matches

Solution Library

Expert Answer

Textbooks

Search Textbook questions, tutors and Books

Oops, something went wrong!

Change your search query and then try again

Result Not Found

Books FREE
Tutors
Study Help
Ask a Question

Search
Sign In
Register

study help
computer science
introduction to algorithms

Questions and Answers of Introduction to Algorithms

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
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
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
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
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
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
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
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
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
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
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
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
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,
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
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
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,
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
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
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
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
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
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.
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
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
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 =
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
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
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
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,
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
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
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
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 ? ?
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
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
Suppose we have a potential function Φ such that Φ(Di)≥ Φ(D0) for all i, but Φ(D0) ≠ 0. Show that there exists a potential function Φ′ such
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
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
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
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
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 :
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
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
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
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
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
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
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
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
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
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
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
Give pseudocode to reconstruct an LCS from the completed c table and the original sequences X = 〈x1, x2, . . . , xm〉 and Y = 〈y1, y2, . . ,
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
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
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
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
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

Showing 800 - 900 of 1549

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

Get In Touch

About Us
Contact Us
Career
Jobs
FAQ
Campus Ambassador

Company Info

Security
Copyrights
Privacy Policy
Terms & Condition
SolutionInn Fee
Scholarship

Services

Sitemap
Fun
Definitions
Become Tutor
Study Help Categories
Recent Questions
Expert Questions

Copyright © 2024 SolutionInn All Rights Reserved.

Get the SolutionInn - Study Help App