Tietorakenteet

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

27.02.2012 16.00 A111
07.05.2012 16.00 A111
07.05.2012 16.00 A111
Vuosi Lukukausi Päivämäärä Periodi Kieli Vastuuhenkilö
2012 kevät 16.01-25.04. 3-4 Suomi Patrik Floréen

Luennot

Aika Huone Luennoija Päivämäärä
Ma 12-14 A111 Patrik Floréen 16.01.2012-22.02.2012
Ke 12-14 A111 Patrik Floréen 16.01.2012-22.02.2012
Ma 12-14 A111 Patrik Floréen 12.03.2012-25.04.2012
Ke 12-14 A111 Patrik Floréen 12.03.2012-25.04.2012

Harjoitusryhmät

Group: 1
Aika Huone Ohjaaja Päivämäärä Huomioitavaa
Ke 14-16 B222 Miikka Hilke 16.01.2012—24.02.2012
Ke 14-16 B222 Miikka Hilke 12.03.2012—27.04.2012
Group: 2
Aika Huone Ohjaaja Päivämäärä Huomioitavaa
Ke 16-18 B222 Patrik Floréen 16.01.2012—24.02.2012
Ke 16-18 B222 Patrik Floréen 12.03.2012—27.04.2012
Group: 3
Aika Huone Ohjaaja Päivämäärä Huomioitavaa
Pe 12-14 B222 Pekka Mikkola 16.01.2012—24.02.2012
Pe 12-14 B222 Pekka Mikkola 12.03.2012—27.04.2012
Group: 4
Aika Huone Ohjaaja Päivämäärä Huomioitavaa
Pe 14-16 B222 Pekka Mikkola 16.01.2012—24.02.2012
Pe 14-16 B222 Pekka Mikkola 12.03.2012—27.04.2012
Group: 5
Aika Huone Ohjaaja Päivämäärä Huomioitavaa
Ti 14-16 BK107 Joel Kaasinen 16.01.2012—27.04.2012 TIRAPAJA!
Ma 14-20 BK107 Joel Kaasinen 16.01.2012—27.04.2012 TIRAPAJA!
Pe 12-14 BK107 Joel Kaasinen 16.01.2012—27.04.2012 TIRAPAJA!
To 10-14 BK107 Joel Kaasinen 16.01.2012—27.04.2012 TIRAPAJA!

Non finnish students, contact the lecturer beforehand.

Information for international students

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 diskreettiin matematiikkaan - Introduction to Discrete Mathematics (from 2012 onwards Johdatus yliopistomatematiikkaan - Introduction to University Mathematics).

There will not be lecture materials or exercises in English.

For self-studies these are the pages in the Cormen et. al book to read. 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).

There will be three batches of example exercises for the non-Finnish students; first batch , second batch , third and last batch. This are intended for self-study.

Please note: You are allowed to have with you for the exams hand-written A4-size notes (one paper, you can write on both sides).

The next separate exams are 27.11.2012 at 16 and 29.1.2013 at 16.

PLEASE NOTE: IF YOU WISH TO HAVE THE EXAM QUESTIONS IN ENGLISH, YOU HAVE TO EXPLICITLY REQUEST IT FROM THE LECTURER (patrik.floreen@cs.helsinki.fi) IN ADVANCE, PREFERABLY AT LEAST ONE WEEK BEFOREHAND.

Yleistä

HUOM: Erilliskoetulokset 14.8.2012 ovat alhaalla sivulla kohdassa Kurssin suorittaminen.

 

Esitiedot

Kurssin pakollisina esitietovaatimuksina on kurssit Ohjelmoinnin jatkokurssi ja Johdatus diskreettiin matematiikkaan.

Syksystä 2012 kurssi Johdatus diskreettiin matematiikkaan poistuu. Uusi esitietovaatimuskurssi on Johdatus yliopistomatematiikkaan.

Esitietokoe, joka korvaa puutteet esitietovaatimuksista, pidettiin 13.1.

Opiskelijat, joilla ei ole vielä esitietovaatimukset kunnossa, pyydetään ottamaan yhteyttä luennoijaan.

Luennot

Luentomateriaali (pdf)

Lisälehti verkkoalgoritmien kertausosioon (lisätty kurssisivulle 16.4.2012).

Järjestämisalgortmien havainnollistuksia internetissä (Annika Piiroisen löytämät linkit:)

Hakualgoritmien (verkon läpikäynnit, Dijkstra, A*) havainnollistaminen.

