ALGORITMIEN SUUNNITTELU JA ANALYYSI

Kevät-2007

Harjoitus 4.

1. Mitkä ovat seuraavien algoritmien suuruusluokat, kun T(n) on algoritmin aikavaatimus?

a) T(n) = 3 T(n / 3) + n log₃ n

b) T(n) = 3 T(n / 4) + n lg n

Kummassakin tapauksessa T(1) = 1. Mieti tarkoin, miten voit edetä.

2. Tee opetusmonisteen sivulla 42 harjoitustehtäväksi jätetty todistus ("Tapaus 3", opetusmonisteen kohdan "Mukautuvat puut" lopussa.

3. Kirjoita algoritmi (pseudokoodi), joka laskee pelkkien yhteenlaskujen avulla kertolaskun n*x, kun n on positiivinen kokonaisluku. Algoritmi saa tehdä O(log n) yhteenlaskua. Vihje: Käytä hajoita ja hallitse –menetelmää. 4*a = (a+a)+(a+a).

4. Tasapainoisessa binäärisessä hakupuussa minkä tahansa solmun alipuiden korkeusero on enintään yksi. Tällaisen voi tehdä n alkion järjestetystä taulukosta esimerkiksi lisäämällä alkiot aluksi tyhjään AVL-puuhun yksi kerrallaan – mutta tämä vie ajan O(n log n), koska AVL-puun lisäys on O(log n).

Kirjoita algoritmi, joka tekee n:n alkion järjestetystä taulukosta tasapainoisen binäärisen hakupuun ajassa O(n). Vihje: Käytä hajoita ja hallitse –menetelmää.

5. Osoita, että Strassenin algoritmissa osamatriisin C₂₂ alkiot muodostuvat oikein.

6. Kokonaisluvut 1,2,...,25 on talletettu taulukkoon seuraavassa järjestyksessä:

1, 25, 2, 24, 3, 23,...,11, 15, 12, 14, 13.

Modifioidaan opetusmonisteen sivun 52 mediaanin etsimisalgoritmia siten, että alussa oleva ehto |F| < 20 muuttuu ehdoksi |F| < 5. Selvitä askeleittain, miten yllä olevan lukujonon mediaani löytyy modifioidulla algoritmilla.