1. Selvitä binomikeon rakenne ja keko-operaatioiden suoritus binomikeossa.

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

3. Taulukon T sisältö (paikat T(1) , T[2), ..., T[22) on

9 11 11 11 4 19 7 6 19 6 21 9 7 14 14 4 15 14 7 22 9 14

Taulukko on erään joukkokokoelman Union-Find -rakenteen toteutus. Kokoelmaan kohdistetaan operaatio Union(Find(4), Find(15)). Union suoritetaan koon mukaan ja Findien yhteydessä suoritetaan polun tiivistys. Piirrä (a) taulukon sisältämä metsä ennen operaatioiden suorittamista; (b) taulukon sisältämä metsä Find-operaatioiden jälkeen ja (c) taulukon sisältämä metsä Union-operaation jälkeen ja (d) selvitä taulukon sisältö Union-operaation jälkeen.

4. a) Selvitä, mitä tarkoitetaan dynaamisella ohjelmoinnilla algoritmien suunnittelussa.

b) Anna jokin algoritmi, joka soveltaa dynaamisen ohjelmoinnin periaatetta. Analysoi algoritmin aikavaativuus.

5. Metrisen kauppamatkustajaongelman likimääräisratkaisun etsimiseen täydellisessä verkossa käytetään seuraavaa approksimointialgoritmia:

1. Etsi verkon minimaalinen virittävä puu.

2. Käy puun solmut syvyyssuuntaisesti läpi; tulosta solmut esijärjestyksessä.

3. Tulostettu solmujono täydennettynä siten, että viimeisen solmun jälkeen palataan ensimmäiseen, on kauppamatkustajan reitti.

Analysoi saadun likimääräisratkaisun tarkkuus.