Tietorakenteet ja algoritmit

58131
8-10
Algoritmit ja koneoppiminen
Aineopinnot
Perustietorakenteet kuten pinot, jonot, puut ja verkot sekä niiden käsittelyalgoritmit. Esitiedot: Ohjelmoinnin jatkokurssi (Java-ohjelmointi) ja Johdatus yliopistomatematiikkaan (Johdatus diskreettiin matematiikkaan). Huom: Kurssin harjoitukset alkavat jo ensimmäisellä luentoviikolla. Kurssikirja: T. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein: Introduction to Algorithms, 3rd ed., MIT Press, 2009.

Koe

02.03.2015 16.00 A111 ja CK112
06.05.2015 16.00 A111 ja CK112
Vuosi Lukukausi Päivämäärä Periodi Kieli Vastuuhenkilö
2015 kevät 12.01-29.04. 3-4 Suomi Patrik Floréen

Luennot

Aika Huone Luennoija Päivämäärä
Ma 10-12 A111 Patrik Floréen 12.01.2015-25.02.2015
Ke 10-12 A111 Patrik Floréen 12.01.2015-25.02.2015
Ma 10-12 A111 Patrik Floréen 09.03.2015-01.04.2015
Ke 10-12 A111 Patrik Floréen 09.03.2015-01.04.2015
Ke 10-12 A111 Patrik Floréen 15.04.2015-15.04.2015
Ke 10-12 A111 Patrik Floréen 29.04.2015-29.04.2015

Harjoitusryhmät

Group: 1
Aika Huone Ohjaaja Päivämäärä Huomioitavaa
Ke 16-18 B119 Patrik Floréen 12.01.2015—27.02.2015
Ke 16-18 B119 Patrik Floréen 09.03.2015—24.04.2015
Group: 2
Aika Huone Ohjaaja Päivämäärä Huomioitavaa
To 12-14 B222 Toni Annala 12.01.2015—27.02.2015
To 12-14 D122 Toni Annala 09.03.2015—24.04.2015
Group: 3
Aika Huone Ohjaaja Päivämäärä Huomioitavaa
To 16-18 B222 Teemu Pitkänen 12.01.2015—27.02.2015
To 16-18 D122 Teemu Pitkänen 09.03.2015—24.04.2015
Group: 4
Aika Huone Ohjaaja Päivämäärä Huomioitavaa
Pe 12-14 B119 Teemu Pitkänen 12.01.2015—27.02.2015
Pe 12-14 B222 Teemu Pitkänen 09.03.2015—24.04.2015

Non finnish students, contact the lecturer beforehand.

Information for international students

The course is given in Finnish by Jyrki Kivinen and Patrik Floréen. There will not be lecture materials or exercises in English. Non-Finnish speakers please contact the lecturer before starting the course!

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, 3rd edition: 5-29, 43-60, 229-240, 1176-1179, 246-247, 286-298, 253-276, 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 5-27, 41-56,197-208, 1087-1090, 214-216, 253-264, 221-252,127-142, 27-36, 145-173, 1080-1084, 525-635, 498-509. The order of topics will be changed.

For the first exam also AVL-trees (not in Cormen) are included. The material is available here. Decided on the spring 2014 course: The first exam covers the material up to hashing, but not heaps.

We will make some changes to the course in 2015 compared to 2014, so this page will be updated accordingly.

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 2015, although the topics come in different order now.

We offer two ways to pass this course: either by participating in the two exams on the normal course OR by participating in ONE separate exam covering the full course.

The next separate exam: see the department's list of exams.. 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). No pocket calculators at the exam.

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

Yleistä

Esitiedot

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

Luennot

Luentomateriaali tulee tänne ja päivitetään kurssin kuluessa. Luennoitsijoina toimivat professori Jyrki Kivinen ja yliopistonlehtori Patrik Floréen.

  • luennot sivut 351–638 (Patrikin luennot). Huom: Lisäsin sivulle 502 selityksen, mikä on komponenttiverkko. Sivuilla 511-512 otin pois kohdat, joissa viitataan joukkoon S, joka määritellään vasta myöhemmin. Sivulle 520 lisäsin Bellman-Fordin aikavaativuuden ja sivulla 534 tähdensin että löydetään lyhin polku kaikkiin saavutettavissa oleviin solmuihin. Sivulle 550 lisätty että w(u,u) asetetaan arvoon 1 kaikille u. Muutin sivun 383 TSP-algoritmia ja vastaavasti seuraavalla sivulla oleva selitys.
  • Lyhyt johdatus rinnakkaisiin algoritmeihin (luento 15.3., ei tule tenttiin)

