T-106.250/253 Tietorakenteet ja algoritmit T/Y

Tenttivaatimukset (voimassa kevään 2005 kurssilla)

Tenttiin tai välikokeisiin valmistautumisessa kannattaa kerrata seuraavat asiat:

1. Luennoilla käsitellyt asiat
2. Luentotehtävät
3. Perustehtävissä käsitellyt asiat (Y-kurssi)
4. Laskuharjoituksissa käsitellyt asiat (T-kurssi)
5. Opetusmonisteet
6. Seuraavista oppikirjoista alla mainitut kohdat kattavat kurssialueen kohtuullisen hyvin.
   • M.A. Weiss: Data Structures and Algorithm Analysis Algorithms in Java, luvut 1-9, sekä kohdat 10.1.2, 10.3.4 ja 12.2.  Pois jäävät luvut 4.5, 6.5-6.8, 7.10, 8.6.1 ja 9.4. Kirjan C-painoksesta jää lisäksi pois luku 7.11.
   • Cormen-Leiserson-Rivest: Introduction to Algorithms (1st ed., 1990), luvut 1-5, 7-14, 17.3, 19, 22-25, 26.2, 36-36.3 poislukien kohdat 4.4, 10.3, 22.4, 25.3, 25.5.
   • Cormen-Leiserson-Rivest-Stein: Introduction to Algorithms (2nd ed., 2001), liitteet A ja B, luvut 2-4, 6-13, 16.3, 18, 21-24, 25.2, 34-34.2 poislukien kohdat 4.4, 9.3, 21.4, 24.1 ja 24.4
   • Sahni: Data Structures, Algorithms, and Applications In Java (1st ed., 2000), 2-3, 4.5 (vain T-kurssille), 5-13, 15-17, 18.3.3, 18.3.5-18.3.6 ja 19. Pois jäävät kohdat 6.5.3, 8.3-8.4, 11.4, 11.6, 13.5, 16.3 ja 19.4.
   • Levitin: The Design and Analysis of Algorithms (1st ed., 2003), luvut 1-7, 8.2, 9 ja 10.3. Pois jäävät kohdat 3.3 (convex hull), 3.4, 4.5-4.6, 5.4-5.5, 6.2 ja 7.2.

• Esitetyt algoritmit ja tietorakenteet on hallittava periaatteellisella tasolla.
• Algoritmien suoritusaika- ja tilavaatimusanalyysien tulokset sekä niiden johtaminen kuuluvat tenttivaatimuksiin.
• Algoritmien ohjelmakoodeja ei tarvitse opetella ulkoa (vältä muutoinkin ulkoaopettelua ja pyri mieluummin luomaan yhteyksiä eri asioiden välille siten, että syntyy laajempi käsitys aihepiiristä). Mikäli tentissä pyydetään kirjoittamaan jonkin algoritmin koodi, sen voi kirjoittaa pseudokielellä.
• Yksinkertaisen lausekielisen (ANSI-C, Java, Pascal, Pseudo) ohjelman toiminnan ymmärtäminen on tarpeellista.

Tenttitehtävät sisältävät yleensä seuraavanlaisia asioita. Otsakkeiden alla on esimerkkejä kyseisestä tehtävätyypistä. Tehtäviin ei tyypillisesti ole yhtä oikeaa ratkaisua, vaan samaa aihetta voi lähestyä hyvin monella eri tavalla. Oleellista ei siis ole kaikkien nippelitietojen ulkoa muistaminen vaan laajempi näkemys aiheeseen siten, että pystyy palauttamaan riittävästi yksityiskohtia mieleensä ja tenttivastaukseen tehtävän edellyttämässä laajuudessa (vrt. esim. tehtävä B, jossa kriteerit voi/pitää keksiä itse: ei ole olemassa neljää tärkeintä kriteeriä kaikkiin mahdollisiin sovelluksiin, vaan tehtävässä kriteerit tulee perustellä erään sovelluksen näkökulmasta, jonka valinta on jätetty tenttijälle).

