Tietorakenteet ja algoritmit, syksy 2014, 1. välikoe

Tehtävä 1 (5p)

Ilmoita seuraavien algoritmien aikavaativuudet O-merkinnällä. Perustele jokainen aikavaativuus lyhyesti.

1. for i = 1 to n/2
       ...
   for i = 1 to n/3
       ...
   for i = 1 to n/4
       ...
   

2. for i = 1 to n
       for j = 1 to n/100
           ...
   

3. for i = 1 to 1000
       for j = 1 to i
           for k = 1 to log(n)
               ...
   

4. for i = 1 to n2
       for j = 1 to n3
           ...
   for i = 1 to n4
       ...
   

5. function f(n)
       if n < 1 then
           return
       f(n/10)
   

Ratkaisu

1. O(n), koska silmukat ovat peräkkäin ja jokaisen aikavaativuus on O(n)
2. O(n²), koska silmukat ovat sisäkkäin ja kummankin aikavaativuus on O(n)
3. O(log n), koska vain uloin silmukka riippuu n:stä
4. O(n⁵), koska alkuosan silmukat ovat O(n²) ja O(n³)
5. O(log n), koska kutsuja tulee noin log₁₀ n

Tehtävä 2 (5p)

Ilmoita jokaisesta seuraavasta väitteestä, onko se tosi vai epätosi. Joka kohdasta saat 1p, jos vastaus on oikein, ja -1p, jos vastaus on väärin. Jos et ilmoita mitään, saat 0p kohdasta.

1. Jos binääripuun korkeus on n, siinä on vähintään n² solmua.
2. O(2ⁿ)-aikainen algoritmi on aina rekursiivinen.
3. Järjestetyn taulukon lukujen keskiarvo voidaan laskea ajassa O(log n).
4. AVL-puuhun lisäämisen aikavaativuus on O(1).
5. Jono ja pino toteutetaan aina linkitetyn listan avulla.

Ratkaisu

1. epätosi
2. epätosi
3. epätosi
4. epätosi
5. epätosi

Tehtävä 3 (5p)

Sinulle on annettu binääripuu, jossa on n alkiota. Tehtäväsi on laskea suurin summa polulla puun juuresta johonkin sen lehteen. Esitä tehtävään algoritmi (mikä tahansa toimiva algoritmi) ja analysoi sen aikavaativuus. Anna lyhyt sanallinen kuvaus algoritmin toiminnasta sekä algoritmin koodi pseudokoodina, Javalla tai jollain muulla yleisellä kielellä.

Esimerkiksi binääripuussa

    5
   / \
  9   1
     / \
    2   1

suurin summa on 14 polulla 5 -> 9.

Vastaavasti binääripuussa

    5
   / \
  2   1
     / \
    2   1

suurin summa on 8 polulla 5 -> 1 -> 2.

Ratkaisu

Seuraavan koodin aikavaativuus on O(n):

int suurinSumma(Puu p) {
    if (p == null) return 0;
    int vasen = suurinSumma(p.vasen);
    int oikea = suurinSumma(p.oikea);
    return Math.max(vasen, oikea) + p.arvo;
}

Tehtävä 4 (5p)

Sinulle on annettu merkkijonot X ja Y. Molemmat merkkijonot muodostuvat merkeistä a..z ja niissä on kummassakin n merkkiä.

Tehtäväsi on muuttaa merkkijono X merkkijonoksi Y. Saat siirtää joka siirrolla minkä tahansa merkin merkkijonon alkuun. Onko tehtäväsi mahdollinen ja montako siirtoa tarvitset vähintään?

Esitä tehtävään algoritmi, jonka aikavaativuus O(n²) tai parempi. Algoritmille annetaan merkkijonot X ja Y, ja sen täytyy palauttaa pienin määrä siirtoja, tai -1, jos muunnos ei ole mahdollinen.

Anna lyhyt sanallinen kuvaus algoritmin toiminnasta sekä algoritmin koodi pseudokoodina, Javalla tai jollain muulla yleisellä kielellä. Analysoi myös algoritmin aikavaativuus.

Esimerkki 1: jos X = baaca ja Y = aabca, tarvitset vähintään 2 siirtoa: baaca -> abaca -> aabca.

Esimerkki 2: jos X = abcde ja Y = edcba, tarvitset vähintään 4 siirtoa: abcde -> bacde -> cbade -> dcbae -> edcba.

Esimerkki 3: jos X = abcde ja Y = ababa, tehtävä ei ole mahdollinen.

Ratkaisu

Ensinnäkin tehtävä on mahdollinen tarkalleen silloin, kun X:ssä ja Y:ssä on kutakin merkkiä yhtä monta (eli X ja Y ovat anagrammeja).

Tämän jälkeen olennainen havainto on, että Y:n loppuosa, joka on X:ssä oikeassa järjestyksessä (välissä saattaa olla muita merkkejä), voi säilyä ennallaan, kun taas kaikkia muita X:n merkkejä täytyy siirtää.

Seuraavan ratkaisun aikavaativuus on O(n):

int siirtomaara(String x, String y) {
    int n = x.length();
    // 1. ovatko x ja y anagrammeja?
    int c[] = new int[256];
    for (int i = 0; i < n; i++) c[x.charAt(i)]++;
    for (int i = 0; i < n; i++) c[y.charAt(i)]--;
    for (int i = 'a'; i <= 'z'; i++) {
        if (c[i] != 0) return -1;
    }
    // 2. montako merkkiä oikeassa järjestyksessä?
    int j = n-1;
    for (int i = n-1; i >= 0; i--) {
        if (x.charAt(i) == y.charAt(j)) j--;
    }
    return j+1;
}