Tietorakenteet ja algoritmit (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

18.10.2013 16.00 A111
09.12.2013 16.00 B123
Year Semester Date Period Language In charge
2013 autumn 02.09-06.12. 1-2 Finnish Patrik Floréen

Lectures

Time Room Lecturer Date
Tue 14-16 CK112 Patrik Floréen 03.09.2013-03.09.2013

Exercise groups

Group: 1
Time Room Instructor Date Observe
Tue 12-14 CK112 Mika Huttunen 10.09.2013—08.10.2013 Kyselytunnit
Tue 12-14 CK112 Mika Huttunen 29.10.2013—03.12.2013 Kyselytunnit
Group: 2
Time Room Instructor Date Observe
Fri 14-16 D122 Mika Huttunen 06.09.2013—11.10.2013 Laskuharjoitukset
Fri 14-16 D122 Mika Huttunen 01.11.2013—29.11.2013 Laskuharjoitukset
Thu 14-16 D122 Mika Huttunen 05.12.2013—05.12.2013 Laskuharjoitukset
Group: 3
Time Room Instructor Date Observe
Fri 10-12 D122 Mika Huttunen 06.09.2013—11.10.2013 Laskuharjoitukset
Fri 10-12 DK116 Mika Huttunen 01.11.2013—01.11.2013 Laskuharjoitukset
Fri 10-12 CK108 Mika Huttunen 08.11.2013—08.11.2013 Laskuharjoitukset
Fri 10-12 DK116 Mika Huttunen 15.11.2013—29.11.2013 Laskuharjoitukset
Thu 12-14 C220 Mika Huttunen 05.12.2013—05.12.2013 Laskuharjoitukset
Group: 4
Time Room Instructor Date Observe
Thu 10-12 C220 Mika Huttunen 05.09.2013—10.10.2013 Laskuharjoitukset/Ohjaus
Thu 10-12 C220 Mika Huttunen 31.10.2013—05.12.2013 Laskuharjoitukset/Ohjaus

Non finnish students, contact the lecturer beforehand.

Information for international students

The course is given in Finnish without lectures. International students may study the course material using the book, and participate in the written exam(s). No particular guidance is given in English.

Students at the course 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.

New: both Heaps and Hash Tables are included in the first exam.

For self-studies please read the following pages in the book Cormen, Leiserson, Rivest, Stein:  Introduction to Algorithms: 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, New: 151-165 (Heaps) and for the second course exam  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-252 and heaps 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) are included. The material is available here.

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 2013. Batch one and two covers the first part of the course; the third batch covers the second part. Unfortunately there are not answers in English available.

We offer two alternative ways to pass this course:

1. You can participate in the two exams on the normal course going on now (these are 18.10. at 16.00 (NOTE: NEW DATE) in Exactum A111 and 9.12. at 16.00 in Exactum B123). in this case, as you do not participate in the exercise group, I will scale your points so that the maximum points of the exams (44) correspond to the maximum points in the course (60). So, for example, if you get 22 points in the exams, your course points will be calculated as 22/44*60=30. Note that in this case you need to be signed up to the course and you have had to inform me by email (patrik.floreen (at) cs.helsinki.fi) at the beginning of the course that you are a non-Finnish-speaking participant in the course.

2. You can participate in a separate exam covering the full course, at the normal times when there is a separate exam. In this case you need not to sign up to the course, but you need to sign up to the separate exam AND tell me (patrik.floreen (at) cs.helsinki.fi) at least one week in advance that you need the exam questions in English. The next separate exams are 17.9.2013, 26.11.2013, 28.1.2014 and 8.4.2014.

Please note that you are allowed to have a hand-written A4-sized sheet of paper of personal notes with you at all these exams (you can write on both pages).

General

Uutta: Erilliskoe 8.4.2014 on korjattu. Korjaaja: Mika.Huttunen@helsinki.fi, eli häneltä saa lisätietoja.

Uusinta- ja erilliskokeen 6.2.2014 tehtävät. Uusinta- ja erilliskokeen 6.2.2014 ratkaisut. Tulokset (vaatii kirjautumisen).

Kurssikoe1 tulokset. Myös laskuharjoituspisteet viikolle 9 asti. Ilmoita, jos huomaat virheitä.

Kysymykset

Mallivastaukset

Kurssikoe2 tulokset. Kohdasta HT löytyy tirapajan lisäpisteet. 2. Tentin tehtävä kohtaiset pisteet ovat kohdissa "Koe" 5-8.

Kysymykset

