[SOLVED] CS algorithm Analysis of Algorithms

Analysis of Algorithms
V. Adamchik CSCI 570
Lecture 5
University of Southern California
Greedy Algorithms
Reading: chapter 4

Homework 2
We do not have enough time to cover the master theorem this week. Therefore, you do not need to solve the last homework problem #5, it will be a part of the next Hw-3 assignment.

The Minimum Spanning Tree
Find a spanning tree of the minimum total weight.
MST is fundamental problem with diverse applications.

Kruskals Algorithm algorithm builds a tree one EDGE at a time.
Sort all edges by their weights.
Loop:
Choose the minimum weight edge and join correspondent vertices (subject to cycles).
Go to the next edge.
Continue to grow the forest until all vertices are connected.
Sorting edges O(E log E)
Cycle detection O(V) for each edge
Total: O(V*E + E*log E)

Prims Algorithm
algorithm builds a tree one VERTEX at a time.
Start with an arbitrary vertex as a sub-tree C.
Expand C by adding a vertex having the minimum weight edge of the graph having exactly one end point in C.
Update distances from C to adjacent vertices.
Continue to grow the tree until C gets all vertices.
deleteMin O(V), for each vertex update(decreaseKey) O(log V ), for each edge
Total: O(V log V + E log V)

Discussion Problem
Assume that an unsorted array is used instead of a binary heap. What would the running time of the Prim algorithm?
Assume that we need to find an MST in a dense graph using Prims algorithm. Which implementation (heap or array) shall we use?

MST: Proof of the correctness
A cut of a graph is a partition of its vertices into two disjoint sets (blue and green vertices below.)
A crossing edge is an edge that connects a vertex in one set with a vertex in the other.
The smallest crossing edge must be in the MST.
a
1
b2c1d
357 e3f
4
2

MST: Proof of the correctness Lemma: Given any cut in a weighted graph , the crossing
edge of minimum weight is in the MST of the graph.
G-X
X
e
v u

Review Questions
(T/F) The first edge added by Kruskals algorithm can be the last edge added by Prims algorithm.
(T/F) Suppose we have a graph where each edge weight value appears at most twice. Then, there are at most two minimum spanning trees in this graph.
(T/F) If a connected undirected graph G = (V, E) has V + 1 edges, we can find the minimum spanning tree of G in O(V) runtime.

The Shortest Path Problem
Edsger Dijkstra (1930-2002)

The Shortest Path Problem
Given a positively weighted graph G with a source vertex s, find the shortest path from s to all other vertices in the graph.
1
24 2
5 19
11
9
S
18 14
2
30
4
5
3
16
20
5
16
6
6 44 7

The Shortest Path Problem
What is the shortest distance from s to 4?
1
24 2
5 19
11
9
S
18 14
2
30
4
5
3
16
20
5
16
6
6 44 7

Greedy Approach
When algorithm proceeds all vertices are divided into two groups
vertices whose shortest path from the source is known
vertices whose shortest path from the source is NOT discovered yet
Move vertices one at a time from the undiscovered set of vertices to the known set of the shortest distances, based on the shortest distance from the source.

solution tree = s
heap = {1, 2, 3, 4, 5, 6, 7}

24 2 1
9
0
s
14
18
5 30
2
19
5

3
11 16
5 16
4 20

6 44 7
6

solution tree = { s }
heap = {1, 2, 3, 4, 5, 6, 7}
decreaseKey

9
24 2 1
9
14
s
14 18
5 30
2
19
5

3
11 16
5 16
4 20
16
6 44 7
6

solution tree = { s }
heap = {1, 2, 3, 4, 5, 6, 7}
deleteMin

24 2 1
9
9
14
s
14 18
5 30
2
19
5

3
5 16
4 20
11 16
16
6 44 7
6

solution tree = { s, 1 } heap = {2, 3, 4, 5, 6, 7}
24 2 1

9
9
14
s
14 18
5 30
2
19
5

3
5 16
4 20
11 16
16
6 44 7
6

solution tree = { s, 1 } heap = {2, 3, 4, 5, 6, 7}
9
1
decreaseKey 24 2
5

3
33
9
14
s
14 18
5 30
2
19
11 16
5 16
4 20
16
6 44 7
6

