ALGORITMIEN SUUNNITTELU JA ANALYYSI, kevät-2007

Harjoitus 1. (viikolla 3)

1. Mitkä seuraavista väitteistä ovat tosia ja mitkä eivät? Perustele!

a) n⁵ + n⁴ + n log n - n = O(n⁵)

b) log(n⁴) = Q(log n)

c) log(n⁴) = O(n²)

d) (log n)⁴ = O(log n)

e) 1² + 2² + ... + n² = O(n²)

f) n log n = W(n log log n)

2. Mitkä symboleista O, W, Q ja o sopivat ?:n paikalle seuraavissa lausekkeissa? (Esimerkki:

n = ?(n²). Tähän sopivat O ja o, koska n = O(n²) ja n = o(n²), mutta eivät Q eikä W.)

a) √2n = ?(12n)

b) 12n = ?(√2n)

c) log₂ n = ?(log_l0 n)

d) ³√n = ?(√n)

e) n² - 2n = ?(n log n)

f) 3n³ + 42n² - n + 123 = ?(n³)

3. Kirjoita pseudokoodi algoritmille, joka laskee kahden polynomin tulon koulussa opetetulla kertolaskumenetelmällä. Menetelmä siis toimii esimerkiksi näin:

x² + 2x + 3

x² - x + 1

x² + 2x + 3

- x³ - 2x² - 3x

x⁴ + 2x³ + 3x²

x⁴ + x³ + 2x² – x + 3

4. Analysoi edellisen tehtävän algoritmin aikavaatimus n:n funktiona, kun kummankin kerrottavan polynomin aste on (sama) n.

5. Oletetaan, että T(n) = O(f(n)) ja S(n) = O(g(n)). Osoita, että

a) T(n) + S(n) = O(max{f(n), g(n)})

b) T(n) · S(n) = O(f(n) · g(n))

6. Verkon kaaret voidaan tallentaa vieruslistojen sijasta yhteysmatriisina. Tämä on V x V kokoinen taulukko, jossa on jokaiselle solmuparille numero 0 tai 1, joka kertoo, onko solmujen välillä kaarta.

a) Mikä on seuraavan suuntaamattoman verkon yhteysmatriisi: (a, b), (a, e), (b, e), (b, d), (e, d)

b) Kirjoita pseudokoodina algoritmi, joka rakentaa verkon vieruslistaesityksestä yhteysmatriisin. (Keksi oma abstraktio sille, miten algoritmi pääsee käsiksi vieruslistaan.) Mikä on algoritmisi aikavaatimus, kun verkossa on V solmua ja E kaarta?