Mallivastaukset kokeeseen 2

Kysymykset kokeista voi esittää Mika Huttuselle (mika.huttunen(at)helsinki.fi) 31.12.2013 mennessä.

Tämä kurssi on Tietorakenteet ja algoritmit -kurssin "itseopiskeluversio". Tämä tarkoittaa, että kurssilla ei ole luentoja.

ALOITUSTILAISUUS ON 3.9. POIKKEAVAAN AIKAAN KLO 14-16 salissa CK112.

Esitiedot

Kurssi vaatii riittävää ohjelmointi- ja matematiikkaosaamista. Kurssin esitietovaatimuksina on kurssit Ohjelmoinnin jatkokurssi ja Johdatus yliopistomatematiikkaan (ennen Johdatus diskreettin matematiikkaan). Kurssin suorittaminen on käytännössä mahdotonta, jos näissä esitiedoissa on huomattavia puutteita. Matematiikan osalta on riittävää, että osallistuu kurssille Johdatus yliopistomatematiikkaan samanaikaisesti tämän kurssin kanssa.

Kokemus osoittaa, että ellei suoridu ensimmäisistä laskuharjoituksista, ei käytännössä pysty suoriutumaan kurssista. Siksi vaadimme tällä itseopiskelukurssilla, että kolmessa ensimmäisessä laskuharjoituksessa on kussakin tehtävä vähintään kaksi tehtävää, muuten opiskelija poistetaan kurssilta.

Kurssin sisältö

Syksyn 2013 kurssin sisältö on sama kuin kevään 2013 kurssin.

Luentomateriaali (pdf). Materiaaliin tehdään kirjoitusvirhekorjauksia, kun niitä löytyy. Sivu 475 alalaidassa korjattu 14.11.2013. Virhe w->z, korjaus w->y.

Kyselytunnit

Tarkoituksena on, että opiskelija lukee vaaditut sivut luentomateriaalista ennen kyselytuntia. Kyselytunnilla syvennytään jo luettuun aiheeseen. Aiheita käsitellään seuraavasti:

1. Aloitustilaisuus 3.9. sivut 1-32

2. Kyselytunti 10.9. sivut 33-100

3. Kyselytunti 17.9. sivut 101-164

4. Kyselytunti 24.9. sivut 165-251

5. Kyselytunti 1.10. sivut 335-354

6. Kyselytunti 8.10. sivut 252-334

 

2. Periodi

7. Kyselytunti 29.10. sivut 355-421

8. Kyselytunti 5.11. sivut 422-473

9. Kyselytunti 12.11. sivut 474-505

10. Kyselutunti 19.11. sivut 506-548

11. Kyselytunti 26.11. sivut 549-593

12. Kyselytunti 3.12. Materiaali loppuun ja kertausta

 

 

KURSSIKOKEEN 1 ALUE:

  • Alkutekstit s. 1-12
  • 1 Johdanto tietorakenteisiin s. 19-106
  • 2. Perustietorakenteet: Pino, jono ja lista s. 107-153
  • 3. Hakupuut s. 154-294
  • 4. Hajautus s. 295-334
  • 5. Keko s. 335-354

KURSSIKOKEEN 2 ALUE (ALUSTAVA JAKO, sen lisäksi että on osattava kurssikokeen 1 asiat):

  • 6. Järjestäminen s. 355-421
  • 7. Verkot s. 422-623 (huom: osa luvun lopusta on "ylikurssia" eikä tule kokeeseen: eli kokeeseen ei tule A* tai vuo verkoissa; ihan luvun lopussa on yhteenveto, joka koskee aiemmin esitettyjä asioita ja on sitä kautta siis koealuetta)
  • 8. Algoritminsuunnittelumenetelmiä s. 624-635 (huom: tämäkin on yhteenveto aiemmin kurssilla mainitusta asioita, joten tämä tulee sitä kautta siis mukaan koealueeseen)

Oppimista tukevaa lisämateriaalia internetissä: Järjestämisalgoritmien visualisointi. Lyhimpien polkujen etsinnän visualisointi.

Harjoitukset

Harjoituksia on kahdenlaisia: Tavalliset laskuharjoitukset ja ohjelmointitehtävät (Tira-paja). Tavalliset laskuharjoitukset alkavat jo ensimmäisellä kurssiviikolla, eli 6.9.! Pajatehtävät alkavat vasta seuraavalla viikolla.

