TIE310 Algoritmien teoria (3 ov)
Kurssikoe ke 24.3.1999 8-12

1. Osoita, että n-solmuisen binomimetsän korkeus on .
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. Selitä ns. ``kahdesti puun ympäri''-heuristiikka TSP-ongelman ratkaisuun, ja todista sitä koskeva approksimointitakuutulos.
4. Syötteenä annetaan joukko tason kiekkojen keskipisteitä ja säteitä . Suunnittele ja analysoi tehokas algoritmi sen tutkimiseen, leikkaavatko jotkin annetuista kiekoista toisensa, vai ovatko ne kaikki erillisiä. Algoritmisi tulee olla tehokkaampi kuin kaikkien kiekkoparien läpikäyntiin perustuvan triviaaliratkaisun, jonka aikavaativuus on .

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