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

1. Esitä perustellut ylä- ja alarajat n-lehtisen (a,b)-puun korkeudelle.
2. 1. Mitä tarkoitetaan taulukon kekojärjestyksellä?
   2. Esitä ja analysoi algoritmi, joka saattaa n-alkioisen taulukon kekojärjestykseen ajassa O(n).
3. 1. Esitä hyppylistojen lisäys- ja poistoalgoritmit ja niiden analyysi (pääpiirteissään; yksityiskohtaisia odotusarvolaskelmia ei tarvitse esittää).
   2. Suunnittele ja analysoi jokin hyppylistoihin perustuva tehokas lajittelumenetelmä.
4. Tason (äärelliset) pistejoukot A ja B ovat lineaarisesti erottuvat, jos on jokin sellainen (suunnattu) suora , että kaikki A:n pisteet ovat suoran vasemmalla ja kaikki B:n pisteet suoran oikealla puolen. Suunnittele ja analysoi mahdollisimman tehokas algoritmi sen tutkimiseksi, ovatko kaksi syötteenä annettua pistejoukkoa lineaarisesti erottuvat. (Vihje: Pistejoukot eivät ole lineaarisesti erottuvat, joss jokin joukon A piste on joukon B ``sisällä'' tai toisinpäin. Mieti mitä tämä tarkoittaa geometrisesti.)

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