Laskuharjoituksia ei palauteta etukäteen, vaan tehdään etukäteen ja käydään läpi laskuharjoitustilaisuudessa. Jos sinulla on vaikeuksia laskuharjoitusten kanssa, voi tulla kysymään torstain laskuharjoitusohjaukseen.

Huomio: Jos tehtävä koostuu monesta alakohdasta (a, b, c, ...), voit merkitä rastin tehtävän suorituksen merkkinä, jos olet tehnyt vähintään puolet alakohdista.

Tira-paja: https://www.cs.helsinki.fi/group/tirapaja/s13/

Yhteyshenkilö: jarmo.isotalo (at) cs.helsinki.fi - Mika Huttunen ei vastaa TiRa-pajaan liittyvissä kysymyksissä!

Aloitustilaisuudessa sovittu määräaika tehtäville: Joka viikon tiistai, aamulla klo 7.00.

 

Laskuharjoitukset

Laskuharjoitus 1

Laskuharjoitus 2

Laskuharjoitus 3

Laskuharjoitus 4

Laskuharjoitus 5

Laskuharjoitus 6

Laskuharjoitus 7

Laskuharjoitus 8

Laskuharjoitus 9

Laskuharjoitus 10

Laskuharjoitus 11

Laskuharjoitus 12

Jos osallistuit kurssille ja olet osallistumassa uusintakokeeseen, niin voit pyytää malliratkaisuja sähköpostilla (mika.huttunen ät helsinki.fi).

Completing the course

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.

Ensimmäinen kurssikoe on pe 18.10. klo 16.00 (Huom: uusi päivämäärä), Exactum A111. Toinen kurssikoe on 9.12. klo 16.00, Exactum B123.

Tässä vanhoja kurssikokeita: Vuoden 2013 kevään kurssikoe1 ja kurssikoe 2. Vuoden 2012 kevään kurssikoe 1 ja kurssikoe 2. Vuoden 2011 kevään kurssikoe 1 ja kurssikoe 2.

Omat tulokset (myös laskuharjoitusrastien määrät) näkyvät TIKLIssä https://ilmo.cs.helsinki.fi/tulokset/.

Harjoituksia oli siis kahdenlaisia:

  • 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 sovitaan aloitustapaamisessa 3.9. Ohjelmointitehtävät tarkastetaan TMC-ohjelmalla ("Test My Code").

Kurssin suoritukseen vaaditaan 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 (viimeinen vaihtoehto alla).

Erittäin kiitettävästä laskuharjoitustehtävien ja paja-tehtävien tekemisestä saa lisäksi ylimääräisiä opintopisteitä 1 tai 2: jos on tehnyt vähintään 80% tehtävistä (siis laskuharjoitustehtävistä ja paja-tehtävistä yhteensä) saa yhden lisäopintopisteen, ja jos on tehnyt vähintään 95% saa kaksi lisäopintopistettä.

Vaihtoehtoinen tapa suorittaa kurssi on erilliskokeella (60 maksimipistettä), jolloin kurssin suoritukseen kuuluu ainoastaan yksi erilliskoe. Myös uusinta- ja erilliskokeissa saa olla mukana samanlainen "lunttilappu" kuin kurssikokeissa. Uusintakoe on erilliskokeen 28.1.2014 yhteydessä. Uusintakoe on kuin erilliskoe, mutta niin että laskuharjoituspisteet lasketaan mukaan.

Kurssilta voi saada siis 8,9 tai 10 opintopistettä. 9 tai 10 opintopistettä voi saada vain, jos opiskelija on suorittanut tarvittavan määrän tehtäviä harjoituksista ja suorittaa kurssin kurssikokeilla tai uusintakokeessa (28.1.2014 järjestettävän erilliskokeen yhteydessä). Muissa erilliskokeissa ei enää huomioida laskuharjoituspisteitä ja niistä saa 8 opintopistettä.

Tässä joitakin 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.

Kurssin arvosana määräytyy kokonaispistemäärästä, ohjeellisesti seuraavalla tavalla:

50-60 p.: arvosana 5

45-49 p.: arvosana 4

40-44 p.: arvosana 3

35-39 p.: arvosana 2

30-34 p.: arvosana 1

0-29 p.: hylätty

 

Kurssin saama palaute: Arvosanat olivat erinomaiset, yleisarvosana 4,5/5. Tässä yksittäisiä kommentteja kommentoituna. Valtaosa kommenteista olivat kiitoksia, joten ohessa vain kriittiset kommentit.

