(Project on Data Structures and Algorithms, 2 cu)
Syksyllä 2002 töitä jakaa ja ohjaa Simo Juvaste, juvaste@cs.joensuu.fi, huone T/B325.
Työ on tehtävä kahden kuukauden kuluessa sen antamisesta
Perusohjeena (mm. dokumentoinnista) käytetään Ohjelmoinnin peruskurssin työohjetta. Työn dokumennoinnissa keskitytään moduulien liittymien dokumentointiin sekä itse tehtäväalgoritmin toiminnan ja aikavaativuuden kuvaamiseen. Työn kannalta vähemmän tärkeiden osien (esim. käyttöliittymän) toteutusdokumentointi voi olla kevyempi, kunhan käyttöohje on riittävä. Ristiinviittaustaulun sijaan voi piirtää kuvan moduulien käytöstä ja kunkin moduulin aliohjelmien keskinäisistä kutsuista. Lisäksi on syytä piirtää kuva talletustietorakenteesta.
Kussakin työssä käytetty abstrakti tietorakenne (esim. verkko, joukko) tulee toteuttaa erikseen (voitava irrottaa muusta ohjelmasta). Tietorakenteen toteutuksen julkinen osa sisältää vain operaatiot ja tyypit.
Varsinaisen työnannon mukaisen algoritmin ja pääohjelman (tai esimerkkiohjelman) tulee käyttää toteutettuja abstraktin tietorakenteen operaatioita, eikä missään tapauksessa käyttää toteutuksen kenttiä suoraan.
Ohjelma koostuu siis useimmiten vähintään kolmesta moduulista:
Myös dokumentointi jakautuu absraktin tietorakenteen liittymän ja toteutuksen dokumentointiin, sekä varsinaisen algoritmin dokumentointiin.
Työn dokumenteissa ja ohjelmakoodissa (moduuleissa, tarvittaessa aliohjelmissa) on oltava maininta siitä kumpi ko. osan on tehnyt. Jos osaan ovat osallistuneet molemmat, on kummankin osuus jaoteltava tarkemmin.
Parityössä molemmille annetaan sama arvosana jollei ym. selvitys, työn osien laatueerot (yhdessä tekijöiden kanssa keskusteltuna) anna aihetta erilliseen arvosteluun.
Pascal-kieliset ohjelmat voi kirjoittaa laajennetulla Pascalilla (mutta ei kuitenkaan esimerkiksi vain Turbo Pascalista tai Delphistä löytyviä kirjastoja käyttäen). Esimerkiksi string-tyypin käyttö on luvallista, mutta Turbo Pascalin crt-modulia ei tule käyttää. Näin ohjelman voi kääntää myös mm. cs:n gpc-kääntäjällä (kuten ohjaaja tekee). Kuten C:lläkin, ohjelmakoodi kannattaa jakaa erillisiksi ADT:n toteutustiedostoksi, algoritmitiedostoksi ja pääohjelmatiedostoksi.
Esimerkki Pascalin moduulien käytöstä löytyy tra-kurssin esimerkkeistä.
Java-kieliset työt on käännyttävä ja toimittava cs:n Java-kääntäjällä ja tulkilla.
Jos ongelman algoritminen ratkaisu tuntuu vaikealta tai mahdottomalta, algoritmeja moneen apuun löytyy kirjallisuudesta (jota on lueteltu TRA-kurssin verkkosivulta). Rohkeasti vain kirjastoa käyttämään. Työn ohjaaja voi myös antaa kirjallisuusviitteitä. Varsinaisten TRA-kirjojen lisäksi (matematiikan hyllyistä) löytyvät verkkoteorian kirjat, erityisesti Harary: Graph Theory, ovat käyttökelpoisia. Tkt-kirjaston aineistokoneelta (kirjaston sisäpuolella) löytyy 9 hyvää algoritmikirjaa sähköisessä muodossa (Dr. Dobb's Essential Books on Algorithms and Data Structures). Kirjoista voi myös tehdä vapaatekstihaun. Kirjat löytyvä ko. koneen www-selaimen kirjanmerkeistä. CD-ROM on myös lainattavissa kirjastosta.