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
7. Quicksort: analiza złożoności średniej
8. Sortowanie turniejowe, liczba porownań a dolne oszacowanie na złożoność sortowania
9. Algorytm Forda-Johnsona i problem minimalnej liczby porównań
10. Znajdowanie k-tego elementu (lub k największych): algorytm Hadiana-Sobela, metoda Hoare'a i jej złożoność średnia
11. Wyszukiwanie interpolacyjne w tablicy posortowanej, złożoność średnia wyszukiwania kwadratowego
12. Model permutacyjny dla drzew BST: średnia złożoność operacji, oczekiwana wysokość drzewa
13. Drzewa splay: analiza złożoności
14. Problem statycznego słownika, rozwiązanie za pomocą drzew splay i jego efektywność
15. Drzewa treaps, algorytmy, analiza operacji usuwania
16. Problem Find-Union, rozwiązanie drzewowe z kompresją ścieżek
17. Haszowanie: analiza haszowania otwartego (wtórna funkcja haszująca)
18. Haszowanie: uniwersalna rodzina funkcji haszujących (2 przykłady)
19. Haszowanie doskonałe (CLRS, rozdz. 11.5)