Tietorakenteet ja algoritmit

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

07.03.2016 16.00 A111 ja B123
11.05.2016 16.00 A111 ja CK112
Year Semester Date Period Language In charge
2016 spring 18.01-04.05. 3-4 Finnish Jyrki Kivinen

Lectures

Time Room Lecturer Date
Mon 10-12 A111 Jyrki Kivinen 18.01.2016-02.03.2016
Wed 10-12 A111 Jyrki Kivinen 18.01.2016-02.03.2016
Mon 10-12 A111 Jyrki Kivinen 14.03.2016-04.05.2016
Wed 10-12 A111 Jyrki Kivinen 14.03.2016-04.05.2016

Exercise groups

Group: 1
Time Room Instructor Date Observe
Wed 12-14 D122 Toni Annala 18.01.2016—04.03.2016
Wed 12-14 C222 Toni Annala 14.03.2016—06.05.2016
Group: 2
Time Room Instructor Date Observe
Wed 14-16 C222 Jesse Väisänen 18.01.2016—04.03.2016
Wed 14-16 C222 Jesse Väisänen 14.03.2016—06.05.2016
Group: 3
Time Room Instructor Date Observe
Wed 16-18 C222 Toni Annala 18.01.2016—04.03.2016
Wed 16-18 C222 Toni Annala 14.03.2016—06.05.2016
Group: 4
Time Room Instructor Date Observe
Thu 12-14 B119 Jyrki Kivinen 18.01.2016—04.03.2016
Thu 12-14 B119 Jyrki Kivinen 14.03.2016—06.05.2016

Non finnish students, contact the lecturer beforehand.

Information for international students

The course will be given in Finnish.  This means that lectures and exercise groups will be in Finnish, and there will be compulsory reading material that is written in FInnish.  If you cannot follow the course in FInnish but still wish to take it, please contact the lecturer (Jyrki Kivinen) as soon as possible to discuss alternative reading materials etc.  However, this option will include some extra work also on part of the student.

If you can follow teaching in Finnish but would still prefer to take the exams in English, this can be arranged, but again please contact the lecturer about this as soon as possible.

 

General

Kurssin sisältö ja opetusmuodot ovat oleellisesti samat kuin keväällä 2015.

 

Ajankohtaista

Kurssi on päättynyt ja arvosteltu on tehty.  Tätä sivua ei enää suuremmin ylläpidetä.  Sivun alaosaan kohtaan "Kurssin suorittaminen" tulee tietoja pidetyistä erilliskokeista.  Siellä on myös tiedot kevään kurssikokeista.

Laitoksen kurssipalautejärjestelmän kautta saatiin palautetta 61 opiskelijalta; kiitos vastanneille!  Palautteesta on saatavilla luennoijan laatima ja kommentoima yhteenveto.

 

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. Luennoijalta ei siis tarvitse kysyä, saako osallistua kurssille, vaikka esitietokurssin suoritus puuttuu.

 

Luennot

Luentomateriaali perustuu kurssin aiempiin luentokertoihin. Luennot piti Jyrki Kivinen.

Ylimääräinen luento 27.4.: rinnakkaisuus

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

Korjauksia luentomateriaaliin:

  • Sivun 157 taulukossa esitettiin, että kekojärjestämisen aikavaativuus on parhaassakin tapauksessa O(n log n).  Kuten laskuharjoituksessa 9.1 todettiin, tämä pitää paikkansa, jos järjestettävänä on n erisuurta avainta.  Kuitenkin jos kaikki avaimet ovat yhtäsuuria, aikavaativuus on vain O(n).
  • Sivulla 593 operaation Find pseudokoodi oli väärin; korjattu 25.4.
  • Pari kirjoitusvirhettä korjattu 4.5.
  • Kiitos virheistä ilmoittaneille!

Luentojen eteneminen:

  • ma 18.1. luento peruutettu; ke 20.1. sivut 1–39 (luennon piti Patrik Floréen)
  • ma 25.1. sivut 40–72; ke 27.1. sivut 73–121 (luennot piti Patrik Floréen)
  • ma 1.2. sivut 122–137; ke 3.2. sivut 138–143 ja 149–186 (sivut 144–148 jätettiin väliin)
  • ma 8.2. sivut 187–216; ke 10.2. sivut 217–244
  • ma 15.2. sivut 245–273; ke 17.2. sivut 274–290 
  • ma 22.2. sivut 291–312; ke 24.2. sivut 313–354 
  • ma 29.2. kertausluento 1: luentokalvojen kertaus, vähän O-notaatiota
  • ke 2.3. kertausluento 2: lisää O-notaatiosta, muita opiskelijoiden ehdottamia aiheita (mm. hajautus)
  • tenttiviikolla 7.–11.3. ei ollut luentoja
  • ma 14.3. sivut 355–383; ke 16.3. sivut 384–415
  • ma 21.3. sivut 416–447; ke 23.3. sivut 448–479
  • ma 4.4. sivut 480–499; ke 6.4. sivut 500–512
  • ma 11.4. sivut 513–533; ke 13.4. sivut 534–552
  • ma 18.4. sivut 553–575; ke 20.4. sivut 576–596 ja 600
  • ma 25.4. sivut 597–599 ja 601–627; ke 27.4. rinnakkaisuus
  • ma 2.5. sivut 628–642 (viimeinen luento)

 

