Tietoa laitoksesta:

58131 Tietorakenteet (4 ov) syksy 2004

Sivua muutettu viimeksi Jan 30, 2005

0. Ajankohtaista

1. Asema opetuksessa

Kurssi on cum laude approbatur -tason pakollinen neljän (4) opintoviikon luentokurssi, joka kestää koko lukukauden.

Esitietoina vaaditaan ohjelmointitaidon alkeet jollakin ohjelmointikielellä kurssin Java-ohjelmointi laajuudessa.

Kielen ei siis tarvitse olla Java, kurssi on kieliriippumaton.

2. Kurssin sisältö

3. Kurssin suorittaminen

Kurssin suoritus koostuu kahdesta kurssikokeesta ja aktiivisesta osallistumisesta laskuharjoituksiin. Kokeissa ja laskuharjoituksissa käsitellään luennoilla esitettyjä asioita.

Kurssikokeet on merkitty tällä sivulla olevaan aikatauluun. Koealue käsittää siihen mennessä käsitellyt asiat. Ne ilmoitetaan tällä sivulla myöhemmin.

Kurssin voi suorittaa myös erilliskokeella. Erilliskokeen vaatimukset ovat aina viimeisimmän päättyneen luennointikerran mukaiset.

3.1. Luennot

Kurssilla on luentoja 14.9.-2.12. tiistaisin ja torstaisin 10-12 auditoriossa.

Luennoijana on Matti Luukkainen.

3.2. Laskuharjoitukset

Kurssiin liittyy pakollisia laskuharjoituksia ajalla 20.9.- 10.12. Katso ajat opetusohjelmasta

Tehtäviä (ryhmäharjoitustehtävät) käsitellään ohjatuissa pienryhmissä. Ensimmäisessä laskuharjoitustilaisuudessa tilaisuuteen ilmoittautuneista muodostetaan (noin) neljän  hengen pienryhmiä, joiden on tarkoitus toimia yhdessä koko kurssin ajan. Kukin ryhmä on yhteisvastuussa siitä, että se saa tehtävät ratkaistua! Tämä vaatinee pienryhmältä tapaamisia (ellei fyysisesti niin ainakin virtuaalisesti) myös laskuharjoitustilaisuuksien välillä.

Tästä seuraa, että muissa laskuharjoitustilaisuuksissa ei voi vierailla. Kurssiin sisältyy myös "vanhan tyylin" laskareita (yksilöharjoitustehtävät) eli itsenäisesti ratkaistavia tehtäviä.

Ryhmätehtäviä käsitellään noin kolmen viikon jaksoissa seuraavasti:

1. Edellisen luentoviikon päätteeksi luennoija jakaa seuraavat ryhmätehtävät tämän verkkosivun kautta.

2. Ensimmäisen ja toisen viikon laskuharjoitustilaisuudessa kukin ryhmä ratkoo edellisen viikon päätteeksi saamiaan tehtäviä yhdessä. Laskuharjoitusassistentti on paikalla auttamassa.

3. Tämän lisäksi laskuharjotuksissa käydään normaaliin tapaan läpi mahdolliset yksilöllisesti tarkaistavat tehtävät

4. Kolmannen viikon laskuharjoitustilaisuudessa ryhmät esittelevät ratkaisujaan toisilleen ja niistä keskustellaan.

   Lisäksi ryhmät palauttavat ratkaisunsa myös kirjallisesti laskuharjoitusassistentille. Assistentti arvioi näiden kirjallisten ratkaisujen perusteella, montako pistettä (0-3) ryhmä tältä kierrokselta saa.

   Pisteytyksen perusteena on, kuinka kelvollisen suullisen esityksen ryhmä olisi voinut tilaisuudessa antaa muille ryhmille. Ryhmä voi tutustua saamiinsa pisteisiin seuraavassa tilaisuudessa.

   Ryhmäläiset arvioivat kirjallisesti myös oman ryhmänsä toimintaa.

   Tämä tehdään siten, että ryhmä kirjoittaa kirjallisten ratkaisujensa loppuun arvion ryhmän toiminnasta tällä kierroksella. Arvioitiohje.

Kurssin lopuksi laskuharjoitusassistentti pisteyttää (0-2 p.) ryhmän kaikki kurssin aikana tekemät arviot. Nämä pisteet vaikuttavat suoraan arvosteluun. Pisteytyksen perusteena on, kuinka asianmukaisesti ryhmä on arvionsa laatinut.

