Analiza algorytmów 2010/11

Egzamin ustny, z przygotowaniem odpowiedzi na kartce - pytania egzaminacyjne

Wymagany jest stopień szczegółowości opisu algorytmu pozwalajacy bez wątpliwości zanalizować jego złożoność. Analiza poszczególnych algorytmów i dowody twierdzeń obowiązują w zakresie jak na wykładzie.

1. Twierdzenie o rekurencji uniwersalnej, dowód dla wersji n=b^k
2. Analiza problemu sekretarki: wersja postawowa (zmienne losowe wskaźnikowe) oraz wersja on-line
3. Generowanie permutacji losowej metodą Knutha
4. Analiza problemu sekretarki za pomocą funkcji tworzących prawdopodobieństwa (wartośc średnia oraz wariancja)
5. Dolne oszacowanie na złożoność sortowania w modelu drzew decyzyjnych, pesymistyczne i średnie
6. Quicksort: rozkład prawdopodobieństwa w podzadaniach i analiza złożoności średniej (równanie rekurencyjne na wartość oczekiwaną liczby porównań)
7. Sortowanie turniejowe, liczba porownań a dolne oszacowanie na złożoność sortowania
8. Znajdowanie k-tego elementu (lub k największych): algorytm Hadiana-Sobela, metoda Hoare'a i jej złożoność średnia, metoda mediany median
9. Wyszukiwanie interpolacyjne w tablicy posortowanej, złożoność średnia wyszukiwania kwadratowego
10. Model permutacyjny dla drzew BST: średnia złożoność operacji, oczekiwana wysokość drzewa
11. Drzewa splay: analiza złożoności
12. Drzewa treaps: algorytmy, analiza operacji usuwania - oczekiwana głębokość węzła i liczba rotacji
13. Problem Find-Union, rozwiązanie drzewowe z kompresją ścieżek
14. Haszowanie: analiza haszowania otwartego (wtórna funkcja haszująca)
15. Haszowanie: uniwersalna rodzina funkcji haszujących - wersja stosowana do haszowania doskonałego
16. Haszowanie doskonałe
17. Kopiec Fibonacciego: algorytmy, analiza złożoności amortyzowanej
18. Kopiec Fibonacciego: twierdzenie o stopniu wierzchołka.