Seuraavassa on varsinaisten tulosten jälkeen lisäksi arviointiohjeet, jotka kannattaa lukea ennen tentin tutustumistilaisuuteen saapumista.
Terveisin
Ari Korhonen, Jussi Nikander ja Lauri Malmi
Arvosteluun voi tulla tutustumaan 17.6. klo 13-14 huoneeseen B219. Tutustumistilaisuuteen on ilmoittauduttava Webtopilla.
Review of the exam will be held on friday 17th of June at 13-14 (1-2 pm) in room B219 of the CS-building. Register for the review session through Webtopi.
| Pisteet / Points | Arvosana / Grade |
|---|---|
| 0-11 | 0 |
| 12-14 | 1 |
| 15-17 | 2 |
| 18-20 | 3 |
| 21-23 | 4 |
| 24- | 5 |
| Pisteet / Points | Arvosana / Grade |
|---|---|
| 0-9 | 0 |
| 10-12 | 1 |
| 13-15 | 2 |
| 16-18 | 3 |
| 19-21 | 4 |
| 22- | 5 |
opnro b 1 2 3 4 yht as --------------------------------------------------------- 52555b 2 2 4 5 1 14 1 53668p 2 2 5 3 2 14 1 53754d 0 1 6 3 0 10 0 57207v 2 0 3 5 3 13 1 58317h 2 0 6 3 1 12 1 58788c 2 2 5 4 0 13 1 60260n 2 2 0 4 0 8 0 60501f 0 2 6 6 2 16 2 63246s 0 0 2 2 0 4 0
opnro b 1 2 3 4 yht as --------------------------------------------------------- 39340m 2 0 1 2 1 6 0 44448j 0 2 4 5 2 13 2 44737n 2 1 5 6 6 20 4 45626j 2 1 2 6 1 12 1 52299n 2 2 3 7 2 16 3 53969l 2 2 4 6 2 16 3 54295p 2 0 4 8 4 18 3 55272b 2 2 6 7 2 19 4 55340p 2 0 2 4 2 10 1 55484e 2 2 4 5 4 17 3 57213e 2 0 0 7 1 10 1 57750l 2 0 4 5 3 14 2 57811r 2 2 3 4 3 14 2 57981p 0 0 2 2 2 6 0 58146h 2 0 2 4 3 11 1 58725t 2 0 2 0 1 5 0 59932h 2 0 2 4 2 10 1 60068l 2 1 4 5 4 16 3 60078a 2 0 5 7 5 19 4 60687b 2 2 4 7 5 20 4 61057m 2 0 1 4 2 9 0 61085a 2 1 2 2 2 9 0 61126d 2 1 1 3 1 8 0 61395h 2 0 2 5 2 11 1 62735u 2 0 3 5 4 14 2 62785l 2 2 1 4 4 13 2 62793v 2 2 3 4 3 14 2 62861l 0 3 2 7 3 15 2 62883p 2 1 5 8 5 21 4 62918l 0 0 4 2 5 11 1 63050k 2 3 3 6 5 19 4 63333h 2 1 3 6 4 16 3 63344v 0 0 2 1 3 6 0 63511r 2 2 4 7 6 21 4 63683s 0 2 5 8 3 18 3 63738p 2 0 2 5 2 11 1 71741u 2 0 1 4 1 8 0
1) Algoritmianalyysi (2p + 4p) a) Määrittele formaalisti käsitteet O(N) ja Omega(N). - 1 piste kummastakin määritelmästä, jos asian formaali määritelmä on kohdallaan. Pelkästä sanallisesta kuvauksesta ei saa pisteitä, koska tehtävässä korostetusti vaaditiiin formaalia määritelmää. b) Ratkaise seuraava rekursioyhtälö, kun N on kahden potenssi ja T(1) = 0. T(N) = T(N / 2) + log N Esitä lopputulos O-notaatiossa ja riittävästi välivaiheita, jotta tuloksen johtaminen käy selvästi ilmi. - Oikea tulos = O(log^2 N) - Tuloksen oikea johtaminen, 3p - Oikea tulos, 1p (tätä ei saa, jos johto on virheellinen tai puuttuu) - Oikeasta tuloksesta saa pisteen vain, jos se on em. muodossa. Jos tulos johdettu oikein, mutta se on sieventämätön, esim. summalauseke, saa siten yhteensä 3 pistettä. 2) Järjestäminen (4p + 4p) a) Esitä neljä keskeistä kriteeriä, joiden avulla voit verrata eri järjestämisalgoritmeja keskenään. Perustele lyhyesti, miksi ne ovat tärkeitä. Esitä vastauksesi siten, että kukin kriteeri perusteluineen on tekstissä eri kappaleena lukemisen helpottamiseksi. - Mahdollisia kriteerejä ovat esimerkiksi: - worst case performance (+ aineiston koko) - average case performance (+ aineiston koko) - lisätilan tarve - aineiston järjestysaste - menetelmän stabiilisuus - Kukin näistä kriteereistä, 1p, jos se on selitetty ja perusteltu. Pelkästä maininnasta ilman perusteluja, 0.5 p. - Jos on jokin hyvin perusteltu muu kriteeri, siitä voi antaa +1 p. - Max. 4p b) Arvioi kunkin kriteerin valossa seuraavia algoritmeja: Insertion sort, Quicksort ja Mergesort. Esitä vastauksesi siten, että vertailutulos kunkin kriteerin suhteen on helposti luettavissa. - Kunkin a-kohdan vastauksessa esitetyn kriteerin käsittely, 1p - Täyteen pisteeseen täytyy olla maininta tilanteesta kaikkien algoritmien kohdalla. Jos jokin puuttuu, saa vain 0.5p - Jos täällä esitetään kriteereitä, joita ei a-kohdassa ole mainittu, niistä ei saa pistettä. 3) Hakurakenteet (4p + 4p) Vertaile avoimeen osoitukseen perustuvia hajautusrakenteita ja tasapainotettuja hakupuita keskenään hakurakenteina. a) Esitä ja perustele ensin mielestäsi neljä keskeisintä vertailukriteeriä tässä asiassa. - Mahdollisia kriteerejä ovat esimerkiksi: - worst case performance - average case performance - käyttäytyminen dynaamisessa tilanteessa (paljon lisäyksiä ja poistoja) - haut, joissa aineistoa käydään läpi järjestyksessä - menetelmän tilankäyttö - Kukin näistä kriteereistä, 1p, jos se on selitetty ja perusteltu. Pelkästä maininnasta ilman perusteluja, 0.5 p. - Jos on jokin hyvin perusteltu muu kriteeri, siitä voi antaa +1 p. - Max. 4p b) Esitä vertailun tulokset kunkin kriteerin suhteen. Kirjoita vastauksesi siten, että kukin kriteeri perusteluineen on omana kappaleenaan ja vastaavasti vertailutulokset omina kappaleinaan. - Kunkin a-kohdan vastauksessa esitetyn kriteerin käsittely, 1p - Täyteen pisteeseen täytyy olla maininta tilanteesta kaikkien algoritmien kohdalla. Jos jokin puuttuu, saa vain 0.5p - Jos täällä esitetään kriteereitä, joita ei a-kohdassa ole mainittu, niistä ei saa pistettä. 4) Verkot (2p + 2p) Toimivatko seuraavat algoritmit, jos painotetussa graafissa on negatiivisia särmiä? Perustele näkemyksesi. Jos jokin algoritmi toimii mielestäsi virheellisesti, esitä sopiva vastaesimerkki. a) Primin algoritmi pienimmän virityspuun etsimisessä - Toimii - Oikea vastaus, 1p - Perustelu oikein, 1p b) Dijkstran algoritmi lyhimmän reitin etsimisessä. - Ei toimi - Oikea vastaus, 1p - Perustelu oikein tai vastaesimerkki, 1p
1) Algoritmianalyysi (1p + 1p + 1p + 1p)
Mikä on seuraavien koodien aikakompleksisuus O-notaatiossa. Pelkkä
lopputulos riittää vastaukseksi.
a) sum = 0;
for (i = 0; i < 10*n; i++)
for (j = 1; j < 3*n; j++) sum++;
b) sum = 0;
for (i = 1; i <= n; i = i+10)
for (j= -i; j <= i; j = j+10) sum++;
c) sum = 0;
for (i = 0; i < 3*n*n; i++)
for (j = 0; j < i*i*i; j++) sum++;
d) sum = 0;
for (i=1; i< n/100; i++)
for (j=2; j < (i+n)*i*i; j++)
if (j<=10000)
for (k=0; k< i*j; k++) sum++;
a) O(N^2)
b) O(N^2)
c) O(N^8)
d) O(N^4)
- Oikea vastaus, 1p
- Oikea vastaus, mutta mukana kertoimia, esim. O(2N^2), 0.5 p
2) Määrittele seuraavat tietorakenteet (2p + 2p + 2p)
a) Jono
- Peräkkäisrakenne, 1p
- Lisäys toiseen päähän, poisto vastakkaisesta päästä, 1p
b) Keko (heap)
- Täydellinen binääripuu (joka voidaan toki esittää taulukkona), 1p
- Kekoehto (joko isä > lapset tai päinvastoin), 1p
- Lisäys- ja poistoalgoritmeja ei tarvitse selittää.
c) B+-puu
- Monihaarainen puu, jossa kullakin solmulla voi olla M/2 - M lasta
(tämä tarkkuus riittää), 0.5p
- Juurella voi olla 2 - M lasta, 0.5p
- Kaikki avaimet talletetaan lehtiin, 0.5p
- Kaikki lehdet samalla etäisyydellä juuresta, 0.5p
3) Järjestäminen (4p + 4p)
a) Esitä neljä keskeistä kriteeriä, joiden avulla voit verrata eri
järjestämisalgoritmeja keskenään. Perustele lyhyesti, miksi ne ovat
tärkeitä. Esitä vastauksesi siten, että kukin kriteeri perusteluineen
on tekstissä eri kappaleena lukemisen helpottamiseksi.
- Mahdollisia kriteerejä ovat esimerkiksi:
- worst case performance (+ aineiston koko)
- average case performance (+ aineiston koko)
- lisätilan tarve
- aineiston järjestysaste
- menetelmän stabiilisuus
- Kukin näistä kriteereistä, 1p, jos se on selitetty ja perusteltu.
Pelkästä maininnasta ilman perusteluja, 0.5 p.
- Jos on jokin hyvin perusteltu muu kriteeri, siitä voi antaa +1 p.
- Max. 4p
b) Arvioi kunkin kriteerin valossa seuraavia algoritmeja: Insertion
sort, Quicksort ja Mergesort. Esitä vastauksesi siten, että
vertailutulos kunkin kriteerin suhteen on helposti luettavissa.
- Kunkin a-kohdan vastauksessa esitetyn kriteerin käsittely, 1p
- Täyteen pisteeseen täytyy olla maininta tilanteesta kaikkien
algoritmien kohdalla. Jos jokin puuttuu, saa vain 0.5p
- Jos täällä esitetään kriteereitä, joita ei a-kohdassa ole mainittu,
niistä ei saa pistettä.
4) Hakurakenteet (3p + 3p)
a) Tasapainotetut puut ovat hakurakenteita, joita välillä suositellaan
dynaamisiin sovelluksiin, missä tapahtuu hakujen lisäksi runsaasti
lisäyksiä ja poistoja. Selitä, mihin niiden toiminta
perustuu. Määrittele esimerkkinä jokin tasapainotettu binääripuu.
- Puun worst-case korkeus aina logaritminen tai O(log N) , 1p
- Jokaisen päivityksen jälkeen puu tasapainotetaan tarvittaessa, 1p
- Esimerkkipuun määrittely oikein, 1p
b) Esitä, miten kuvaamasi puu muuttuu, kun alunperin tyhjään puuhun
lisätään seuraavassa järjestyksessä avainarvot 1, 20, 2, 19, 3, 18, 4,
17, 5, 16. Esitä välivaiheet.
- Oikea vastaus välitilanteineen, 3p
- Jokin virhe toiminnassa, mutta pääsääntöisesti oikein, 2p
- Toiminta virheellinen, mutta vastauksesta löytyy jokin selvästi
oikea tasapainotustoiminto, 1p