Tietorakenteet ja algoritmit

Kurssille voi ilmoittautua »
Vuosi Lukukausi Päivämäärä Periodi Kieli Vastuuhenkilö
2013 kevät 14.01-24.04. 3-4 Suomi Patrik Floréen

Non finnish students, contact the lecturer beforehand.

Information for international students

The course is given in Finnish. There will not be lecture materials or exercises in English.

At the course, students are expected to know programming in the extent of the Java programming courses Ohjelmoinnin perusteet and Ohjelmoinnin jatkokurssi and mathematics in the extent of the course Johdatus yliopistomatematiikkaan - Introduction to University Mathematics, or similar.

For self-studies these are the pages in the book Cormen, Leiserson, Rivest, Stein:  Introduction to Algorithms: For the first course exam the pages in the 3rd edition are 5-29, 43-60, 229-240, 1176-1179, 246-247, 286-298, 253-276 and for the second course exam 151-165, 29-38, 170-199, 1168-1172, 587-699, 561-572. Also the 2nd edition book is ok (the difference is mainly in the pseudocode style). The corresponding pages in the 2nd edition are for the first exam 5-27, 41-56,197-208, 1087-1090, 214-216, 253-264, 221-244 and for the second exam127-142, 27-36, 145-173, 1080-1084, 525-635, 498-509.

For the first exam also AVL-trees (not in Cormen) are included. The material is available here.

Some freely available videos from MIT covering even more than what this course covers (but not AVL-trees).

Three batches of example exercises for the non-Finnish students have been prepared for the course in 2012: first batch , second batch , third and last batch. This are intended for self-study and are suitable also in year 2013. Batch one and two covers the first part of the course; the third batch covers the second part.

I offer two ways to pass this course: either by participating in the two exams on the normal course going on now (these are 25.2. at 16.00 in Exactum A111 and 6.5. at 16.00 in Exactum A111) OR by participating in ONE separate exam covering the full course.

The next separate exam is 11.6. at 16.00 in Exactum A111. Please note that you are allowed to have a hand-written A4-sized sheet of paper of personal notes with you at the exam (you can write on both pages).

Please note: if you wish to have the exam questions in English, you have to explicity request it from the lecturer (patrik.floreen@cs.helsinki.fi) in advance, perferably at least one week before.

Yleistä

Esitiedot

Kurssin esitietovaatimuksina on kurssit Ohjelmoinnin jatkokurssi ja Johdatus yliopistomatematiikkaan (UUTTA!, ennen Johdatus diskreettiin matematiikkaan). Kurssin suorittaminen on käytännössä mahdotonta, jos näissä esitiedoissa on huomattavia puutteita. Esitietovaatimuksia ei enää testata esitietokokeessa, niin kuin aiemmin (UUTTA!). Luennoijalta ei siis tarvitse kysyä, saako osallistua kurssille vaikka esitietokurssi puuttuu.

Luennot

Vuoden 2013 kurssin sisältö on sama kuin aikaisemman kurssin Tietorakenteet, vaikka nimi on vaihtunut paremmin sisältöä kuvaavaksi.

Luentomateriaali (pdf). Materiaali päivitetään kurssin kuluessa.

Muutoksia tehty seuraaville sivuille (epäolennaisia kirjoitusvirhe- y.m. muutoksia ei luetella): s. 25 lisätty sana "yli", s. 54-55 korjattu numerot esimerkissä, s. 70 käytetty A.length algoritmissa, s. 68, 72, 83 ja 100 poistettu sisimmästä loopista puhuminen, s.69 poistettu pari turhaa kohtaa sivun lopusta. s. 46 lisätty selitys, että oikeastaan lasketaan bittejä ja s. 61 kirjoitettu määritelmän negaatio auki, s. 102 tarkennettu että x on viite, s. 121 ja 134 muutettu otsikot, s. 143 tähdennetty että on kaksisuuntaisesta listasta kyse, s. 148 insert ei ole laskareissa joten ko. toteamus poistettu, s. 170 viimeinen sulussa oleva kommentti sanottu yksinkertaisemmin, s. 181 korjattu väärät sivunumerot, s. 238 lisätty tieto uuden solmun korkeudesta 0, s. 241-242 muutettu kommentit niin että korkeutta mainitaan myös, s. 357 lisätty sana keskimäärin pikajärjestämisen yhteyteen, s. 358 korjattu viittaus sivuun 338, s. 363 korjattu korkeudet (äh, olihan se oikein), s. 376 laitettu selkeämmin mikä on k.

