CS 277 TU Floyd Warshall and Graph Algorithms Questions

CS277 – Reading 5a1
Reading
For this lecture, we will have a bit of a reading and then work on exercises that are designed to
help prepare you for the midterm exam.
The reading is for CLRS, Introduction to Algorithms.
• Read pp 684 – 685 to introduce the all pairs shortest path (APSP) problem.
• Read pp 693 – 697 to review the Floyd-Warshall algorithm.
• Read pp 697 – 698 to review a way of calculating transitive closure of a graph using FloydWarshall algorithm.
2
Questions
1. Floyd-Warshall algorithm is simply a triple nested for loop that has a O(V 3 ) runtime. It does
not use any helper data structure, no fancy calculation, nothing. Despite its simplicity, it does
the Herculian job of calculating shortest path between ALL PAIRS OF NODES in a graph.
To put into perspective, this is equivalent to running Dijkstra’s algorithm for every node in
a graph! Remember how Dijkstra’s algorithm was using priority queues… Floyd-Warshall
achieves this goal by simply using a 2 dimensional array in a triple nested for loop!! In this
question, we will explore why this triple nested for loop achieves the desired goal.
(a) In your own words, explain what the outer most loop of the algorithm achieves relative to
the overall job that the algorithm performs? What does the inner nested for loop achieve?
(b) Memory complexity of Floyd-Warshall could be O(V 3 ) if done loosely, but O(V 2 ) can also
be achieved. Give an explanation for both cases.
(c) Transitive closure can be calculated using the Floyd-Warshall algorithm, as explained in
pages 697-698, which leads to a Θ(V 3 ) algorithm. However, if the graph is sparse, it is
possible to calculate transitive closure much cheaper. Suggest a O(V E) time algorithm
for computing transitive closure on a directed graph.
2. For each of the following statements, fill in the blank with whichever word makes the statement
true: “always”, “never”, or “sometimes”. If your answer is “always” or “never”, you must
explain why. If your answer is “sometimes”, you must give two examples: one where the
statement is true and one where the statement is false.
For example, the statement “A day in February is
a holiday” is sometimes true, because
February 14th (Valentine’s Day) is a holiday but February 15th isn’t.
1
(a) Given two asymptotically non-negative functions f and g, if ∀n ∈ R, f (n) < g(n), then f (n) is equal to o(g(n)). (b) Suppose G is a dag with more than one vertex. It is possible to reduce the number of strongly connected components to one by adding exactly one edge. (c) Given a graph G and a minimum spanning tree of that graph T , the path between two vertices in T is the shortest path between them in G. (d) If G is a directed graph with cycles, then G has a topological sorting. 3. (a) Prove that if f (n) = O(g(n)), then kf (n) = O(g(n)) for all positive constants k. (b) Explain what you have just proved in plain English. 4. Give a tight bound on the running time of each of the following algorithms and justify your answer using summations. Note: A return statement exits the function immediately. (a) foo1 1 Function foo1(L, n): 2 3 4 5 6 7 /* L is a list of n integers, starting at index 1 i := 1 x := 0 while i ≤ n do x := x + L[i] i := i + 2 return x */ (b) foo2 1 Function foo2(L, n): /* Assume n = 2k where 2 3 4 5 6 7 k is a non-negative integer i := n x := 0 while i > 1 do
x=x+1
i := i/2
return x
5. Consider the following pseudocode of binary search:
Page 2
*/
A is a sorted list of integers indexed from 1 to n
x is an integer
3 // Assume the function will always be initially called with p = 1, r = n
4 Function BinarySearch(A, x, p, r ):
5
q = floor((p + r)/2)
6
if p > r then
7
return false
8
if x < A[q] then 9 return BinarySearch(A, x, p, q - 1) 10 else if x > A[q] then
11
return BinarySearch(A, x, q + 1, r)
12
else
13
return true
1 //
2 //
(a) Give a recurrence of the following form to represent binary search’s worst case runtime:
(
aT ( nb ) + D(n) + C(n)
T (n) =
Θ(1)
n>1
n=1
Explain each of your choices for a, b, D(n), and C(n), where D(n) and C(n) represent the
runtime to divide and conquer each subproblem, respectively.
Note: Binary search will exit as soon as it finds x. If x is in A, the worst case occurs
when the subproblem size is reduced to 1, i.e. when it performed the maximum number
of recursive calls possible before it found x. You may ignore the case where x isn’t in A,
as this affects the worst case runtime by only a constant factor.
(b) Draw a recursion tree of your recurrence. You must label the total work done on each level
of the tree and the total number of levels, explaining your answers. Using your recursion
tree, prove a tight bound on the worst case runtime of binary search.
Page 3