Tietorakenteiden harjoitustyö (periodi IV)

58161
4
Algoritmit ja koneoppiminen
Aineopinnot
Vuosi Lukukausi Päivämäärä Periodi Kieli Vastuuhenkilö
2012 kevät 12.03-27.04. 4-4 Suomi Tomi Pasanen

Ilmoittautuminen tälle kurssille alkaa tiistaina 21.2. klo 9.00.

Non finnish students contact Henning Lübbers (lubbers@cs.helsinki.fi). Registration for this course starts on Tue 21st of February at 9.00.

Yleistä

Harjoitustyön tarkoituksen on harjoitella dynaamisten tietorakenteiden ohjelmointia erilaisilla keoilla. Jokainen asettaa töilleen omat aikataulut, mutta kunkin työn hyväksynnän edellytys on että työt on näytetty ohjaajalle henkilökohtaisessa tapaamisessa. Ensimmäisenä tehtävä on toteuttaa normaali keko osoittimilla, ilman taulukkoesitystä. Tämän lisäksi täytyy tehdä yksikkötestit omalle rakenteelle. Merkitse Doodle-kalenteriin http://www.doodle.com/ixwve8fq5n9g9sqg sinulle sopiva henkilökohtainen tapaamisaika. Tapaamisajat pysyvät koko periodin ajan samoina ja oletuksena on, että ensimmäisen kerran tavataan vasta periodin toisella viikolla. Mikäli haluat tavata jo periodin ensimmäisellä viikolla ota yhteyttä ohjaajaasi.  

Alla on lueteltuna vaaditut ja vapaaehtoiset operaatiot eri keoille (Brodalin paperissa on lueteltuina vaaditut operaatiot Brodalin keolle).

Normaali binäärikeko (binäärikeon rakenne täytyy säilyttää!) 
- keon rakennus n:stä alkiosta O(n) ajassa 
- pienimmän alkion poisto O(log(n)) ajassa
- yhden uuden alkion lisäys O (log (n)) ajassa

Binomikeko 
- yhden uuden alkion lisäys 
- pienimmän alkion poisto 
- kahden keon yhdistäminen 
- vapaaehtoinen: keon alkion arvon pienentäminen (metodille annetaan osoitin, ko. solmuun) 
- vapaaehtoinen: mielivaltaisen alkion poisto (metodille annetaan osoitin, ko. solmuun)

Fibonaccikeko 
- yhden uuden alkion lisäys 
- pienimmän poisto 
- kahden keon yhdistäminen 
- keon alkion arvon pienentäminen (metodille annetaan osoitin, ko. solmuun) 
- mielivaltaisen alkion poisto (metodille annetaan osoitin, ko. Solmuun)

Palautusohjeet 
- työ(t) palautetaan ryhmän ohjaajalle yhdessä zip-pakatussa kansiossa viimeistään periodin viimeisen opetusviikon sunnuntaina. 

Palautuksen kansiorakenne 
- kansiolle nimeksi palauttajan nimi muodossa sukunimi_etunimi 
- projektit (Netbeansin projektihakemistot) 
- lyhyt työselostus jokaisesta tehdystä projektista (keko, bin-keko, fib-keko, Brodal-keko): mitä toteutettu, mitä jäi toteuttamatta ja miksi, jäikö epävarmoja kohtia jne 
 

  

Harjoitusryhmät

Ryhmän numero: 1
Aika Huone Ohjaaja Päivämäärä Huomioitavaa
To 13-16 B228 Tomi Pasanen 12.03.2012-27.04.2012
Ti 13-16 B228 Tomi Pasanen 12.03.2012-27.04.2012