Tietorakenteet / syksy 2004 / 2. välikoe / 3. tehtävä

Joitakin huomioita:

-Algoritmi 3 p., vaativuusanalyysi 3 p.
-Kuten paperissa sanottiin, ilman intuitiivisluontoista selvennystä tai
 vähintäänkin kommentteja ei saanut pisteitä.
-Riittävä aika-analyysi ei ollut "algoritmi on bubblesortin variaatio ja
 siksi O(l^2)".
-"Lista käydään läpi kahteen kertaan joten aikavaativuus on O(l^2)"
 -tyyppisistä perustavaa laatua olevista virheistä -2 p.
-Tilavaativuuden puuttumisesta -1 p.
-Täysin sallittua oli muuttaa lista ensin tauluksi, järjestää taulu ja
 sitten muuttaa takaisin listaksi.
-Jos toteutti laskemisjärjestyksen eikä huomannut että algoritmin piti
 toimia myös negatiivisilla luvuilla, niin -1 p.
-Kekojärjestämisalgoritmista johon ei kuulunut keko-operaatioiden
 (heapify ym.) toteutusta ja analyysiä sai max 4 p., yleensä vähemmän.
-Jos totesi esim. keko-operaatioiden vaativuudeksi log n ilman
 perusteluita tälle, niin -1 p.