1. Przedstawić algorytmy wyszukiwania zadanej wartości liczbowej w tablicy lub zbiorze. Przykłady działania. Przedyskutować problem złożoności obliczeniowej tych algorytmów.

2. Omówić kopiec dwumianowy i podać stosowne przykłady, podać strukturę węzła. Omówić algorytm usuwania węzła z minimalnym kluczem; zilustrować go na przykładzie kopca z czterema węzły na liście korzeni, gdy klucz minimalny znajduje się w węźle o stopniu 4.

3. Omówić pojęcie kosztu zamortyzowanego. Scharakteryzować metody wyznaczania i jedną z nich dokładnie omówić (przykład).

4. Podać przykłady poznanych typów grafów oraz metody ich implementacji. Omówić problemy grafów z wagami i ich zastosowanie. Wyjaśnić pojęcie minimalne drzewo rozpinające dla grafu spójnego i podać algorytm rozwiązujący ten problem (zilustrować przykładem i przedyskutować złożoność obliczeniową).

5. Omówić B-drzewa i metodykę korzystania z nich, podać strukturę węzła, przykłady. Przedstawić algorytm usuwania kluczy (wszystkie przypadki) i zilustrować je przykładami

6. Podać algorytmy wyszukiwania informacji w pamięciowych (PAO) strukturach danych. Ich działanie zilustrować na przykładach. Przedyskutować problem złożoności obliczeniowej.

7. Wyjaśnić pojęcie entropia źródła informacji i jej znaczenie w kompresji danych. Wyjaśnić pojęcie kod prefiksowy i jego przydatność w kompresji danych, przykład. Omówić algorytm kompresji metodą Huffmana i zilustrować jego działanie, pokazując jak powstaje pełne drzewo kodowe dla przykładowych danych (7 lub więcej pozycji).

8. Omówić algorytmy sortowania klasy O(nlg(n)) i zilustrować je przykładami.

   1. Dla QuickSort przedstawić algorytmy (kod lub pseudokod) realizujące funkcje podziału i zilustrować ich działanie na przykładzie zbioru danych (min. 8 elementów). Przeanalizować dokładnie złożoność obliczeniową algorytmu QuickSort

9. Omówić poznane struktury danych realizujące wydajne przetwarzanie informacji trzymanej w pamięciach dyskowych. Zilustrować struktury przykładami, podać budowę węzła.

   1. Omówić algorytmy usuwania kluczy z wybranej struktury i zilustrować je przykładami. Przedyskutować problem złożoności obliczeniowej.

10. Omówienie złożoności obliczeniowej algorytmów, łącznie z Notacjami. Omówić zastosowanie równań rekurencyjnych w analizie złożoności. Zamieścić stosowne przykłady.

11. Przedstawić algorytmy sortowania klasy O(n). Jeden z nich dokładnie omówić – przykład. Przeanalizować złożoność obliczeniową tych algorytmów.

12. Omówić wyszukiwanie wzorca metodą Knutha-Morrisa-Pratta. Podać stosowne algorytmy i przykłady obliczeniowe. Przedyskutować złożoność obliczeniową.

13. Omówić pojęcie grafu, podać przykłady grafów oraz metody ich implementacji. Omówić dokładnie algorytm przeszukiwania wszerz BFS, podać pełny przykład. Wyjaśnić praktyczny aspekt tej metody przeglądania. Przeanalizować złożoność obliczeniową.

14. Przeanalizować poznane konstrukcje abstrakcyjnego typu danych: drzewo. Przedstawić i omówić algorytmy usuwania z nich elementów, przykłady.

15. Podać formalną definicję notacji O. Wyjaśnić różnicę w interpretacji O i Ω. Podać przyczyny powstawania tych notacji. Omówić miary złożoności wykorzystujące informacje o rozkładach prawdopodobieństwa.

16. Podać strukturę węzła B-drzewa. Narysować optymalne B-drzewo rzędu 5 zawierające wartości 12 kluczy. Pokazać jak przebiega usunięcie jednego klucza z korzenia tego drzewa i podać koszt tej operacji.

