Next: About this document
Up: No Title
Previous: No Title
-
Osoita, että n-solmuisen binomimetsän korkeus on
. -
-
Selitä AVL-puiden poistoalgoritmin toiminta.
-
Anna esimerkki AVL-puusta, jossa jonkin solmun poistaminen
vaatii vähintään kaksi tasapainottavaa kiertoa. Esitä tarvittavat
kierrot.
-
Selitä ns. ``kahdesti puun ympäri''-heuristiikka
TSP-ongelman
ratkaisuun, ja todista sitä koskeva approksimointitakuutulos. - 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ä.
Pekka Orponen
Wed Mar 24 10:23:38 EET 1999