Algoritmien teoria, kevät 1999
Harjoitus 4, 15.2. klo 10-12 sali MaD380

1. Millainen puurakenne syntyy, kun luennolla (ss. 172-173) esitettyä tasapainottavaa ja tiivistävää union-find-algoritmia sovelletaan seuraavan ohjelman tuottamaan union-find-operaatiojonoon? Aluksi on .

   
   
   				 i = 1  15  2  union(i,i+1,i);
   
   				 i = 1  13  4  union(i,i+2,i);
   
   				union(1,5,1);
   
   				union(9,13,9);
   
   				union(1,9,1);
   
   				 i = 1  13  4  find(i)
   
   		.
   
   

2. Osoita, että jos union-find-algoritmissa käytetään puiden tasapainotusta, mutta ei polun tiivistystä, n:n union-find-operaation jonon suorittaminen voi vaatia ajan . (Vihje: Tarkastele jonoja, joista syntyy edellisen tehtävän tapaan binomipuita.)
3. Tarkastellaan muotoa

   

   olevien yhtälöryhmien ratkaisemista, missä kukin ja on muuttuja tai kokonaisluku. Esimerkiksi ryhmällä

   

   on ratkaisu X=Y=3, mutta laajennetulla ryhmällä

   

   ei ole ratkaisua. Selitä, miten union-find-algoritmilla voidaan tehokkaasti päättää, onko annetulla yhtälöryhmällä ratkaisua vai ei.

4. Todista seuraava väite (luentojen s. 180, Lause 2): Jos (v,w) on syvyyshaun määrittämä suunnatun verkon sivuttaiskaari, niin postnum[v] > postnum[w].
5. Määritä alla olevan verkon vahvasti yhtenäiset komponentit luentojen s. 181 algoritmilla. Oletetaan, että solmut ovat vieruslistoissa aakkosjärjestyksessä ja että algoritmi aloittaa verkon tutkimisen solmusta a.

   

6. Sanotaan, että suunnatun verkon G = (V,E) solmu u on alkusolmu, jos verkon kaikki muut solmut voidaan saavuttaa u:sta, so. jos kuhunkin muuhun solmuun johtaa u:sta suunnattu polku. Suunnittele tehokas algoritmi, joka etsii vieruslistoina esitetyn suunnatun verkon jonkin alkusolmun, mikäli verkossa sellaisia on. Miten muuttaisit algoritmia, jos tehtävänä olisi määrittää verkon kaikki alkusolmut?