17. Narysować nietrywialny kopiec Fibonacciego mający 31 węzłów. Narysować nietrywialny kopiec dwumianowy mający 31 węzłów. Omówić mechanizm zmiany wartości klucza położonego na najdalszym poziomie w narysowanym kopcu dwumianowym. Podać koszt tej operacji.

18. Kiedy rotacje ROTPrawa() i ROTLewa() mogą być wykonane? Kiedy to ma sens praktyczny? Podać pełny koszt wykonania rotacji ROTPrawa(). Omówić różnice i podobieństwa między drzewami typu Splay a drzewami AVL. Omówić mechanizmy stosowane w obsłudze tych drzew i zilustrować ich działanie przykładami.

19. Problem minimalnego drzewa rozpinającego dla ważonego grafu niekierowanego, można rozwiązać dwoma wersjami algorytmu Kruskala. Wyjaśnić dlaczego dostępne są dwie wersje. Zilustrować działanie algorytmu na przykładzie nietrywialnego grafu spójnego.

20. Omówić struktury danych występujące w problemie 8 hetmanów. Podać algorytm rozwiązujący problem 8 hetmanów, który wykorzystuje te struktury. Przedstawić wartości tych struktur dla przykładowego ustawienia Hetmana. Przedyskutować złożoność obliczeniową algorytmu.

21. Udowodnić, że algorytm sortowania przez proste wstawianie może być klasy O(n). Udowodnić, że algorytm sortowania przez zliczanie może nie być klasy O(n). Jak wykorzystać algorytm sortowania przez kopcowanie(kopiowanie) do znalezienia 4-tej największej wartości w zbiorze losowym. Wymienić metody poprawienia złożoności obliczeniowej algorytmu sortowania bąbelkowego. Jaka będzie ostateczna złożoność obliczeniowa po zastosowaniu wszelkich ulepszeń?

22. Przedstawić równania rekurencyjne stosowane w analizie złożoności. Podać przebieg rozwiązania tych równań. Podać przykłady algorytmów, których czasy działania spełniają te równania. Podać metodykę rozwiązania tych równań.

23. Wyjaśnić pojęcia: cykl Eulera, cykl Hamiltona w grafach i podać stosowne przykłady. Omówić algorytm przeszukiwania grafu wszerz BFS i zilustrować go na przykładzie grafu spójnego o parametrach 8 węzłów i 12 krawędzi. Wyjaśnić praktyczny aspekt metody BFS. Przeanalizować złożoność obliczeniową.

24. Omówić wszystkie poznane algorytmy sortowania klasy O(n). Dowieść, że rzeczywiście posiadają złożoność O(n).

25. Omówić algorytm (2 etapy) wyszukiwania wzorca metodą Knutha-Morrisa-Pratta i zilustrować jego działanie przykładem. Przedyskutować złożoność obliczeniową.

26. Omówić B-drzewa. Przedstawić poznane algorytmy z nimi związane i zilustrować je przykładami.

27. Omówić dokładnie algorytm przeszukiwania wszerz BFS i zilustrować jego działanie na bazie spójnego grafu nieskierowanego o parametrach 9 węzłów i 14 krawędzi. Wyjaśnić praktyczny aspekt tej metody przeglądania. Przedstawić koncepcję algorytmu Kruskala.

28. Omówić wyszukiwanie wzorca metodą Knutha-Morrisa-Pratta. Podać pełny algorytm (tok postępowania). Zilustrować algorytm dla danych zamieszczonych niżej, pokazując dokładnie jak przebiega wyznaczenie 4-ch kolejnych przesunięć. Przedyskutować złożoność obliczeniową. Tekst: tokomarekniekomarekonjest… Wzorzec: tokomarekniekomareczek. Przedyskutować złożoność obliczeniową.

29. Przedstawić i omówić mechanizmy rotacji na drzewach (lewy, prawy, dwustronny). Omówić drzewa AVL i przedstawić algorytmy na nich realizowane; podać przykład(y) na drzewach posiadających co najmniej 14 węzłów. Przedstawić problematykę złożoności obliczeniowej operacji na drzewach AVL.

