English summary for foreign students.

58131 Tietorakenteet syyslukukaudella 2003

Huomaa: Sekä kurssin että erilliskokeen tulokset ovat nyt esillä salin A412 ilmoitustaululla! Voit katsella niitä myös verkossa jos sinulla on käyttäjätunnus Tietojenkäsittelytieteen laitoksella:

• kurssi
• erilliskoe

Note: The results are now on the notice board in room A412! You can also view them on the web if you have a username for the Department of Computer Science.

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. Ja kääntäen, tämä kurssi ei siis opeta Java-kieltä.

2. Sisältö

Kurssi käsittelee perustietorakenteita kuten

• pinoja (stacks)
• jonoja (queues)
• puita (trees)
• verkkoja (graphs)

sekä niihin liittyviä algoritmeja.

Tämä kurssi käsittelee CC2001-kurssisisältöjen seuraavia aihepiirejä:

• DS5. Graphs and trees (etupäässä esimerkein).
• AL1. Basic algorithmic analysis (mutta ei juurikaan palautuskaavoja).
• AL3. Fundamental computing algorithms (mutta ei numeerisia algoritmeja).
• PF3. Fundamental data structures (mutta ei kieli- ja laitekohtaisia osia).

3. Suoritus

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

Kurssikokeet on maerkitty 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. Näin ollen tämän luennointikerran mukaisia erilliskokeita järjestetään kevätlukukaudella 2004.

3.1. Luennot

Kurssilla on luentoja viikoilla 38-49/2003, eli 16.9.-4.12.2003. Luennot pidetään tiistaisin ja torstaisin klo 10-12 auditoriossa.

Luennoijana on mvs.prof. Matti Nykänen.

(Luentotauon pituudeksi on sovittu vain 5 min. ja luennot päättyvät jo klo 11.50.)

3.2. Laskuharjoitukset

Kurssiin liittyy pakollisia laskuharjoituksia viikoilla 39-48/2003.

Tehtäviä käsitellään ohjatuissa pienryhmissä. Ensimmäisessä laskuharjoitustilaisuudessa (viikolla 39) tilaisuuteen ilmoittautuneista muodostetaan (noin) neljän (4) 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. Jos et pääse omaan tilaisuuteesi jollakin viikolla, niin sinun on sovittava asiasta etukäteen sekä laskuharjoitusassistenttisi että pienryhmäsi kanssa.

Tehtäviä käsitellään kahden viikon jaksoissa seuraavasti:

1. Edellisen luentoviikon päätteeksi luennoija jakaa seuraavan kahden viikon tehtävät tämän verkkosivun kautta.

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

3. Toisen 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-2 p.) ryhmä tältä kierrokselta saa. Nämä pisteet vaikuttavat suoraan arvosteluun.

   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 seuraavia asioita:

• Oman ryhmänsä toimintaa.

  Tämä tehdään siten, että ryhmä kirjoittaa kirjallisten ratkaisujensa loppuun lyhyet kommentit ryhmän toiminnasta tällä kierroksella. Kommentit voivat koskea esimerkiksi seuraavanlaisia kysymyksiä:

  • Toimiko ryhmän yhteistyö kitkatta?
  • Jakautuiko vastuu tasan ryhmäläisten kesken?
  • Ilmenikö ongelmia? Jos ilmeni, niin miten ne voisi välttää jatkossa?

  Kommenteissa ei tarvitse mainita ryhmäläisiä nimeltä. Keskeistä on, että koko ryhmä tarkkailee ja parantaa toimintaansa yhdessä.

• Toisilta ryhmiltä kuulemiaan ratkaisuesityksiä.

  Tämä tehdään siten, että jokaisella esityksellä on etukäteen nimetty toinen ryhmä, jonka vastuulla on sen arviointi.

  Arvioinnissaan ryhmän tulee keskittyä siihen, kuinka ymmärrettävän esityksen he saivat kuulla, ja kuinka sitä voisi jatkossa parantaa.

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.

3.3. Arvostelu

Kurssi pisteytetään ja arvostellaan seuraavasti:

I kurssikoe

24 p.

II kurssikoe

24 p.

Laskuharjoitukset:

5*2 p.

Ryhmien kirjalliset arvioinnit:

2 p.

Yhteensä:

60 p.

Läpipääsyarvosanan 1-/3 raja (korkeintaan):

30 p.

Korkeimman arvosanan 3/3 raja (korkeintaan):

52 p.

Muut arvosanat (1/3,1+/3,2-/3,2/3,2+/3,3-/3):

tasavälein näiden rajojen sisällä

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 (verkossa).

Tämä luentokurssi on siis mahdollista suorittaa juuri tämän luentokerran mukaisena kevätlukukauden 2004 ajan.

