Questions and Answers of Data Structures Algorithms

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
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
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,
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,
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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,
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
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
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
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
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)
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.
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
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
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
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
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,
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 ,
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,
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),
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
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
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
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
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”
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,
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
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
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
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
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
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,
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
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
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
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
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
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
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,
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
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),
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,
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
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
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
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.
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
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.
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
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
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
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
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,
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
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
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
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;
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
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
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
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