# 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.

Kruskal’s 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)

Prim’s 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 Prim’s 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 Kruskal’s algorithm can be the last edge added by Prim’s 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 Dijkstra’s 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 Dijkstra’s 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 Hardy’s 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 Dijkstra’s algorithm to find the shortest distances from the start vertex to all other vertices. Design a new linear time algorithm that will outperform Dijkstra’s algorithm.

Solution