辅导dynamic programming、讲解Floyd-Warshall、web编程语言辅导、讲解web/HTML语言
- 首页 >> 其他 Problem 6.4. Given an array A[1..n] of integers, we want to find the length L of the longest
contiguous interval of distinct numbers.
(1) Let P[i] be the maximum j such that j < i and A[j] = A[i], that is, the most recent
previous occurrence of the symbol A[i], scanning the array from left to tight. Show how to
compute P[i] in time O(n).
(2) Using (1), explain how to compute L in time O(n) using dynamic programming.
For both (1) and (2) you can have an error probability of 1/100.
Solution (1) Let h be a hash function mapping into an array T of size 100n
2
, initialized
to 0. For i = 1..n, we set P[i] to be T[h(A[i])] and then T[h(A[i])] = i. Since we are hashing
n numbers, the error probability is 1/100.
(2) Subproblems: Let S[i] be the minimum j, j < i such that the numbers A[j..i] are
distinct. In other words, i S[i] + 1 is the length of the longest interval of distinct numbers
ending at postition i.
Final answer: Once we have S[i] the final answer L is maxi i S[i] + 1.
Recursion: S[i] = S[i 1] if P[i] < S[i 1]. Otherwise S[i] = P[i] + 1.
There are O(n) subproblems, and the recursion time is O(1). So the total time is O(n).
7 Homework 5
Problem 7.1. (Difficulty 2) Run the Floyd-Warshall algorithm on the following graph.
Write down the five matrixes corresponding to the computation.
Problem 7.2. (Difficulty 3) Display a graph with negative weights and without any negative
cycles where Dijkstra’s shortest path algorithm returns the wrong value.
Problem 7.3. (Difficulty 3) You have to enter a cave which has many entrances A, and
many exits B. You have the entire map of the cave as a graph. You don’t like being in
the cave, and so you want to find the shortest way to enter the cave somewhere and exit it
somewhere.
51More formally, you are given an undirected, unweighted graph and two subsets of nodes,
A and B, which are disjoint. Give an efficient algorithm for computing the minimum distance
from A to B, defined as mina∈A,b∈B δ(a, b).
Problem 7.4. (Difficulty 2) Compute the maximum flow of the following flow network using
the Edmonds-Karp algorithm, where the source is S and the sink is T. Beginning with the
path (S, C, D, T) show the residual network after each flow augmentation. Write down the
maximum flow value.
T
Problem 7.5. (Difficulty 3) Let G = (V, E) be a flow network with source s and sink t.
We say that an edge e is a chokepoint if it crosses every minimum-capacity cut separating
s from t. Give an efficient algorithm to determine if a given edge e is a chokepoint in G.
(Hint: Use the max-flow min-cut theorem. What happens if you change the capacity of a
chokepoint edge?)
Problem 7.6. (Difficulty 3) [Modified from Erickson’s book] Suppose you are running a web
site that is visited by the same set of people every day. Each visitor claims membership in
one or more demographic groups; for example, a visitor might describe himself as male, 20–30
years old, a father, a resident of Massachusetts, an academic, a blogger, and a juggler. Your
site is supported by advertisers. Each advertiser has told you which demographic groups
should see its ads and how many, at least, of its ads you must show each day. Altogether,
there are n visitors, k demographic groups, and m advertisers. Describe an efficient algorithm
to determine, given all the data, whether you can show each visitor at most one ad per day,
so that every advertiser has its desired number of ads displayed, and every ad is seen by
someone in an appropriate demographic group.
52
contiguous interval of distinct numbers.
(1) Let P[i] be the maximum j such that j < i and A[j] = A[i], that is, the most recent
previous occurrence of the symbol A[i], scanning the array from left to tight. Show how to
compute P[i] in time O(n).
(2) Using (1), explain how to compute L in time O(n) using dynamic programming.
For both (1) and (2) you can have an error probability of 1/100.
Solution (1) Let h be a hash function mapping into an array T of size 100n
2
, initialized
to 0. For i = 1..n, we set P[i] to be T[h(A[i])] and then T[h(A[i])] = i. Since we are hashing
n numbers, the error probability is 1/100.
(2) Subproblems: Let S[i] be the minimum j, j < i such that the numbers A[j..i] are
distinct. In other words, i S[i] + 1 is the length of the longest interval of distinct numbers
ending at postition i.
Final answer: Once we have S[i] the final answer L is maxi i S[i] + 1.
Recursion: S[i] = S[i 1] if P[i] < S[i 1]. Otherwise S[i] = P[i] + 1.
There are O(n) subproblems, and the recursion time is O(1). So the total time is O(n).
7 Homework 5
Problem 7.1. (Difficulty 2) Run the Floyd-Warshall algorithm on the following graph.
Write down the five matrixes corresponding to the computation.
Problem 7.2. (Difficulty 3) Display a graph with negative weights and without any negative
cycles where Dijkstra’s shortest path algorithm returns the wrong value.
Problem 7.3. (Difficulty 3) You have to enter a cave which has many entrances A, and
many exits B. You have the entire map of the cave as a graph. You don’t like being in
the cave, and so you want to find the shortest way to enter the cave somewhere and exit it
somewhere.
51More formally, you are given an undirected, unweighted graph and two subsets of nodes,
A and B, which are disjoint. Give an efficient algorithm for computing the minimum distance
from A to B, defined as mina∈A,b∈B δ(a, b).
Problem 7.4. (Difficulty 2) Compute the maximum flow of the following flow network using
the Edmonds-Karp algorithm, where the source is S and the sink is T. Beginning with the
path (S, C, D, T) show the residual network after each flow augmentation. Write down the
maximum flow value.
T
Problem 7.5. (Difficulty 3) Let G = (V, E) be a flow network with source s and sink t.
We say that an edge e is a chokepoint if it crosses every minimum-capacity cut separating
s from t. Give an efficient algorithm to determine if a given edge e is a chokepoint in G.
(Hint: Use the max-flow min-cut theorem. What happens if you change the capacity of a
chokepoint edge?)
Problem 7.6. (Difficulty 3) [Modified from Erickson’s book] Suppose you are running a web
site that is visited by the same set of people every day. Each visitor claims membership in
one or more demographic groups; for example, a visitor might describe himself as male, 20–30
years old, a father, a resident of Massachusetts, an academic, a blogger, and a juggler. Your
site is supported by advertisers. Each advertiser has told you which demographic groups
should see its ads and how many, at least, of its ads you must show each day. Altogether,
there are n visitors, k demographic groups, and m advertisers. Describe an efficient algorithm
to determine, given all the data, whether you can show each visitor at most one ad per day,
so that every advertiser has its desired number of ads displayed, and every ad is seen by
someone in an appropriate demographic group.
52