Algorithm Design And Applications 1st Edition Michael T. Goodrich, Roberto Tamassia - Solutions

Suppose that a well-known collector, Kivas Fajo, is trying to collect each of 50 coupons, as in the coupon collector problem. Derive good upper and lower bounds on the expected number of times that Kivas has to visit the ticket window to get all 50 coupons.
Suppose you have a collection, S, of n distinct items and you create a random sample, R, of S, as follows: For each x in S, select it to belong to R independently with probability 1/n1/2. Derive bounds on the probability that the number of items in R is more than 2n1/2 or less than n1/2/2.
Suppose you have a collection, S, of n distinct items and you wish to select a random sample of these items of size exactly [n1/2]. Describe an efficient method for selecting such a sample so that each element in S has an equal probability of being included in the sample.
Give a Monte Carlo algorithm for the previous problem that examines at most [log n] entries in A and succeeds in finding a 1 in A with high probability.Data From Previous ProblemSuppose A is an array of n bits, half of which are 0’s and half of which are 1’s. But the bits in A can be in any
Suppose A is an array of n bits, half of which are 0’s and half of which are 1’s. But the bits in A can be in any order, so that the worst-case performance of any deterministic algorithm for finding a 1 in A is Θ(n). Give a Las Vegas algorithm that finds a 1 in A in O(log n) time with high
The Massachusetts state lottery game, Cash WinFall, used to have a way that anyone with enough money and time could stand a good chance of getting rich, and it is reported that an MIT computer scientist did just that. In this game, a player picks 6 numbers from the range from 1 to 46. If he matches
Consider a modification of the Fisher-Yates random shuffling algorithm where we replace the call to random(k + 1) with random(n), and take the for-loop down to 0, so that the algorithm now swaps each element with another element in the array, with each cell in the array having an equal likelihood
Suppose a builder, named Bob, wants to hammer in 20 nails into a piece of wood. Bob is very strong and can hammer down a nail in a single blow if he hits the nail square on its head. But Bob is also a little near-sighted and, in any given swing of his hammer, he only hits any given nail square on
In a famous experiment, Stanley Milgram told a group of people in Kansas and Nebraska to each send a postcard to a lawyer in Boston, but they had to do it by forwarding it to someone that they knew, who had to forward it to someone that they knew, and so on. Most of the postcards that were
Suppose a certain birth defect occurs independently at random with probability p = 0.02 in any live birth. Use a Chernoff bound to bound the probability that more than 4% of the 1 million children born in a given large city have this birth defect.
In the Mega Millions lottery game, a player picks five lucky numbers, in the range from 1 to 56, and one additional Mega number, in the range from 1 to 46. In order to win the jackpot, a player must match all six numbers. If there is no jackpot winner for a given drawing, then the jackpot is rolled
Suppose two teams, the Anteaters and the Bears, have a long rivalry in basketball. Suppose further that in any given game, the Anteaters will beat the Bears with probability 2/3, independent of any other games that they play. Give a bound on the probability that, in spite of this, the Bears will
A renowned food critic, Anton Ego, will enjoy a meal only if it is the highestquality meal he has ever eaten up to that point in his life. Assuming that the qualities of the n meals he eats in his life are distinct and come in a random order over the course of his life, what is the expected number
Suppose that Bob wants a constant-time method for implementing the random(k) method, which returns a random integer in the range [0, k − 1]. Bob has a source of unbiased bits, so to implement random(k), he samples [log k] of these bits, interprets them as an unsigned integer, K, and returns the
Show that the number of vertices of odd degree in a tree is even.
Suppose we are given the following collection of sets: What is the optimal solution to this instance of the SET-COVER problem and what is the solution produced by the greedy algorithm? S1 = {1, 2, 3, 4, 5, 6}, S2 = {5,6,8,9}, S3 = {1,4, 7, 10}, %3D %3D S4 = {2,5, 7, 8, 11}, S3 = {3,6,9, 12},
In the HITTING-SET problem, we are given a set U of items, and a collection of subsets of U, S1, S2,...,Sm. The problem is to find a smallest subset T of U such that T “hits” every subset Si, that is, T ∩ Si = ∅, for i = 1,...,m. Design a polynomial-time O(log n)-approximation
Consider a greedy algorithm for the VERTEX-COVER problem, where we repeatedly choose a vertex with maximum degree, add it to our cover, and then remove it and all its incident edges. Show that this algorithm does not, in general, produce a 2-approximation. Hint: Use a bipartite gra
Suppose G is an undirected weighted graph such that G is not the complete graph but every edge in G has positive weight. Create a complete graph, H, having the same vertex set as G, such that if (v, u) is an edge in G, then (v, u) has the same weight in H as in G, and if (v, u) is not an edge in G,
Suppose G is a complete undirected graph such that every edge has weight 1 or 2. Show that the weights in G satisfy the triangle inequality.
Consider the KNAPSACK problem, but now instead of implementing the PTAS algorithm given in the book, we use a greedy approach of always picking the next item that maximizes the ratio of value over weight (as in the optimal way to solve the fractional version of the KNAPSACK problem). Show that this
In the Euclidean traveling salesperson problem, cities are points in the plane and the distance between two cities is the Euclidean distance between the points for these cities, that is, the length of the straight line joining these points. Show that an optimal solution to the Euclidean TSP is a
Give a pseudocode description of the branch-and-bound algorithm for TSP.
Consider the astronomy application of METRIC-TSP, as in the previous exercise, but now suppose that you have an improvement to your supervisor’s nearestneighbor idea. Your nearest-neighbor greedy algorithm works like this: you start with city number 1 and add cities one at time, always
In the bottleneck traveling salesperson problem (TSP), we are given an undirected graph G with weights on its edges and asked to find a tour that visits the vertices of G exactly once and returns to the start so as to minimize the cost of the maximum-weight edge in the tour. Assuming that the
Give a recursive pseudocode description of the backtracking algorithm, assuming the search strategy should visit configurations in a depth-first fashion.
Suppose you are preparing an algorithm for the problem of optimally drilling the holes in an aluminum plug plate to allow it to do a spectrographic analysis of a set of galaxies. Based on your analysis of the robot drill device, you notice that the various amounts of time it takes to move between
Give a pseudocode description of the backtracking algorithm for CNF-SAT.
Suppose you work for a major package shipping company, FedUP, as in the previous exercise, but suppose there is a new law that requires every truck to carry no more than M pounds, even if it has room for more boxes. Now the optimization problem is to use the fewest number of trucks possible to
Derive an efficient branch-and-bound algorithm for the KNAPSACK optimization problem.
Draw an example of a graph with 10 vertices and 20 edges that has a Hamiltonian cycle. Also, draw an example of a graph with 10 vertices and 20 edges that does not have a Hamiltonian cycle.
Suppose you have n rooms that you would like to connect in a communication network in one of the dormitories of Flash University. You have modeled the problem using a connected, undirected graph, G, where each of the n vertices in G is a room and each of the m edges in G is a possible connection
Suppose you are given a connected weighted undirected graph, G, with n vertices and m edges, such that the weight of each edge in G is an integer in the interval [1, c], for a fixed constant c > 0. Show how to solve the single-source shortestpaths problem, for any given vertex v, in G, in time
Suppose, at some distance point in the future, the World Series in major league baseball becomes a best-of-n series, where n is an arbitrary odd number set by the Commissioner of Baseball in that year, based on advertising revenue. Suppose the Anteaters and the Bears are meeting in the World Series
Give a complete, weighted graph G, such that its edge weights satisfy the triangle inequality but the MST-based approximation algorithm for TSP does not find an optimal solution.
Derive an efficient backtracking algorithm for the KNAPSACK decision problem.
Give an example of a graph G with at least 10 vertices such that the greedy 2- approximation algorithm for VERTEX-COVER given above is guaranteed to produce a suboptimal vertex cover.
Suppose you work for a major package shipping company, FedUP, and it is your job to ship a set of n boxes from Rhode Island to California using a given collection of trucks. You know that these trucks will be weighed at various points along this route and FedUP will have to pay a penalty if any of
In a synchronous optical network (SONET) ring, a collection of routers are connected with fiber-optic cables to form a single, simple cycle. A message between two routers, x and y, can then be transmitted by routing it clockwise or counter-clockwise around the ring. Given a set, M, of messages to
Derive an efficient backtracking algorithm for the HAMILTONIAN-CYCLE problem.
Suppose you are working for a cartography company, that is, a company that makes maps. Your job is to design a software package that can take as input the map of some region, R, and label as many of the cities of R as possible. Each of the n cities in such a region, R, is given by an (x, y)
Consider the general optimization version of the TSP problem, where the underlying graph need not satisfy the triangle inequality. Show that, for any fixed value δ ≥ 1, there is no polynomial-time δ-approximation algorithm for the general TSP problem unless P = NP.
The Manhattan distance between two points (a, b) and (c, d) in the plane is |a − c| + |b − d|. Using Manhattan distance to define the cost between every pair of points, find an optimal traveling salesperson tour of the following set of points: {(1, 1),(2, 8),(1, 5),(3, −4),(5, 6),(−2,
Given a graph G and two distinct vertices, v and w in G, define HAMILTONIANPATH to be the problem of determining whether there is a path that starts at v and ends at w and visits all the vertices of G exactly once. Show that the HAMILTONIAN-PATH problem is NP-complete.
Consider the special case of TSP where the vertices correspond to points in the plane, with the cost defined on an edge for every pair (p, q) being the usual Euclidean distance between p and q. Show that an optimal tour will not have any pair of crossing edges.
Show that the SUBSET-SUM problem is in NP.
Show that the KNAPSACK problem is solvable in polynomial time if the input is given in a unary encoding. That is, show that KNAPSACK is not strongly NPhard. What is the running time of your algorithm?
Show that the SUBSET-SUM problem is solvable in polynomial time if the input is given in a unary encoding. That is, show that SUBSET-SUM is not strongly NP-hard. What is the running time of your algorithm?
Show that the SET-COVER problem is in NP.
Is there a subset of the numbers in {23, 59, 17, 47, 14, 40, 22, 8} that sums to 100? What about 130? Show your work.
Show that the HAMILTONIAN-CYCLE problem on directed graphs is NP-complete.
Professor Amongus has just designed an algorithm that can take any graph G with n vertices and determine in O(nk) time whether G contains a clique of size k. Does Professor Amongus deserve the Turing Award for having just shown that P = NP? Why or why not?
Define PARTITION as the problem that takes a set S = {s1, s2,...,sn} of numbers and asks whether there is a subset T of S such that That is, it asks whether there is a partition of the numbers into two groups that sum to the same value. Show that PARTITION is NP-complete. Σ Σ Si Si s;ET
Draw an example of a graph with 10 vertices and 15 edges that has a clique of size 6.
Define HYPER-COMMUNITY to be the problem that takes a collection of n web pages and an integer k, and determines if there are k web pages that all contain hyperlinks to each other. Show that HYPER-COMMUNITY is NP-complete.
Define INDEPENDENT-SET as the problem that takes a graph G and an integer k and asks whether G contains an independent set of vertices of size k. That is, G contains a set I of vertices of size k such that, for any v and ω in I, there is no edge (v, ω) in G. Show that INDEPENDENT-SET is
Draw an example of a graph with 10 vertices and 15 edges that has a vertex cover of size 2.
Define SUBGRAPH-ISOMORPHISM as the problem that takes a graph, G, and another graph, H, and determines if H is isomorphic to a subgraph of G. That is, the problem is to determine whether there is a one-to-one mapping, f, of the vertices in H to a subset of the vertices in G such that, if (v, w) is
Suppose an oracle has given you a magic computer, C, that when given any Boolean formula B in CNF will tell you in one step whether B is satisfiable. Show how to use C to construct an actual assignment of satisfying Boolean values to the variables in any satisfiable formula B. How many calls do you
Show that the CLIQUE problem is in NP.
Consider the problem DNF-DISSAT, which takes a Boolean formula S in disjunctive normal form (DNF) as input and asks whether S is dissatisfiable, that is, there is an assignment of Boolean values to the variables of S so that it evaluates to 0. Show that DNF-DISSAT is NP-complete.
Show how to construct a Boolean circuit C such that, if we create variables only for the inputs of C and then try to build a Boolean formula that is equivalent to C, then we will create a formula exponentially larger than an encoding of C.
Imagine that you are a Hollywood movie producer who is trying to decide how your new movie should end. To help you make this decision, you would like to assemble a group of movie-goers together to do a focus group. To avoid biases, you have asked that the group be selected so that no two people in
Show that every language L in P is polynomial-time reducible to the language M = {5}, that is, the language that simply asks whether the binary encoding of the input is equal to 5.
Suppose you are computer security expert working for a major company, CableClock, any you have just discovered that many of the computers at CableClock are infected with malware that must have come from users visiting unsafe websites. For each infected computer, you are given a log file that lists
Consider the problem DNF-SAT, which takes a Boolean formula S in disjunctive normal form (DNF) as input and asks whether S is satisfiable. Describe a deterministic polynomial-time algorithm for DNF-SAT.
Suppose a friend of yours is rushing for one of the university fraternities, Tau Nu Tau (TNT). His job for this week is to arrange all the bottles in the TNT beerbottle collection in a circle, subject to the constraint that each pair of consecutive bottles must be for beers that were both drunk in
Show that the problem SAT, which takes an arbitrary Boolean formula S as input and asks whether S is satisfiable, is NP-complete.
Show that we can deterministically simulate in polynomial time any nondeterministic algorithm A that runs in polynomial time and makes at most O(log n) calls to the choose method, where n is the size of the input to A.
Consider the trophy-choosing problem from the previous exercise, but now suppose that each of the prestige scores is an integer in the range from 1 to 10. Describe how you can solve this version of the problem in polynomial time.Data From Previous ExerciseSuppose the football coach for the
Use a truth table to convert the Boolean formula B = (a ↔ (b + c)) into an equivalent formula in CNF. Show the truth table and the intermediate DNF formula for B.
Using the definition of a c-incremental algorithm from the previous exercise, show that, if a c-incremental algorithm A has a worst-case running time t(N) in the RAM model, as a function of the number of input items, N, for some constant c > 0, then A has running time O(n2t(n)), in terms of the
Suppose the football coach for the Anteaters has heard about your abilities to solve challenging problems and has hired you to write a computer program that can decide which of their many trophies to feature on their prized trophy shelf. He is asking that you do this as a computer program, rather
Professor Amongus has shown that a decision problem L is polynomial-time reducible to an NP-complete problem M. Moreover, after 80 pages of dense mathematics, he has also just proven that L can be solved in polynomial time. Has he just proven that P = NP ? Why, or why not?
Let n denote the size of an input in bits and N denote the size in a number of items. Define an algorithm to be c-incremental if any primitive operation involving one or two objects represented with b bits results in an object represented with at most b + c bits, for c ≥ 0. Show that an algorithm
Imagine that the annual university job fair is scheduled for next month and it is your job to book companies to host booths in the large Truman Auditorium during the fair. Unfortunately, at last year’s job fair, a fight broke out between some people from competing companies, so the university
Illustrate the execution of the minimum-cost flow algorithm based on successive augmentations along minimum-cost paths for the flow network of Figure 16.2, where the cost of an edge (u, v) is given by |deg(u) − deg(v)|. Figure 16.2 2 5 5 3 3 6
Illustrate the execution of the minimum-cost flow algorithm based on successive augmentations along negative-cost cycles for the flow network of Figure 16.16a. Figure 16.16a. 0/1, 3 0/2, 1 0/3, 1 3. 0/2, 1 0/1, 3 (а)
A vertex cover for a graph, G, is a set of vertices, C, such that every edge in G is incident to one of the vertices in C. The problem of finding a smallest vertex cover is useful in network monitoring and other applications, but it is a difficult problem for general graphs. Show that the problem
Illustrate the execution of the Edmonds-Karp algorithm in the flow network of Figure 16.8a. Figure 16.8a 0/1 beta alpha 0/1 0/2 0/1 0/2 gamma delta sink 0/2 0/4 0/1 0/4 source 0/2 0/1 0/4 theta omega 0/2 (a)
In the context of the baseball elimination problem, one can show that if wi+gi ≤ wk + gk and team k is eliminated, then team i is also eliminated. Use this fact to show that among a set of n teams, one can determine all the eliminated teams by solving O(log n) maximum flow problems.
Illustrate the execution of the Ford-Fulkerson algorithm in the flow network of Figure 16.11b. Figure 16.11b H: Y
Show that in a flow network with noninteger capacities, the Ford-Fulkerson algorithm may not terminate.
Let G be a complete bipartite graph such that |X| = |Y | = n and for each pair of vertices x ∈ X and y ∈ Y , there is an edge joining x and y. Show that G has n! distinct maximum matchings.
Find two maximum matchings for the bipartite graph of Figure 16.11a that are different from the maximum matching of Figure 16.11b. G: H: X Y Y
A limousine company must process pickup requests every day, for taking customers from their various homes to the local airport. Suppose this company receives pickup requests from n locations and there are n limos available, where the distance of limo i to location j is given by a number, dij.
Give an algorithm that determines, in O(n + m) time, whether a graph with n vertices and m edges is bipartite.
Show that, given a maximum flow in a network with m edges, a minimum cut of N can be computed in O(m) time.
Suppose a friend of yours has created a simulation game based on J.R.R. Tolkien’s epic The Lord of the Rings. The game environment is Middle Earth, which is populated by various noble creatures, including hobbits, humans, dwarves, and elves. Unfortunately, these noble creatures are under attack
Given a flow network N and a maximum flow f for N, suppose that the capacity of an edge e of N is decreased by one, and let N' be the resulting network. Give an algorithm for computing a maximum flow in network N' by modifying f.
Find a minimum cut in the flow network of Figure 16.8a. Figure 16.8a 0/1 beta alpha 0/1 0/2 0/1 0/2 gamma delta sink 0/2 0/1 0/4 source 0/2 0/4/ 0/1 0/4 theta omega 0/2 (a)
Suppose, as an interview question, you are told that you have a goat and a wolf that need to go from a node, s, to a node, t, in a directed acyclic graph, G. To avoid the wolf eating the goat, their paths must never share an edge. Describe a polynomial-time algorithm for finding two edge-disjoint
You want to increase the maximum flow of a network as much as possible, but you are only allowed to increase the capacity of one edge. a. How do you find such an edge? (Give pseudocode.) You may assume the existence of algorithms to compute max flow and min cut. What’s the running time of
Draw a flow network with 9 vertices and 12 edges. Illustrate an execution of the Ford-Fulkerson algorithm on it.
Imagine that you are working on creating a flow for a set of packets in a media stream, as described in the introduction to this chapter. So you are given a network, G, with a source, s, and sink, t, together with bandwidth constraints on each edge, which indicate the maximum speed that the
Show that the Ford-Fulkerson algorithm runs in time O(m2 log n log |f ∗|) when, at each iteration, the augmenting path with the largest residual capacity is chosen.
Illustrate the execution of the Ford-Fulkerson algorithm in the flow network of Figure 16.2. Figure 16.2. 2 7 5 5 3 3 6 8 9. 5.
Consider the previous exercise, but suppose the city of Irvine, California, changed its dog-owning ordinance so that it still allows for residents to own a maximum of three dogs per household, but now restricts each resident to own at most one dog of any given breed, such as poodle, terrier, or
Let N be a flow network with n vertices and m edges. Show how to compute an augmenting path with the largest residual capacity in O((n + m) log n) time.
The city of Irvine, California, allows for residents to own a maximum of three dogs per household without a breeder’s license. Imagine you are running an online pet adoption website for the city, as in the previous exercise, but now for n Irvine residents and m puppies. Describe an efficient

Showing 300 - 400 of 819

Algorithm Design And Applications 1st Edition Michael T. Goodrich, Roberto Tamassia - Solutions

Step by Step Answers