A) Käsitteiden määritteleminen

Määrittele lyhyesti seuraavat käsitteet

a) Pakka (deque)
b) Prioriteettijono
c) Hajautusfunktio

B) Algoritmien ja tietorakenteiden keskinäinen vertailu

Hakurakenteet

a) Mainitse neljä keskeistä kriteeriä, joita joudut miettimään valitessasi hakurakennetta johonkin sovellukseen. Oletetaan, että rakenteessa tarvitaan vain yhdenlaisia hakuavaimia.

b) Vertaile näiden kriteerien perusteella hakumenetelmänä binäärihakupuuta, AVL-puuta ja kaksoishajautusta.
 

C) Kokonaisnäkemys johonkin kurssin osa-alueeseen.

Järjestäminen

Joudut valitsemaan algoritmin tehtävään, jossa pitää järjestää joukko keskusmuistissa olevia alkioita suuruusjärjestykseen. Mitä asioita otat huomioon tehdessäsi valintaa ja mitä algoritmeja suosittelet eri tilanteisiin? Perustele mielipiteesi lyhyesti ja tiiviisti (pituus korkeintaan 1 sivu).
 

D) Algoritmien ja tietorakenteiden toiminnan kuvaaminen

Selitä sanallisesti algoritmi, jonka avulla voidaan muodostaa verkon minimaalinen virityspuu. Anna esimerkki algoritmin toiminnasta (tehtävässä mahdollisesti annetulla verkolla). Mikä on algoritmin tehokkuus, jos verkossa on V solmua ja E kaarta?
 

E) Algoritmien ja tietorakenteiden soveltaminen / valitseminen annettuun ongelmaan

 
Kirjoita seuraavat algoritmit. Voit esittää ne Pascalilla, C-kielellä, Javalla tai käyttäen  pseudokieltä. Esitä algoritmin perusajatus myös sanallisesti.

a) Algoritmi, joka laskee annetun binääripuun korkeuden. Mikä on algoritmisi tehokkuus O()-notaatiossa, kun puussa on N alkiota?

b) Algoritmi, joka saa argumenttina kaksi binääripuuta ja joka palauttaa tiedon siitä, ovatko puut identtisiä. Mikä on algoritmisi tehokkuus O()-notaatiossa, kun molemmissa puissa on N alkiota?

c) Algoritmi, joka saa argumenttina kaksi alkioiden arvon mukaan nousevassa järjestyksessä olevaa taulukkoa ja joka tulostaa niissä olevat yhteiset alkiot. Mikä on algoritmisi tehokkuus O()-notaatiossa, kun taulukoissa on M ja N alkiota.
 

F) Algoritmianalyysi

a) Määrittele formaalisti käsitteet O(N) ja Omega(N).

b) Ratkaise rekursioyhtälö T(N) = 2 T(N / 2) + N, kun N on kahden potenssi ja T(1) = 0. Esitä riittävästi välivaiheita ja esitä lopputulos O()-notaatiossa.

G) Algoritmien ja tietorakenteiden soveltaminen yksinkertaiseen ongelmaan, kuten perustehtävissä

Keko

a) Rakenna avaimista

P R I O R I T E E T T I J O N O

keko (heap) käyttäen build-heap -menetelmää. Kekoehtona on se, että isä >= lapset. Näytä välivaiheita.

b) Poista sen jälkeen keosta avain ja näytä keon sisältö. Poista vielä toinen avain ja näytä keon sisältö.

c) Esitä lopullinen keko taulukkomuodossa.

Muista ilmoittautua välikokeisiin/tenttiin! Ensimmäinen välikoe on pe 11.3. Ilmoittautuminen tehdään TOPIn kautta. Ilman ilmoittautumista paperi voidaan jättää korjaamatta.

Viimeinen tenttimahdollisuus on alkukevään 2006 1. tentti (arviolta helmi- tai maaliskuussa) joulukuun tenttikaudella.