Oppimista tukevaa lisämateriaalia internetissä (HUOM! Yksityiskohdat eivät välttämättä ole toteutettu täsmälleen niin kuin Cormenin kirjassa ja luentomateriaalissa): Tietorakenteiden visualisointeja (esimerkiksi tässä binääripuiden delete on erilainen, kun on kaksi lasta poistettavalla alkiolla). Järjestämisalgoritmien visualisointi. Lyhimpien polkujen etsinnän visualisointi.

Luentoaikataulu:

Viimeinen ensimmäiseen kurssikokeeseen tuleva asia on AVL-puut (monisteessa sivulle 350 asti), joka käsitellään luennolla ma 16.2. Luento ke 18.2. käytetään kertaamiseen.

Maanantaina 23.2. oli halukkaille vielä yksi kertausluento.  Keskiviikkona 25.2. ei enää ole luentoa. Seuraava luento on 9.3.

Laskuharjoitukset ja TMC-tehtävät jatkuvat normaalisti myös 23.–27.2.

  • viikko 1: ma s. 1–18; ke 19–60 (vaativuusluokat, s. 51–60, käsiteltiin melko nopeasti ja niihin palataan vielä viikon 2 maanantaina)
  • viikko 2: ma s. 51–60 (kertaus) ja 61–97; ke s. 98–137
  • viikko 3: ma s. 138–165, ke 166–211
  • viikko 4: s. 212–257, s. 267–273 (pääosin)
  • viikko 5: s. 258–309
  • viikko 6: s. 310–350; kertausta (vanhoja tenttikysymyksiä)
  • viikko 7: ei uutta asiaa; ma kertausta (TMC-tehtäviä); ke ei luentoa
  • viikko 8: ma 9.3.: s. 351-393, ke 11.3.: s. 395-435
  • viikko 9: ma 16.3.: s. 436-468, ke 18.3.: s.469-508
  • viikko 10: ma 23.3.: s. 509-534, ke 25.3.: s. 535-572
  • viikko 11: ma 30.3.: s. 573-638, ke 1.4. kertausta
  • pääsiäisloma 2.4.-8.4., jolloin ei ole opetusta (ei luentoja, ei laskuharjoituksia)
  • viikko 12: ma 13.4.(EI LUENTOA 13.4) ja ke 15.4. Jyrkin luento rinnakkaisuudesta (viimeinen luento!)
  • VIIMEINEN LUENTO (kertaus): ke 29.4.

Harjoitukset

Harjoituksia on kahdenlaisia: Tavalliset laskuharjoitukset ja ohjelmointitehtävät (Tira-paja). Aikaisempina vuosina käyttössä olleista ns. Trakla-tehtävistä on luovuttu.

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. Laskuharjoitukset ja pajat alkoivat jo ensimmäisellä luentoviikolla!

Laskuharjoitustehtävät:

Huomio: Viikolla 2.3.-6.3. ei ole laskuharjoituksia (tenttiviikko), eikä myöskään viikolla 9.-13.3. Pajassa on tänä aikana meneillään bonustehtävien viikko. Viikolla 9.-13.3. on normaalit luennot.

Huomio: Jos tehtävä koostuu monesta alakohdasta (a, b, c, ...), voit merkitä rastin tehtävän suorituksen merkkinä, jos olet valmis tulemaan taululle esittämään suurimman osan kohdista.

Laskuharjoituspisteiden tarkastaminen: Yrittääkää tätä  linkkiä Tikliin.

Tira-paja.  Määräaika on maanantaisin klo 1.59. Yhteyshenkilö: toni.annala(at)helsinki.fi.

Huom. Opiskelijoiden pyynnöstä viikon 7 pajatehtävien määräaikaa on siirretty viikolla eteenpäin.  Uusi määräaika on ma 9.3. klo 1.59.  Muistakaa kuitenkin, että viikon tehtävät liittyvät 3.3. pidettävän ensimmäisen kurssikokeen koealueeseen.

Jatkuva palaute

