58131 Tietorakenteet (8 op), kevät 2007

Yleisiä tietoja kurssista löytyy kurssikuvauksesta.

Ajankohtaista

• Luentomateriaalista on tehty korjattu versio; korjauksia sivuilla 145, 149, 227 ja 449. (10.10.2007)
• Koeohjelmaan on lisätty ylimääräinen Tietorakenteiden erilliskoe 5.6.2007. Kysymyksessä on kuitenkin normaali erilliskoe, ts. laskuharjoituspisteitä ei oteta huomioon (16.5.2007).
• Kurssi on päättynyt ja tulokset saatavilla. Kokeet osoittautuivat aiottua vaikeammiksi, mikä on otettu huomioon pisterajoissa (16.5.2007).

Annettava opetus

Kurssi kestää koko kevätlukukauden (periodit III ja IV).

Luennot 16.1.-22.2. ja 13.3.-26.4. Jyrki Kivinen ti, to 10-12 A111

Harjoitukset

1. Janne Korhonen ti 16-18 B222
2. Janne Korhonen ke 14-16 C222
3. Jyrki Kivinen to 8-10 C222
4. Janne Korhonen pe 12-14 B119
5. Ari Meriläinen ke 16-18 B119
6. Ari Meriläinen to 16-18 CK111

Harjoitukset ovat enimmäkseen (tavallisia) yksilöharjoituksia, jotka kukin opiskelija ratkaisee itsenäisesti.

Osa harjoitustehtävistä on tarkoitus tehdä pienryhmissä. Ryhmätyötehtäviä käsiteltäessä ei sallita vierailuja (opiskelijan pitää osallistua siihen ryhmään, johon on ilmoittautunut).

Harjoituksia tehdään myös TRAKLA2-ohjelmistolla.

Kurssikokeet

1. ma 26.2. klo 9-12
2. ma 7.5. klo 9-12

(Varmista ajat ja salit vähän ennen koetta!)

Oppimateriaali

Kevään 2007 kurssi noudattaa pääosin aiemminkin käytettyjä luentokalvoja

Matti Luukkainen ja Matti Nykänen: 58131: Tietorakenteet.

Kalvoja ei pitäisi tulostaa laitoksen kirjoittimilla (niitä on yli 700 sivua). Valmiiksi pienennetty paperiversio on kopioimista varten huoneessa C127. Lisäksi alla on lisämateriaalia joistakin aiheita.

B-puista käsitellään hieman eri versio kuin Luukkaisen ja Nykäsen monisteessa ja Cormenin ym. oppikirjassa. Tämä osa kurssia noudattaa esitystä

Kerttu Pollari-Malmi: B-puut (in English B-trees). Helsinki 2006.

Luennolla käsiteltiin Luukkaisen ja Nykäsen monisteen ulkopuolelta reikäkorttijäjestäminen: luentokalvojen sivut 375-378 PS (pienennetty) / PDF.

Kokeissa edellytetään osattavaksi luennoilla ja harjoituksissa käsitellyt asiat. Periaatteessa kaikki luentojen asiat löytyvät Luukkaisen ja Nykäsen kalvoista ja ylläolevasta lisämateriaalista. Kalvoja ei kuitenkaan ole laadittu itseopiskelukäyttöön, joten niiden tueksi saattaa tarvita luentojen seuraamista tai kirjan lukemista.

Kurssin asiasisältö ja esitystapa (mutta ei aina esitysjärjestys) perustuvat pitkälti kirjaan

Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein: Introduction to Algorithms (Second Edition). MIT Press 2001.

Kirja sisää huomattavasti enemmän materiaalia, kuin kurssilla käsitellään. Se on varsin hyvä hakuteos sellaisillekin tietorakenneasioille, jotka jäävät kurssin ulkopuolelle.

Kurssin eteneminen

Tänne ilmestyy viikoittain luennoilla ja laskuharjoituksissa käsitelty materiaali.

Merkintä "[LN xxx-yyy]" viittaa monisteen Luukkainen-Nykänen vastaaviin sivuihin, "[CLRS xxx-yyy]" Cormenin et al. kirjaan.

Merkintä "kalvot" viittaa oheisiin luennoilla esitettyihin kalvoihin: saatavana sivut 1-552.

• kalenteriviikko 3 (periodi III, viikko 1)
  • luennoilla käsiteltiin kalvot 1-47; vastaavat asiat kuin [LN 1-32], [CLRS 5-26, 41-46]
