58131 Tietorakenteet (8 op), kevät 2009

Ajankohtaista

Erilliskokeen 26.1.2010 tulokset ovat ilmoitustaululla.

Uusi kurssi on alkanut: vanhat mallivastaukset on poistettu.

Erilliskoe 10.11.2009.
Tulokset. Kokeen keskiarvo oli 20,25 ja hajonta 6,61.
Viime erilliskokeen 10.11.2009 tulokset ovat ilmoitustaululla. Ottakaa kiitos yhteyttä sähköpostitse (patrik.floreen (at) cs.helsinki.fi) 27.11. mennessä, jos teillä on kysyttävää.

Aiempia tuloksia

Erilliskoe 15.9.2009.

Tulokset. Kokeen keskiarvo oli 31,17 ja hajonta 18,15.
Palautetilaisuus: Arvosteluun voi tutustua sopimalla sähköpostitse (patrik.floreen (at) cs.helsinki.fi) tapaamisajasta. Sähköpostin asiasta kuuluu lähettää viimeistään 5.10.2009.
Erilliskoe 11.8.2009.

Tulokset. Kokeen keskiarvo oli 22,45 ja hajonta 17,96; tätä laskiessa ei ole huomioitu kolme osallistujaa, jotka eivät vastanneet yhteenkään tehtävään.
Uusinta- ja erilliskoe 9.6.2009.

Tulokset. Vitostehtävä ei ollut niin helppo korjata ja muutin arvostelun siitä vielä, jolloin korotin pari arvosanaa maanantaina 15.6. Kokeen keskiarvo oli 28,7 ja hajonta 14,3.
Kurssin tuloslista.
Tarkastuslista, jossa on kaikki laskarikerrat eriteltynä. Tässä listassa laskuharjoitus 13=Trakla, laskuharjoitus 14=ryhmätehtävä 1 jne.
Arvosteluasteikko:
50-60: 5
45-49: 4
40-44: 3
35-39: 2
30-34: 1
-29: hylätty

Perustietoa kurssista

Kurssille voi osallistua opiskelija, joka on suorittanut kurssit Johdatus diskreettiin matematiikkaan ja Ohjelmoinnin jatkokurssi.
Tiedot siitä kenellä on puutteita esitietovaatimuksissa löytyy Moodlesta courses.cs.helsinki.fi
Lisätehtävät opiskelijoille, joilla ei ole esitiedot kunnossa esitietokokeen jälkeenkään ovat tässä: Lisätehtävät (pdf).
Kurssi 2009 seuraa olennaisesti Jyrki Kivisen vuonna 2008 pitämän kurssin sisältöä. Luentomateriaali perustuu pitkälti Jyrki Kivisen materiaaliin. Tämä perustuu taas pitälti kirjaan T.H. Cormen, C. E. Leiserson, R. L. Rivest and C. Stein: Introduction to Algorithms, 2nd edition, MIT Press, Cambridge, Massachusetts, 2001. Tätä kirjaa ei tarvitse kurssilla välttämättä hankkia.
Yleisiä tietoja kurssista löytyy kurssikuvauksesta.

Annettava opetus

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

Luennot: ti 10-12, to 10-12, A111 (Patrik Floréen)

Harjoitusryhmät:
ti 14-16, C222 (Topi Musto)
ti 16-18, B119 (Janne Korhonen)
ke 12-14, CK111 (Topi Musto)
ke 16-18, CK111 (Janne Korhonen - in English)
to 14-16, CK111 (Antti Laaksonen)
pe 12-14, CK111 (Antti Laaksonen)

Opettajien sähköpostiosoitteet ovat:
Patrik.Floreen (at) cs.Helsinki.FI
Janne.H.Korhonen (at) cs.Helsinki.FI
Antti.H.S.Laaksonen (at) cs.Helsinki.FI tai Antti.H.Laaksonen (at) Helsinki.FI
Topi.Musto (at) cs.Helsinki.FI

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.

Kurssikokeissa ja erilliskokeissa saa olla mukana A4-kokoinen "lunttilappu"!

kurssikoe 1: ma 23.2.2009 klo 16-19. Tämän kurssikokeen alueeseen kuuluu luentojen luvut 1-3.
Kokeen keskiarvo oli 16,29 ja hajonta 5,15; tehtävien keskiarvot (ja hajonnat) olivat 1: 5,76 (1,77) 2: 5,00 (2,63) 3: 5,90 (2,40). Huom: Keskiarvot on laskettu tehtyjen tehtävien yli, joten jos joku ei ole tehnyt tehtävää k, niin sitä ei ole otettu mukaan tehtävän keskiarvoa laskettaessa.
kurssikoe 2: ke 29.4.2009 klo 16-19. Tämän kurssikokeen alueeseen kuuluu koko kurssi.
Kokeen keskiarvo oli 13,41 ja hajonta 4,78; tehtävien keskiarvot (ja hajonnat) olivat 4: 6,46 (1,68) 5: 2,8 (3,1) 6a: 5,5 (2,3) 6b: 2,4 (2,3).