Käytämme Aktivator++:aa jatkuvaan pienimuotoiseen palautteeseen. Seuraa allaolevia linkkejä ja vastaa pariin monivalintakysymykseen, tai anna halutessasi enemmänkin palautetta.

  • kysymys 1 (aiheena viikkojen 1 ja 2 luennot; vastausaika päättynyt)
  • kysymys 2 (aiheena viikkojen 1 ja 2 TMC-tehtävät; vastausaika päättynyt)
  • kysymys 3 (aiheena viikkojen 1–3 "tavalliset" laskuharjoitukset; vastausaika päättynyt)
  • kysymys 4 (aiheena viikon 4 luennot; vastausaika päättynyt)
  • kysymys 5 (aiheena toiveet kertausluennolle; vastausaika päättynyt)
  • kysymys 6 (aiheena mahdollinen lisäkertaus)
  • kysymys 7 (aiheena loppukertaus, vastausmääräaika 24.4. 9.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. Tentissä ei saa olla taskulaskinta.

Opiskelijoiden palaute Luennoijien kommentit
Tehtävät olivat vaikeita. Tämä on on totta, tällä kurssilla on tosiaan tarkoitus oppia kohtalaisen vaikeita asioita.
Kurssin työmäärä on varsin huima ja etenkin TMC-tehtävät saattoivat syödä allekirjoitaneelta päivän per tehtävä. Tehtävien tekemiseen on tarkoituskin mennä aikaa.  Kaikki tehtävät ratkaisemalla kurssista saa 10 opintopistettä (ja oletettavasti hyvän arvosanan), joten se ei välttämättä ole kaikille sopiva tavoite.  Mutta jos tehtäviin menee keskimäärin päivä per tehtävä, tämä on selvästi enemmän kuin olisi tarkoitus.  Apua voi hakea apua paja-ohjauksesta, jota käytettiin vähemmän kuin oli odotettu.
TMC-tehtävissä ensimmäiset tehtävät kustakin asiasta voisivat olla helpompia (esim. esitellyn rakenteen tai algoritmit hyvin peruslaatuista toteuttamista). Tämä on hyvä huomio. Tehtävien luominen TMC-tehtävään on kohtalaisen työlästä, mutta pistetään tämä muistiin.
Kurssin alku- ja loppupuoli olivat kuin yö ja päivä, johtuen alkuosan luennoijan esiintymistavasta. / Luennoitsijan vaihdos antoi hyvää uutta tuulta kurssin luentoihin. / Floréen tuntui olevan luentosalissa paljon enemmän kotonaan kuin Kivinen. / Molemmat luennoistijat tuntuivat osaavan asiansa. Floréen on vuosikaudet luennoinut just tätä kurssia. Olemme erilaisia. Keskustelemme luennoijien kesken siitä, mitä eroja alku- ja loppupuolen luennoinnissa on ollut.  Yksi kurssin aikaisessa palautteessa esille tullut konkreettinen seikka oli alkupään luentokalvojen käyminen läpi liian nopeasti.
Teoreettisempi lähestymistapa olisi ollut ns. siisti juttu. Ensimmäisen vuoden tietojenkäsittelykurssiksi tämä on teoreettisemmasta päästä, haluamme korostaa käytäntöä esim. ohjelmointitehtävien muodossa.
Kurssikokeiden päivämäärät pitäisi olla selvillä ehti, kun kurssi alkaa. Niin olivatkin ja tieto niistä oli netissä kurssikokeiden listauksessa. Jos opiskelija ei löydä tarvitsemansa informaation, voi kysyä. Kurssikokeiden ajat ei ole kokemuksemme mukaan koskaan olleet kiinnittämättä ennen kurssin alkua.
Luentokalvoista voisi poistaa sanat "on tietenkin", "selvästi" koska suurimmassa osassa en ymmärtänyt. Luentomateriaali on tarkoitettu luentoja varten ja varsinkin luennoilla käydään asiat tarvittaessa tarkemmin läpi. Materiaalin tarkoitus on myös totuttaa opiskelijoita matemaattiseen esitystapaan, jossa tällaisia ilmauksia käytetään tarkoittamaan, että jokin asia katsotaan riittävän selväksi, että se ei vaadi erillistä perustelua (ts. todistusta).
Ensimmäinen koe vähän pilkunviilaus. Tämä kommentti varmaan liittyy arvosteluun? Tiukkaa arvostelua ensimmäisessä välikokeessa korvasi lasketut läpipääsyrajat. Arvostelussa ykkösasiana on oikeudenmukaisuus: joka on vastannut paremmin pitää saada paremmat pisteet ja kaikki samalla tavalla vastanneet samat pisteet. Skaalaa voidaan aina rukata opiskelijoiden hyväksi.
Kurssi sai myös kiitosta: Loistava kurssi. / Kaikesta huolimatta ehkä antoisin kurssi jonka olen käynyt yliopistolla. Kiitos.
  • Kurssikoe 1 (2.3.): tehtävät ja vastaukset. Koe on korjattu. Tehtävien keskiarvot olivat seuraavat: 1: 1,62/4; 2: 2,81/6; 3: 3,68/6, 4: 3,74/6. Koko tentin keskiarvo 11,86/22. Palautetilaisuus kurssikokeesta 1 pidetään pe 20.3. klo 11-12 tilassa Exactum A317 (Exactumin 3. krs A-siiven parvekepääty).
  • Kurssikoe 2 (6.5.): tehtävät ja vastaukset. Koe on korjattu. Tehtävien keskiarvot olivat seruaavat : 1: 2,92/4; 2: 3,77/6; 3: 2,97/6, 4: 4,40/6. Koko tentin keskiarvo 14,06/22. Palautetilaisuus kurssikokeesta 2 pidetään to 21.5. klo 12-13 tilassa Exactum A317 (Exactumin 3. krs A-siiven parvekepääty). Kurssin tulokset ovat ilmestyneet. Koska ensimmäinen kurssikoe meni huonosti, läpipääsyraja (normaalisti 30) alennettiin 27 pisteeseen ja myös minimimäärä jota pitää saada kokeista (normaalisti 22) alennettiin 20 pisteeseen. Huomio: Kukin koetilanne on erilainen, joten tämä ei tarkoita, että samaa skaalaa käytettäisiin uusintakokeessa. Uusintakokeen jälkeen arvioidaan erikseen millaisia mahdollisia korjaavia toimenpiteitä arvostelussa tarvitaan.
  • Uusintakoe pidettiin ti 9.6. klo 16 salissa B123. Koe on korjattu: tehtävät ja vastaukset. Omat pisteesi ja arvosanasi näet tästä taulukosta (vaatii kirjautumisen). Tietojärjestelmään on vain viety arvosana, joten vain se näkyy Tiklistä. Palautetilaisuus: Lähettäkää tehtävien 1-3 osalta sähköpostia Jyrki Kiviseen (jyrki.kivinen at cs.helsinki.fi) ja tehtävien 4-6 osalta sähköpostia Patrik Floréenille (patrik.floreen at cs.helsinki.fi) viimeistään 25.6.
  • Kurssipalaute: Kurssipalautteeseen vastasi vain 19 opiskelijaa (keväällä 2014 37 opiskelijaa). Numeeristen kysymysten keskiarvot olivat seuraavat: Kurssin tavoitteet olivat selvät: 3,8; Kussilla käytetty materiaali tuki oppimistavoitteiden saavuttamista: 4,2; Toiminta kurssila tuki oppimistavoitteiden saavuttamista: 3,9; Kurssin arviointi mittasi keskeisten oppmistavoitteiden saavuttamista: 3,9; Kussi oli työläs: 4,5; Kurssin kokonaisarvosana: 4,2. Eli hyvin, erityisesti vastauksia "1=eri mieltä" oli kaikissa kysymyksissä 0 kpl. Alla on otos kommenteista tekstimuotoisissa vastauksissa ja vieressä luennoijien palaute.
  • Erilliskoe 15.9.2015: Tehtävät. Huom: Tehtävään 4a oli jäänyt kirjoitusvirhe: 20 piti olla 23 (ja arvostelussa on hyväksytty kaikki järkevät tavat korjata tilanne). Ja tehtävässä 6a pitäisi olettaa, että painot ovat vähintään 1. Jos on arvostelusta kysyttävää, laittakaa sähköpostia arvostelijalle, mieluiten viimeistään 28.9.: tehtävät 1a-c, 2, 3 ja 4a-b Jyrki Kivinen ja tehtävät 1d-f, 4c ja 5 Patrik Floréen.
  • Erilliskoe 1.12.2015: Tehtävät. Korjaus valmistunut. Jos haluatte katsoa tehtäväpaperinne tai saada "lunttilappunne" takaisin, ottakaa yhteyttä sähköpostitse patrik.floreen (at) cs.helsinki.fi.

Harjoitustehtävät:

  • 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ä. Koska laskuharjoitustehtäviä on yhteensä 74, joista 4 olivat ylimääräisiä tehtäviä, puolet 70:stä on 35 (1 piste) ja 90% on 63 (8 pistettä). Eli skaala on 35-38: 1 p, 39-42: 2 p, 43-46: 3 p, 47-50: 4 p, 51-54: 5 p, 55-58: 6 p, 59-62: 7 p, 63-74: 8 p.
  • 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ävät tarkastetaan TMC-ohjelmalla ("Test My Code").

Kurssin suoritukseen vaaditaan tavallisesti 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.

Erittäin kiitettävästä harjoitustehtävien tekemisestä saa lisäksi ylimääräisiä opintopisteitä 1 tai 2: jos on tehnyt vähintään 80% tehtävistä saa yhden lisäopintopisteen, jos on tehnyt vähintään 95% saa kaksi lisäopintopistettä. Harjoitustehtävillä tarkoitetaan tässä sekä laskuharjoitustehtäviä että ohjelmointitehtäviä, eli nämä lasketaan yhteen.

Kevään 2015 kurssin paja- ja laskaripisteet löytyvät tästä! Jos on jotain korjattavaa ottakaa yhteyttä laskaripitäjäänne (tai pajan tapauksessa Toni Annalaan).

Vaihtoehtoinen tapa suorittaa kurssi on erilliskokeella (60 maksimipistettä), jolloin kurssin suoritukseen kuuluu ainoastaan yksi erilliskoe. Harjoituspisteitä ei ole. Kurssin suoritus erilliskokeena on 8 opintopisteen laajuinen.

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

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. Uusintakokeen 10.6.2014 kysymykset ja vastaukset.

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.