Da Wikipedia, l'enciclopedia libera.

Contents 1 Uova pasquali 2 Matching Stabili 3 Interval Scheduling 4 Dijkstra 5 Minimum Spanning Tree 5.1 Prim 5.2 Kruskal

Uova pasquali

• Alberi e grafi: esercizi 5 & 6
  • http://algo2.googlegroups.com/web/graphs.pdf
• Greedy- parte prima: esercizi 1, 2, 4, 6, 9
  • http://algo2.googlegroups.com/web/exGreedy1.pdf

Matching Stabili

• Algoritmo:

Initially all m € M and w € W are free

While there is a man m who is free and hasn't proposed to every woman w for  witch (m,w) !€ F
       Choose such a man m
       Let w be the highest-ranked woman in m's preference list to which m has not yet proposed
       If w is free then
               (m,w) become engaged
       Else w is currently engaged to m'
               if w prefers m' to m then
                       m remains free
               Else
                       (m,w) become engaged
                       m' becomes free
               Endif
       Endif
Endwhile

Return the set S of engaged pairs

• Dimostrazione matching perfetto
• Dimostrazione matching stabile
• Dimostrazione che gli uomini hanno sempre best(m)
• Dimostrazione che le donne hanno sempre worst(w)
• Implementazione in O(n^2)

Interval Scheduling

Dijkstra

Minimum Spanning Tree

Prim

Kruskal