Lisäksi, kurssin lopuksi jokainen opiskelija arvioi oman ryhmänsä toiminnan antaen arvosanan kullekin ryhmän jäsenelle itsensä mukaanlukien

3.3. Arvostelu

Kurssi pisteytetään ja arvostellaan seuraavasti:

3.4. Suoritus erilliskokeella

Tämä luentokurssi on mahdollista suorittaa myös erilliskokeella. Jokaisessa erilliskokeessa tentitään kurssi sellaisena, kuin se pidettiin edellisellä päättyneellä luentokerralla. Eri luentokerrat lienevät tosin sisällöiltään ja vaatimuksiltaan samankaltaiset. Tarkemmat erilliskoeajat selviävät kyseisen lukukauden erilliskoelistasta.

4. Kurssimateriaali

Kurssimateriaali koostuu

• Kurssin kuluessa syntyvistä luentokalvoista, jotka luennoija jakaa tämän verkkosivun ja luentomapin kautta kunkin luentoviikon aluksi
• Timo Karvin tekemästä luentomuistiinpanoista, jonka voi ostaa laitoksen monistemyynnistä ja
• Oppikirjasta T.H.Cormen, C.E.Leiserson, R.L.Rivest ja C.Stein: Introduction to Algorithms. Second Edition. The MIT Press, 2001.
• Hyötyä voi olla myös edellisten Tira-kurssien materiaaleista, ks. Syksy 03, Kevät 03
• Muitakin tietorakenne-aiheisia kirjoja voi toki vilkaista, esim.
  J.H.Kingston: Algorithms and data structures : design, correctness, analysis
  M.A.Weiss: Data structures and algorithm analysis ja Data structures and problem solving using Java
  A.V. Aho, J.E. Hopcroft., J.D. Ullman: Data structures and algorithms
  A.Levitin:Introduction to the design & analysis of algorithms
• Internetistä löytyy esim. hakusanalla data structures valtava määrä materiaalia, ohessa muutama hyödylliseksi todettu linkki:
  2-3-4-puusimulaattori
  Dijkstra-simulaattori
  MatrixPro a tool for instructors to create algorithm animations used in teaching
  TRAKLA2 an automatic exercise system for learning data structures and algorithms

5. Aikataulu

