1 Selvitä, mitä tarkoitetaan branch-and-bound-menetelmällä ja kirjoita jokin menetelmää käyttävä algoritmi.
2. Järjestetystä lukujonosta voidaan etsiä lukua binäärihaulla. Algoritmissa verrataan aina jonon noin keskimmäistä lukua etsittävään. Jos lukua ei löytynyt, jatketaan hakua joko verratun alkion vasemmalla tai oikealla puolella olevasta jonosta. Näin jatketaan, kunnes luku löytyi tai kunnes jäljellä oleva lukujono on tyhjä.
Analysoi seuraavien algoritmin muunnelmien pahimman tapauksen aikavaatimus:
(a) Tavanomainen binäärihaku lopetetaan jo, kun jäljellä olevassa jonossa on vähemmän kuin 6 lukua. Jäljellä olevaan osaan sovelletaan peräkkäishakua.
(b) Kohdan (a) muunnoksen lisäksi binäärihakualgoritmin noin keskimmäisen luvun sijaan valitaan aina jonon kuudes luku.
(b) Kohdan (a) muunnoksen lisäksi binäärihakualgoritmin noin keskimmäisen luvun sijaan valitaan aina sellainen, että valitun vasemmalle puolelle jää noin 1/5 jonon luvuista.
3. Union-Find -rakenteessa Find-operaatioiden yhteydessä rakennetta ei muuteta. Analysoi Find-operaation pahimman tapauksen aikavaatimus, kun Union-operaatiossa liitetään aina korkeampi puu matalamman juuren alipuuksi (tämä tapa on epätavanomainen) .
4. Binaariluku on talletettu taulukkoon, yksi bitti kuhunkin taulukon alkioon. Lukuun kohdistetaan jono operaatioita. joista kukin kasvattaa lukua yhdellä. Suunnittele algoritmi, joka toteuttaa operaation ja vaatii pahimmassa tapauksessa ajan O(k) (k on luvun ykkösbittien määrä). Jos n operaatiota kohdistetaan alussa nollan sisältävään taulukkoon, tulee operaatiojonon aikavaativuuden olla Of). Perustele tasoitetulla vaatimusanalyysillä, että algoritmisi täyttää jälkimmäisen ehdon.
5. Metrisen kauppamatkustajaongelman likimääräisratkaisun etsimiseen täydellisessä verkossa käytetään seuraavaa approksimointialgoritmia:
1. Etsi verkon minimaalinen virittävä puu.
2. Käy puun solmut syvyyssuuntaisesti läpi; tulosta solmut esijärjestyk
sessä.
3. Tulostettu solmujono täydennettynä siten, että viimeisen solmun jäl
keen palataan ensimmäiseen, on kauppamatkustajan reitti.
Analysoi saadun likimääräisratkaisun tarkkuus.
Kunkin tehtävän oikeasta ratkaisusta saa 6 pistettä.