TIE310 Algoritmien teoria (3 ov)
Loppukoe ke 8.9.1999 klo 8-12

1. Määritä rekursioyhtälön

   

   ratkaisun kertaluokka, kun n on kahden potenssi.

2. 1. Selitä AVL-puiden poistoalgoritmin toiminta.
   2. Anna esimerkki AVL-puusta, jossa jonkin solmun poistaminen vaatii vähintään kaksi tasapainottavaa kiertoa. Esitä tarvittavat kierrot.
3. Muodosta seuraavan verkon solmut kiertävä TSP-reitti käyttäen (a) ``kahdesti puun ympäri''-menetelmää, (b) Christofidesin algoritmia. (Esitä myös ratkaisun välivaiheet.)

   

4. Suunnittele jokin kohtuullisen tehokas algoritmi suunnatun, syklittömän verkon sisältämän pisimmän polun pituuden määrittämiseksi. Arvioi algoritmisi aikavaativuutta. Algoritmin tulee toimia verkon koon suhteen polynomisessa ajassa.

Pisteytys: Kukin tehtävä 15 pistettä, yhteensä 60 pistettä.