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

Answer the following questions on the flow network N and flow f shown in Figure 16.6a: What are the forward and backward edges of augmenting path π? How many augmenting paths are there with respect to flow f? For each such path, list the sequence of vertices of the path and the residual
In 2006, the city of Beijing, China, instituted a policy that limits residents to own at most one dog per household. Imagine you are running an online pet adoption website for the city. Your website contains pictures of adorable puppies that are available for adoption, and it allows for dogless
What is the worst-case running time of the Ford-Fulkerson algorithm if all edge capacities are bounded by a constant?
Show that for a flow f, the total flow out of the source is equal to the total flow into the sink, that is, E f(e) = E f(e). ee E+(s) eƐE-(t)
Suppose Vojtech Jarnìk had an evil twin, named Stanislaw, who designed a divideand-conquer algorithm for finding minimum spanning trees. Suppose G is an undirected, connected, weighted graph, and, for the sake of simplicity, let us further suppose that the weights of the edges in G are distinct.
Suppose Joseph Kruskal had an evil twin, named Peter, who designed an algorithm that takes the exact opposite approach from his brother’s algorithm for finding an MST in an undirected, weighted, connected graph, G. Also, for the sake of simplicity, suppose the edges of G have distinct weights.
Suppose G is a weighted, connected, undirected graph with each edge having a unique integer weight, which may be either positive or negative. Let G be the same graph as G, but with each edge, e, in G having weight that is 1 greater than e’s weight in G. Show that G and G have the same minimum
Let G be a weighted, connected, undirected graph, and let V1 and V2 be a partition of the vertices of G into two disjoint nonempty sets. Furthermore, let e be an edge in the minimum spanning tree for G such that e has one endpoint in V1 and the other in V2. Give an example that shows that e is not
Give an example of weighted, connected, undirected graph, G, such that the minimum spanning tree for G is different from every shortest-path tree rooted at a vertex of G.
Suppose you are given a weighted graph, G, with n vertices and m edges, such that the weight of each edge in G is a real number chosen independently at random from the interval [0, 1]. Show that the expected running time of the PrimJarnìk algorithm on G is O(n log2 n + m), assuming the priority
Give an alternative pseudocode description of Kruskal’s algorithm that makes explicit use of the union and find operations.
Why do all the MST algorithms discussed in this chapter still work correctly even if the graph has negative-weight edges, and even negative-weight cycles?
Suppose, for a data approximation application, you are given a set of n points in the plane and you would like to partition these points into two sets, A and B, such that each point in A is as close or closer to another point in A than it is to any point in B, and vice versa. Describe an efficient
Consider a scenario where you have a set of n players in a multiplayer game that we would like to connect to form a team. You are given a connected, weighted, undirected graph, G, with n vertices and m edges, which represents the n players and the m possible connections that can be made to link
Show how to modify the Prim-Jarnìk algorithm to run in O(n2) time.
Suppose G is an undirected, connected, weighted graph such that the edges in G have distinct edge weights, which may be positive or negative. Show that the minimum spanning tree for G may be changed if we square all the edge weights in G, that is, G may have a different set of edges in its minimum
Imagine that you just joined a company, GT&T, which set up its computer network a year ago for linking together its n offices spread across the globe. You have reviewed the work done at that time, and you note that they modeled their network as a connected, undirected graph, G, with n vertices,
Suppose NASA wants to link n stations spread out over the solar system using free-space optical communication, which is a technology that involves shooting lasers through space between pairs of stations to facilitate communication. Naturally, the energy needed to connect two stations in this way
Suppose G is an undirected, connected, weighted graph such that the edges in G have distinct positive edge weights. Show that the minimum spanning tree for G is unchanged even if we square all the edge weights in G, that is, G has the same set of edges in its minimum spanning tree even if we
Suppose G is an undirected, connected, weighted graph such that the edges in G have distinct edge weights. Show that the minimum spanning tree for G is unique.
Suppose G is a weighted, connected, undirected, simple graph and e is a largestweight edge in G. Prove or disprove the claim that there is no minimum spanning tree of G that contains e.
Suppose you are a manager in the IT department for the government of a corrupt dictator, who has a collection of computers that need to be connected together to create a communication network for his spies. You are given a weighted graph, G, such that each vertex in G is one of these computers and
Suppose G is a weighted, connected, undirected graph and e is a smallest-weight edge in G. Show that there is a minimum spanning tree of G that contains e.
Consider the unsorted sequence implementation of the priority queue Q used in Dijkstra’s algorithm. In this case, why is the best-case running time of Dijkstra’s algorithm Ω(n2) on an n-vertex graph?
A part of doing business internationally involves the trading of different currencies, and the markets that facilitate such trades can fluctuate during a trading day in ways that create profit opportunities. For example, at a given moment during a trading day, 1 U.S. dollar might be worth 0.98
The dynamic programming algorithm of Algorithm 14.11 computes only shortest-path distances, not actual paths. Describe a version of this algorithm that outputs the set of all shortest paths between each pair of vertices in a directed graph. Your algorithm should still run in O(n3) time.Algorithm
The dynamic programming algorithm of Algorithm 14.11 uses O(n3) space. Describe a version of this algorithm that uses O(n2) space.Algorithm 14.11 Algorithm AllPairsShortestPaths(G): Input: A simple weighted directed graph G without negative-weight cycles Output: A numbering v1, v2, ..., Un of the
Draw a (simple) directed weighted graph G with 10 vertices and 18 edges, such that G contains a minimum-weight cycle with at least 4 edges. Show that the Bellman-Ford algorithm will find this cycle.
Suppose you live far from work and are trying to determine the best route to drive from your home to your workplace. In order to solve this problem, suppose further that you have downloaded, from a government website, a weighted graph, G, representing the entire road network for your state.
There is an alternative way of implementing Dijkstra’s algorithm that avoids use of the locator pattern but increases the space used for the priority queue, Q, from O(n) to O(m) for a weighted graph, G, with n vertices and m edges. The main idea of this approach is simply to insert a new
Show how to modify Dijkstra’s algorithm to not only output the distance from v to each vertex in G, but also to output a tree T rooted at v, such that the path in T from v to a vertex u is actually a shortest path in G from v to u.
Suppose that CONTROL, a secret U.S. government counterintelligence agency based in Washington, D.C., has build a communication network that links n stations spread across the world using m communication channels between pairs of stations. Suppose further that the evil spy agency, KAOS, is able to
In a side-scrolling video game, a character moves through an environment from, say, left-to-right, while encountering obstacles, attackers, and prizes. The goal is to avoid or destroy the obstacles, defeat or avoid the attackers, and collect as many prizes as possible while moving from a starting
Show that it is possible to count the total number of paths in a directed acyclic graph, G , with n vertices and m edges using O(n + m) additions. Also, show that there is a graph, G , where this number is at least 2n/2.
In the pseudocode description of the directed DFS traversal algorithm we did not distinguish the labeling of cross edges and forward edges. Describe how to modify the directed DFS algorithm so that it correctly labels each nontree edge as a back edge, forward edge, or cross edge.
The directed version of the BFS algorithm classifies nontree edges as being either back edges or cross edges, but it does not distinguish between these two types. Given a BFS spanning tree, T, for a directed graph, G , and a set of nontree edges, E , describe an algorithm that can correctly label
Show how to perform a BFS traversal using, as an auxiliary data structure, a single queue instead of the level containers L0, L1, ... .
Imagine that you are a medical practitioner for a developing country, Strategia, and it is your job to inoculate people in each village in Strategia so as to limit the ability of the Kissoba virus to spread in Strategia. The Kissoba virus can only be spread between two people if they kiss. For each
Show that if a graph G has at least three vertices, then it has a separation edge only if it has a separation vertex.
Suppose we represent a graph G having n vertices with an adjacency matrix. Why, in this case, would inserting an undirected edge in G run in O(1) time while inserting a new vertex would take O(n2) time?
Tamarindo University and many other schools worldwide are doing a joint project on multimedia. A computer network is built to connect these schools using communication links that form a free tree. The schools decide to install a file server at one of the schools to share data among all the schools.
Suppose you work for a company that is giving a smartphone to each of its employees. Unfortunately, the companies that make apps for these smartphones are constantly suing each other over their respective intellectual property. Say that two apps, A and B, are litigation-conflicting if A contains
Let G be a simple connected graph with n vertices and m edges. Explain why O(log m) is O(log n).
Suppose we are given an n-node rooted tree T, such that each node v in T is given a weight w(v). An independent set of T is a subset S of the nodes of T such that no node in S is a child or parent of any other node in S. Design an efficient dynamic programming algorithm to find the maximum-weight
A grammar G is a way of generating strings of “terminal” characters from a nonterminal symbol S, by applying simple substitution rules, called productions. If B → β is a production, then we can convert a string of the form αBγ into the string αβγ. A grammar is in Chomsky normal form if
How can we modify the dynamic programming algorithm from simply computing the best benefit value for the 0-1 knapsack problem to computing the assignment that gives this benefit?
Suppose n computers in a wired local-area network are arranged in a tree, T, which is rooted at one of these computers (say, one that is connected to the Internet). That is, the computers in this network form the nodes of T, and the edges of T are determined by the pairs of computers that have
Let A, B, and C be three length-n character strings taken over the same constantsized alphabet Σ. Design an O(n3)-time algorithm for finding a longest substring that is common to all three of A, B, and C.
A substring of some character string is a contiguous sequence of characters in that string (which is different than a subsequence, of course). Suppose you are given two character strings, X and Y , with respective lengths n and m. Describe an efficient algorithm for finding a longest common
Consider a variant of the coins-in-a-line game, which we are calling houses-ina-row. In this game, two real estate moguls, Alice and Bob, take turns divvying up n houses that are lined up in a row, with Alice going first. When it is a player’s turn, he or she must choose one or more of the
Speech recognition systems need to match audio streams that represent the same words spoken at different speeds. Suppose, therefore, that you are given two sequences of numbers, X = (x1, x2,...,xn), and Y = (y1, y2,...,ym), representing two different audio streams that need to be matched. A mapping
Sally is hosting an Internet auction to sell n widgets. She receives m bids, each of the form “I want ki widgets for di dollars,” for i = 1, 2,...,m. Characterize her optimization problem as a knapsack problem. Under what conditions is this a 0-1 versus fractional problem?
When data is transmitted across a noisy channel, information can be lost during the transmission. For example, a message that is sent through a noisy channel as “WHO PARKED ON HARRY POTTER’S SPOT? could be received as the message, “HOP ON POP''That is, some characters could be
Show that a sequence of n distinct numbers contains a decreasing or increasing subsequence of size at least [√n].
Consider a variant of the telescope scheduling problem, where we are given a list, L, of n observational requests for a large telescope, but now these requests are specified differently. Instead of having a start time, finish time, and benefit, each request i is now specified by a deadline, di, by
Suppose we define a probabilistic event so that V (i, 0) = 1 and V (0, j)=0, for all i and j, and V (i, j), for i, j ≥ 1, is defined as V (i, j)=0.5V (i − 1, j)+0.5V (i, j − 1). What is the probability of the event, V (2, 2)?
The pointy-haired boss (PHB) of an office in a major technology company would like to throw a party. Based on the performance reviews he has done, the PHB has assigned an integer “fun factor” score, F(x), for each employee, x, in his office. In order for the party to be as crazy as possible,
Suppose we are given a set of telescope observation requests, specified by triples of (si, fi, bi), defining the start times, finish times, and benefits of each observation request as L = {(1, 2, 5),(1, 3, 4),(2, 4, 7),(3, 5, 2),(1, 6, 3),(4, 7, 5),(6, 8, 7),(7, 9, 4)}. Solve the
Scientists performing DNA sequence alignment often desire a more parametrized way of aligning two strings than simply computing a longest common subsequence between these two strings. One way to achieve such flexibility is to use the Smith-Waterman algorithm, which is generalization of the dynamic
Show that we can solve the telescope scheduling problem in O(n) time even if the list of n observation requests is not given to us in sorted order, provided that start and finish times are given as integer indices in the range from 1 to n2.
Let S = {a, b, c, d, e, f, g} be a collection of objects with benefit-weight values, a: (12, 4), b : (10, 6), c : (8, 5), d: (11, 7), e: (14, 3), f : (7, 1), g : (9, 6). What is an optimal solution to the 0-1 knapsack problem for S assuming we have a sack that can hold objects with total weight 18?
The comedian, Demetri Martin, is the author of a 224-word palindrome poem. That is, like any palindrome, the letters of this poem are the same whether they are read forward or backward. At some level, this is no great achievement, because there is a palindrome inside every poem, which we explore in
Design an O(n)-time non-losing strategy for the first player, Alice, in the coinsin-a-line game. Your strategy does not have to be optimal, but it should be guaranteed to end in a tie or better for Alice.
Suppose that in an instance of the coins-in-a-line game the coins have the following values in the line: (9, 1, 7, 3, 2, 8, 9, 3). What is the maximum that the first player, Alice, can win, assuming that the second player, Bob, plays optimally?
An American spy is deep undercover in the hostile country of Phonemia. In order not to waste scarce resources, any time he wants to send a message back home, he removes all the punctuation from his message and converts all the letters to uppercase. So, for example, to send the
Show that, in the coins-in-a-line game, a greedy-denial strategy of having the first player, Alice, always choose the available coin that minimizes the maximum value of the coin available to Bob will not necessarily result in an optimal solution for her.
Suppose that during the playing of the coins-in-a-line game that Alice’s opponent, Bob, makes a choice that is suboptimal for him. Does this require that Alice recompute her table of remaining Mi,j values to plan her optimal strategy from this point on?
Every web browser and word processor needs a way of breaking English paragraphs into lines at word boundaries that is both fast and looks good. Some systems even have ways of hyphenating words to make good line breaks, but let us ignore that complication here. Say that the width of each line on a
Show that, in the coins-in-a-line game, a greedy strategy of having the first player, Alice, always choose the available coin with highest value will not necessarily result in an optimal solution (or even a winning solution) for her.
Suppose that the coins of the fictional country of Combinatoria come in the denominations, d1, d2,...,dk, where d1 = 1 and the other di values form a set of distinct integers greater than 1. Given an integer, n > 0, the problem of making change is to find the fewest number of Combinatorian coins
Binomial coefficients are a family of positive integers that have a number of useful properties and they can be defined in several ways. One way to define them is as an indexed recursive function, C(n, k), where the “C” stands for “choice” or “combinations.” In this case, the definition
Suppose you have a geometric description of the buildings of Manhattan and you would like to build a representation of the New York skyline. That is, suppose you are given a description of a set of rectangles, all of which have one of their sides on the x-axis, and you would like to build a
Give an example of a set of n points in the plane such that every point is a maximum point, that is, no point in this set is dominated by any other point in this set.
Suppose you have a high-performance computer, which has a CPU containing a dedicated bank of k > 2 optimization registers. This bank of registers supports the insertion of key-value pair, (x, y), into the bank of registers in O(1) time, assuming that there are fewer than k numbers already stored
What is the maxima set from the following set of points: {(7, 2),(3, 1),(9, 3),(4, 5),(1, 4),(6, 9),(2, 6),(5, 7),(8, 6)}?
Selecting out a maxima set of points from among a set of points in the plane seems is intended to filter away a lot of points from consideration in a multiobjective optimization problem. For example, if we grade hotels by the sizes of their pools and the quality of their restaurants, then we would
Consider the Stooge-sort algorithm, shown in Algorithm 11.5, and suppose we change the assignment statement for m (on line 6) to the following: m ← max{1, [n/4]} Characterize the running time, T(n), in this case, using a recurrence equation, and use the master theorem to determine an
A complex number a + bi, where i = √−1, can be represented by the pair (a, b). Describe a method performing only three real-number multiplications to compute the pair (e, f) representing the product of a + bi and c + di.
In some multi-objective optimization problems (such as that exemplified by the choosing of hotels based on the sizes of their pools and quality scores of their restaurants), we may have different kinds of constraints involving the variables instead of the desire to avoid points dominated by others.
There is a sorting algorithm, “Stooge-sort,” which is named after the comedy team, “The Three Stooges.” if the input size, n, is 1 or 2, then the algorithm sorts the input immediately. Otherwise, it recursively sorts the first 2n/3 elements, then the last 2n/3 elements, and then the first
Given a set, P, of n teams in some sport, a round-robin tournament is a collection of games in which each team plays each other team exactly once. Such round-robin tournaments are often used as the first round for establishing the order of teams (and their seedings) for later single- or
There are several cases of divide-and-conquer recurrence relations that are not covered in the master theorem. Nevertheless, the intuition for the master theorem can still give us some guidance. Derive and prove a general solution, like that given in the master theorem, to the following recurrence
A very common problem in computer graphics is to approximate a complex shape with a bounding box. For a set, S, of n points in 2-dimensional space, the idea is to find the smallest rectangle, R, with sides parallel to the coordinate axes that contains all the points in S. Once S is approximated by
Suppose you are organizing a party for a large group of your friends. Your friends are pretty opinionated, though, and you don’t want to invite two friends if they don’t like each other. So you have asked each of your friends to give you an “enemies” list, which identifies all the other
Consider the recurrence equation,
Indicate for each of the lemmas used in the proof of correctness for the Huffman coding algorithm whether the proof of that lemma uses an exchange argument or a lower-bound argument?
Consider again the time-travel problem of the previous exercise, but now consider a greedy algorithm that sorts the men by increasing heights and sorts the spears by increasing heights, and then assigns the ith spear in the ordered list of spears to the ith man in the ordered list of Roman
Repeat the previous exercise for the code words, 00, 100, 101, 11.Data From Previous ExerciseFred says that he ran the Huffman coding algorithm for the four characters, A, C, G, and T, and it gave him the code words, 0, 10, 111, 110, respectively. Give examples of four frequencies for these
Suppose you’ve been sent back in time and have arrived at the scene of an ancient Roman battle. Moreover, suppose you have just learned that it is your job to assign n spears to n Roman soldiers, so that each man has a spear. You observe that the men and spears are of various heights, and you
Repeat the previous exercise for the code words, 0, 10, 101, 111.Data From Previous ExerciseFred says that he ran the Huffman coding algorithm for the four characters, A, C, G, and T, and it gave him the code words, 0, 10, 111, 110, respectively. Give examples of four frequencies for these
Fred says that he ran the Huffman coding algorithm for the four characters, A, C, G, and T, and it gave him the code words, 0, 10, 111, 110, respectively. Give examples of four frequencies for these characters that could have resulted in these code words or argue why these code words could not
In the 2003 California gubernatorial recall election, the ballot contained 135 candidates, including people with various listings for their current job, including “actor,” “comedian,” and even “adult film actress.” The winner was the actorbusinessman Arnold Schwarzenegger, who got over
Give an example set of 8 characters and their associated frequencies so that the Huffman tree for this set is a complete binary tree.
Give an example set of 10 characters and their associated frequencies so that, in the Huffman tree for this set, every internal node has an external-node child.
Draw the frequency table and Huffman tree for the following string: "dogs do not spot hot pots or cats".
A floating-point number is a pair, (m, d), of integers, which represents the number m × bd, where b is either 2 or 10. In any real-world programming environment, the sizes of m and d are limited; hence, each arithmetic operation involving two floating-point numbers may have some roundoff error.
Given a character string X of length n, describe an O(n)-time algorithm to construct the set, C, of distinct characters that appear in C, along with a count, f(c), for each c in C, of how many times the character c appears in X. You may assume that the characters in X are encoded using a standard
Suppose we are given a set of tasks specified by pairs of the start times and finish times as T = {(1, 2),(1, 3),(1, 4),(2, 5),(3, 7),(4, 9),(5, 6),(6, 8),(7, 9)}. Solve the task scheduling problem for this set of tasks.
Consider a single machine scheduling problem, where we are given a set, T, of tasks specified by their start times and finish times, as in the task scheduling problem, except now we have only one machine and we wish to maximize the number of tasks that this single machine performs. Design a greedy
Suppose you are given an instance of the fractional knapsack problem in which all the items have the same weight. Show that you can solve the fractional knapsack problem in this case in O(n) time.

Showing 400 - 500 of 819

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

Step by Step Answers