Tietorakenteet, syksy 2002

Yleistä

Tietorakenteet on tietojenkäsittelytieteen cum laude approbatur -oppimäärän pakollinen kurssi. Sen laajuus on 4 opintoviikkoa. Kurssilla tutustutaan keskusmuistissa toteutettaviin tietorakenteisiin, niiden erilaisiin toteutustapoihin, tietorakenteiden käyttöön algoritmeissa ja algoritmien analyysiin. Esimerkkien ohjelmointikielenä on Java, mutta paljon käytetään myös pseudokieltä.

Luennot

Luennot ovat 12.9. - 5.12. TI 10-12, TO 12-14 Auditoriossa. Syyskuussa joudutaan todennököisesti peruuttamaan yksi luento, joka korvataan joulukuussa. Luennoitsija on Timo Karvi, sähköposti Timo.Karvi@cs.Helsinki.FI.

Kurssin suorittaminen

Kurssi voidaan suorittaa joko kurssikokeilla eli välikokeilla tai erilliskokeella eli loppukokeella. Välikokeilla suoritettaessa harjoituksia on tehtävä vähintään 40%. Harjoituksista saa myös pisteitä, 40% tuottaa yhden pisteen ja 80% kuusi pistettä.

Kurssimateriaali

Luentojen materiaali on koottu monisteeksi, jota saa ostaa 9.9. alkaen laitoksen monistemyynnistä. Materiaalin paino- ja muista virheistä kannattaa ilmoitella laskuharjoitusryhmissä tai suoraan luennoijalle. Oleellisten virheiden luettelo julkaistaan tällä sivulla.

Ajankohtaista

Kurssin lopputulokset julkaisee Olli Lahti. Tulostietoja saa seuraavilta sivuilta tammikuussa:
Vanhoja 2. välikokeita: sy00.ps, sy01.ps, sy00.pdf, sy01.pdf.
1. kurssikokeen arvosteluun voi tutustua to 5.12. klo 12-13 salissa B451. Kysymykset ps-, pdf-muodossa. Arvosteluperusteita: tehtävät 1 ja 4, tehtävä 2. tehtävä 3.
1. kurssikokeen tulokset.
Torstain 21.11. luennolla käsitellään lopuksi seuraavan viikon harjoituksia.
Pari vanhaa välikoetta, sy -00 (ps), sy -00 (pdf), sy -01 (ps), sy -01 (pdf).
Kertausluento pidetään koetta edeltävänä torstaina eli 24.10. Luennolla luodaan katsaus kokeeseen tuleviin asioihin ja kerrataan seikkaperäisemmin ainakin O-merkintää ja lineaaristen listojen toteutusta. Koealue kattaa luvut 1-6.
Valitettavasti opintopiirille ei saatu vetäjää, joten se joudutaan peruuttamaan.
Opintopiiriin on ilmoittautunut riittävä määrä opiskelijoita ja se yritetään perustaa. Tällä hetkellä etsitään vetäjää. Jos vetäjä löytyy, ryhmä aloittaa jo loppuviikolla (viikko 41), viimeistään ensi viikolla.
Muuntokoulutettaville voidaan järjestää viikoittainen valmennustilaisuus (lähinnä harjoituksiin), jos riittävä määrä ilmoittautuu. Siis ne, jotka ovat kiinnostuneita, lähettäköön sähköpostia luennoitsijalle.
Torstain 26.9. luento peruutetaan.
Tiistain harjoitusryhmä 14-16 pidetään englannin kielisenä. On suositeltavaa, että ryhmään jo ilmoittautuneet jatkavat ryhmässä kielen vaihdosta huolimatta. Myös muille suositellaan, että vierailut keskitetään tiistain 14-16 ryhmään. Mikäli ulkolaisia opiskelijoita osallistuu kurssille huomattavan paljon, on mahdollista, että heille perustetaan kokonaan uusi ryhmä. Siinä tapauksessa tiistain ryhmä jää suomen kieliseksi. Tilanne selviää ensimmäisen harjoitusviikon jälkeen.

Korjauksia monisteeseen ja harjoituksiin

Harjoituksen 12 tehtävässä 2 union-operaation parametrit voivat olla alkioita, ei välttämättä puiden juuria. Sen vuoksi union-operaatiossa on ensin etsittävä sen puun juuri, johon annettu parametri kuuluu (find-operaatiolla). Sen jälkeen puut yhdistetään. Huomattakoon, että korkeustaulukko h ei sisällä aina puun todellista korkeutta, vaan korkeuden ylärajan. Polun tiivistämisen yhteydessähän korkeutta ei muuteta, vaikka siihen saattaisi olla aihetta.
Harjoituksissa 11 on virheellinen vuosiluku. Vuoden pitäisi olla 2002 (tehtävätkin ovat uusia).
Sivulla 135 alkaa kappale 9.3.1 (monisteessa virhellinen numero 8.3.1) leveyssuuntaisesta etsinnästä. Kappaleessa on monessa kohtaa käytetty vahingossa termiä syvyyssuuntainen etsintä (ainakin s. 135, 2 kertaa s. 136, s. 139).
Sivulla 76 kasajärjestelyn yhteydessä mainitaan, että taulukko tulkitaan täydelliseksi binääripuuksi. Pitäisi mainita, että taulukko tulkitaan melkein täydelliseksi binääpuuksi. p>

Luokassa BinaryTree on pari kirjoitusvirhettä. 1) Loppusulku puuttuu seuraavasta (alla korjattu versio):


public void attachLeft(Object newItem) {
     if (!isEmpty() && root.getLeft() == null) {

2) Alltosulku kiinni ennen else if -osaa (alla korjattu):

public void attachLeftSubtree(BinaryTree leftTree) 
                       throws TreeException {
   if (isEmpty()) { 
     throw new TreeException("TreeException: Empty tree");
   }
   else if (root.getLeft() != null {

Korjaukset tehty myös tiedostoon.

Keko-operaation Build-heap aika-analyysissä käytetään ääretöntä sarjaa, jonka arvo lasketaan perustelematta ensin, että sarja suppenee. Aika-analyysissä riittää osoittaa pelkkä suppeneminen, joka seuraa esim. Diff. int I:n sarjateoriasta. Jos sarjan arvo halutaan laskea ehdotetulla menetelmällä, täytyy vielä perustella se, että sarja voidaan integroida termeittäin. Tähän löytyy perusteluja vaikkapa Olli Lehdon Diff. int. III:n monisteen lopusta (rajankäynnin ja integroimisen kommutointi).
Listakoodissa sivuilla 19-22 on kommenteissa painovirheitä (johtuen replacen käytöstä): Operaation insert kommentissa pitäisi lukea: Lisäys käsiteltävän solmun edeltäjäksi (ei käsiteltävä-edn solmun edeltäjäksi). Sama kommentin korjaus operaatioon delete.
Monisteen sivulla 53 keskeytysluokan TreeException määrittelyssä on painovirhe: Time täytyy kirjoittaa pienellä, siis RuntimeException.

Sivulla 54 metodista setRootItem puuttuu varattu sana new:

     ...
     else {
       root = new TreeNode(newItem, null, null);