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

Alice has a copy of a long?n-bit file?A?=??an-1, an-2, . . . , a0?, and Bob similarly has an?n-bit file?B?=??bn-1, bn-2, . . . , b0?. Alice and Bob wish to know if their files are identical. To avoid transmitting all of?A?or?B, they use the following fast probabilistic check. Together, they select
Given two patterns P and P′, describe how to construct a finite automaton that determines all occurrences of either pattern. Try to minimize the number of states in your automaton.
Show how to improve KMP-MATCHER by replacing the occurrence of ? in line 7 (but not line 12) by _0, where ?? is defined recursively for q = 1, 2, . . . ,m ? 1 by the equation Explain why the modified algorithm is correct, and explain in what sense this change constitutes an improvement. if π[g]
Give a linear-time algorithm to determine whether a text T is a cyclic rotation of another string T′. For example, arc and car are cyclic rotations of each other.
Give an O(m |∑|)-time algorithm for computing the transition function ı for the string-matching automaton corresponding to a given pattern P. Prove that δ(q, a) = δ(π[q], a) if q = m or P [q + 1] ≠ a.
Prove that if p1 × p2 is positive, then vector p1 is clockwise from vector p2 with respect to the origin (0, 0) and that if this cross product is negative, then p1 is counterclockwise from p2.
Professor Williams comes up with a scheme that allows the closest-pair algorithm to check only 5 points following each point in array Y′. The idea is always to place points on line l into set PL. Then, there cannot be pairs of coincident points on
Given a set Q of points in the plane, we define the convex layers of Q inductively. The first convex layer of Q consists of those points in Q that are vertices of CH (Q). For i > 1, define Qi to consist of the points of Q with all points in convex layers 1, 2, . . . , i − 1 removed. Then, the
Professor van Pelt proposes that only the x-dimension needs to be tested in line 1 of ON-SEGMENT. Show why the professor is wrong.
Given two segments a and b that are comparable at x, show how to determine in O(1) time which of a ≼ x b or b ≼ x a holds( Assume that neither segment is vertical. If a and b do not intersect, you can just use cross products. If a and b intersect-which you can of course determine using only
Consider a model of computation that supports addition, comparison, and multiplication and for which there is a lower bound of Ω(n lg n) to sort n numbers. Prove that Ω(n lg n) is a lower bound for computing, in order, the vertices of the convex hull of a set of n points in such a model.
Show that it actually suffices to check only the points in the 5 array positions following each point in the array Y′.
Let Q be a set of n points in the plane. We say that point (x, y) dominates point (x?, y?) if x ? x? and y ? y?. A point in Q that is dominated by no other points in Q is said to be maximal. That Q may contain many maximal points, which can be organized into maximal layers as follows. The first
The polar angle of a point p1 with respect to an origin point p0 is the angle of the vector p1 − p0 in the usual polar coordinate system. For example, the polar angle of (3, 5) with respect to (2, 4) is the angle of the vector (1, 1), which
Professor Mason suggests that we modify ANY-SEGMENTS-INTERSECT so that instead of returning upon finding an intersection, it prints the segments that intersect and continues on to the next iteration of the for loop. The professor calls the resulting procedure PRINT-INTERSECTING-SEGMENTS and claims
Given a set of points Q, prove that the pair of points farthest from each other must be vertices of CH (Q).
We can define the distance between two points in ways other than euclidean. In the plane, the Lm-distance between points p1 and p2 is given by the expression (|x1 − x2|m + |y1 − y2|m)1/m. Euclidean distance, therefore, is L2-distance. Modify the
A group of n Ghostbusters is battling n ghosts. Each Ghostbuster carries a proton pack, which shoots a stream at a ghost, eradicating it. A stream goes in a straight line and terminates when it hits the ghost. The Ghostbusters decide upon the following strategy. They will pair off with the ghosts,
Show how to determine in O(n2 lg n) time whether any three points in a set of n points are colinear.
Give an O(n lg n)-time algorithm to determine whether an n-vertex polygon is simple.
Given two points p1 and p2 in the plane, the L∞ -distance between them is given by max(|x1 − x2| , |y1 − y2|). Modify the closest-pair algorithm to use the L∞ -distance.
Professor Charon has a set of n sticks, which are piled up in some configuration. Each stick is specified by its endpoints, and each endpoint is an ordered triple giving its (x, y, z) coordinates. No stick is vertical. He wishes to pick up all the sticks, one at a time, subject to the condition
A polygon is a piecewise-linear, closed curve in the plane. That is, it is a curve ending on itself that is formed by a sequence of straight-line segments, called the sides of the polygon. A point joining two consecutive sides is a vertex of the polygon. If the polygon is simple, as we shall
Give an O(n lg n)-time algorithm to determine whether two simple polygons with a total of n vertices intersect.
In the on-line convex-hull problem, we are given the set Q of n points one point at a time. After receiving each point, we compute the convex hull of the points seen so far. Obviously, we could run Graham’s scan once for each point, with a total running time of O(n2
Suppose that Ω(n) of the points given to the closest-pair algorithm are covertical. Show how to determine the sets PL and PR and how to determine whether each point of Y is in PL or PR so that the running time for the closest-pair algorithm remains O(n lg n).
Consider the problem of computing the convex hull of a set of points in the plane that have been drawn according to some known random distribution. Sometimes, the number of points, or size, of the convex hull of n points drawn from such a distribution has expectation
Given a point p0 = (x0, y0), the right horizontal ray from p0 is the set of points {pi = (xi, yi) : xi ≥ x0 and yi = y0}, that is, it is the set of points due right of p0 along with p0 itself. Show how to determine whether a given right horizontal ray from p0 intersects a line
A disk consists of a circle plus its interior and is represented by its center point and radius. Two disks intersect if they have any point in common. Give an O(n lg n)-time algorithm to determine whether any two disks in a set of n intersect.
Show how to implement the incremental method for computing the convex hull of n points so that it runs in O(n lg n) time.
Suggest a change to the closest-pair algorithm that avoids presorting the Y array but leaves the running time as O(n lg n). Merge sorted arrays YL and YR to form the sorted array Y.
One way to determine whether a point p0 is in the interior of a simple, but not necessarily convex, polygon P is to look at any ray from p0 and check that the ray intersects the boundary of P an odd number of times but that p0 itself is not on the boundary
Given a set of n line segments containing a total of k intersections, show how to output all k intersections in O((n + k) lg n) time.
Argue that ANY-SEGMENTS-INTERSECT works correctly even if three or more segments intersect at the same point.
Show that ANY-SEGMENTS-INTERSECT works correctly in the presence of vertical segments if we treat the bottom endpoint of a vertical segment as if it were a left endpoint and the top endpoint as if it were a right endpoint.
Define the optimization problem LONGEST-PATH-LENGTH as the relation that associates each instance of an undirected graph and two vertices with the number of edges in a longest simple path between the two vertices. Define the decision problem LONGEST-PATH = {〈G, u, ν, k〉 : G = (V, E) is an
Consider the language GRAPH-ISOMORPHISM = {〈G1, G2〉 : G1 and G2 are isomorphic graphs}. Prove that GRAPH-ISOMORPHISM ∈ NP by describing a polynomial-time algorithm to verify the language.
The subgraph-isomorphism problem takes two undirected graphs G1 and G2, and it asks whether G1 is isomorphic to a subgraph of G2. Show that the subgraph-isomorphism problem is NP-complete.
An independent set of a graph G = (V, E) is a subset V′ ⊆ V of vertices such that each edge in E is incident on at most one vertex in V′. The independent-set problem is to find a maximum-size independent set in G.a. Formulate a related decision problem for the independent-set problem,
Give a formal definition for the problem of finding the longest simple cycle in an undirected graph. Give a related decision problem. Give the language corresponding to the decision problem.
Prove that if G is an undirected bipartite graph with an odd number of vertices, then G is nonhamiltonian.
Show that the ≤ P relation is a transitive relation on languages. That is, show that if L1 ≤ P L2 and L2 ≤ P L3, then L1 ≤ P L3.
Given an integer m × n matrix A and an integer m-vector b, the 0-1 integer-programming problem asks whether there exists an integer n-vector x with elements in the set {0, 1} such that Ax ≤ b. Prove that 0-1 integer programming is NP-complete.
Bonnie and Clyde have just robbed a bank. They have a bag of money and want to divide it up( For each of the following scenarios, either give a polynomial-time algorithm, or prove that the problem is NP-complete. The input in each case is a list of the n items in the bag, along with the value of
Give a formal encoding of directed graphs as binary strings using an adjacency matrix representation. Do the same using an adjacency-list representation. Argue that the two representations are polynomially related.
Show that if HAM-CYCLE ∈ P, then the problem of listing the vertices of a hamiltonian cycle, in order, is polynomial-time solvable.
Prove that L ≤ P L̅ if and only if L̅ ≤ P L.
Professor Jagger proposes to show that SAT ≤ P 3-CNF-SAT by using only the truth-table technique in the proof of Theorem 34.10, and not the other steps. That is, the professor proposes to take the boolean formula ϕ, form a truth table for its variables, derive from the truth table a formula in
Mapmakers try to use as few colors as possible when coloring countries on a map, as long as no two countries that share a border have the same color. We can model this problem with an undirected graph G = (V, E) in which each vertex represents a country and vertices whose respective countries share
Prove that the class NP of languages is closed under union, intersection, concatenation, and Kleene star. Discuss the closure of NP under complement.
Show that the problem of determining whether a boolean formula is a tautology is complete for co-NP.
Show how to solve the subset-sum problem in polynomial time if the target value t is expressed in unary.
Suppose that we have one machine and a set of n tasks a1, a2, . . . ,an, each of which requires time on the machine. Each task aj requires tj time units on the machine (its processing time), yields a profit of pj, and has a deadline dj. The machine can process only one task at a
Show that if an algorithm makes at most a constant number of calls to polynomial time subroutines and performs an additional amount of work that also takes polynomial time, then it runs in polynomial time. Also show that a polynomial number of calls to polynomial-time subroutines may result in an
Show that any language in NP can be decided by an algorithm running in time 2O(nk) for some constant k.
Show that the problem of determining the satisfiability of boolean formulas in disjunctive normal form is polynomial-time solvable.
The set-partition problem takes as input a set S of numbers. The question is whether the numbers can be partitioned into two sets A and A ̅ = S − A such that ∑x ∈ A x = Px ∈ A̅ x. Show that the set-partition problem is NP-complete.
Show that the class P, viewed as a set of languages, is closed under union, intersection, concatenation, complement, and Kleene star. That is, if L1, L2 ∈ P, then L1 ⋃ L2 ∈ P, L1 ⋂ L2 ∈ P, L1L2 ∈ P, L̅1 ∈ P, and L*1 ∈
A hamiltonian path in a graph is a simple path that visits every vertex exactly once. Show that the language HAM-PATH = {〈G, u, ν〉 : there is a Hamiltonian path from u to ν in graph G} belongs to NP.
A language L is complete for a language class C with respect to polynomial-time reductions if L ∈ C and L′ ≤ P L for all L′ ∈ C. Show that ; and {0, 1}* are the only languages in P that are not complete for P with respect to polynomial-time reductions.
Prove that Σ 2 i=1 + N
Suppose that someone gives you a polynomial-time algorithm to decide formula satisfiability. Describe how to use this algorithm to find satisfying assignments in polynomial time.
Show that the hamiltonian-path problem is NP-complete.
Let 2-CNF-SAT be the set of satisfiable boolean formulas in CNF with exactly 2 literals per clause. Show that 2-CNF-SAT 2 P. Make your algorithm as efficient as possible. Observe that x ∨ y is equivalent to ¬ x → y. Reduce 2-CNF-SAT to an efficiently solvable problem on a directed graph.
The longest-simple-cycle problem is the problem of determining a simple cycle (no repeated vertices) of maximum length in a graph. Formulate a related decision problem, and show that the decision problem is NP-complete.
Let Φ be a boolean formula constructed from the boolean input variables x1, x2, . . . ,xk, negations (¬), ANDs (∧), ORs (∨), and parentheses. The formula Φ is a tautology if it evaluates to 1 for every assignment of 1 and 0 to the input variables. Define TAUTOLOGY as the
The reduction algorithm F in the proof of Lemma 34.6 constructs the circuit C = f (x) based on knowledge of x, A, and k. Professor Sartre observes that the string x is input to F, but only the existence of A, k, and the constant
In the half 3-CNF satisfiability problem, we are given a 3-CNF formula ϕ with n variables and m clauses, where m is even. We wish to determine whether there exists a truth assignment to the variables of ϕ such that exactly half the clauses
Prove that P ⊆ co-NP.
Prove that if NP ≠ co-NP, then P ≠ NP.
Let G be a connected, undirected graph with at least 3 vertices, and let G3 be the graph obtained by connecting all pairs of vertices that are connected by a path in G of length at most 3. Prove that G3 is hamiltonian.
Consider each of the following words as a set of letters: {arid, dash, drain, heard, lost, nose, shun, slate, snare, thread}. Show which set cover GREEDY-SET-COVER produces when we break ties in favor of the word that appears first in the dictionary.
Suppose that we are given a set of n objects, where the size si of the i th object satisfies 0 < si < 1. We wish to pack all the objects into the minimum number of unit-size bins. Each bin can hold any subset of the objects whose total size does not exceed 1.a. Prove that the problem of
Show that even if we allow a clause to contain both a variable and its negation, randomly setting each variable to 1 with probability 1/2 and to 0 with probability 1/2 still yields a randomized 8/7-approximation algorithm.
Suppose that a complete undirected graph G = (V, E) with at least 3 vertices has a cost function c that satisfies the triangle inequality. Prove that c (u, ν) ≥ 0 for all u, ν ∈ V.
Let G = (V, E) be an undirected graph. For any k ≥ 1, define G(k) to be the undirected graph (V(k), E(k)), where V(k) is the set of all ordered k-tuples of vertices from V and E(k) is defined so that (ν1, ν2, . . . , νk) is adjacent to (w1, w2, . .
The MAX-CNF satisfiability problem is like the MAX-3-CNF satisfiability problem, except that it does not restrict each clause to have exactly 3 literals. Give a randomized 2-approximation algorithm for the MAX-CNF satisfiability problem.
Prove that the set of edges picked in line 4 of APPROX-VERTEX-COVER forms a maximal matching in the graph G.
Show how in polynomial time we can transform one instance of the traveling-salesman problem into another instance whose cost function satisfies the triangle inequality. The two instances must have the same set of optimal tours. Explain why such a polynomial-time transformation does not contradict
Show how to implement GREEDY-SET-COVER in such a way that it runs in time o(EseF IS1). SEF
Professor Bundchen proposes the following heuristic to solve the vertex-cover problem. Repeatedly select a vertex of highest degree, and remove all of its incident edges. Give an example to show that the professor’s heuristic does not have an approximation ratio of 2.
Consider the following closest-point heuristic for building an approximate traveling-salesman tour whose cost function satisfies the triangle inequality. Begin with a trivial cycle consisting of a single arbitrarily chosen vertex. At each step, identify the vertex u that is not on the cycle but
Show that the constraints in line (35.19) are redundant in the sense that if we remove them from the linear program in lines (35.17)-(35.20), any optimal solution to the resulting linear program must satisfy x(ν) ≤ 1 for each ν ∈ V .
How would you modify the approximation scheme presented in this section to find a good approximation to the smallest value not less than t that is a sum of some subset of the given input list?
Give an efficient greedy algorithm that finds an optimal vertex cover for a tree in linear time.
Suppose that the vertices for an instance of the traveling-salesman problem are points in the plane and that the cost c (u, ν) is the euclidean distance between points u and ν. Show that an optimal tour never crosses itself.
GREEDY-SET-COVER can return a number of different solutions, depending on how we break ties in line 4. Give a procedure BAD-SET-COVER-INSTANCE (n) that returns an n-element instance of the set-covering problem for which, depending on how we break ties in line 4, GREEDY-SET-COVER can return a number
In the?parallel-machine-scheduling problem, we are given?n?jobs,?J1, J2, . . . ,Jn, where each job?Jk has an associated nonnegative processing time of?pk. We are also given?m?identical machines,?M1, M2, . . . ,Mm. Any job can run on any machine. A?schedule?specifies, for each job?Jk, the machine on
Modify the APPROX-SUBSET-SUM procedure to also return the subset of S that sums to the value z*.
Let G = (V, E) be an undirected graph with distinct edge weights w (u, ν) on each edge (u, ν) ∈ E. For each vertex ν ∈ V, let max(ν) = max(u,ν) ∈ E {w(u, ν)} be the maximum-weight edge incident on that vertex. Let SG = {max(ν) : ν ∈ V} be the set of
Find a simple formula for? ΣΗ(k-1). -k=1
Show that ∑n k = 1 1/k2 is bounded above by a constant.
Give asymptotically tight bounds on the following summations. Assume that r ? 0 and s ? 0 are constants. a. b. c. η Σκ. in k=1
Show that by manipulating the harmonic series. Ek=1 1/(2k – 1) = In(n) + 0(1)
Find an asymptotic upper bound on the summation Llg n] E In/2*] . k=0
Show that Ef-ok²x* = x(1 + x)/(1 – x)³ for 0 < |x| < 1.
Show that the nth harmonic number is Ω(lg n) by splitting the summation.
Show that E,(k – 1)/2* = 0. k=0
Approximate ∑n k = 1 k3 with an integral.
Evaluate the sum E=1(2k + 1)x²2k

Showing 500 - 600 of 1549

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
Last

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