Muutoksia 12.3. s. 361 for-looppi voi loppua 2:een, koska sen jälkeen viimeinenkin alkio on paikallaan.

Muutoksia 13.3. s. 402 viittaus sivuun 84 (eikä 79).

Muutoksia 19.3. s. 490 kuvan numeroinnit korjattu.

Muutoksia 20.3. s. 477-483 esiintyi DFS-visit ilman parametria G, nyt lisätty.

Muutoksia 25.3. s. 500, 503 ja 504 korjattu G G^T:ksi ja s. 514 korjattu w(v_i-1,v_i) w(v_i,v_i+1):ksi.

Oppimista tukevaa lisämateriaalia internetissä: Järjestämisalgoritmien visualisointi. Lyhimpien polkujen etsinnän visualisointi.

Luennot ma, ke 10-12 alkavat 10.15, välissä pidetään 5 minuutin tauko ja loppuvat 11.50.

Luentojen sisällysluettelo:

KURSSIKOKEEN 1 ALUE:

  • Alkutekstit s. 1-12
  • 1 Johdanto tietorakenteisiin s. 19-106
  • 2. Perustietorakenteet: Pino, jono ja lista s. 107-153
  • 3. Hakupuut s. 154-294
  • 4. Hajautus s. 295-334

KURSSIKOKEEN 2 ALUE (sen lisäksi että on osattava kurssikokeen 1 asiat):

  • 5. Keko s. 335-354
  • 6. Järjestäminen s. 355-421
  • 7. Verkot s. 422-623
  • 8. Algoritminsuunnittelumenetelmiä s. 624-635

Luentoaikataulu:

  • Viikko 1: ma s. 1-32, ke s. 33-61.
  • Viikko 2: ma s. 62-100, ke s. 101-164.
  • Viikko 3: ma s. 165-215, ke s. 216-250.
  • Viikko 4: ma s. 251-294, ke s. 295-334.
  • Viikko 5: ma s. 335-362, ke kertausta ja vanhoja tenttitehtäviä (invariantti sekä aika- ja tilavaativuuden määrittäminen)
  • Viikko 6: kertausta ja vanhoja tenttitehtäviä (linkitetyt listat, O-notaatio, rekursio, puut). Ei luentoa 20.2.
  • Viikko 7: ma s. 363-395, ke s. 396-433 sekä kurssikokeen 1 palautetilaisuus.
  • Viikko 8: ma s. 434-462, ke s. 463-491.
  • Viikko 9: ma s. 492-517, ks s. 517-548.
  • Pääsiäisloma on 28.3.-3.4., minkä aikana EI ole opetusta (ei luentoja, ei laskuharjoituksia).
  • Viikko 10: virittävät puut
  • Viikko 11: kurssi loppuun, sen jälkeen kertausta ja vanhojen tenttitehtävien läpikäyntejä
  • Viikko 12: ei luentoa maanantaina 22.4.!

Harjoitukset

Harjoituksia on kolmelaisia: Tavalliset laskuharjoitukset, ohjelmointitehtävät (Tira-paja) ja Trakla2-automaattitehtäviä. Tavalliset laskuharjoitukset alkavat jo ensimmäisellä luentoviikolla!

Laskuharjoitukset: Laskuharjoituksia ei palauteta etukäteen, vaan tehdään etukäteen ja käydään läpi laskuharjoitustilaisuudessa. Jos sinulla on vaikeuksia laskuharjoitusten kanssa, voi kysyä neuvoja Jarmolta pajassa. Laskuharjoitustehtäviä tulee olemaan yhteensä noin 67-68.

Huomio: Jos tehtävä koostuu monesta alakohdasta (a, b, c, ...), voit merkitä rastin tehtävän suorituksen merkkinä, jos olet tehnyt vähintään puolet alakohdista.

Tira-paja. Vara-pajasivut (mikäli viralliset tirapajan sivut ovat nurin): http://www.cs.helsinki.fi/u/jarmoiso/tira/ Pajan määräaika on yleensä seuraavan viikon maanantai klo 23.59. Yhteyshenkilö: jarmo.isotalo@cs.helsinki.fi. Pajatehtäviä tulee olemaan kurssilla noin 60-64.

