Rästitehtävät

Sovellustehtävien rästit

Sovellustehtävien osalta rästitehtäviä voivat tehdä

• ne, jotka eivät saaneet sovellustehtävistä vaadittuja 37 pistettä.
• ne, jotka haluavat korottaa arvosanaansa
• ne, jotka haluavat suorittaa kurssin kokonaan kesällä

Jokaisen, joka tekee rästitehtäviä, on saatava vähintään 5 pistettä niistä.  Tätä pienempiä muutoksia ei kirjata.

Jos em. minimivaatimus täyttyy, rästitehtävien ja alkuperäisten sovellustehtävien pisteet lasketaan yhteen ja yhteispisteiden kanssa noudatetaan seuraavia arvosanarajoja.  (tässä yhteydessä otamme käyttöön myös arvosanat 1 ja 2)

        32 - 34 : 1
        35 - 36 : 2
        37 - 51 : 3
        52 - 66 : 4
        67 -    : 5

Tehtävien palautuksen deadline on 30.9 klo 16.  Tehtävät palautetaan paperilla kyyhkyslakkojen alla olevaan lokeroon 42.  Paperin päällä tulee olla nimi, opintokirjan numero ja merkintä "Tietorakenteet ja algoritmit, rästitehtävät".  Sähköisessä muodossa ratkaisuja ei oteta vastaan.
 

Tehtävät

1)  Laske seuraavan lausekkeen arvo muuntamalla se ensin infix-muodosta postfix-muotoon ja laskemalla sitten postfix-lausekkeen arvo.  Käytä hyväksi pinorakennetta samalla tavalla kuin oppikirjassa on esitetty luvussa 3.3.3. (2p)
 
     1 + 5 * ((2 * 3 + 4) * 2 + 3 * (4 + 5 * 6))
 
Esitä pinon sisältö jokaisen symbolin lukemisen jälkeen algoritmin molemmissa vaiheissa.
 
 
2)  Edellisen tehtävän algoritmi toimii myös vähennys- ja jakolaskujen yhteydessä, kun näille operaattoreille asetetaan sopivat prioriteetit. Se ei toimi potenssiinkorotuksen kanssa, koska potenssiinkorotus assosioi oikealta vasemmalle, t.s 2^3^4  = 2^(3^4) eikä (2^3)^4. Miten algoritmeja tulee muuntaa, jotta myös potenssiinkorotus on mahdollista? (2p)
 
 
3)  Esitä algoritmi, joka laskee annetun mielivaltaisen binääripuun solmujen määrän. (2p)
 
 
4)  Esitä algoritmi, joka laskee annetun mielivaltaisen binääripuun korkeuden.  Mikä on algoritmisi tehokkuus O-notaatiossa? (2p)
 

5)  Hajautuksen perusmenetelmät eivät säilytä avainten järjestystä, jolloin haluttaessa luetella tietyllä avainvälillä olevat avaimet joudutaan käymään läpi kaikki rakenteessa olevat avaimet.  Mieti, miten toteuttaisit hajautusalgoritmin ja -tietorakenteen, jos tämä toimenpide pitäisi pystyä tekemään selvästi nopeammin (ei kuitenkaan välttämättä ajassa O(M), jossa M on haettavien avainten määrä). (2p)
 
 
6a) Montako bittiä / solmu tarvitaan tallettamaan N-alkioiseen AVL-puuhun kunkin solmun korkeus? (1p + 1p)

 b) Oletetaan, että solmun korkeutta varten on varattu 8 bittiä.  Mikä on pienin  AVL-puu, jossa korkeutta ei voida tallettaa ko. tilaan?  Anna karkea arvio tällaisen puun solmujen lukumäärästä?

Lisäksi oppikirjasta (2. painos) seuraavat tehtävät

2.5   (2p)
2.11  (3p)
4.5   (2p)
4.31  (4p)
4.41  (3p)
4.45  (4p)
5.9   (5p)   (huomaa, että tehtävä on jatkoa tehtävälle 5.8)
6.1   (2p)
Tehtävässä tulee toteuttaa rakenne, jossa operaatiot
• findMin,
• DeleteMin ja
• Insert.

6.9a  (2p)
6.35  (2p)
7.9   (3p)
7.29  (3p)   (taulukkojen yhdistäminen, kirjan 1. painoksessa tehtävä 7.28)
Tehtävässä "non-trivial lower bound" tarkoittaa pahimman tapauksen alarajaa.
9.2   (2p)
9.4   (3p)
Perusratkaisussa (standard double loop) kaikki verkon särmät luetaan yksitellen ja talletetaan tieto vierusmatriisiin.

Myös seuraavia bonustehtäviä voi tehdä.

       2.7ab (4p)
       4.7   (4p)
       4.17  (4p)
       4.43  (6p)
       4.46  (4p)