Optimal Coin Payment using Greedy Algorithm

1. Greedy Algorithms Pasi Frnti 8.10.2013

2. Greedy algorithm 1. Coin problem 2. Minimum spanning tree 3. Generalized knapsack problem 4. Traveling salesman problem

3. Task: Given a coin set, pay the required amount (36 snt) using least number of coins. Coin problem

4. 25 1 10 Coin problem Another coin set Amount to be paid: 30 Greedy: Optimal:

5. Blank space for notes

6. Minimum spanning tree When greedy works Needs problem definition! Tree = (no cycles) Spanning Tree = Minimum = (couple of examples with simple graph)

7. Prim (V, E): RETURN T Select (u,v) E with min weight S S {u,v}; P P {(u,v)}; E E\{(u,v)}; REPEAT Select (u,v) with min weight (u,v) E, u S, v S S S {v}; P P {(u,v)}; E E\{(u,v)}; UNTIL S=V Return P; Minimum spanning tree Prims algorithm

8. 136 170 315 148 78 231 234 120 89 131 109 116 86 246 182 216 110 117 199 121 142 242 79 191 178 191 126 149 170 51 112 90 163 59 143 73 63 53 27 135 105 58 116 72 79 Example of Prim

10. Proof of optimality General properties of spanning trees Spanning tree includes N-1 links There are no cycles Minimum spanning tree is the one with the smallest weights A B C A B C Remove Link BC Cycle No cycle

11. Proof of optimality Case: minimum link 2 A B C 2 1 2 A B C 2 1 Link AB is minimum Suppose it is not in MST Path A B must exist Add AB Adding AB we can remove another link (e.g. AC) Path A C exists All nodes reached from C can now be reached from B

12. Proof of optimality Induction step A B C 4 3 E D Replace CD by CE MST solved for Subset S Suppose CE is minimum connecting S outside Path D E must exist and is outside S

13. Proof of optimality Induction step A B C 4 3 E D MST solved for Subset S Path D E still exist as before All nodes reachable via D can now be reached via C D

14. Source of data just for fun

15. 1. A // initially A is empty 2. for each vertex v V [ G ] // line 2-3 takes O ( V ) time 3. do Create-Set( v ) // create set for each vertex 4. sort the edges of E by nondecreasing weight w 5. for each edge ( u , v ) E, in order by nondecreasing weight 6. do if Find-Set( u ) Find-Set( v ) // u & v on different trees 7. then A A {( u , v )} 8. Union( u , v ) 9. return A Total running time is O ( E lg E ). Minimum spanning tree Kruskals algorithm Needs revisions: - Remove numbers - Change terminology

16. Cardiff Sheffield Nottingham Oxford Southampton Bristol Shrewsbury Liverpool Aberystwyth B/ham Manchester 50 40 40 30 80 70 80 50 90 50 110 70 120 110 70 100

17. Cardiff Sheffield Nottingham Oxford Southampton Bristol Shrewsbury Liverpool Aberystwyth B/ham Manchester 50 40 40 30 80 70 80 50 90 50 110 70 120 110 70 100

18. Cardiff Sheffield Nottingham Oxford Southampton Bristol Shrewsbury Liverpool Aberystwyth B/ham Manchester 50 40 40 30 80 70 80 50 90 50 110 70 120 110 70 100

19. Cardiff Sheffield Nottingham Oxford Southampton Bristol Shrewsbury Liverpool Aberystwyth B/ham Manchester 50 40 40 30 80 70 80 50 90 50 110 70 120 110 70 100

20. Cardiff Sheffield Nottingham Oxford Southampton Bristol Shrewsbury Liverpool Aberystwyth B/ham Manchester 50 40 40 30 80 70 80 50 90 50 110 70 120 110 70 100

21. Cardiff Sheffield Nottingham Oxford Southampton Bristol Shrewsbury Liverpool Aberystwyth B/ham Manchester 50 40 40 30 80 70 80 50 90 50 110 70 120 110 70 100

22. Cardiff Sheffield Nottingham Oxford Southampton Bristol Shrewsbury Liverpool Aberystwyth B/ham Manchester 50 40 40 30 80 70 80 50 90 50 110 70 120 110 70 100

23. Cardiff Sheffield Nottingham Oxford Southampton Bristol Shrewsbury Liverpool Aberystwyth B/ham Manchester 50 40 40 30 80 70 80 50 90 50 110 70 120 110 70 100

24. Cardiff Sheffield Nottingham Oxford Southampton Bristol Shrewsbury Liverpool Aberystwyth B/ham Manchester 50 40 40 30 80 70 80 50 90 50 110 70 120 110 70 100

25. Cardiff Sheffield Nottingham Oxford Southampton Bristol Shrewsbury Liverpool Aberystwyth B/ham Manchester 50 40 40 30 80 70 80 50 90 50 110 70 120 110 70 100

26. Cardiff Sheffield Nottingham Oxford Southampton Bristol Shrewsbury Liverpool Aberystwyth B/ham Manchester 50 40 40 30 80 70 80 50 90 50 110 70 120 110 70 100

27. Input: Weight of N items { w 1 , w 2 , ..., w n } Cost of N items {c 1 , c 2 , ..., c n } Knapsack limit S Output: Selection for knapsack: {x 1 ,x 2 ,x n } where x i {0,1}. Sample input: w i ={1,1,2,4,12} c i = {1,2,2,10,4} S=15 Generalized Knapsack problem Problem definition

28. Will appear 2014 Generalized Knapsack problem

29. Semi-blank space

30. Traveling salesman problem GreedyTSP (V, E, home): RETURN T X[1] home; FOR i 1 TO N-1 DO Select (u,v) with min weight (u,v) E, u S, v S X[.. S S {v}; . UNTIL V {} Return something; Needs to be done

31. Greedy algorithms 1. Coin problem 2. Minimum spanning tree 3. Generalized knapsack problem 4. Traveling salesman problem Solved Not Solved Not