Tietorakenteet ja algoritmit (ohjattu itseopiskelu)

58131
8-10
Algorithms and machine learning
Intermediate studies
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.

Exam

25.10.2016 09.00 A111, CK112
20.12.2016 14.00 A111, CK112
Year Semester Date Period Language In charge
2016 autumn 08.09-16.12. 1-2 Finnish Kjell Lemström

Lectures

Time Room Lecturer Date
Thu 10-12 B123 Kjell Lemström 08.09.2016-20.10.2016
Thu 10-12 CK112 Kjell Lemström 03.11.2016-03.11.2016
Thu 10-12 B123 Kjell Lemström 10.11.2016-08.12.2016
Thu 10-12 CK112 Kjell Lemström 15.12.2016-15.12.2016

Exercise groups

Group: 1
Time Room Instructor Date Observe
Tue 14-16 C222 Paul Saikko 12.09.2016—21.10.2016
Tue 14-16 C222 Paul Saikko 31.10.2016—16.12.2016
Group: 2
Time Room Instructor Date Observe
Fri 12-14 B121 Johannes Verwijnen 09.09.2016—09.09.2016
Fri 12-14 D123 Johannes Verwijnen 16.09.2016—16.09.2016
Mon 10-12 C222 Johannes Verwijnen 19.09.2016—17.10.2016
Mon 10-12 C222 Johannes Verwijnen 31.10.2016—12.12.2016
Group: 3
Time Room Instructor Date Observe
Fri 14-16 B121 Toni Annala 09.09.2016—09.09.2016
Fri 14-16 D123 Toni Annala 16.09.2016—16.09.2016
Mon 14-16 D122 Toni Annala 19.09.2016—17.10.2016
Mon 14-16 D122 Toni Annala 31.10.2016—12.12.2016

HUOM! Luentoaika on muuttunut!

Non finnish students, contact the lecturer beforehand.

General

6.12. Laskaripaja siirretty 7.12. 12-14 C122

 

Kurssimateriaalia ja laskuharjoitukset löytyvät kurssin Moodle-sivustolta osoitteesta https://moodle.helsinki.fi/course/view.php?id=21003.

 

Esitiedot

Kurssin esitietovaatimuksina on kurssit Ohjelmoinnin jatkokurssi ja Johdatus yliopistomatematiikkaan. Kurssin suorittaminen on käytännössä erittäin vaikeaa, jos näissä esitiedoissa on huomattavia puutteita. Esitietokurssien muodollisia suorituksia ei kuitenkaan tarkasteta. Opiskelijan ei siis tarvitse kysyä, saako osallistua kurssille, vaikka esitietokurssin suoritus puuttuu.

"Luennot" ja luentomateriaali

Kurssi on ns. itseopiskelu-kurssi, joka tarkoittaa, että tavallisia luentoja ei pidetä. "Luentoina" on yllä merkitty kertaustapahtumat, joissa käydään läpi edellisen viikon vaikeimmiksi koettuja tehtäviä ja asioita. Ensimmäiselle luennolle osallistuminen on suotavaa. "Luennot" pitää Johannes Verwijnen.

Syksyn 2016 kurssi on sisällöltään sama kuin kevään 2016 kurssi. Luentomateriaali kevään kurssilta on käytössä:

Luentomateriaali jaettuna lukuihin:

  1. Johdanto
  2. Johdanto tietorakenteisiin
  3. Järjestäminen
  4. Perustietorakenteet
  5. Hajautus
  6. Hakupuut
  7. Keko
  8. Verkot
    • osa 1: peruskäsitteet; leveys- ja syvyyssuuntainen läpikäynti
    • osa 2: lyhimmät polut
    • osa 3: virittävät puut
    • osa 4: muita verkkoalgoritmeja (ei kuulu koealueeseen)
  9. Yhteenveto

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 visualisointiLyhimpien polkujen etsinnän visualisointi.

Opiskelija Simone Romeon tekemä lista termeistä suomeksi ja englanniksi.

Muuta lisämateriaalia itseopiskelun tueksi julkaistaan kurssin Moodle-sivustolla osoitteessa https://moodle.helsinki.fi/course/view.php?id=21003.

Completing the course

Kurssiin kuuluu kaksi koetta, kustakin saa maksimissaan 22 pistettä, eli yhteensä maksimi on 44 pistettä. 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.

Harjoitustehtävät:

  • Tavallisia laskuharjoituksia, joista voi saada yhteensä 8 pistettä. Yhden pisteen saa saavuttamalla viikottain noin 50% laskuharjoituksien tavoitepistemäärästä. Täydet 8 pistettä saa tekemällä viikottain 100% laskuharjoituksien tavoitepistemäärästä. Joka viikko tarkoituksena olisi olla mahdollista tehdä noin 200% tavoitepistemäärästä. Laskuharjoitustehtäviin vastataan kurssin Moodle-ympäristössä. Osa tehtävistä on 1 pisteen tehtäviä, jotka arvostellaan automaattisesti - monimutkaisemmat tehtävät ovat joko 2 tai 3 pisteen arvoisia ja ne arvostellaan henkilökunnan toimesta skaalalla 0-2 tai 0-3. 2 ja 3 pisteen tehtäviin saa ohjausta laskuharjoitustilaisuuksissa, joihin voi osallistua vapaasti. Ensimmäisen 2 viikon laskuharjoituksista kaikkien opiskelijoiden on saavutettava 100% tavoitepistemäärästä voidakseen jatkaa kurssin suoritusta.
  • Ohjelmontitehtäviä, joista saa ohjausta TiRa-pajassa ja joista voi saada yhteensä 8 pistettä (50% antaa 1 pisteen, 90% antaa 8 pistettä). Ohjelmointitehtävät tarkastetaan automaattisesti 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 kahden ensimmäisen viikon jälkeen, 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 saavuttanut vähintään 120% tavoitepistemäärästä saa yhden lisäopintopisteen, jos on tehnyt vähintään 150% saa kaksi lisäopintopistettä. Harjoitustehtävillä tarkoitetaan tässä sekä laskuharjoitustehtäviä että ohjelmointitehtäviä, eli nämä lasketaan yhteen. 

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.

Literature and material

Kurssikirjana toimii T. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein: Introduction to Algorithms, 3rd ed., MIT Press, 2009. Myös kirjan toista painosta voi käyttää - erona on lähinnä pseudokoodin esitystapa.

Kurssilla on muutamia asioita joita Cormenin kirjasta ei löydy. Kaikissa asioissa käsittelytapa ei vastaa täysin Cormenia.