Harjoitustehtäviä on kolmenlaisia: tavallisia laskuharjoitustehtäviä, ryhmätyötehtäviä ja TRAKLA2-järjrestelmään tehtyjä tehtäviä.

Hyväksytyn suorituksen raja on n. 30 pistettä ja arvosanan 5/5 raja n. 50 pistettä. Laskuharjoitussuorituksia pitää olla ainakin 25% tehtävistä; pienempi määrä johtaa suorituksen hylkäämiseen. Jos suorittaa 25% tehtävistä saa 0 pistettä laskuharjoituksista; maksimipistemäärän 12 saa suorittamalla noin 85% tehtävistä. (Käytännössä kurssin menestyksekäs suorittaminen edellyttää yleensä huomattavasti minimin ylittävää harjoitussuoritusmäärä.) Laskuharjoituspisteitä saa seuraavasti:
76-90 tehtävää: 12 pist.
71-75 tehtävää: 11 pist.
67-70 tehtävää: 10 pist.
62-66 tehtävää: 9 pist.
58-61 tehtävää: 8 pist.
53-57 tehtävää: 7 pist.
49-52 tehtävää: 6 pist.
44-48 tehtävää: 5 pist.
40-43 tehtävää: 4 pist.
35-39 tehtävää: 3 pist.
31-34 tehtävää: 2 pist.
26-30 tehtävää: 1 pist.
22-25 tehtävää: 0 pist.
-21 tehtävää: hylätty kurssista.

Uusintakoe pidetään ti 9.6.2009 klo 16-20 salissa A111. Uusintakokeessa harjoituspisteet otetaan huomioon.

Vaihtoehtoinen suoritustapa on erilliskokeella, ilman osallistumista opetukseen. Erilliskoe pidetään ti 9.6.2009 klo 16-20 salissa A111 (samassa yhteydessä kuin uusintakoe). Erilliskokeessa on yksi tehtävä enemmän kuin uusintakokeessa.

Luentomateriaali

Luennot pdf-muotoisena.

Luennot ps-muotoisena 4 sivua per sivu.

Luentomateriaaliin tehtiin pieniä korjauksia 16.1.2009: s. 35 (ä-kirjaimet), s. 37 (j+1 piti olla i ja i piti olla k+1), s. 38 (kuin s.35), s. 46 (Theta), s. 50 (lyöntivirhe t->s), s. 52 (summa d(f_1(n)+f_s(n)) ).
Luentomateriaaliin tehtiin 20.1.2009 korjauksia: s. 1 (ohjelmointikurssin nimi), s. 65 (induktiolla -> iteroimalla).
Luentomateriaaliin tehtiin 23.1.2009 lyöntivirhekorjauksia sivuilla 89 ja 93.
Luentomateriaaliin tehtiin 27.1.2009 korjauksia kaavoihin sivuilla 159, 161 ja 162 sekä pseudokoodiin sivuilla 180-181.
Luentomateriaaliin tehtiin 2.2.2009 korjauksia sivuille 231 (lisäinformaatiota) ja 241 (max -> min)
Luentomateriaaliin tehtiin 12.2.2009 korjaus sivulle 307: Max-Heapify -> Build-Max-Heap toiseksi viimeisellä rivillä.
Luentomateriaaliin tehtiin 16.2.2009 korjaus sivulle 130 (left -> right) ja korjaus sivulle 195: tarkennettiin miten B+-puun sisäsolmun halkaisu tehdään.
Luentomateriaaliin tehtiin 10.3.2009 korjaus sivulle 334 (u+v u+v<=n) ja sivulle 362 (lattiafunktio otetaan arvosta (p+r)/2).
Luentomateriaaliin tehtiin 11.3.2009 korjaus sivulle 336, jossa kuvataan aikavaativuus.
Luentomateriaaliin tehtiin 12.3.2009 korjaus sivulle 361 (p<20 -> r-p<20).
Luentomateriaaliin tehtiin 18.3.2009 korjaus sivulle 293 (ylivuoto tarkistetaan Max-Heapify:ssa eikä Left:issa ja Right:issa).
Luentomateriaaliin tehtiin 19.3.2009 korjaus sivulle 422 (u->v) ja sivulle 424 (nuolien suunta todistuksessa, erikoistapaus p=u huomioitu).
Luentomateriaaliin tehtiin 24.3.2009 korjaus sivulle 448 (\delta(v,s) -> \delta(s,v) ).
Luentomateriaaliin tehtiin 26.3.2009 korjaus sivulle 460 (d[u] -> d[v]).
Luentomateriaaliin tehtiin 31.3.2009 korjauksia sivuille 501 (aliooon -> alkioon), 510 (\alpha(m,n) -> \alpha(n) ), s. 524 (s. 514 -> s. 516), s. 525 (selvennetty missä kohtaa algoritmia ollaan sekä (p[u],v) -> (p[u],u) ).
Luentomateriaaliin tehtiin 8.4.2009 korjaus sivulle 543 (ylimääräinen sana "pidetään" poistettiin).
Luentomateriaaliin tehtiin 17.5.2009 korjaus sivulle 297 (kohta: avain A[heap-size[A]] positioon 1).
Luentomateriaaliin tehtiin 23.4.2009 sivulle 439 selventävä lisälause siitä, mitä transpoosiverkko on.
Luentomateriaaliin korjattiin 29.4.2009 sivulle 6 sisällysluettelo vastaamaan lopullista lukujakoa.