• kalenteriviikko 4 (periodi III, viikko 2)
  • luennoilla käsiteltiin kalvot 48-100; vastaavat asiat kuin [LN 33-94, 103-108], [CLRS 197-206]
  • harjoitus 1: tehtävät PS/PDF; ratkaisuja PS/PDF
  • exercise 1, problems in English: PS/PDF
• kalenteriviikko 5 (periodi III, viikko 3)
  • luennoilla käsiteltiin kalvot 101-148; vastaavat asiat kuin [LN 95-102, 109-167], [CLRS 206-208, 253-264]
  • harjoitus 2: tehtävät PS/PDF; ratkaisuja PS/PDF
  • exercise 2, problems in English: PS/PDF
• kalenteriviikko 6 (periodi III, viikko 4)
  • luennoilla käsiteltiin kalvot 149-189; vastaavat asiat kuin [LN 168-234, Pollari-Malmi 1-4], [CLRS 273-293, 434-440]
  • harjoitus 3: tehtävät PS/PDF; ratkaisuja PS/PDF
  • exercise 3, problems in English: PS/PDF
• kalenteriviikko 7 (periodi III, viikko 5)
  • luennoilla käsiteltiin kalvot 190-251; vastaavat asiat kuin [Pollari-Malmi 5-11, LN 280-346], [CLRS 441-452, 214-215, 221-226 sekä peruuttava etsintä ja pelipuut joita CLRS ei käsittele]
  • harjoitus 4: tehtävät PS/PDF; ratkaisuja PS/PDF
  • exercise 4, problems in English: PS/PDF
• kalenteriviikko 8 (periodi III, viikko 6)
  • luennoilla käsiteltiin kalvot 252-284; vastaavat asiat kuin [LN 347-417], [CLRS 226-244 poislukien todistukset]
  • harjoitus 5: tehtävät PS/PDF; ratkaisuja PS/PDF
  • exercise 5, problems in English: PS/PDF
• kalenteriviikko 9 (periodi III, viikko 7)
  • 1. kurssikoe ma 26.2. klo 9-12: tehtävät PS/PDF, ratkaisuja PS/PDF
• kalenteriviikko 10: periodien väliviikko, ei opetusta
• kalenteriviikko 11 (periodi IV, viikko 1)
  • luennoilla käsiteltiin kalvot 285-332; vastaavat asiat kuin [LN 418-486], [CLRS 127-144, 27-36]
  • harjoitus 6: tehtävät PS/PDF; ratkaisuja PS/PDF
  • exercise 6, problems in English: PS/PDF
• kalenteriviikko 12 (periodi IV, viikko 2)
  • luennoilla käsiteltiin kalvot 333-379; vastaavat asiat kuin [LN 487-548], [CLRS 145-154, 165-173]
  • harjoitus 7, tehtävät: PS/PDF; ratkaisuja PS/PDF
  • exercise 7, problems in English: PS/PDF
• kalenteriviikko 13 (periodi IV, viikko 3)
  • luennoilla käsiteltiin kalvot 380-437; vastaavat asiat kuin [LN 549-624], [CLRS 525-553]
  • harjoitus 8, tehtävät: PS/PDF; ratkaisuja: PS/PDF
  • exercise 8, problems in English: PS/PDF
• kalenteriviikot 14 ja 15 (periodi IV, viikko 4)
  • ei opetusta pääsiäisloman aikana 5.-11.4.
  • luennoilla käsiteltiin kalvot 438-471; vastaavat asiat kuin [LN 625-669], [CLRS 554-557, 580-591, 595-599]
  • harjoitus 9, tehtävät: PS/PDF; ratkaisuja: PS/PDF
  • exercise 9, problems in English: PS/PDF
• kalenteriviikko 16 (periodi IV, viikko 5)
  • luennoilla käsiteltiin kalvot 472-513; vastaavat asiat kuin [LN 670-713], [CLRS 629-634, 561-570]
  • harjoitus 10, tehtävät: PS/PDF; ratkaisuja: PS/PDF
  • exercise 10, problems in English: PS/PDF
• kalenteriviikko 17 (periodi IV, viikko 6)
  • luennoilla käsiteltiin kalvot 514-552; vastaavat asiat kuin [LN 714-725], [CLRS 570-573] sekä kertausta)
  • harjoitus 11, tehtävät: PS/PDF; ratkaisuja: PS/PDF
  • exercise 11, problems in English: PS/PDF
• kalenteriviikko 18 (periodi IV, viikko 7)
  • ei opetusta eikä (vapun takia) tenttiä
• kalenteriviikko 19
  • 2. kurssikoe maanantaina 7.5. kello 9-12: tehtävät PS/PDF, ratkaisuja PS/PDF.

---

10. lokakuuta 2007 Jyrki Kivinen