30. Przedstawić algorytmy wyszukiwania zadanej wartości liczbowej w tablicy lub zbiorze. Przykłady działania. Przedyskutować problem złożoności obliczeniowej tych algorytmów.

31. Omówić algorytm sortowania QuickSort (2 opcje) i zilustrować go przykładem. Przedstawić algorytmy realizujące funkcję podziału i zilustrować przykładami. Przeanalizować złożoność obliczeniową algorytmu QuickSort.

32. Omówić trzy abstrakcyjne typy danych: Stos, kolejka, lista. Podać algorytmy w języku C lub pseudokodzie realizujące standardowe funkcje Stosu i kolejki. Podać i omówić algorytmy usuwania ze środka i wstawiania w środek listy węzła. Przedyskutować złożoność obliczeniową algorytmów korzystających z wyżej wymienionych struktur. Przedstawić algorytm prezentujący zastosowanie stosu.

33. Omówić tematykę, której przedstawicielem jest problem Hetmanów. Przedstawić algorytm Hetmana, omówić struktury danych, z których korzysta. Podać zawartość w/wym struktur danych dla przykładowych ustawień Hetmana. Przedyskutować złożoność obliczeniową.

34. Omówić potencjalne problemy w grafach z wagami ujemnymi, przykłady. Przedstawić algorytm przeszukiwania grafu w głąb DFS i zilustrować go na przykładzie grafu spójnego (9węzłow i 14 krawędzi). Wyjaśnić pojęcie etykiety czasowe w grafie. Przeanalizować złożoność obliczeniową.

35. Omówić kopiec Fibonacciego, podać stosowne przykłady, podać strukturę węzła. Omówić algorytm zmniejszania wartości klucza (wszystkie aspekty). Zilustrować go na przykładzie kopca z czterema węzłami na liście korzeni, gdy klucz zmniejszany znajduje się w węźle o stopniu 4. Przedyskutować problematykę złożoności obliczeniowej kopca Fibonacciego.

36. Omówić pojęcie złożoność obliczeniowa algorytmów, uwzględnić notacje, równania rekurencyjne. Przedstawić metodykę rozwiązywania na przykładzie wybranego równania rekurencyjnego.

37. Krótko scharakteryzować poznane algorytmy sortowania klasy O(n). Przedstawić algorytm sortowania przez zliczanie i zilustrować jego działanie dla danych: X e N; X e (1,15); x = {7, 4, 13, 5, 7, 1, 9, 7}. Podać koszt posortowania tablicy zamieszczonej wyżej. Czy rzeczywiście jest to algorytm klasy O(n), a może nie jest? – uzasadnić.

38. Podać przykłady poznanych typów grafów, nazywając je oraz pokazać metody ich implementacji. Omówić dokładnie algorytm przeszukiwania wszerz BFS i zilustrować jego działanie na bazie spójnego grafu nieskierowanego o parametrach 9 węzłów i 14 krawędzi. Wyjaśnić praktyczny aspekt tej metody przeglądania. Przeanalizować złożoność obliczeniową

39. Napływają dane pomiarowe: 190, 20, 30, 40, 80, 120, 150, 170, 200, 70, które na bieżąco umieszczane są na drzewie BST; pokazać jak będzie wyglądać takie drzewo. Omówić drzewa samo korygujące się – drzewa Splay, podać przykłady tych drzew. Omówić wybraną strategię dla drzew samo korygujących się i z ilustrować je przykładami.

40. Przedstawić i omówić algorytm przeszukiwania grafu w głąb DFS (dwie części). Zilustrować jego działanie na przykładzie grafu spójnego: 9 węzłów i 14 krawędzi. Wyjaśnić pojęcie etykieta czasowa w grafie.

41. Kolejka: podać algorytmy w C lub pseudokodzie realizujące standardowe funkcje. Lista: podać i omówić algorytmy usuwania i wstawiania węzła ze środka listy. Stos: przedstawić algorytm prezentujący zastosowanie stosu i pokazać na przykładzie działanie tego algorytmu. Przedyskutować złożoność obliczeniową algorytmów korzystających z w/wym struktur.