Trakla2 Traklaan kirjaudutaan tietojenkäsittelytieteen laitoksen tunnuksilla. Mikäli järjestelmään kirjautuminen ei toimi, niin ilmoitathan siitä yhteyshenkilölle. Yhteyshenkilö: jarmo.isotalo@cs.helsinki.fi. Traklatehtäviä on yhteensä 25.

Jatkuva palaute

Tänne tulee viikoittain uusi kysymys vastattavaksi. Kysymys vaihtuu maanantaisin.

Viikon 1 kysymys: Kurssin alussa on edetty liian nopeasti: 8; sopivalla vauhdilla: 31; liian hitaasti: 9.

Viikon 2 kysymys: Laskuharjoitukset 1-2 ovat olleet liian helppoja: 3; sopivia: 23; liian vaikeita: 48. Kommenteista selvisi, että laskarit 2 pidettiin vaikeampina kuin laskarit 1.

Viikon 3 kysymys: Pajatehtävät viikko 1-2 ovat olleet liian helppoja: 4; sopivia: 51; liian vaikeita: 42.

Viikon 4 kysymys: Vaikeinta kurssilla tähän mennessä on ollut: rekusio: 13; invariantti: 6; aika- ja tilavaativuuden määrittäminen: 16; O-notaatio: 4; pino ja jono: 1; linkitetty lista: 15; binäärihakupuu ja sen operaatiot: 2; AVL-puu: 2.

Viikon 5 kysymys: Mikä osuus kurssin opetuksesta on hyödyllisintä? Luennot: 4; Laskuharjoitukset: 26; Paja-tehtävät: 18; Trakla: 4. Kommentti luennoijalta: Tulos on odotettu, koska aihe on sellainen, jota oppi parhaiten tekemällä itse.

Kurssikokeen 1 jälkeinen kysymys: Tentti oli: ihan liian helppo: 0; helppo: 6; sopiva: 29; vaikea: 24; ihan liian vaikea: 6.

Viikon 7 kysymys: Viime viikkojen pajatehtävät ovat olleet: liian helppoja: 0; helppoja: 1; sopivia: 6; vaikeita: 16; liian vaikeita: 15.

Viikon 8 kysymys: Viime viikkojen laskaritehtävät ovat olleet: liian helppoja : 1; helppoja : 2; sopivia : 8; vaikeita : 10; liian vaikeita : 9.

Viikon 9 kysymys: Ajankohtainen kysymys. (on nyt aktivoitu!), määräaika 8.4.

Kurssin suorittaminen

Kurssiin kuuluu kaksi koetta, kukin 22 maksimipistettä, eli yhteensä 44 maksimipistettä. Kokeissa saa olla mukana itse tehty, käsin kirjoitettu yksi A4-kokoinen "lunttilappu", jonka molemmilla puolilla saa olla tekstiä. Lunttilapun tekemisessä ei siis saa käyttää tietokonetta eikä kopiokonetta.

Tässä vanhoja kurssikokeita: Vuoden 2012 kevään kurssikoe 1 ja kurssikoe 2. Vuoden 2011 kevään kurssikoe 1 ja kurssikoe 2.

Kurssikoe 25.2. Ratkaisut Tehtävien keskiarvo;keskihajonta (/maksimi) olivat seuraavat 1: 3,38;0,94  (/4), 2: 1,83; 1,78 (/4), 3: 3,50; 1,60 (/5); 4: 5,97;2,61 (/9), yhteensä 14,68; 5,24 (/22). Pistejakauma oli seuraava (154 osallistujaa):


Pisteet Lkm
22 7
21 14
20 11
19 12
18 14
17 8
16 11
15 5
14 16
13 5
12 13
11 10
10 5
9 3
8 5
7 2
6 1
5 4
4 1
3 1
2 1
1 5
0 0

Omat tulokset (myös laskuharjoitusrastien määrät) näkyvät TIKLIssä https://ilmo.cs.helsinki.fi/tulokset/. HUOM: Vaikuttaa siltä, että tämä ei toimi niin kuin on kerrottu. Kokeilkaa tätä linkkiä: https://ilmo.cs.helsinki.fi/tulokset/study/58131/2013/K/K/1. Palautetilaisuus: Heti luentojen jälkeen keskiviikkona 13.3. luentosalissa.

Kurssikokeen yhteydessä tehtiin kokeilu, jossa joillekin opiskelijoille oli jaettu tarra kiinnitettäväksi vastauspapereihin. Tarkoitus on, että näitä papereita skannataan ja kukin kokeiluun osallistuva saa sähköpostiinsa skannatut vastauspaperit. Mahdolliset kommentit tähän kokeiluun liittyen osoitetaan Ossi Karkulahdelle: karkulah@cs.helsinki.fi. Skannaus on suoritettu 12.3.2013.

