1. Selvitä Fibonacci-keon (Fibonacci heap) rakenne ja keko-operaatioiden suoritus Fibonacci-keossa.

2. Tarkastellaan suunnatun verkon syvyyssuuntaista etsintää.

a) Määrittele käsitteet puukaari, etenevä kaari, takautuva kaari ja poikittaiskaari.

b) Kirjoita algoritmi, joka suorittaa verkon syvyyssuuntaisen etsinnän ja tulostaa kaikki takautuvat kaaret.

3. Union-Find -rakenteessa Union suoritetaan korkeuden mukaan ja Find suoravuvaisesti polkua tiivistämättä. Osoita, että Find vaatii pahimmassa tapauksessa ajan O(log n), missä n on rakenteessa olevien affloiden määrä.

4. a) Selvitä, mitä tarkoitetaan hajoita ja hallitse -periaatteella algoritmien suunnittelussa.

b) Anna algoritmi, joka määrää n-alkioisen lukujoukon maksimin ja minimin hajoita ja hallitse -periaatetta käyttäen. Kuinka monta vertailua algoritmi suorittaa (olettaen, että n on kahden potenssi)?

5. a) Selosta branch-and-bound etsintään perustuvan approksimointialgoritmin periaate.

b) Selosta esimerkin avulla branch-and-bound -tekniikan toiminta TSP:N (Traveling Salesman Problem) approksimointialgoritmina.