Skorowidz strony 287-291.

1. Podstawowe zasady analizy algorytmów. 1.1. Złożoność obliczeniowa. 1.2. Równania rekurencyjne. 1.3. Funkcje tworzące. 1.4. Poprawność semantyczna. 1.5. Podstawowe struktury danych. 1.5.1. Lista. 1.5.2. Zbiór. 1.5.3. Graf. 1.5.4. Notacja funkcyjna dla atrybutów obiektów. 1.5.5. Drzewo. 1.6. Eliminacja rekursji. 1.7. Koszt zamortyzowany operacji w strukturze danych. 1.8. Metody układania algorytmów. 1.8.1. Metoda „dziel i zwyciężaj”. 1.8.2. Programowanie dynamiczne. 1.8.3. Metoda zachłanna. 1.8.4. Inne metody. Zadania. 2. Sortowanie. 2.1. Selectionsort – sortowanie przez selekcję. 2.2. Insertionsort – sortowanie przez wstawianie. 2.3. Quicksort – sortowanie szybkie. 2.4. Dolne ograniczenie na złożoność problemu sortowania. 2.5. Sortowanie pozycyjne. 2.6. Kolejki priorytetowe i algorytm heapsort. 2.7.. Drzewa turniejowe i zadania selekcji. 2.8. Szybkie algorytmy wyznaczania k-tego największego elementu w ciągu. 2.9. Scalanie ciągów uporządkowanych. 2.10. Sortowanie zewnętrzne. 2.10.1. Scalanie wielofazowe z 4 plikami. 2.10.2. Scalanie wielofazowe z 3 plikami. Zadania. 3. Słowniki. 3.1. Implementacja listowa nieuporządkowana. 3.2. Implementacja listowa uporządkowana. 3.3. Drzewa poszukiwań binarnych. 3.3.1. Drzewa AVL. 3.3.2. Samoorganizujące się drzewa BST. 3.4. Mieszanie. 3.4.1. Wybór funkcji mieszającej. 3.4.2. Struktury danych stosowane do rozwiązywania problemu kolizji. 3.5. Wyszukiwanie pozycyjne. 3.5.1. Drzewa RST. 3.5.2. Drzewa TRIE. 3.5.3. Drzewa PATRICIA. 3.6. Wyszukiwanie zewnętrzne. 3.6.1. Pliki nieuporządkowane. 3.6.2. Pliki z funkcją mieszającą. 3.6.3. Sekwencyjne pliki indeksowane. 3.6.4. B-drzewo jako wielopoziomowy indeks rzadki. 3.6.5. B-drzewo jako wielopoziomowy indeks gęsty. Zadania. 4. Złożone struktury danych dla zbiorów elementów. 4.1. Problem sumowania zbiorów rozłącznych. 4.1.1. Implementacja listowa. 4.1.2. Implementacja drzewowa. 4.2. Złączalne kolejki priorytetowe. Zadania. 5. Algorytmy tekstowe. 5.1. Problem wyszukiwania wzorca. 5.1.1. Algorytm N („naiwny”). 5.1.2. Algorytm KMP (Knutha-Morrisa-Pratta). 5.1.3. Algorytm liniowy dla problemu wyszukiwania wzorca dwuwymiarowego, czyli algorytm Bakera. 5.1.4. Algorytm GS′ (wersja algorytmu Galila-Seiferasa dla pewnej klasy wzorców). 5.1.5. Algorytm KMR (Karpa-Millera-Rosenberga). 5.1.6. Algorytm KR (Karpa-Rabina). 5.1.7. Algorytm BM (Boyera-Moore‘a). 5.1.8. Algorytm FP (Fishera-Patersona). 5.2. Drzewa sufiksowe i grafy podsłów. 5.2.1. Niezwarta reprezentacja drzewa sufiksowego. 5.2.2. Tworzenie drzewa sufiksowego. 5.2.3. Tworzenie grafu podsłów. 5.3. Inne algorytmy tekstowe. 5.3.1. Obliczanie najdłuższego wspólnego podsłowa. 5.3.2. Obliczanie najdłuższego wspólnego podciągu. 5.3.3. Wyszukiwanie słów podwójnych. 5.3.4. Wyszukiwanie słów symetrycznych. 5.3.5. Równoważność cykliczna. 5.3.6. Algorytm Huffmana. 5.3.7. Obliczanie leksykograficznie maksymalnego sufiksu. 5.3.8. Jednoznaczne kodowanie. 5.3.9. Liczenie liczby podsłów. Zadania. 6. Algorytmy równoległe. 6.1. Równoległe obliczanie wyrażeń i prostych programów sekwencyjnych. 6.2. Sortowanie równoległe. Zadania. 7. Algorytmy grafowe. 7.1. Spójne składowe. 7.2. Dwuspójne składowe. 7.3. Silnie spójne składowe i silna orientacja. 7.4. Cykle Eulera. 7.5. 5-kolorowanie grafów planarnych. 7.6. Najkrótsze ścieżki i minimalne drzewo rozpinające. Zadania. 8. Algorytmy geometryczne. 8.1. Elementarne algorytmy geometryczne. 8.2. Problem przynależności. 8.3. Wypukła otoczka. 8.4. Metoda zamiatania. 8.4.1. Najmniej odległa para punktów. 8.4.2. Pary przecinających się odcinków. Zadania.