Tietorakenteiden harjoitustyö (periodi IV)
3-5
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 algoritmit sekä Aineopintojen harjoitustyö: Ohjelmointi.
| Year | Semester | Date | Period | Language | In charge |
|---|---|---|---|---|---|
| 2012 | spring | 12.03-27.04. | 4-4 | Finnish | Tomi Pasanen |
Exercise groups
| Time | Room | Instructor | Date | Observe |
|---|---|---|---|---|
| Thu 13-16 | B228 | Tomi Pasanen | 12.03.2012—27.04.2012 | |
| Tue 13-16 | B228 | Tomi Pasanen | 12.03.2012—27.04.2012 |
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.
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