Explore BrainMass
Share

# Describe an Algorithm

This content was STOLEN from BrainMass.com - View the original, and get the already-completed solution here!

The question is attached and there are some clarifications

1. The integers are NOT sorted and you CANNOT sort them. You need to see if the numbers would match the pattern if you were to sort them.
2. a and b can be any integer and we don't know the values in advance.

https://brainmass.com/computer-science/sorting/describe-algorithm-165449

#### Solution Preview

The basic idea is to find a and b in O(n) time.
Here is the description of the algorithm, with input array A[1..n] of n integers.
Step 1: Find the smallest element y1 in A[1..n], this will take O(n) time.
Step 2: Find the largest element y2 in A[1..n], this will take O(n) time
If y1=y2, then return true. ...

#### Solution Summary

The solution describes an algorithm.

\$2.19

## Algorithm Problem

Let G = (V, E) be a flow network with source s, sink t, and suppose each edge e &#61646; E has capacity c(e) = 1. Assume also, for convenience, that |E| = &#61527; (V).

a. Suppose we implement the Ford-Fulkerson maximum-flow algorithm by using depth-first search to find augmenting paths in the residual graph. what is the worst-case running time of this algorithm on G?

b. Suppose a maximum flow for G has been computed, and a new edge with unit capacity is added to E. Describe how the maximum flow can be efficiently updated. (Note: It is not the value of the flow that must be updated, but the flow itself.) Analyze your algorithm.

c. Suppose a maximum flow for G has been computed, but an edge is now removed form E. Describe how the maximum flow can be efficiently updated. Analyze your algorithm.

See attached file for full problem description.

View Full Posting Details