Huomaa, että englanninkielisillä sivuilla on selostettu, mitkä osat Cormenin kirjasta vastaavat luentoja.

Luennoilla eteneminen

Luento 1 (13.1.): kalvot 1-37
Luento 2 (15.1.): kalvot 33-66
Luento 3 (20.1.): kalvot 67-108
Luento 4 (22.1.): kalvot 109-144
Luento 5 (27.1.): kalvot 145-173
Luento 6 (29.1.): kalvot 174-216
Luento 7 (3.2.): kalvot 215-243
Luento 8 (5.2.): kalvot 244-262
Luento 9 (10.2.): kalvot 263-292
Luento 10 (12.2.): kalvot 293-314
Luento 11 (17.2.): kertaus: matematiikan todistusmenetelmiä, O-notaatio, rekursio, linkitetyt listat, B+-puut
Luento 12 (19.2.): kertaus: AVL-puiden rotaatiot, B+-puu-esimerkki; katsottiin edellisvuoden kurssikoe läpi
Luento 13 (10.3.): tasoitettu vaativuus, kalvot 315-340
Luento 14 (12.3.): kalvot 341-379
Luento 15 (17.3.): kalvot 380-412
Luento 16 (19.3.): kalvot 413-435
Luento 17 (24.3.): kalvot 436-458
Luento 18 (26.3.): kalvot 459-497
Luento 19 (31.3.): kalvot 498-533
Luento 20 (2.4.): EI LUENTOA
Luento 21 (7.4.): kalvot 534-548, vaativuusanalyysin kertaus
Luento 22 (16.4.): Lukujen 4-6 kertaus; edellisvuoden kurssikokeen tehtävät 1-2
Luento 23 (21.4.): Luvun 7 kertaus: läpikäynnit ja lyhimmät polut; edellisvuoden kurssikokeen tehtävä 3
Luento 24 (23.4.): Kertaus loppuun; edellisvuosien koetehtävien läpikänti

Harjoitustehtävät

Ensimmäiset laskuharjoitukset pidetään jo ensimmäisellä luentoviikolla!

Harjoitus 1

Harjoitus 2
Huom: Tehtävässä 5 tarvitaan raja-arvon määritelmää. Reaalimuuttujan funktion f(x) raja-arvo äärettömyydessä on a, jos kaikille reaaliluvuille e>0 on olemassa reaaliluku m siten, että |f(x) - a| < e, kun x > m.

Harjoitus 3

Harjoitus 4 Huom: Voit tehtävässä 1 yksinkertaisesti täydentää oheista luokkaa.
Koska on ollut ongelmia TRAKLAn Shibboleth-kirjautumisen kanssa yhdessä vaiheessa, kierroksen 2 määräaika on siirretty: uusi määräaika on 11.2.

Harjoitus 10 Huom: Tehtävässä 3b pitäisi lukea rivillä 2 print v, eikä return v.

Harjoitus 11

Harjoitus 12

Pistetilanne 27.4.2009 klo: 12.02 on täällä. Tässä listassa laskuharjoitus 13=Trakla, laskuharjoitus 14=ryhmätehtävä 1 jne.

TRAKLA2-tehtävät

TRAKLA2 on TKK:ssa kehitetty oppimisympäristö. Tehtävät on ryhmitelty "kierroksiin", siis ryhmiin tehtäviä, joilla on sama määräaika. Kunkin tehtävän oikeasta ratkaisusta saa yhden laskaripisteen. Samaa tehtävää voi yrittää monta kertaa ja paras tulos jää voimaan. TRAKLA2:een pääset täältä Hakan kautta omilla yliopiston käyttäjätunnuksillasi. Voit valita TRAKLA2:n kieleksi suomen tai englannin.

Vanhoja kurssikokeita

Vuoden 2008 kurssikoe 1 ratkaisuineen ja kurssikoe 2 ratkaisuineen.

Muita vanhoja tehtäviä ratkaisuineen.

2.2.2010 Patrik Floréen

Tietojenkäsittelytieteen laitos

Tietoa laitoksesta: