next up previous
Next: About this document Up: No Title Previous: No Title

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

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

    eqnarray16

    ratkaisun kertaluokka, kun n on kahden potenssi.

    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.
  2. 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.)

    picture24

  3. 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ä.



Pekka Orponen
Fri Sep 24 21:01:12 EET DST 1999