KURSSIN TULOKSET OVAT VALMISTUNEET!.

Esitiedot

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

Esitietokoe, joka korvaa puutteet esitietovaatimuksista, pidettiin 13.1.

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

Luennot

Luentomateriaali (pdf)

Luentomateriaali korjataan sitä mukaan kun korjattavaa ilmenee, joten sitä kannattaa tulostaa osissa. Materiaalia tulee myös lisää ajan kanssa.

Korjaukset 16.1.: s. 5 (ei B+-puita), s. 9 (pariton -> parillinen), s. 10 loppusulku puuttui, s. 23 Algoritmien suunnittelu ja analyysi -kurssin nimi englanniksi.

Korjaukset 18.1.: s.46 algoritmin B aikavaativuuksissa oli kirjain A, s. 66 lisätty selventävä "(while)", s. 73 Algoritmien suunnittelu ja analyysi -kurssin nimi englanniksi, s. 98 kalvon viimeisenä kohtana ollut turha lisäselitys poistettu, s.99 kirjoitusvirhe korjattu ("jäälkeen") - tästä lähtien pienten ilmeisten kirjoitusvirheitten korjauksista ei kerrota erikseen.

Korjaukset 25.1.: s.107 tasoitettu analyysi: poistettu ettei siihen palata kurssilla (koska siihen palataan), s. 144 pidetty huolta, että mahtuu yhdelle siuvlle, s. 163 lehtisolmujen lukumäärä korjattu (puuttui +1 kaavasta), s.167 on uusi sivu, johon on koottu puiden läpikäyntien pseudokoodit ja tämän jälkeen viittaukset sivuihin on päivitetty.

Korjaukset 30.1.: s. 234 lisätty (AVL-insertin toinen osa puuttui), s. 239 pidetty huolta, että mahtuu yhdelle sivulle.

Korjaukset 7.2.: s. 278 current-sana korjattu, s. 288 prev korjattu -> pred, s. 302 m selostettu tarkemmin, s. 306 kuva korjattu.

Korjaukset 8.2.: s. 319 NIL->DEL, sl. 323 vaihdettu 27 92:ksi, jotta kokeilujunon askelpituudeksi saataisiin 5.

Korjaukset 22.2. Tilanteessa, jossa AVL-deleten johdosta AVL-ehti riikkoontuu ja korkeamman alipuun oikea ja vasen haara ovat yhtä pitkiä, ei ole annettu luennolla yksikäsitteistä vastausta käytetäänkö kiertoa vai kaksoiskiertoa. Tällaisessa yhteydessä pitäisi yksinkertaisuuden vuoksi käyttää yhtä kiertoa. Tällainen tilanne esiintyi laskarien 5 tehtävässä 3. Sivulla 238 vaihdettu algoritmin rivien 8-9 ja 10-11 paikkaa ja s. 239 lisätty korjaavan kierto-operaation yhteyteen "(mahdollisimman yksinkertainen)".

Korjaukset 12.3.: s.348 muutettu lista aikaisemmin esiintyneistä järjestämisalgoritmeista, s. 376 otsikko lisätty, s. 377 algoritmin lyöntivirheet korjattu.

Korjaukset 14.3.: s. 384-385 korjattu lyöntivirheitä epäyhtälöissä, s. 395 kalvolla 70 -> kalvolla 79, s. 396 korjattu lyöntivirheitä, myös algoritmin rivillä 1, s. 400 kalvo 147 -> kalvo 157. Ylipäätään korjattu kirjoitusvirheitä koko luvun 6 loppuosassa (pikajärjestämisestä alkaen).

Korjaukset 19.3.: s. 420 todettu että polku u:sta u:hun on nollamittainen polku, s. 426 automaatti tunnistaa vain etumerkittömiä lukuja, s. 441 algoritmin viimeisellä rivillä pitäisi olla color[u] = black, s. 456 todettu, että saadaan syvyyssuuntainen etsintä korvaamalla BFS:n jono pinolla, korjattu kirjoitusvirheitä sieltä täältä.

Korjaukset 28.3.: s. 510 kirjoitusvirheitä korjattu, s. 515 algoritmin rivi 10 korjattu (väärä sisennys), s. 514, 519-520 ja 523 viittaukset sivunumeroihin korjattu, s.516 merkitty selkeämmin mitä rivi 5 tulostaa.

Korjaukset 4.4.: s. 560 jollekin pienimmälle virittävälle puulle (V,T) (tämä on tärkeä korjaus), myös osajoukkomerkintä tehty selvemmäksi, s. 568 while -> for, s. 572 A ->T algoritmin rivillä 10, s. 580 alaindeksi 2 puuttui log*-merkinnästä, s. 581 sulkumerkkejä puuttui, toistolauseeseen -> while-silmukkaan.

Korjaukset 16.4.: s. 585 sivunumerot korjattu, s. 589 tarkennettu että etäisyysarvio on siihen mennessä tiedossa oleva etäisyys, s. 610 lisätty viittaus Cormeniin.

Luennoilla 30.1.2012 esitetty induktiotodistus. Lisälehti verkkoalgoritmien kertausosioon (lisätty kurssisivulle 16.4.2012).

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

• http://www.youtube.com/watch?v=t8g-iYGHpEA
• http://www.i-programmer.info/news/150-training-a-education/2255-sorting-algorithms-as-dances.html

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!

• Harjoitus 1 Ratkaisut 1
• Harjoitus 2 Ratkaisut 2 On kysytty mitä tarkoittaa "ylimääräinen lisätehtävä": Se on normaali laskuharjoitustehtävä, mutta kun lasketaan maksimitehtävämäärää, sitä ei oteta mukaan laskuun. Eli se on bonustehtävä.
• Harjoitus 3 Ratkaisut 3
• Harjoitus 4 Ratkaisut 4
• Harjoitus 5 Ratkaisut 5
• Harjoitus 6 Ratkaisut 6
• Harjoitus 7 Ratkaisut 7
• Harjoitus 8 Ratkaisut 8
• Harjoitus 9 Ratkaisut 9
• Harjoitus 10 Ratkaisut 10
• Harjoitus 11 Ratkaisut 11
• Harjoitus 12 Ratkaisut 12

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ä. 

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.

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.