Questions and Answers of Algorithms

Although merge sort runs in Θ (n lg n) worst-case time and insertion sort runs in Θ(n2) worst-case time, the constant factors in insertion sort make it faster for small n. Thus, it makes
Consider the problem of making change for n cents using the fewest number of coins. Assume that each coin's value is an integer.a. Describe a greedy algorithm to make change consisting of quarters,
Binary search of a sorted array takes logarithmic search time, but the time to insert a new element is linear in the size of the array. We can improve the time for insertion by keeping several sorted
There are four basic operations on red-black trees that perform structural modifications: node insertions, node deletions, rotations, and color modifications. We have seen that RB-INSERT and
The off-line minimum problem asks us to maintain a dynamic set T of elements from the domain {1, 2, ..., n} under the operations INSERT and EXTRACT-MIN. We are given a sequence S of n INSERT and m
In the depth-determination problem, we maintain a forest F = (Ti) of rooted trees under three operations:• MAKE-TREE (v) creates a tree whose only node is v.• FIND-DEPTH (v) returns the depth of
Consider the problem of neatly printing a paragraph on a printer. The input text is a sequence of n words of lengths l1, l2, ..., ln, measured in characters. We want to print this paragraph neatly on
In order to transform one source string of text x [1 ¬ m] to a target string y [1 ¬ n], we can perform various transformation operations. Our goal is, given x and y, to produce a series of
Suppose that you are given an n × n checkerboard and a checker. You must move the checker from the bottom edge of the board to the top edge of the board according to the following rule. At each step
Suppose that instead of always selecting the first activity to finish, we instead select the last activity to start that is compatible with all previously selected activities. Describe how this
Suppose that we have a set of activities to schedule among a large number of lecture halls. We wish to schedule all the activities using as few lecture halls as possible. Give an efficient greedy
Not just any greedy approach to the activity-selection problem produces a maximum-size set of mutually compatible activities. Give an example to show that the approach of selecting the activity of
Given an m × n matrix T over some field (such as the reals), show that (S,ℓ) is a matroid, where S is the set of columns of T and A ¬ℓ if and only if the columns in A are linearly
Show that if (S, ℓ) is a matroid, then (S, ℓ′) is a matroid, where ℓ′ = {A′: S - A′ contains some maximal A ⁪ ¬ℓ}. That is, the maximal
Give a dynamic-programming solution to the 0–1 knapsack problem that runs in O (n W) time, where n is number of items and W is the maximum weight of items that the thief can put in his knapsack.
Professor Midas drives an automobile from Newark to Reno along Interstate 80. His car's gas tank, when full, holds enough gas to travel n miles, and his map gives the distances between gas stations
Show how to solve the fractional knapsack problem in O (n) time. Assume that you have a solution to Problem 9-2.
Suppose you are given two sets A and B, each containing n positive integers. You can choose to reorder each set however you like. After reordering, let ai be the ith element of set A, and let bi be
A sequence of n operations is performed on a data structure. The ith operation costs i if i is an exact power of 2, and 1 otherwise. Use aggregate analysis to determine the amortized cost per
A sequence of stack operations is performed on a stack whose size never exceeds k. After every k operations, a copy of the entire stack is made for backup purposes. Show that the cost of n stack
Suppose we wish not only to increment a counter but also to reset it to zero (i.e., make all bits in it 0). Show how to implement a counter as an array of bits so that any sequence of n INCREMENT and
Consider an ordinary binary min-heap data structure with n elements that supports the instructions INSERT and EXTRACT-MIN in O (lg n) worst-case time. Give a potential function Φ such that the
When an adjacency-matrix representation is used, most graph algorithms require time Ω (V2), but there are some exceptions. Show that determining whether a directed graph G contains a universal
The incidence matrix of a directed graph G = (V, E) is a |V| Ã— |E| matrix B = (bij) such thatDescribe what the entries of the matrix product B BT represent, where BT is the transpose of
Let G = (V, E) be an undirected, connected graph with weight function w : E → R, and suppose that |E| ≥ |V| and all edge weights are distinct. A second-best minimum spanning tree is
Suppose that a graph G has a minimum spanning tree already computed. How quickly can the minimum spanning tree be updated if a new vertex and incident edges are added to G?
Suppose that all edge weights in a graph are integers in the range from 1 to |V|. How fast can you make Prim’ s algorithm run? What if the edge weights are integers in the range from 1 to W for
Given a weighted, directed graph G = (V, E) with no negative-weight cycles, let m be the maximum over all pairs of vertices u, v ¬⁪ V of the minimum number of edges in a shortest path from u
The PERT chart formulation given above is somewhat unnatural. It would be more natural for vertices to represent jobs and edges to represent sequencing constraints; that is, edge (u, v) would
Suppose we change line 4 of Dijkstra' s algorithm to the following. 4 while |Q| > 1. This change causes the while loop to execute |V | - 1 times instead of |V | times. Is this proposed algorithm
We are given a directed graph G = (V, E) on which each edge (u, v) ¬ E has an associated value r(u, v), which is a real number in the range 0 ≤ r(u, v) ≤ 1 that represents the
Let G = (V, E) be a weighted, directed graph with weight function w: E → {0, 1, ..., W } for some nonnegative integer W . Modify Dijkstra' s algorithm to compute the shortest paths from a given
Modify your algorithm from Exercise 24.3-6 to run in O ((V + E) lg W ) time. (Hint: How many distinct shortest-path estimates can there be in V - S at any point in time?)
Express the single-pair shortest-path problem as a linear program.
Show how a system of difference constraints can be solved by a Bellman-Ford-like algorithm that runs on a constraint graph without the extra vertex v0.
Suppose that every row in the matrix A of a linear program Ax ≤ b corresponds to a difference constraint, a single-variable constraint of the form xi ≤ bk, or a single-variable constraint
Let G = (V, E) be a weighted, directed graph with source vertex s, and let G be initialized by INITIALIZE-SINGLE-SOURCE(G, s). Prove that if a sequence of relaxation steps sets π[s] to a non-NIL
As it appears above, the Floyd-War shall algorithm requires Θ (n3) space, since we compute for d (k) i, j, k = 1, 2,...,n. Show that the following procedure, which simply drops all the
Give an efficient algorithm to find the length (number of edges) of a minimum-length negative-weight cycle in a graph.
Show how to express the single-source shortest-paths problem as a product of matrices and a vector. Describe how evaluating this product corresponds to a Bellman-Ford-like algorithm (see Section
What does the matrix used in the shortest-paths algorithms correspond to in regular matrix multiplication?
A sequence is bitonic if it monotonically increases and then monotonically decreases, or if it can be circularly shifted to monotonically increase and then monotonically decrease. For example the
Arbitrage is the use of discrepancies in currency exchange rates to transform one unit of a currency into more than one unit of the same currency. For example, suppose that 1 U.S. dollar buys 46.4
b. Describe an efficient method to determine whether or not one d-dimensional box nests inside another.c. Suppose that you are given a set of n d-dimensional boxes {B1, B2,..., Bn}. Describe an
Suppose that we order the edge relaxations in each pass of the Bellman-Ford algorithm as follows. Before the first pass, we assign an arbitrary linear order v1, v2,..., v |v| to the vertices of the
Let G be an arbitrary weighted, directed graph with a negative-weight cycle reachable from the source vertex s. Show that an infinite sequence of relaxations of the edges of G can always be
Let G = (V, E) be a weighted, directed graph that contains no negative-weight cycles. Let s ¬ V be the source vertex, and let G be initialized by INITIALIZE-SINGLE-SOURCE (G, s). Prove that there
How can the output of the Floyd-War shall algorithm be used to detect the presence of a negative-weight cycle?
Professor Green street claims that there is a simpler way to re-weight edges than the method used in Johnson's algorithm. Letting w* = min (u, v)E {w(u, v)}, just define w(u, v) = w(u, v) - w* for
Professor Michener claims that there is no need to create a new source vertex in line 1 of JOHNSON. He claims that instead we can just use G′ = G and let s be any vertex in V [G]. Give an
Suppose that we wish to maintain the transitive closure of a directed graph G = (V, E) as we insert edges into E. That is, after each edge has been inserted, we want to update the transitive closure
Given a flow network G = (V, E), let f1 and f2 be functions from V × V to R. The flow sum f1 + f2 is the function from V × V to R defined by (26.4) (fi + f2) (u, v) = f1 (u, v) + f2(u, v) for all
Let f be a flow in a network, and let α be a real number. The scalar flow product, denoted α f, is a function from V × V to R defined by (αf)(u, v) = α • f (u, v). Prove that
Professor Adam has two children who, unfortunately, dislike each other. The problem is so severe that not only do they refuse to walk to school together, but in fact each one refuses to walk on any
Prove that for any pair of vertices u and v and any capacity and flow functions c and f, we have cf (u, v) + cf (v, u) = c(u, v) + c(v, u).
The edge connectivity of an undirected graph is the minimum number k of edges that must be removed to disconnect the graph. For example, the edge connectivity of a tree is 1, and the edge
Suppose that a flow network G = (V, E) has symmetric edges, that is, (u, v) ¬⁪ E if and only if (v, u) ¬⁪ E. Show that the Edmonds-Karp algorithm terminates after at most |V| |E|/4
Let G = (V, E) be a bipartite graph with vertex partition V = L R, and let G' be its corresponding flow network. Give a good upper bound on the length of any augmenting path found in G' during the
Prove that the generic pusher label algorithm spends a total of only O(V E) time in performing all the O(V2) relabel operations.
Suppose that a maximum flow has been found in a flow network G = (V, E) using a pusher label algorithm. Give a fast algorithm to find a minimum cut in G.
Show that line 7 of INITIALIZE-PREFLOW can be changed to 7 h[s] ← |V [G]| - 2 without affecting the correctness or asymptotic performance of the generic pusher label algorithm.
A path cover of a directed graph G = (V, E) is a set P of vertex-disjoint paths such that every vertex in V is included in exactly one path in P. Paths may start and end anywhere, and they may be of
Let G = (V, E) be a flow network with source s, sink t, and integer capacities. Suppose that we are given a maximum flow in G. a. Suppose that the capacity of a single edge (u, v) ⁪¬ E is
Let G = (V, E) be a flow network with source s, sink t, and an integer capacity c (u, v) on each edge (u, v) ¬ ⁪ E. Let C = max (u, v) ⁪ Ec (u, v). a. Argue that a minimum cut of G has
Prove that any sorting network on n inputs has depth at least lg n.
Prove that the number of comparators in any sorting network is Ω (n lg n).
We can represent an n-input comparison network with c comparators as a list of c pairs of integers in the range from 1 to n. If two pairs contain an integer in common, the order of the corresponding
Prove that a comparison network with n inputs correctly sorts the input sequence ⁪¬n, n - 1,..., 1¬ if and only if it correctly sorts the n - 1 zero-one sequences ⁪¬1, 0, 0,..., 0,
How many comparators are there in SORTER [n]?
Show that the depth of SORTER [n] is exactly (lg n) (lg n + 1)/2.
Argue that in a breadth-first search, the value d[u] assigned to a vertex u is independent of the order in which the vertices in each adjacency list are given. Using Figure 22.3 as an example, show
Give an example of a directed graph G = (V, E), a source vertex s ¬ V, and a set of tree edges E π ¬ E such that for each vertex v ¬ V, the unique path in the graph (V, E π) from s to v
There are two types of professional wrestlers: "good guys" and "bad guys." Between any pair of professional wrestlers, there may or may not be a rivalry. Suppose we have n professional wrestlers and
Show that edge (u, v) isa. a tree edge or forward edge if and only if d[u] < d[v] < f[v] < f[u],b. a back edge if and only if d[v] < d[u] < f[u] < f[v], andc. a cross edge if and only if d[v] < f[v]
Give a counterexample to the conjecture that if there is a path from u to v in a directed graph G, and if d[u] < d[v] in a depth-first search of G, then v is a descendant of u in the depth-first
Give a counterexample to the conjecture that if there is a path from u to v in a directed graph G, then any depth-first search must result in d[v] ≤ f[u].
Explain how a vertex u of a directed graph can end up in a depth-first tree containing only u, even though u has both incoming and outgoing edges in G.
Show that a depth-first search of an undirected graph G can be used to identify the connected components of G, and that the depth-first forest contains as many trees as G has connected components.
Give an algorithm that determines whether or not a given undirected graph G = (V, E) contains a cycle. Your algorithm should run in O (V) time, independent of |E|.
Another way to perform topological sorting on a directed acyclic graph G = (V, E) is to repeatedly find a vertex of in-degree 0, output it, and remove it and all of its outgoing edges from the graph.
Give an O (V + E)-time algorithm to compute the component graph of a directed graph G = (V, E). Make sure that there is at most one edge between two vertices in the component graph your algorithm
Given a directed graph G = (V, E), explain how to create another graph G′ = (V, E′) such that (a) G′ has the same strongly connected components as G, (b) G′ has the same
A directed graph G = (V, E) is said to be semi connected if, for all pairs of vertices u, v ¬⁪ V, we have u →v or v→ u. Give an efficient algorithm to determine whether or not G is
A depth-first forest classifies the edges of a graph into tree, back, forward, and cross edges. A breadth-first tree can also be used to classify the edges reachable from the source of the search
An Euler tour of a connected, directed graph G = (V, E) is a cycle that traverses each edge of G exactly once, although it may visit a vertex more than once. a. Show that G has an Euler tour if and
Let G = (V, E) be a directed graph in which each vertex u ⁪ ¬ V is labeled with a unique integer L(u) from the set {1, 2,..., |V|}. For each vertex u ¬⁪ V, let R(u) = (v ε V : u
Give a simple example of a graph such that the set of edges {(u, v): there exists a cut (S, V - S) such that (u, v) is a light edge crossing (S, V - S)} does not form a minimum spanning tree.
Show that a graph has a unique minimum spanning tree if, for every cut of the graph, there is a unique light edge crossing the cut. Show that the converse is not true by giving a counterexample.
Given a graph G and a minimum spanning tree T, suppose that we decrease the weight of one of the edges in T. Show that T is still a minimum spanning tree for G. More formally, let T be a minimum
Suppose that all edge weights in a graph are integers in the range from 1 to |V|. How fast can you make Kruskal’s algorithm run? What if the edge weights are integers in the range from 1 to W for
What is the meaning of each of the following error messages?• ######• #NAME?• #N/A• #REF!• #VALUE!• #NUM!• #DIV/0!
What new formula results for each of the following formulas if you copy it from cell C10 to cell E12? a. =A1+A2 b. =$A$1+A2 c. =$A1+A2 d. =A$1+A2
What formula would you write to do each of the following? a. Add a range of numbers in cells B2:B12. b. Find the largest value in cells C2:F2. c. Find the smallest value in cells A1 through X10. d.
Define the following terms: syntax, arguments, and algorithm.
Explain the difference between a €œwhat-if€ analysis and Goal Seek by giving an example based on the worksheet shown in Question 11.
List and describe the significance of each of Tufte’s five data graphics principles.
What are the differences between a bar chart and a column chart? Give an example of when you would use each one.
What are the differences between a column chart and an area chart? Give an example of when you would use each one.
How do pie charts differ from doughnut charts?
When should you use a 100% stacked line, column, or area chart? How do the 100% stacked charts differ from stacked charts?

Showing 100 - 200 of 575