Harjoitukset

Kurssilla on kahdenlaisia harjoitustehtäviä: tavallisia laskuharjoituksia ja TMC-järjestelmällä tehtäviä ohjelmointiharjoituksia.

Tavallisissa laskuharjoituksissa opiskelija ratkaisee itse etukäteen kullekin viikolle annetut tehtävät ja osallistuu sitten johonkin laskuharjoitusryhmään, jossa tehtävistä keskustellaan ja opiskelijoiden ratkaisut tarkastetaan.

TMC on sama järjestelmä kuin kursseilla Ohjelmoinnin perusteet ja Ohjelmoinnin jatkokurssi. Kullekin viikolle tulee TMC-järjestelmään tehtät, jotka pitää ratkaista määräaikaan mennessä.

Sekä tavallisten laskuharjoitusten että TMC-tehtävien ratkaisemiseen saa opastusta pajassa aikoina, jotka selviävät pajasivulta.

  • Ohjelmointiharjoitukset löytyvät kurssin TMC-sivulta.
  • TMC:ssä on nyt menossa bonusviikko. Ratkaisujen määräaika on 16.5. klo 1.59.

Completing the course

Kurssiin kuuluu kaksi pakollista kurssikoetta.  Kokeet ovat periodien III ja IV koeviikoilla.  Tarkista kokeiden tarkempi ajankohta laitoksen koeaikataulusta.  Kokeessa saa olla mukana yhdelle A4-arkille itse käsin kirjoitettu "lunttilappu", jonka molemmilla puolilla saa olla tekstiä.

Kurssin suoritus pisteytetään siten, että maksimipistemäärä on 60 pistettä.  Alin hyväksytty pistemäärä on noin 30 pistettä, ja korkeimpaan arvosanaan 5/5 vaaditaan noin 50 pistettä.

Kurssin maksimipistemäärä on 60 ja jakautuu osasuorituksille seuraavasti:

  • kaksi kurssikoetta: kumpikin 22 pistettä, eli yhteensä 44 pistettä
  • tavalliset laskuharjoitukset: 8 pistettä
  • ohjelmointiharjoitukset (TMC): 8 pistettä.

Kurssin hyväksyttyyn suoritukseen vaaditaan 30 pistettä, ja korkeimpaan arvosanaan 5/5 vaaditaan 50 pistettä.  Lisäksi  hyväksymiseen vaaditaan, että kahden kurssikokeen yhteispistemäärä on vähintään 22 (eli puolet maksimista).  Laskuharjoitukset eivät ole pakollisia, mutta parhaisiin arvosanoihin pääseminen edellyttää luonnollisesti, että myös harjoituksista saa pisteitä.

Sekä tavalliset että ohjelmointiharjoitukset pisteytetään kurssiarvostelussa siten, että tekemällä noin 90% tehtävistä saa täydet 8 pistettä.  Tähän maksimiin asti pisteet kertyvät tasaisesti siten, että noin 11% tehtävistä antaa aina yhden pisteen.  (Tarkat rajat asetetaan sopiviin kokonaislukuarvoihin kurssin loppuarvostelussa.)

Lisäopintopisteet: Erityisen ahkerasta harjoitustehtävien tekemisestä palkitaan siten, että tekemällä vähintään 80% kaikista harjoitustehtävistä (tavalliset ja ohjelmointiharjoitukset yhteensä) saa yhden lisäopintopistettä ja tekemällä 95% harjoitustehtävistä saa vielä toisen lisäopintopisteen.

Kurssi on mahdollista suorittaa myös erilliskokeella, jolloin arvosana määräytyy pelkästään yhden kokeen perusteella.  Erilliskokeella suoritettuna kurssin laajuus on 8 op.  Erilliskokeessa sallitaan samanlainen "lunttilappu" kuin kurssikokeissa.

Kevään 2016 luentokurssin tentit

Toisen kurssikokeen palautetilaisuus oli torstaina 26.5.

Ensimmäinen kurssikoe oli 7.3. Palautetilaisuus pidettiin maanantaina 21.3.

Uusinta- ja erilliskokeet

Koetulokset ilmestyvät tavalliseen tapaan Oodiin. Jos haluat tutustua tarkemmin kokeesi arvosteluun, ota sähköpostitse yhteyttä Jyrki Kiviseen.