Tenttitehtävät 15.5.1995

1. Selvitä, mitä tarkoitetaan ahneella (greedy) algoritmilla.

2. Selvitä vasemmalle kallistuvan puun (leftist tree) rakenne ja yhdistämisoperaation, minimialkion etsintäoperaation ja minimialkion poisto-operaation toteutus vasemmalle kallistuvassa puussa.

3. Olkoon u ja v annetun suunnatun verkon kaksi solmua. Kirjoita algoritmi, joka selvittää, onko verkossa u:sta v:hen johtava Hamiltonin polku, eli polku, joka alkaa u:sta, päättyy v:hen, ja käy täsmälleen kerran kaikissa verkon solmuissa.

4. Pinoon kohdistetaan jono tavanomaisia alkion liittämisoperaatioita (push(x)) ja erikoisia poisto-operaatioita multipop(k), jotka poistavat pinon huipulta k alkiota (jos pinossa on vähemmän kuin k alkiota, operaatio tyhjentää pinon). Analysoi operaatioiden tasoitettu aikavaatimus (amortized complexity).

5. On annettu positiivisia kokonaislukuja sisältävä kolmiomatriisi (rivillä 1 on 1 luku, rivillä 2 on 2 lukua, . . . , ja viimeisellä rivillä k on k lukua). Tarkastellaan k:n luvun jonoja, jotka on muodostettu matriisin luvuista valitsemalla yksi luku kultakin riviltä seuraavilla säännöillä: Jonon ensimmäinen luku on rivin 1 ainut luku. Jos riviltä i (1 < i < k - 1) on valittu sarakkeessa j oleva luku, riviltä i + 1 saa valita joko sarakkeessa j tai sarakkeessa j + 1 olevan luvun. Tehtävänä on etsiä näin valittujen lukujonojen lukujen summista pienin. Tee algoritmi, joka ratkaisee tehtävän. Algoritmi saa vaatia pahimmassakin tapauksessa vain ajan O(k 2). Vihje: Käytä dynaamisia ohjelmointia.