joew, hier zijn de examenvragen voor Datastructuren en Algoritmen van 2e zit. Ze leken mij vrij gemakkelijk.
1. Toon aan dat bij een topological sort van een graph met gesloten paden, het aantal foute edges niet altijd minimaal is.
(Hint: een graph met 4 nodes was voldoende)
2. Toon aan dat c(u,v) + c(v,u) = fc(u,v) + fc(v,u) met c de capacity en fc de flow van een flow-netwerk.
(Antwoord in 2 lijntjes).
3. Schrijf een algortime met complixiteit O(E* log E) , dat in een flownetwork het augmenting path vind met de grootste capaciteit. (Hint: Sorteer edges op capacity en zoek met DFS ofdat {E1,...,EK} een path vormt met E1 tot EK edges).
4. Gegeven een bipartite graph. Doe het Ford-Fulkerson algoritme en bepaal de kleinste bovengrens van het langste augmenting path dat je kan hebben.
5. Je hebt een niet geconnecteerde graph G, met k delen. Zoek een algoritme dat deze delen vindt en ze kan voorstellen
(Hint : Disjoint Sets.)
6. Gegeven een spannings tree T van graph G. Amax(T) = de maximum weight van een edge.
Bewijs dat als Amax(T) miminaal beschouwt wordt T ook een minimal spannings tree is of geef een tegenvoorbeeld.
7. Gegeven een Fibonacci heap met 30 nodes. Wat is het maximale aantal root nodes die je kan overhouden nadat je een Delete-Min hebt uitgevoerd.