Tietorakenteiden harjoitustyö (periodi III)

58161
4
Algorithms and machine learning
Intermediate studies
Opintojaksossa opiskelijat harjoittelevat vaikeahkojen tietorakenteiden ja algoritmien toteuttamista, sekä erilaisten ratkaisujen vertailemista käytännössä. Työn arvioinnissa keskeistä on ohjelmakoodin oikeellisuus, selkeys ja tehokkuus, sekä vertailuissa saatujen tulosten esittäminen ja arviointi. Työn tekeminen edellyttää jossain määrin tieteellisen kirjallisuuteen perehtymistä. Esitiedot: Tietorakenteet ja Ohjelmoinnin harjoitustyö.
Year Semester Date Period Language In charge
2012 spring 16.01-24.02. 3-3 Finnish Tomi Pasanen

Exercise groups

Group: 1
Time Room Instructor Date Observe
Tue 13-16 A318 Tomi Pasanen 16.01.2012—24.02.2012
Wed 13-16 A318 Tomi Pasanen 16.01.2012—24.02.2012

Non finnish students contact Henning Lübbers (lubbers@cs.helsinki.fi).

General

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