solution tree = { s, 1 } heap = {2, 3, 4, 5, 6, 7}
24 2
1 deleteMin
9 1418 14 5 30
9
4 16
33
2
19
5

3
11 16
s
16 5 20
6

6 44 7

solution tree = { s, 1, 5 } heap = {2, 3, 4, 6, 7}
24 2 1
9
33
9
14
s
14 18
5 30
2
19
5

3
5 16
4 20
11 16
16
6 44 7
6

solution tree = { s, 1, 5 } heap = {2, 3, 4, 6, 7}
24 2 1
32
9
9
14
s
5 16
14 18
5 30
4
44
2
19
11
5

3
16
20
16
6 44 7
6 deleteMin

solution tree = { s, 1, 5, 6 } heap = {2, 3, 4, 7}
32
24 2 91
9 14182 14 5 30
s 436
16 5 20
5
19
11

3
6
16
16
44 7
6
60

solution tree = { s, 1, 5, 6, 2, 4, 3, 7 } heap = {}
32
14182 5
530 19 45
24 2 91
9
14
s
5 16
34 11 3 4
16
20
16
50
7
6
6
44

Complexity
Let D(v) denote a length from the source s to vertex v. We store distances D(v) in a binary heap.

Discussion Problem
Assume that an unsorted array is used instead of a binary heap. What would the running time of the Dijkstra algorithm?

Proof of Correctness
Lemma. For each node u S (solution tree), d(u) is the shortest s-u path.
P
d

S
26

Proof of Correctness
s
S
u
v
27

Discussion Problem 1
You are given a graph representing the several career paths available in industry. Each node represents a position and there is an edge from node v to node u if and only if v is a pre-requisite for u. Top positions are the ones which are not pre-requisites for any positions. Start positions are the ones which have no pre- requisites. The cost of an edge (v,u) is the effort required to go from one position v to position u. Salma wants to start a career and achieve a top position with minimum effort. Using the given graph can you provide an algorithm with the same run time complexity as Dijkstras algorithm?

8
VP1
758654 8
CEO
COO CTO
6
10
132
Dir2
6
142
Prog
VP2 VP3 VP4
4754
VP5
5
3
QA
Dir1
Dir3
Dir4
MKT
ADV

Discussion Problem 2
Design a linear time algorithm to find shortest distances in a DAG.
3a S547
e -1 -3 d
22b
6
1
c

Review Questions
(T/F) If all edges in a connected undirected graph have distinct positive weights, the shortest path between any two vertices is unique.
(T/F) Suppose we have calculated the shortest paths from a source to all other vertices. If we modify the original graph, G, such that weights of all edges are increased by 2, then the shortest path tree of G is also the shortest path tree of the modified graph.
(T/F) Suppose we have calculated the shortest paths from a source to all other vertices. If we modify the original graph G such that weights of all edges are doubled, then the shortest path tree of G is also the shortest path tree of the modified graph.

Discussion Problem 3
Why Dijkstras greedy algorithm does not work on graphs with negative weights?
S5A 5
3
C -9 B

Discussion Problem 4
In this problem you are to find the most efficient way to deliver power to a network of n cities. It costs pi
to open up a power plant at city i. It costs cij 0 to put a cable between cities i and j. A city is said to have power if either it has a power plant, or it is connected by a series of cables to some other city with a power plant. Devise an efficient algorithm for finding the minimum cost to power all the cities.

Discussion Problem 5
Hardy decides to start running to work in San Francisco to get in shape. He prefers a route to work that goes first entirely uphill and then entirely downhill. To guide his run, he prints out a detailed map of the roads between home and work. Each road segment has a positive length, and each intersection has a distinct elevation. Assuming that every road segment is either fully uphill or fully downhill, give an efficient algorithm to find the shortest path that meets Hardys specifications.

3
0 9 10 8 1
57 6
Home
Work
4

Discussion Problem 6
Given a graph G=(V,E) whose edge weights are integers in the range [0, W], where W is a relatively small integer number compare to the number of vertices, W = O(1). We could run Dijkstras algorithm to find the shortest distances from the start vertex to all other vertices. Design a new linear time algorithm that will outperform Dijkstras algorithm.

Solution