Kurssikoe 2 on 6.5. klo 16.00 salissa A111.

Harjoituksia on siis kolmenlaisia:

  • Tavallisia laskuharjoituksia, joista voi saada yhteensä 8 pistettä. Yhden pisteen saa tekemällä noin 50% tehtävistä. Täydet 8 pistettä saa tekemällä noin 90%:lla tehtävistä.
  • Ohjelmontitehtäviä, joista saa ohjausta TiRa-pajassa ja joista voi saada yhteensä 8 pistettä (samalla kaavalla: 50% antaa 1 pisteen, 90% antaa 8 pistettä). Ohjelmointitehtävien määräaika sovitaan ensimmäisellä luennolla. Ohjelmointitehtävät tarkastetaan TMC-ohjelmalla ("Test My Code").
  • TRAKLA2-automattitehtäviä, joilla voi korvata (noin) 1/3 ohjelmointitehtävistä (eli pistemäärä sisällytetään ohjelmointitehtäväpistemäärään). Tarkka kaava riippuu TRAKLA2-tehtävien määrästä.

Kurssin suoritukseen vaaditaan vähintään puolet kurssin kokonaispistemäärästä eli 60/2 = 30, koepisteiden summan täytyy myös olla vähintään 44/2 = 22 (eli vaikka ensimmäisestä kurssikokeesta 9 ja toisesta 13). Huomaa, että harjoitukset eivät ole pakollisia, mutta jos harjoituksia ei tee, voi maksimissaan saada koepisteiden summan verran pisteitä, eli ei ole mahdollista saada ylempiä arvosanoja. Tällöin voisi olla eduksi suorittaa kurssi erilliskokeella ilman että harjoituspisteet vaikuttaisivat (viimeinen vaihtoehto alla).

Erittäin kiitettävästä paja-tehtävien (ei Trakla2) tekemisestä saa lisäksi ylimääräisiä opintopisteitä 1 tai 2 (UUTTA!): jos on tehnyt vähintään 80% tehtävistä saa yhden lisäopintopisteen, jos on tehnyt vähintään 95% saa kaksi lisäopintopistettä. (Huom: mainitut rajat on vielä ehdotus, tarkka raja vahvistetaan myöhemmin.)

Vaihtoehtoinen tapa suorittaa kurssi on erilliskokeella (60 maksimipistettä), jolloin kurssin suoritukseen kuuluu ainoastaan yksi erilliskoe.

Kurssin uusintakoe on 11.6. klo 16.00 salissa A111. Uusintakoe tarkoittaa, että laskuharjoituspisteitä käytetään hyväksi kurssin arvostelussa. Uusintakokeessa voi korvata myös vain ensimmäisen kurssikokeen suoritus tai toisen kurssikokeen suoritus.

Myös uusinta- ja erilliskokeissa saa olla mukana samanlainen "lunttilappu" kuin kurssikokeissa.

Kevään 2013 kurssia seuraavat ensimmäiset erilliskokeet ovat 11.6. klo 16.00 salissa A111 ja 13.8. klo 16.00 salissa A111. Tässä vanhoja erilliskokeita: Uusinta- ja erilliskoe 12.6.2012: tehtävät, ratkaisut. Erilliskoe 14.8.2012: tehtävät, ratkaisut. Erilliskoe 18.9.2012: tehtävät. Erilliskoe 27.11.2012: tehtävät, ratkaisut. Erilliskoe 29.1.2013 (syksyn Tiralle uusintakoe): tehtävät, ratkaisut, tulokset.

Kurssin arvosana määräytyy kokonaispistemäärästä, ohjeellisesti seuraavalla tavalla:

50-60 p.: arvosana 5

45-49 p.: arvosana 4

40-44 p.: arvosana 3

35-39 p.: arvosana 2

30-34 p.: arvosana 1

0-29 p.: hylätty

Kirjallisuus ja materiaali

Kurssimateriaali pohjautuu suurelta osin kirjaan: T. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein: Introduction to Algorithms, 3rd ed., MIT Press, 2009. Kirjan 2. painos on sekin käyttökelpoinen.Kurssilla on muutamia asioita joita Cormenin kirjasta ei löydy. Kaikissa asioissa käsittelytapa ei vastaa täysin Cormenia.