Luentoaikataulu:

  • Viikko 1: ma s. 1-31, ke s. 32-64
  • Viikko 2: ma s. 65-126, ke s. 127-168
  • Viikko 3: ma s. 169-204, ke s. 205-268
  • Viikko 4: ma s. 269-306, ke s. 307-347. Keko ei kuulu ensimmäisen kurssikokeen alueeseen, vaan ensimmäisen kurssikokeen viimeinen asia on hajautus.
  • Viikot 5-6: Kertausta ja vanhojen tenttitehtävien läpikäynti, ei luentoa 22.2.
  • Viikko 7: ma Keon kertausta ja s. 348-380, ke s. 381-414, kurssikokeen malliratkaisut
  • Viikko 8: ma s. 415-444, ke s. 445-476
  • Viikko 9: ma 477-498, ke s. 499-524
  • Viikko 10: ma s. 525-557, ke s. 558-583
  • Viikko 11: ma s. 584-622 ja kertausta (keko, järjestäminen), ke kertausta (verkot) ja vanhojen tenttitehtävien läpikäynti
  • Viikko 12: ma vanhojen tenttiehtävien läpikäynti, ei luentoa 25.4.

Laskuharjoitukset alkavat jo ensimmäisellä luentoviikolla!

Laskuharjoituspisteiden tarkistuslista 18.5.2012.

Ohjelmointitehtävät (TiRa-paja)

Pajatehtävien tarkastusautomaatista on nyt uusi versio, joka edellyttää että tehtävät on ohjelmoitu nimenomaan Javalla. Uusi versio tarkastelee ohjelmakoodia, eikä vain tee syöte-tuloste-testausta.

TiRa-paja

Trakla2

Tehtävät ovat traklassa. Traklaan kirjaudutaan tietojenkäsittelytieteen laitoksen tunnuksilla.

Trakla-tehtävillä on kaksi deadlineä. Ensimmäisten modulien deadline on välikoepäivä 27.2., ja loppujen välikoepäivä 7.5.

Trakla on auki. Ota yhteyttä Joel Kaasiseen (joel . kaasinen ät cs . helsinki . fi) jos et pääse kirjautumaan.

Jatkuva palaute

Mikä osio toisen puoliskon asioista on ollut vaikein? Keko: 1, Järjestäminen: 4, Verkkojen läpikäynnit: 7, Lyhimmät polut verkoissa: 8, Pienimmät virittävät puut verkoissa: 12.

Vauhti luennoilla on  nyt verkko-osiossa ollut: liian nopea: 5; nopea: 5; sopiva: 9; hidas: 0; liian hidas: 0.

Laskaritehtävistä 7 ja 8 oltiin mieltä näin: erittäin vaikeita: 2; vaikeita: 3; sopivia: 8; helppoja: 0; erittäin helppoja: 0.

Tirapajan bonustehtävistä oltiin mieltä näin: olivat hyviä: 4, olivat ok: 9, olivat huonoja: 2, olivat turhia, olisi pitänyt olla kunnon taukoa: 1. Näistä ei ollut erillisiä kommentteja.

Kurssikokeesta 1 oltiin mieltä näin: erittäin vaikea: 23, vaikea: 25, sopiva: 31, helppo: 3, erittäin helppo: 0. Kommenteista sai kuvan, että suurin ongelma oli ajan loppuminen kesken, ei tehtävien vaikeus sinänsä.

Trakla-tehtävistä oltiin mieltä näin: erittäin hyviä: 4, hyviä: 13, huonoja: 3, erittäin huonoja: 1. Edustava kommentti Traklasta: "Sisällöltään hyviä, mutta Trakla on kyllä sekava systeemi." Yksi kommentti sanoi, että eniten aikaa menee pajatehtäviin. Tähän voisi todeta, ettei kaikkia pajatehtäviä suinkaan tarvitse tehdä. Pajatehtävistä kolmasosan voi korvata Traklalla ja koko tästä puolesta voi saada korkeintaan 8 pistettä. Mutta tähän aiheeseen sopii, että tekemällä oppii, joten siksi pajatehtävät ovat käytännössä tärkeitä.

Luentoilla etenemisestä oltiin mieltä näin: aivan liian nopeasti: 22, aika nopeasti: 16, sopivasti: 6, aika hitaasti: 2, aivan liian hitaasti: 0. Luennoista oli hyviä kommentteja muun muassa siitä, että luennot on edennyt laskareita ripeämmin, joka ei ole hyvä asia.

Pajatehtävistä 1-3 oltiin mieltä näin: liian vaikeita: 17, vaikeita: 15, just sopivia: 16, helppoja: 0, liian helppoja: 0 Oli kommenttia, jonka mukaan tehtävien vaikeusaste on nousussa 1->2->3. Sanottiin näin: "Jos tavoitteena on kurssin suurin droppausprosenttti niin jatka vain samalla linjalla." Luennoijan kommentti kommentteihin: Pajasta saa opastusta, jos on vaikeuksissa. Ja toki seuraamme miten tehtävät onnistuvat ja reagoimme siihen. Ei kannata heittää pyyhettä kehään jos jotain vaikeata tulee vastaan. Ei tässä vaadita että kaikkia tehtäviä osaisi tehdä.

Viikon 2 laskareista oltiin mieltä näin: liian vaikeita: 8, vaikeita: 19, just sopivia: 11, helppoja: 3, liian helppoja: 1. Kommenteissa mm. todettiin, että matemattiset tehtävät ovat vaikeita kun matematiikkan opinnoista voi olla useita vuosia ja jopa vuosikymmen, että tehtävä 1 oli epäselvästi kirjoitettu ja osa tehtävistä liian matemaattisia.

