Tietorakenteet ja algoritmit
Exam
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
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 |
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 |
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 |
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.
- koko luentomateriaali (sivut 1–642) yhtenä PDF-tiedostona
Ylimääräinen luento 27.4.: rinnakkaisuus
Luentomateriaali jaettuna lukuihin:
- Johdanto
- Johdanto tietorakenteisiin
- Järjestäminen
- Perustietorakenteet
- Hajautus
- Hakupuut
- Keko
- Verkot
- 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.
- harjoitus 1 (18.–22.1.): tehtävät, malliratkaisut
- harjoitus 2 (25.–29.1.): tehtävät, malliratkaisut
- harjoitus 3 (1.–5.2.): tehtävät, malliratkaisut
- harjoitus 4 (8.–12.2.): tehtävät, malliratkaisut
- harjoitus 5 (15.–19.2.): tehtävät; tehtävän 6 tiedostot vocabulary.txt, vocabulary2.txt; malliratkaisut
- harjoitus 6 (22.–26.2.): tehtävät, malliratkaisut
- harjoitus 7 (29.2.–4.3.): tehtävät, malliratkaisut
- tenttiviikolla 7.–11.3. ei ole laskuharjoituksia
- periodin IV ensimmäisellä luentoviikolla 14.–18.3. ei ole tavallisia laskuharjoituksia, mutta TMC:ssä voi tehdä bonustehtäviä
- harjoitus 8 (23.3. ja 31.3.): tehtävät, malliratkaisut
- harjoitus 9 (4.–8.4.): tehtävät, malliratkaisut
- harjoitus 10 (11.–15.4.): tehtävät, malliratkaisut. Täsmennys: tehtävässä 3 verkko on suuntaamaton.
- harjoitus 11 (18.–22.4.): tehtävät, malliratkaisut
- harjoitus 12 (25.–29.4.): tehtävät, malliratkaisut
- bonusviikko (2.–6.5.): tehtävät, malliratkaisut
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.
- tehtävät
- malliratkaisut ja arvosteluperusteet
- pistejakauma
- keskiarvo 13,6 / 22 pistettä; tehtävän 1 keskiarvo 2,1; tehtävän 2 keskiarvo 4,4: tehtävän 3 keskiarvo 2,6; tehtävän 4 keskiarvo 2,3; ja tehtävän 5 keskiarvo 2,2 pistettä
Uusinta- ja erilliskokeet
Koetulokset ilmestyvät tavalliseen tapaan Oodiin. Jos haluat tutustua tarkemmin kokeesi arvosteluun, ota sähköpostitse yhteyttä Jyrki Kiviseen.
- uusinta- ja erilliskoe 14.6.2016: tehtävät, malliratkaisut