Algoritmien teoria, kevät 1999
Harjoitus 1, 25.1. klo 10-12 sali MaD302

1. Määritä rekursioyhtälön

   

   tarkka ratkaisu, kun n on neljän potenssi.

2. Eräissä ``hajota ja hallitse''-tyyppisissä algoritmeissa voidaan n:n kokoinen ongelman tapaus osittaa tasaisesti :n kokoisiin osatapauksiin niin, että algoritmin aikavaativuutta T(n) tulee kuvaamaan rekursiokaava:

   

   Määrää -yläraja funktiolle T(n). (Vihje: Tee muuttujanvaihto .)

3. Ratkaise generoivia funktioita käyttäen rekursioyhtälö

   

   (Vihje: Kun olet määrittänyt jonon generoivan funktion, yritä kirjoittaa sen nimittäjänä oleva lauseke muotoon (1-az)(1-bz) ja sovella sitten osamurtolukuhajotelmaa.)

4. Tiedetään (Anal. pk/jk), että nollan ympäristössä suppeneva potenssisarja voidaan derivoida termeittäin, so. jos niin .
   1. Johda tämän tiedon avulla jonon generoiva funktio jonon generoivasta funktiosta.
   2. Oletetaan, että jonon arvot ovat jonkin diskreetin todennäköisyysjakauman pistetodennäköisyyksiä, siis esim. `` = todennäköisyys, että algoritmin suoritus vaatii tasan k askelta''. Mitä on tällöin G(1)? Entä mikä on arvon G'(1) tulkinta?
5. Ohjelma käsittelee kahta pinoa S ja T, joihin voidaan tavallisten pino-operaatioiden (push, pop) lisäksi kohdistaa kopiointi-operaatioita copy(S,T) ja copy(T,S). Suunnittele pinoille taulukkototeutus, jossa kopiointi-operaation yhteydessä ainoastaan edellisen kopioinnin jälkeen tapahtuneet muutokset päivitetään pinosta toiseen. Osoita, että tässä toteutuksessa minkä tahansa aluksi samansisältöisiin pinoihin kohdistuvan n operaation jonon kokonaissuoritusaika on vain O(n).