Opiskelijan palaute Kommentti
Tämä itseopiskelukurssi on ihan täydellinen pohjanoteeraus! Ihan sama kuin ryhtyisi kasvissyöjäksi vain jättämällä lihan ruokavaliosta pois, kun tietenkin täytyy lisätä kasvisten määrää ja huolehtia proteiinin saannista muilla konstein. Eli kurssi ei muutu itseopiskelukurssiksi vain sillä, että siinä ei järjestetä luentoja. Tämä kurssi on tiedetysti osalle opiskelijoita todella vaikea (ja tulevissa opinnoissa ja töissä aivan turha), jota joutuu yrittämään moneen kertaan, ja joka lukukausi sinne ilmoittautuu satamäärin ihmisiä. Tätä tietoa vasten on aivan väärä paikka säästää siinä, että kurssi luennoidaan vain kerran vuodessa. Kurssilla pitäisi olla myös kunnollinen suomenkielinen materiaali. Sellaiseksi ei kelpaa luentokalvot, koska ne on tarkoitettu luentojen tueksi, ei itseopiskeluun. Kuten Patrik aloitustilaisuudessa sanoi, materiaali on edelleen sama kuin hänen 80-luvulla käymänsä kurssi. Miksi siis materiaalia ei tehdä? Siinä olisi hyvä kandintyöaihe muutamalle opiskelijalle! Tulevat opiskelijat kiittäisi ja laitoskin saisi ihmiset suorittamaan opintonsa. Vaikka Mika on hyvä tyyppi ja hyvä laskarinpitäjä, edes hän ei kyennyt pelastamaan kurssia kurssipalautteen huonolta arvosanalta.

Puhtaassa itseopetuksessa ei olisi mitään opetusta. Silloin mennään suoraan erilliskokeeseen. Tällä kurssilla on annettu runsaasti opetusta, joten "itseopiskelu" on todellakin väärä termi.

Materiaali ei tietenkään ole sama kuin 80-luvulla; asiakokoinaisuudet kuten puut ja verkot ovat kuitenkin samat, koska kyse on klassisista tietojenkäsittelyn perusasioista. Englanninkielinen kurssikirja on varsin seikkaperäinen.

Pajaohjausta voisi kuitenkin ehkä olla enemmän siltä varalta ettei vertaistukea saa tai että ei IRC:ssä hengaile. Pajassa kävi yllättävän vähän väkeä.
Pajatehtävät eivät aina menneet aivan samaan tahtiin kurssin kanssa ainakaan alussa. Lisäksi muutamassa pajatehtävässä tehtävänanto tai tarjottu pohja tai testien feedback oli erittäin vaikeaselkoista ja vaikeutti siten näiden tehtävien tekemistä väärällä tavalla. Kiitos kommentista. Pajatehtävät ovat jatkuvan kehittelyn kohteena. Yksittäisistä pajatehtävistä kannattaa olla yhteydessä suoraan pajavastaavaan, jotta ne saataisiin paremmiksi.
Toivoisin ens kerralla etä arvosana koostuu joko pelkistä kokeista tai sitten samalla tavalla kun nyt, mutta sen mukaan kummasta tulee parempi. Tämä on mielenkiintoinen idea. Erilliskokeessa harjoituksista ei saa pisteitä.
Pari tehtävänantoa oli kirjoitettu todella epäselvästi. Työmäärä opintopisteisiin nähden huomattavan suuri. Ehkä 10 + 3 op olisi lähempänä totuutta. Ei selvää mistä tehtävistä on kyse (paja?, laskarit?, tenttiehtävät?).
Jos pajatehtävät saataisiin paremmin "synkattua" muun kurssin kanssa, ei jäisi oikeastaan mitään valitettavaa. Ks. yllä.
Floréenilta olisin ehkä kaivannut vähän lempeämpää asennetta tuoreita fukseja kohtaan. Taululle pakottaminen ja siellä kyykyttäminen ei mielestäni tue oppimista samalla tavalla kuin esim. ryhmissä tehtävien pohtiminen. Jos merkitsee tehtävän tehdyksi, eikä kuitenkaan tiedä tehtävästä mitään, voi vain ihmetellä miksi on merkinnyt tehtävän tehdyksi. Huttunen ei ilmeisesti ole yhtä pelottava, vaikka toiminta oli vastaavanlaista;)
Pajaohjauksestakaan en ole aivan varma, milloin oli tarjolla. Ohjausajat ovat pajasivulla.

Literature and material

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. Katso tarkemmat tiedot yllä olevasta informaatiosta kansainvälisille opiskelijoille.