aika	asiat
viikko 1, 13-27.9	Luentojen aiheena johdanto tietorakenteisiin sekä algoritmin oikeellisuuden sekä vaativuuden osoittamiseen Luentokalvot 1-21 (pdf) Karvi 2002, Luku 1 Cormen et all 2001., Chapters 2.1-2.2 and 3. Yksilölaskari 1 (pdf) Ryhmälaskari I (pdf) Exercise 1 (pdf) Group exercise I (pdf)
viikko 2, 20-24.9	Luentojen aiheena Pino, jono ja linkitetty lista Luentokalvot 22-45 (pdf) Karvi 2002, Luvut 3 ja 4 Cormen et all 2001., Chapters 10.1-10.2 Pienryhmät muodostetaan laskuharjoituksissa 1. yksilöharjoitustehtävät käydään läpi I ryhmäharjoitustehtäviä ratkotaan
viikko 3,  27.9-1.10	Luentojen aiheena Binäärihakupuut Luentokalvot 46-66: (2/sivu)   (4/sivu)   (pdf) Karvi 2002, Luvut 5.2, 5.3.2 ja 8.2, 8.3.2-8.3.4 Cormen et all 2001., Chapters 12.1-12.3 I ryhmäharjoitustehtävät käydään läpi Yksilölaskari 2 (pdf) Ryhmälaskari II (pdf) Exercise 2 (pdf) Group exercise II (pdf)
viikko 4,  4-8.10	Luentojen aiheena Punamustat puut Luentokalvot 67-84: (2/sivu)   (4/sivu)   (pdf) Karvi 2002, Luvut 8.4.1-8.4.2 Cormen et all 2001., Chapters 13.1-13.3 2. yksilöharjoitustehtävät käydään läpi II ryhmäharjoitustehtävien ratkaiseminen aloitetaan Yksilölaskari 3 (pdf) Exercise 3 (pdf)
viikko 5, 11-15.10	Luentojen aiheena edelleen Punamustat puut sekä muita puiden sovelluksia Luentokalvot 85-106: (2/sivu)   (4/sivu)   (pdf) Karvi 2002, Luvut 8.4.4, 5.3.3, 5.4.1 Cormen et all 2001., Chapter 13.4, 10.4 3. yksilöharjoitustehtävät käydään läpi II ryhmäharjoitustehtävien ratkaisemista jatketaan Yksilölaskari 4 (pdf) Exercise 4 (pdf)
viikko 6, 18-22.10	Luennoilla aiheina puu-rakenteen soveltaminen ongelmanratkaisuun, sekä pelipuut, torstain luennolla myös kertausta kokeeseen Luentokalvot 107-123: (2/sivu)   (4/sivu)   (pdf) Karvi 2002, Luvut 5.6 4. yksilöharjoitustehtävät käydään läpi II ryhmäharjoitustehtävän kohdat 1 ja 2 käydään läpi
viikko 7, 25-29.10	Luennoilla aiheina hajautusrakenteet Luentokalvot 124-148: (2/sivu)   (4/sivu)   (pdf) Karvi 2002, Luku 9 Cormen et all 2001., Chapter 11.2-11.4 II ryhmäharjoitustehtävän kohta 3 käydään läpi Yksilölaskari 5 (pdf) Ryhmälaskari III (pdf) Exercise 5 (pdf) Ensimmäinen kurssikoe /first course exam ti 26.10. klo 16-20 päärak. suuri luentosali
viikko 8, 1-5.11	Luennoilla aiheina keko Luentokalvot 149-168: (2/sivu)   (4/sivu)   (pdf) Karvi 2002, Luku 6.3 ja 6.4 Cormen et all 2001., Chapter 6.1-6.5 5. yksilöharjoitustehtävät käydään läpi III ryhmäharjoituksia ratkaistaan Yksilölaskari 6 (pdf) Exercise 6 (pdf) Ylimääräinen, vapaaehtoinen ryhmälaskari (pdf)
viikko 9, 8-12.11	Luennoilla aiheina järjestäminen Luentokalvot 169-191: (2/sivu)   (4/sivu)   (pdf) Karvi 2002, Luku 6.1, 6.2, 6.5, 6.6 Cormen et all 2001., Chapter 2.3, 7.1-7.2, 8.1-8.4 6. yksilöharjoitustehtävät käydään läpi III ryhmäharjoituksia ratkaistaan
viikko 10, 15-19.11	Luennoilla aiheina verkkojen määritelmä, toteutus sekä läpikäynti Luentokalvot 192-216: (2/sivu)   (4/sivu)   (pdf) Karvi 2002, Luku 9.1-9.4 Cormen et all 2001., Appendix B.4, Chapters 22.1-22.4 III ryhmäharjoitukset käydään läpi Yksilölaskari 7 (pdf) Ryhmälaskari IV (pdf) Exercise 7 (pdf) Group exercise 4: ask your group members for translation!
viikko 11, 22-26.11	Luennoilla aiheina lyhimmät polut Luentokalvot 217-240: (2/sivu)   (4/sivu)   (pdf) Karvi 2002, Luku 9.4 Cormen et all 2001., Chapter 24.2.-24.3, 25.2 7. yksilöharjoitustehtävät käydään läpi IV ryhmäharjoituksia ratkaistaan Yksilölaskari 8 (pdf) Exercise 8 (pdf)
viikko 12, 29.11-3.12	Luennoilla aiheina verkot virittävät puut torstaina ei luentoa Karvi 2002, Luku 9.5 Cormen et all 2001., Chapter 23 8. yksilöharjoitustehtävät käydään läpi IV ryhmäharjoituksia ratkaistaan Yksilölaskari 9 (pdf) Exercise 9 (pdf)
viikko 13, 6-10.12	tiistaina ei luentoa torstaina 10-12 kertausluento 9. yksilöharjoitustehtävät käydään läpi IV ryhmäharjoitukset käydään läpi
viikko 14, 13-17.12	Toinen kurssikoe Torstaina 16.12. klo 16-20 Exactumin salissa A111, huom: koeaika 3.5 tuntia

Tätä sivua ylläpitää luentojen ajan kurssin luennoija Matti Luukkainen.