Algoritmitekniikka, Harjoitus 7, 16.3.2000

1. Seuraava koodi laskee kokonaisluvun 2-kantaisen logaritmin (pyöristettynä alaspäin) eli luvun merkitsevimmän bitin. (Koodi on peräisin artikkelista Thorup, Andersson: A pragmatic implementation of monotone priority queues, DIMACS'96 implementation challenge.)

   typedef struct {
           unsigned int mantissa2 : 32;
           unsigned int mantissa1 : 20;
           unsigned int exponentbias1023 : 11;
           unsigned int signbit : 1;
   } doublemask;
   
   typedef union {
           double as_double;
           doublemask as_mask;
   } doubleandmask;
   
   inline unsigned int log_2(unsigned long n) {
           doubleandmask fm;
           fm.as_double = (double) n;
           return (fm.as_mask.exponentbias1023 - 1023);
   }
   

   (Joissakin arkkitehtuureissa, esim. sparcissa structin kenttien järjestys pitää kääntää päinvastaiseksi.) Varmista, että koodi toimii (myös suurilla luvuilla). Kokeile toimintaa myös 64-bittisessä arkkitehtuurissa (esim. pneuma). Selvitä, miten ja miksi koodi toimii.

2. Suunnittele vaihtoehtoisia toteutuksia 2-kantaiselle kokonaislukulogaritmille ja vertaa niiden tehokkuutta kokeellisesti tehtävän 1 koodiin. Yritä löytää mahdollisimman tehokas toteutus.

3. Kahden merkkijonon X ja Y pisin yhteinen alijono on pisin merkkijono, joka saadaan sekä X:stä että Y:stä poistamalla joitakin merkkejä. Sivulla http://www.cc.gatech.edu/classes/cs3158_98_fall/lcs.html ja kirjassa Cormen, Leiserson, Rivest: Introduction to Algorithms sivulla 317 (laitoksen kurssikirjahyllyssä) on pisimmän yhteisen alijonon laskeva pseudokoodi. Selvitä algoritmin toiminnan idea ja simuloi algoritmia merkkijonoilla X="madagaskar" ja Y="santiago".

4. Toteuta tehtävän 3 algoritmi C-kielellä. Toteuta myös pisimmän alijonon tulostus, mikä on mahdollista b-taulukon avulla. Varmista, että algoritmisi toimii oikein.

5. Tehtävän 3 algoritmia voidaan yksinkertaistaa, jos halutaan laskea vain pisimmän yhteisen alijonon pituus (siis arvo c[m,n]). Mm. b-taulukkoa ei tarvita. Suunnittele keinoja, joilla tätä yksinkertaistettua algoritmia voidaan optimoida.

Tulevissa harjoituksissa jatketaan tehtävien 3, 4 ja 5 teemaa.