58131 Tietorakenteet (8 op), kevät 2008
Ajankohtaista
- Toisen kurssikokeen palautetilaisuus pidetään to 5.6. klo 9.15-10.00 salissa A218.
-
Toinen kurssikoe on korjattu ja
kurssin tulokset
sekä
kokeen tehtäväkohtaiset pisteet
ovat saatavilla.
Myös malliratkaisut ja arvosteluperusteet ovat saatavilla. - Tarkastuslistassa on mukana kaikki osasuoritukset ("LH13"=TRAKLA-pisteet kertoimella 0,5 skaalattuina; "LH14"="HT"=ryhmäharjoitukset).
- Koko kurssin luentomateriaali (sivut 1-552): PDF / PS (pienennetty)
Yleisiä tietoja kurssista löytyy kurssikuvauksesta.
Annettava opetus
Kurssi kestää koko kevätlukukauden (periodit III ja IV).
Luentoja pidettiin 15.1.-21.2. ja 11.3.-24.4. Jyrki Kivinen ti, to 10-12 A111
Harjoitusajat löytyvät opetusohjelmasta.
Kurssin suorittaminen
Kurssin suoritukseen kuuluu kaksi kurssikoetta ja harjoitustehtäviä. Koko kurssin maksimipistemäärä on 60: kumpikin kurssikoe 24 pistettä ja harjoitustehtävät 12 pistettä.
Kurssikokeet perustuvat luennoilla ja harjoituksissa käsiteltyyn materiaaliin.
- kurssikoe ma 25.2. klo 9-12
- kurssikoe ma 5.5. klo 9-12
Harjoitustehtävistä on mahdollista saada kaikkiaan 93 suoritusta, jotka jakautuvat seuraavasti:
- Kukin ratkaistuksi merkitty tavallinen laskuharjoitustehtävä lasketaan yhdeksi suoritukseksi. Niistä on saatavilla 44 suoritusta.
- Ryhmätyötehtävien ratkaisut pisteytetään, ja yksi piste lasketaan yhdeksi suoritukseksi. Ryhmätehtävistä on saatavilla 14 suoritusta.
- TRAKLA2-järjestelmään tehdyistä tehtävistä aina kaksi TRAKLA2-pistettä lasketaan yhdeksi suoritukseksi. TRAKLA2-tehtävistä on siis saatavilla 35 suoritusta.
Harjoitustehtäväsuoritukset muunnetaan kurssipisteiksi siten, että täydet 12 pistettä saa 78 suorituksella (n. 85% suurimmasta mahdollisesta suoritusmäärästä). Pienin hyväksyttävä määrä laskuharjoitussuorituksia on 24 (n. 25%), joka antaa nolla pistettä. Näiden rajojen välillä interpoloidaan lineaarisesti. Toisin sanoen jos harjoitustehtäväsuoritusten lukumäärä on s, pisteiden lukumäärä saadaan lausekkeesta min ( 12, 12*(s-24)/(78-24) ) (pyöristys alaspäin). (Kolmannella tavalla sanoen yksi kurssipiste vastaa 4,5 harjoitustehtäväsuoritusta.)
Hyväksytyn suorituksen raja on n. 30 pistettä ja arvosanan 5/5 raja n. 50 pistettä. Kurssikokeista ei erikseen edellytetä mitään minimipistemääriä. Laskuharjoitussuorituksia pitää olla ainakin 24; pienempi määrä johtaa suorituksen hylkäämiseen. (Käytännössä kurssin menestyksekäs suorittaminen edellyttää yleensä huomattavasti minimin ylittävää harjoitussuoritusmäärä.)
Luentomateriaali
Luentokalvot ilmestyvät tänne viimeistään
kunkin luentoviikon alussa.
Saatavilla luentoviikkojen 1-11 kalvot (sivut 1-530):
PDF /
PS (4 kalvoa per sivu)
Korjauksia luentomateriaaliin:
- Kalvolla 445 ''solmuun u'' piti olla ''solmuun v''. (Korjattu 21.4.)
- Kalvon 460 kuvassa yhden kaaren paino oli virheellinen. (Korjattu 10.4.)
- Sivulla 449 vaihdettu solmun tunnukseksi r (oli virheellisesti s). (Korjattu 10.4.)
- Kalvolla 256 oli virheellisesti r=1, kun piti olla r=-1. (Korjattu 21.2.)
- Kalvoilla 253 ja 254 kaavoissa oli virheellisesti 2i-1 kun piti olla 256i-1. (Korjattu 21.2.)
- Kalvolla 249 lisäys- ja poisto-operaatioiden parametrit on korjattu vastaamaan sitä, mitä listaoperaatioiden yhteydessä on sovittu (annetaanko avain k vai osoitin x). (Korjattu 21.2.)
- Kalvojen 159-160 numeerisessa laskussa oli kaksi toisensa kumoavaa virhettä; ts. lopputulos on oikein mutta välivaiheet eivät olleet. (Korjattu 7.2.)
- Kalvolla 98 on korjattu luennolla havaittu virhe pseudokoodissa (toinen y korjattu z:ksi). (Korjattu 27.1.)
- Kalvolla 69 on täsmennetty, että kaikki operaatiot (myös Min ja Max) palauttavat osoittimia (eikä avaimen arvoja). (Korjattu 27.1.)
- Algoritmin Insertion-Sort pseudokoodissa (kalvot 35 ja 38) rivillä 7 taulukon indeksi oli i kun pitää olla i+1. (Korjattu 17.1.)
Luennolla ti 22.1. esitettiin ylimääräisiä esimerkkejä algoritmien aikavaativuuksista. Nämä eivä kuulu koealueeseen tms., mutta voivat olla muuten kiinnostavia.
Harjoitustehtävät
Kurssilla pidetään normaaleja viikoittaisia laskuharjoituksia, tehdään muutama tehtävä ryhmätyönä sekä käytetään TRAKLA2:ta.
- harjoitus: PDF, PS; ratkaisut PDF, PS; problems in English PDF, PS
- harjoitus: PDF, PS; ratkaisut PDF, PS; problems in English PDF, PS
- harjoitus: PDF, PS; ratkaisut PDF, PS; ratkaisu ryhmätehtävään 1 PDF, PS; problems in English PDF, PS
- harjoitus: PDF, PS; ratkaisut PDF, PS; problems in English PDF, PS
- harjoitus: PDF, PS; ratkaisut PDF, PS; problems in English PDF, PS
- harjoitus: PDF, PS; ratkaisut PDF, PS; ratkaisu ryhmätehtävään 2 PDF, PS; problems in English PDF, PS
- harjoitus: PDF, PS; ratkaisut PDF, PS; problems in English PDF, PS
- harjoitus: PDF, PS; ratkaisut PDF, PS; ryhmäharjoitus 3 ratkaisut PDF, PS; problems in English PDF, PS
- harjoitus: PDF, PS; ratkaisut PDF, PS; problems in English PDF, PS
- harjoitus: PDF, PS; ratkaisut PDF, PS; problems in English PDF, PS
- harjoitus: PDF, PS; ratkaisut PDF, PS; problems in English PDF, PS
- harjoitus: PDF, PS; ratkaisut PDF, PS; ryhmäharjoitus 4 tehtävät PDF, PS, ratkaisut PDF, PS; problems in English PDF, PS
Kurssin eteneminen
Aikataulu on suuntaa-antava. Pidettyjen luentojen viikkoaikataulu ei täysin täsmää allaolevaan materiaalin jakoon viikoille 1-12.
Harjoitukset on merkitty sille viikolle, jolla ne on pidettykin, joten ne liittyvät aina edellisen viikon luentomateriaaliin.
- luentoviikko 1 (14.1.-18.1.): Järjestelyt; johdatus kurssin aihepiiriin; algoritmianalyysin peruskäsitteitä: silmukkainvariantti ja "O-merkintä"
- luentoviikko 2 (21.1.-25.1.): algoritmin aikavaativuuden määrittäminen; tietotyyppi joukko; pino, jono ja lista
- luentoviikko 3 (28.1.-1.2.): puiden peruskäsitteet; binääripuut ja niiden matemaattiset ominaisuudet; binäärihakupuut
- luentoviikko 4 (4.2.-8.2.): binäärihakupuiden tasapainottaminen (AVL-puut)
- luentoviikko 5 (11.2.-15.2.): tasapainoiset binäärihakupuut oheismuistissa (B-puut); muuta puihin liittyvää
- luentoviikko 6 (18.2.-22.2.): hajautustaulut
- tenttiviikko (25.2.-29.2.): 1. kurssikoe ma 25.2. klo 9-12
- väliviikko (3.3.-7.3.; ei opetusta)
- luentoviikko 7 (10.3.-14.3.): keko ja kekojärjestäminen
- luentoviikko 8 (17.3.-19.3. ja 27.3.-28.3.; huom. pääsiäisloma): lomitusjärjestäminen; pikajärjestäminen
- luentoviikko 9 (31.3.-4.4.): vertailuihin perustuvan järjestämisen alaraja; lineaarisaikainen järjestäminen; verkkojen peruskäsitteet; leveyssuuntainen ja syvyyssuuntainen läpikäynti
- luentoviikko 10 (7.4.-11.4.): lisää syvyyssuuntaisen läpikäynnin sovelluksia; lyhimpien polkujen etsiminen Bellmanin-Fordin algoritmilla; lyhimpien polkujen etsiminen Dijkstran algoritmilla
- luentoviikko 11 (14.4.-18.4.): lyhimpien polkujen etsiminen Floydin algoritmilla; pienin virittävä puu; joukkojen erilliset yhdisteet; Kruskalin algoritmi pienimmälle virittävälle puulle
- luentoviikko 12 (21.4.-25.4.): Primin algoritmi pienimmälle virittävälle puulle; yhteenveto ja kertaus
- tentti"viikko" (28.4.-5.5.)
2. kurssikoe ma 5.5. klo 9-12
28. huhtikuuta 2008 Jyrki Kivinen