Tämän luentokerran laskuharjoituksista kerätyt pisteet huomioidaan kyseisen lukukauden ensimmäisessä erilliskokeessa. Seuraavissa erilliskokeissa niitä ei enää huomioida.

Ensimmäiseenkin erilliskokeeseen voi osallistua, vaikka ei olisikaan kerännyt laskuharjoituspisteitä: ero otetaan huomioon kokeessa.

Jos sinulla on hyväksyttävä este päästä jompaan kumpaan välikokeeseen, voit sopia etukäteen luennoijan kanssa mahdollisuudesta suorittaa vain kyseinen koealue ensimmäisen erilliskokeen yhteydessä.

4. Kurssimateriaali

Kurssimateriaali koostuu

• Timo Karvin tekemästä luentomuistiinpanoista, jonka voi ostaa laitoksen monistemyynnistä

• Kurssin kuluessa syntyvistä luentokalvoista, jotka luennoija jakaa tämän verkkosivun kautta kunkin luentoviikon päätteeksi

• Oppikirjasta T.H.Cormen, C.E.Leiserson, R.L.Rivest ja C.Stein: Introduction to Algorithms. Second Edition. The MIT Press, 2001.

  Kirjaan voi tutustua laitoskirjaston kurssikirjahyllystä. Ostaa ei siis tarvitse, mutta siitä on kyllä iloa myöhemminkin... (Kirjan ensimmäistä laitosta vuodelta 1990 voi myös käyttää, mutta sen kappalenumerointi poikkeaa hieman. Erot mainitaan alla.)

• Mapista, joka sijaitsee opiskelijahuoneessa A412. Mapista löytyvät:

  • Malliratkaisut jo käsiteltyihin laskuharjoitustehtäviin.

    Varoitus: Mapissa on vain ratkaisuluonnokset, joita on täydennettävä itse!

  • Ne luentokalvot, jotka eivät ole saatavilla tämän verkkosivun kautta sähköisessä muodossa.

Luennot etenevät eri järjestyksessä kuin luentomuistiinpanot, ja niiden painotuksetkin poikkeavat osin toisistaan. Tälle sivulle merkitään näkyviin, mitkä kohdat luentomuistiinpanoista ja oppikirjasta liittyvät mihinkin luentokalvoihin.

5. Aikataulu

Allaolevaan aikatauluun linkitetty kurssimateriaali (luentokalvot ja laskuharjoitukset) on sekä PostScript (PS) että Portable Document Format (PDF) -muodoissa.

Kalvot on pienennetty suhteessa 1:4 paperin säästämiseksi.

Ruudulla PDF-tiedostojen ulkoasu saattaa vaikuttaa epätarkalta, mutta paperille niiden pitäisi tulostua silti siististi. Jos myös paperijälki on huonoa, niin ilmoita luennoijalle.