Viikon 1 laskareista oltiin mieltä näin: liian vaikeita: 10, vaikeita: 22, just sopivia: 25, helppoja: 11, liian helppoja: 3. Kommenteissa mm. valitettiin, että liian monta ja vaikeita harjoituksia ja toivottiin lisää rekursiotehtäviä. 

Palaute kurssin lopussa

Yhteenveto palautteesta ja kommentit löytyvät täältä.

 

Tietorakenteiden harjoitustyö

Kesällä on mahdollisuus suorittaa Tietorakenteen kurssille jatkoa oleva Tietorakenteiden harjoitustyö. Hyvä ajankohta harjoitystyön suorittamiselle on, kun tiedot ovat vielä tuoreessa muistissa, ja ohjelmointitaidot hyvällä mallilla. Kesällä kurssi järjestetään kaksi kertaa. 14.5.-15.6. on mahdollista suorittaa kurssi kolmen tai viiden viikon pituisena, 30.7.-31.8. viiden viikon pituisena. Kurssi on pajamuotoinen, eli ohjausta on tarjolla 3-4 kertaa viikossa. Paikalle täytyy tulla vähintään kerran viikossa keskustelemaan edistymisestä. Opettajana toimii kummallakin kurssilla Kristiina Paloheimo.

Kurssin suorittaminen

Toinen kurssikoe oli aika vaikea, mistä syystä pudotettiin vähimmäisraja pisteitä 22:sta 20:een ja laskettiin hyväksymisraja (ja raja kaikille muillekin arvosanoille) kahdella pisteellä (eli 28 pistettä antoi arvosanaksi 1 ja 48 pistettä arvosanan 5).. Näin hyväksyttyyn suoritukseen vaaditiin 28 pistettä ja vähintään 20 pistettä molemmista kurssikokeista yhteensä.

Laskuharjoituspisteiden rajat olivat seuraavat: 30-32 tehtävää 1 piste, 33-36: 2, 37-39: 3, 40-43: 4, 44-46: 5, 47-49: 6, 50-53:7 ja 54-: 8 pistettä.

Tässä on korjattu lista lisäpisteitä ohjelmointi- ja traklatehtävistä (18.5.2012).

Kurssiin kuuluu kaksi välikoetta (1. välikoe 27.2. klo 16-19 salissa Exactum A111, 2. välikoe 7.5. klo 16-19 sallissa Exactum A111), kukin maksimipistemäärältään 22. 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.

Kurssikokeen 1 alueeseen kuuluu luentokalvojen sivut 1-327. Kurssin 2 alueeseen kuuluu koko kurssin materiaali.

Kurssikokeen 1 tehtävät. Koetulokset näkyvät  samalla tarkistuslistalla kuin laskuharjoitustehtävät. Tehtävien keskiarvot ovat 1: 3,77/5, 2: 3,93/6, 3: 4,72/6, 4: 2,25/5, koko tentin: 14,67/22.

Kursikokeen 2 tehtävät. Tenttien tulokset ovat nyt nähtävänä laskuharjoituspistelistassa ja tuloslistassa. Tehtävien keskiarvot ovat: 1: 3,808/4, 2: 2,80/4, 3: 4,14/6, 4: 3,78/8, koko tentin: 14,53/22. Vertailtaessa kurssikokeeseen 1 on muistettava, että monet huonosti menestyneet jättivät ensimmäisen kurssikokeen jälkeen kurssin kesken, joten luvut eivät ole vertailukelpoisia.

Harjoituksia on 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 on tiistai-aamuna klo 7. 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 30, koepisteiden summan täytyy myös olla vähintään 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).

Kurssin jälkeisessä ensimmäisessä (kesäkuun) erilliskokeessa 12.6.2012 voi kurssin suorittaa neljällä vaihtoehtoisella tavalla:

  • Erilliskokeen osalla 1 korvataan kurssikoe 1 (maks. 22 p.), kurssikoe 2 ja laskuharjoituspisteet otetaan huomioon.
  • Erilliskokeen osalla 2 korvataan kurssikoe 2 (maks. 22 p.), kurssikoe 1 ja laskuharjoituspisteet otetaan huomioon.
  • Erilliskokeella korvataan molemmat kurssikokeet (maks 44 p.), laskuharjoituspisteet otetaan huomioon.
  • Erilliskokeella korvataan kurssin koko suoritus (maks. 60 p.), laskuharjoituspisteitä ei oteta huomioon.

Myös erilliskokeissa saa olla mukana itse tehty, käsin kirjoitettu yksi A4-kokoinen " lunttilappu", samalla tavalla kuin välikokeissa.

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.

 

 

 

Kirjallisuus ja materiaali

Kurssimateriaali

Kurssimateriaali pohjautuu suurelta osin kirjaan: T. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein: Introduction to Algorithms, 3nd 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.