58131 - Tietorakenteet 8 op - kevät 2010

Kurssikuvaus ja oppimistavoitteet

Tärkeät linkit

• Luentokalvot
• Kerttu Pollari-Malmin B+-puumoniste
• Joidenkin luentokalvojen algoritmien Python-versioita
• Antti Laaksosen tekemä hyvä Python-opas.
• TRAKLA2
• Project Euler
• Information in English
• Aktivator!

Ajankohtaista

• Toinen kurssikoe

• ensimmäinen kurssikoe

Luennot

19.01.-25.02. ja 16.03.-29.04. TI 10-12, TO 10-12 A111 Matti Luukkainen

Alustava sisältö:

Pvm	aihe	moniste	cormen2	cormen3
19.1.	johdanto, oikeellisuus	1-20	5-21	5-23
21.1.	oikeellisuus jatkuu, vaativuus	21-38	23-27, 41-55	23-28, 43-59
26.1.	vaativuus jatkuu	39-61
28.1.	pino ja jono, linkitetyt rakenteet	61-73, 80-105	200-203	229-235
2.2.	linkitetty lista	74-79, 108-126	204-208	236-240
4.2.	puu ja binäärihakupuu	127-137	1087-1090, 214-215	1176-1179, 246-247
9.2.	binäärihakupuu jatkuu	138-156	253-263	286-298
11.2.	binääripuu jatkuu, AVL-puu alkaa	157-186	Ei Cormenissa
16.2.	AVL-puu jatkuu	187-203	Ei Cormenissa
18.2.	AVL-puu jatkuu	204-227	Ei Cormenissa
23.2.	yleisen puun esittäminen ja läpikäynti, puut ongelmanratkaisussa	228-265	214-215	246-247
25.2.	kertaus	kalvot
1.3.	ensimmäinen välikoe klo 16-19 A111
16.3.	hajautus	268-285	221-236	253-268
18.3.	hajautus jatkuu	286-304	237-245	269-277
23.3.	keko, kekojärjestäminen	305-331	127-132, 138-141	151-158, 162-165
25.3.	järjestämisalgoritmeja	332-350	133-137, 27-36	156-161, 29-39
29.3. klo 14-16 B123	lisää järjestämiseen liittyvää	349-380	145-173	170-199
30.3.	verkko ja sen tallennustavat, leveyssuuntainen läpikäynti	381-407	1080-1085, 525-534	1168-1172, 587-598
13.4.	verkon leveyssuuntaisen läpikäynnin aikavaativuus, verkon syvyyssuuntainen läpikäynti	402-426	534-547	599-612
15.4.	verkon syvyyssuuntaisen läpikäynnin sovelluksia, lyhimpien polkujen alku	427-450	547-560, 580-587, 595-613,	612-620, 643-650, 658-680,
20.4.	lyhimmät polut jatkuu	451-475	629-636	693-699
22.4.	verkon virittävä puu	476-503	561-579	624-642
27.4.	Union-Find-rakenne, A*-algoritmi	515-537
29.4.	kertausta	kalvot
6.5.	toinen välikoe klo 9-12 A111

Laskuharjoitukset

Kurssin laskuharjoitukset alkavat jo ensimmäisellä viikolla

Harjoitusajat:

1. TI 14-16 CK111 Antti Laaksonen
2. TI 16-18 B119 Antti Laaksonen KE 16-18 B119 Pekka Mikkola in English if needed
3. TO 12-14 CK111 Pekka Mikkola
4. PE 12-14 B119 Matti Luukkainen

Opettajien sähköpostiosoitteet ovat:
ahslaaks (at) cs.helsinki.fi tai antti.h.s.laaksonen (at) cs.helsinki.fi
mluukkai (at) cs.helsinki.fi
pekka.mikkola (at) cs.helsinki.fi

Tehtävät ja esimerkkiratkaisut:

• viikko 1: tehtävät, esimerkkivastauksia
• viikko 2: tehtävät, esimerkkivastauksia
• viikko 3: tehtävät, esimerkkivastauksia, ohjelmakoodit
• viikko 4: tehtävät, esimerkkivastauksia, ohjelmakoodit
• viikko 5: tehtävät, esimerkkivastauksia
• viikko 6: tehtävät, esimerkkivastauksia, ohjelmakoodit Jarkko Nymanin kalvosarja tehtävään 6
• viikko 7: tehtävät, esimerkkivastauksia, ohjelmakoodit, B+-puumateriaali
• viikko 8: tehtävät, esimerkkivastauksia, ohjelmakoodit
• viikko 9: tehtävät, esimerkkivastaukset
• viikko 10: tehtävät, esimerkkivastauksia, ohjelmakoodit
• viikko 11: tehtävät esimerkkivastauksia, ohjelmakoodit
• viikko 12: tehtävät, esimerkkivastauksia, ohjelmakoodit

Normaalien laskareiden lisäksi kurssilla tehdään tehtäviä myös TRAKLA2-ohjelmistolla. Rekisteröityminen tapahtuu täällä

TRAKLA2-tehtävät on ryhmitelty "kierroksiin", siis ryhmiin tehtäviä, joilla on sama määräaika. Kunkin tehtävän oikeasta ratkaisusta saa kaksi TRAKLA2-pistettä jos tehtävä on oikein ja tehty määräaikaan mennessä. Samaa tehtävää voi yrittää monta kertaa ja paras tulos jää voimaan. Määräajan jälkeen tehdyistä vastauksista saa ainoastaan yhden TRAKLA2-pisteen.

Normaalilaskarien ja TRAKLA2-tehtävien vaikutus kurssipisteisiin on selitetty sivun alaosassa.

Laskarirasteja on myös mahdollisuus kerätä tekemällä Project Eulerin ohjelmointitehtäviä.

Laskarien vaikutus kurssipisteisiin on selitetty sivun alaosassa.

Kurssimateriaali

Luentokalvot

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 3. painos ilmestyi vasta syyskuussa 2009, esim. kirjastosta löytyy vain toista painosta joka sekin on käyttökelpoinen.

Kurssilla on muutamia asioita joita Cormenin kirjasta ei löydy, mm. AVL-puu ja B+-puut. Kaikissa asioissa käsittelytapa ei vastaa täysin Cormenia.

Vanhoja luentomonisteita:

• kevät 08 ja 09. Sisältö oleellisesti sama kuin nykyisellä kurssilla
• hieman vanhempi. Monisteessa mukana punamustat puut ja B-puun sellainen versio, jota kurssilla ei nykyään enää käsitellä

Kurssin suoritus

Kurssiin kuuluu kaksi välikoetta, 12 laskuharjoitusta, TRAKLA2-tehtäviä sekä vapaaehtoisena Project Euler -tehtäviä. Laskuharjoitukset aloitetaan jo ensimmäisellä viikolla.

Laskuharjoituksista on mahdollista saada 12 kurssipistettä. Laskuharjoituspisteistä 2/3 tulee normaaleista laskarirasteista ja 1/3 TRAKLA2-tehtävistä. Tarkka tehtävien lukumäärä selviää vasta kurssin kuluessa.

Project Euler -tehtävillä voi korvata 1/5 muista harjoitustehtävistä.

Täydet 12 laskuharjoituspistettä saa jos noin 85% harjoituksista on tehty. 100% tarkoittaa siis kaikkia normaaleja- ja traklatehtäviä joita voi korvata Eulereilla.

Kokeiden maksimipistemäärä on 24+24. Läpipääsyyn vaaditaan vähintään puolet kurssin kokonaispistemäärästä eli 30, koepisteiden summan täytyy myös olla vähintään 24.

Kokeissa saa olla mukana itse tehty, käsin kirjoitettu A4-kokoinen lunttilappu. Lunttilapun tekemisessä ei siis saa käyttää tietokonetta eikä kopiokonetta.

8.6. erilliskoetilaisuudessa voi uusia jomman kumman kurssikokeista tai tehdä normaalin erilliskokeen. Kurssikokeen uusiminen on mahdollista myös siinä tilanteessa, että kurssi olisi suoritettu hyväksytysti. Laskuharjoituspisteet huomioidaan arvostelussa, erilliskoevaihtoehdon suorittavilla vain niiden osalta, joille laskuharjoituspisteiden huomioiminen korottaa arvosanaa.