aika	asiat
viikko 38	Luentokalvot 1-41 (PS) (PDF) Materiaali / References: Karvi 2002 Luvut 1 ja 8-8.1.3. Cormen et al 2001 Chapters 2 and 3. Cormen et al 1990 Chapters 1 and 2. Harjoitukset I (PS) (PDF) Exercises I (PS) (PDF)
viikko 39	Pienryhmät muodostetaan laskuharjoituksissa. I laskuharjoitustehtäviä ratkotaan. Luentokalvot 42-79 (PS) (PDF) Materiaali / References: Karvi 2002 Luvut 3 ja 4. Cormen et al 2001 Chapters 10.1 and 10.2. Cormen et al 1990 Chapters 11.1 and 11.2.
viikko 40	I laskuharjoitustehtävät käsitellään. II laskuharjoitustehtävät jaetaan. Luentokalvot 80-119 (PS) (PDF) Materiaali / References: Karvi 2002 Luvut 3.2.3, 4.1.3, 5.1, 5.2 ja 6.2. Cormen et al 2001 Chapters 2.3, 4.2 and B.5 Cormen et al 1990 Chapters 1.3, 4.2 and 5.5. Harjoitukset II (PS) (PDF) Exercises II (PS) (PDF)
viikko 41	II laskuharjoitustehtäviä ratkotaan. Luentokalvot 120-163 (PS) (PDF) Materiaali / References: Karvi 2002 Luvut 6-6.3.1. Cormen et al 2001 Chapters 2.3.2, 6-6.2, 6.4 and 7-7.4.1. Cormen et al 1990 Chapters 1.3.2, 7-7.2, 7.4 and 8-8.4.1.
viikko 42	II laskuharjoitustehtävät käsitellään. III laskuharjoitustehtävät jaetaan. Luentokalvot 164-189 (PS) (PDF) Materiaali / References: Karvi 2002 Luvut 6.3.2-6.6.2. Cormen et al 2001 Chapters 6.3-6.5 and 8. Cormen et al 1990 Chapters 7.3-7.5 and 9. Harjoitukset III (PS) (PDF) Exercises III (PS) (PDF)
viikko 43	III laskuharjoitustehtäviä ratkotaan. Luentokalvot 190-223: (PS) (PDF) Materiaali / References: Karvi 2002 Luvut 5.4, 8.2-8.3 ja 8.4.2. Cormen et al 2001 Chapters 12-12.3, 13.2 and 18.-18.2. Cormen et al 1990 Chapters 13-13.3., 14.2 and 19-19.2.
ma 27.10.	I kurssikoe: klo 16-19.30, päärakennuksen sali 1. Koealue käsittää viikkojen 38-42 asiat, eli kalvot 1-189. (Huomaa: Nyt voit valokopioida myös ne kuvat, joita ei ole sähköisessä mudossa!) Kalvoja vastaava muu materiaali on mainittu yllä. First midterm: 4PM-7.30PM, University main building lecture hall 1. The material consists of lectures for weeks 38-42; in other words, slides 1-189 in Finnish. (Note: Now you can photocopy also those figures that are not available electronically!) The corresponding English material is given above. I kurssikokeen tulokset ovat vihdoin salin A412 ilmoitustaululla. Voit tutustua arvosteluun tarkemmin alla mainittuna aikana. The results for the first midterm are finally on the notice board in room A412. You can ask questions about the grading at the time given below.
viikko 44	III laskuharjoitustehtävät käsitellään. IV laskuharjoitustehtävät jaetaan. Luentokalvot 224-239 (PS) (PDF) Materiaali / References: Karvi 2002 Luvut 8.4.1 ja 8.4.3. Cormen et al 2001 Chapter 13.3. Cormen et al 1990 Chapter 14.3. Harjoitukset IV (PS) (PDF) Exercises IV (PS) (PDF)
viikko 45	IV laskuharjoitustehtäviä ratkotaan. Huomaa! Luentokalvon 233 pseudokoodin riviltä 3 löytyi myöhemmin virhe: solmulla y ei välttämättä ole vasenta lasta! Korjattu versio on tässä PS- ja PDF-muodoissa. Luentokalvot 240-283: (PS) (PDF) Materiaali / References: Karvi 2002 Luvut 2, 7 ja 8.4.4. Cormen et al 2001 Chapters 11.-11.4, 13.4 and 17.4. Cormen et al 1990 Chapters 12-12.4, 14.4 and 18.4.
viikko 46	IV laskuharjoitustehtävät käsitellään. V laskuharjoitustehtävät jaetaan. Luentokalvot 284-306 (PS) (PDF) Materiaali / References: Karvi 2002 Luvut 7.3.2, 9.2 ja 12.3. Cormen et al 2001 Chapters 11.4, 17.4, 22-22.1 and 22.3. Cormen et al 1990 Chapters 12.4, 18.4, 23-23.1 and 23.3. Harjoitukset V (PS) (PDF) Exercises V (PS) (PDF)
viikko 47	V laskuharjoitustehtäviä ratkotaan. Luentokalvot 307-340: (PS) (PDF) Materiaali / References: Karvi 2002 Luvut 9.3 ja 10.2. Cormen et al 2001 Chapters 22.2-22.4. Cormen et al 1990 Chapters 23.2-23.4.
viikko 48	V laskuharjoitustehtävät käsitellään. Huomaa: Tehtävään V.1 saa luentokalvoilla 6.3.4 luonnosteltua yksinkertaisemman ratkaisun, jos muuttaa hieman punamustan puun rakennetta ennen kuin toteuttaa sillä keon. (PS) (PDF) Luentokalvot 341-380: (PS) (PDF) Materiaali / References: Karvi 2002 Luvut 9.2.3 ja 9.4. Cormen et al 2001 Chapters 22.2, 24.2, 24.3 and 25.2. Cormen et al 1990 Chapters 23.2, 25.2, 25.4 and 26.2.
viikko 49	Luentokalvot 381-424: (PS) (PDF) Materiaali / References: Karvi 2002 Luvut 9.5, 10.3 ja 11.2. Cormen et al 2001 Chapters 21.1, 21.3, 23 and 25.2. Cormen et al 1990 Chapters 22.1, 22.3, 24 and 26.2.
pe 05.12.	I kurssikokeen arvosteluun voi tutustua klo 14-15 salissa B452. Questions about the grading of the first midterm are answered at 2-4PM in room B452.
ke 10.12.	II kurssikoe: klo 16-19.30 Porthanian salissa I. Koealue käsittää luennot I kurssikokeen lopusta koko kurssin loppuun, eli kalvot 190-424. Kalvoja vastaava muu materiaali on mainittu yllä. II midterm: at 4PM-7.30PM Porthania building lecture hall I. The material consists of the lectures from I midterm to the end of the course; that is, slides 190-424. The corresponding English material is given above.
ti 13.01.	Erilliskoe klo 16-19.30 Auditoriossa.