Algoritmitekniikka, Harjoitus 8, 23.3.2000

1. Algoritmi laskee c-taulukon rivi kerrallaan ja kunkin rivin laskemiseen tarvitaan vain edellinen rivi. Aiempia rivejä ei siis tarvitse säilyttää muistissa. Alla oleva pseudokoodi toteuttaa algoritmin vain yhtä yksiulotteista taulukkoa käyttäen.

       for j <- 0 to n
           c[j] <- 0
       for i <- 1 to m
           c_im1_jm1 <- 0    /* c_im1_jm1 == c[i-1,j-1] */
           for j <- 1 to n
               c_im1_j <- c[j]
               if (x_i == y_j) {
                  c[j] <- c_im1_jm1 + 1
                  }
               else if (c[j] >= c[j-1]) {
                  c[j] <- c_im1_j
                  }
               else {
                  c[j] <- c[j-1]
                  }
               c_im1_jm1 <- c_im1_j
   

   Pseudokoodi sisältää ainakin yhden turhan sijoituksen. Löydätkö sen? Toteuta algoritmi ja vertaa sitä kokeellisesti kaksiulotteista taulukkoa käyttävään versioon.

2. Tehtävän 1 pseudokoodi tarjoaa monia mahdollisuuksia optimointiin mm. vertailujen järjestystä ja silmukkarakenteita muuttamalla. Seuraavassa pseudokoodissa on käytetty mm. tiiviitä ohitussilmukoita (skip loop) ja sentinel-tekniikkaa.

       for j <- 0 to n
           c[j] <- 0
       c[n+1] <- n+1  /* sentinel */
       for i <- 1 to m
           ch <- x_i
           y_{n+1} <- ch;   /* sentinel */
           j = 1;
           while (j <= n) {
               while (y_j != ch) {
                   j <- j + 1;
                   /* invariant: c[i,j-1] == c[i-1,j-1] */
                   }
               cc = c[j-1] + 1;
               while (c[j] < cc) {
                   c[j] = cc;
                   j++;
                   /* invariant: c[i,j-1] == c[i-1,j-1] + 1 == cc */
                   }
               j++
               }
   

   Vertaa koodia edellisen tehtävän koodiin. Laskevatko ne täsmälleen samat arvot taulukkoon c? Mihin taulukon c ominaisuuksiin tehdyt muutokset perustuvat? Toteuta optimoitu versio ja vertaa sitä kokeellisesti edelliseen versioon.

3. Tehtävän 2 koodin ensimmäisessä tiivissilmukassa ei tehdä mitään muuta kuin kasvatetaan laskuria, kunnes etsitty merkki löytyy merkkijonosta Y. Sopivalla Y:n esikäsittelyllä voidaan yhdestä merkin ch esiintymästä hypätä suoraan seuraavaan. Suunnittele ja toteuta tällainen versio algoritmista ja vertaa sen tehokkuutta tehtävän 2 koodiin.

4. Tehtävän 2 koodin toiselle tiivissilmukalle ei voida tehdä samanlaista optimointia, koska taulukkoa c muutetaan joka kierroksella. Toisenlaisella taulukon koodauksella toisestakin tiivissilmukasta päästään kuitenkin eroon. Määritellään taulukko d seuraavasti:

   Kaikilla 0 <= k <= n: d[k] on pienin j, jolla c[j]==k tai n+1, jos c[j]<k kaikilla j.

   Taulukko d sisältää saman informaation kuin taulukko c: kumpikin voidaan helposti laskea toisen avulla. Taulukko d ei muutu toisenkaan tiivissilmukan aikana. Suunnittele ja toteuta tehtävän 3 algoritmista versio, joka käyttää taulukkoa d taulukon c sijasta, ja vertaa toteutusta aiempiin toteutuksiin.

5. Mikä on tehtävien 3 ja 4 algoritmien asymptoottinen aikavaatimus?