代写dynamic programming、代做Floyd-Warshall、web编程语言代写、代做web/HTML语言

日期：2019-04-15 10:39

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.

51

More 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