1.Rola algorytmów w obliczeniach 1.1.Algorytmy 1.2.Algorytmy jako technologia 2.Zaczynamy 2.1.Sortowanie przez wstawianie 2.2.Analiza algorytmów 2.3.Projektowanie algorytmów 2.3.1.Metoda „dziel i zwyciężaj" 2.3.2.Analiza algorytmów typu „dziel i zwyciężaj" 3.Rzędy wielkości funkcji 3.1.Notacja asymptotyczna 3.2.Standardowe notacje i typowe funkcje 4.Metoda „dziel i zwyciężaj" 4.1.Problem maksymalnej podtablicy 4.2.Algorytm Strassena mnożenia macierzy 4.3.Metoda podstawiania 4.4.Metoda drzewa rekursji 4.5.Metoda rekurencji uniwersalnej 4.6.Dowód twierdzenia o rekurencji uniwersalnej 4.6.1.Dowód dla dokładnych potęg 4.6.2.Podłogi i sufity 5. Analiza probabilistyczna i algorytmy randomizowane 5.1.Problem zatrudnienia sekretarki 5.2.Zmienne losowe wskaźnikowe 5.3.Algorytmy randomizowane 5.4.Analiza probabilistyczna i dalsze zastosowania zmiennych losowych wskaźnikowych 5.4.1.Paradoks dnia urodzin 5.4.2.Kule i urny 5.4.3.Ciągi „dobrej passy", czyli sukcesów 5.4.4.Problem on-line zatrudnienia sekretarki Część II Sortowanie i statystyki pozycyjne 6.Heapsort - sortowanie przez kopcowanie 6.1.Kopce 6.2.Przywracanie własności kopca 6.3.Budowanie kopca 6.4.Algorytm sortowania przez kopcowanie (heapsort) 6.5.Kolejki priorytetowe 7.Quicksort - sortowanie szybkie 7.1.Opis algorytmu 7.2.Czas działania algorytmu quicksort 7.3.Randomizowana wersja algorytmu quicksort 7.4.Analiza algorytmu quicksort 7.4.1.Analiza przypadku pesymistycznego 7.4.2.Analiza oczekiwanego czasu działania 8.Sortowanie w czasie liniowym 8.1.Dolne ograniczenia dla problemu sortowania 8.2.Sortowanie przez zliczanie 8.3.Sortowanie pozycyjne 8.4.Sortowanie kubełkowe 9.Mediany i statystyki pozycyjne 9.1.Minimum i maksimum 9.2.Wybór w oczekiwanym czasie liniowym 9.3.Wybór w pesymistycznym czasie liniowym Część III Struktury danych 10.Elementarne struktury danych 10.1.Stosy i kolejki 10.2.Listy (z dowiązaniami) 10.3.Reprezentowanie struktur wskaźnikowych za pomocą tablic 10.4.Reprezentowanie drzew (ukorzenionych) 11.Tablice z haszowaniem 11.1.Tablice z adresowaniem bezpośrednim 11.2.Tablice z haszowaniem 11.3.Funkcje haszujące 11.3.1.Haszowanie modularne 11.3.2.Haszowanie przez mnożenie 11.3.3. Haszowanie uniwersalne 11.4. Adresowanie otwarte 11.5. Haszowanie doskonałe 12.Drzewa wyszukiwań binarnych 12.1.Co to jest drzewo wyszukiwań binarnych? 12.2.Wyszukiwanie w drzewie wyszukiwań binarnych 12.3.Wstawianie i usuwanie 12.4. Losowo skonstruowane drzewa wyszukiwań binarnych 13.Drzewa czerwono-czarne 13.1.Własności drzew czerwono-czarnych 13.2.Operacje rotacji 13.3.Operacja wstawiania 13.4.Operacja usuwania 14.Wzbogacanie struktur danych 14.1.Dynamiczne statystyki pozycyjne 14.2.Jak wzbogacać strukturę danych 14.3.Drzewa przedziałowe Część IV Zaawansowane metody konstruowania i analizowania algo¬rytmów 15. Programowanie dynamiczne 15.1. Rozcinanie pręta 15.2.Mnożenie ciągu macierzy 15.3.Podstawy programowania dynamicznego 15.4.Najdłuższy wspólny podciąg 15.5.Optymalne drzewa wyszukiwań binarnych 16.Algorytmy zachłanne 16.1.Problem wyboru zajęć 16.2.Podstawy strategii zachłannej 16.3.Kody Huffmana 16.4. Matroidy a strategie zachłanne 16.5. Problem szeregowania zadań 17.Analiza kosztu zamortyzowanego 17.1.Metoda kosztu sumarycznego 17.2.Metoda księgowania 17.3.Metoda potencjału 17.4.Tablice dynamiczne 17.4.1.Powiększanie tablicy 17.4.2.Powiększanie i zmniejszanie tablicy Część V Złożone struktury danych 18.B-drzewa 18.1.Definicja B-drzewa 18.2.Podstawowe operacje na B-drzewach 18.3.Usuwanie klucza z B-drzewa 19.Kopce Fibonacciego 19.1.Struktura kopców Fibonacciego 19.2.Operacje kopca złączalnego 19.3.Zmniejszanie wartości klucza i usuwanie węzła 19.4.Oszacowanie maksymalnego stopnia 20.Drzewa van Emde Boasa 20.1.Wstępne koncepcje 20.2.Struktura rekurencyjna 20.2.1.Prototypowe struktury van Emde Boasa 20.2.2.Operacje na prototypowej strukturze van Emde Boasa 20.3. Drzewo van Emde Boasa 20.3.1.Drzewa van Emde Boasa 20.3.2.Operacje na drzewie van Emde Boasa 21.Struktury danych dla zbiorów rozłącznych 21.1.Operacje na zbiorach rozłącznych 21.2.Listowa reprezentacja zbiorów rozłącznych 21.3. Lasy zbiorów rozłącznych 21.4. Analiza metody łączenia według rangi z kompresją ścieżki Część VI Algorytmy grafowe 22.Podstawowe algorytmy grafowe 22.1.Reprezentacja grafów 22.2.Przeszukiwanie wszerz 22.3.Przeszukiwanie w głąb 22.4.Sortowanie topologiczne 22.5.Silnie spójne składowe 23.Minimalne drzewa rozpinające 23.1.Rozrastanie się minimalnego drzewa rozpinającego 23.2.Algorytmy Kruskala i Prima 24.Najkrótsze ścieżki z jednym źródłem 24.1.Algorytm Bellmana-Forda 24.2.Najkrótsze ścieżki z jednym źródłem w acyklicznych grafach 24.3.Algorytm Dijkstry 24.4.Ograniczenia różnicowe i najkrótsze ścieżki 24.5.Dowody własności najkrótszych ścieżek 25.Najkrótsze ścieżki między wszystkimi parami wierzchołków 25.1.Najkrótsze ścieżki i mnożenie macierzy 25.2.Algorytm Floyda-Warshalla 25.3.Algorytm Johnsona dla grafów rzadkich 26.Maksymalny przepływ 26.1.Sieci przepływowe 26.2.Metoda Forda-Fulkersona 26.3.Najliczniejsze skojarzenia w grafach dwudzielnych 26.4. Algorytmy typu „prześlij-przemianuj" 26.5. Algorytm „przemianuj i przesuń na początek" Część VII Wybrane zagadnienia 27. Algorytmy wielowątkowe 27.1.Podstawy dynamicznej wielowątkowości 27.2.Wielowątkowe mnożenie macierzy 27.3.Wielowątkowe sortowanie przez scalanie 28.Operacje na macierzach 28.1.Rozwiązywanie układów równań liniowych 28.2.Odwracanie macierzy 28.3.Symetryczne macierze dodatnio określone i metoda najmniejszych kwadratów 29.Programowanie liniowe 29.1.Postać standardowa i uzupełnieniowa 29.2.Formułowanie problemów w postaci programów liniowych 29.3.Algorytm sympleks 29.4.Dualność 29.5.Początkowe bazowe rozwiązanie dopuszczalne 30.Wielomiany i FFT 30.1.Reprezentacja wielomianów 30.2.DFT i FFT 30.3.Efektywne implementacje FFT 31.Algorytmy teorioliczbowe 31.1.Podstawowe pojęcia teorii liczb 31.2.Największy wspólny dzielnik 31.3.Arytmetyka modularna 31.4.Rozwiązywanie modularnych równań liniowych 31.5.Chińskie twierdzenie o resztach 31.6.Potęgi elementu 31.7.System kryptograficzny z kluczem publicznym RSA 31.8. Sprawdzanie, czy dana liczba jest pierwsza 31.9. Rozkład na czynniki pierwsze 32.Wyszukiwanie wzorca 32.1.Algorytm „naiwny" wyszukiwania wzorca 32.2.Algorytm Rabina-Karpa 32.3.Wyszukiwanie wzorca z wykorzystaniem automatów skończonych 32.4. Algorytm Knutha-Morrisa-Pratta 33.Geometria obliczeniowa 33.1.Własności odcinków 33.2.Sprawdzanie, czy jakakolwiek para odcinków się przecina 33.3.Znajdowanie otoczki wypukłej 33.4.Znajdowanie pary najmniej odległych punktów 34.NP-zupełność 34.1.Czas wielomianowy 34.2.Weryfikacja w czasie wielomianowym 34.3.NP-zupełność i redukowalność 34.4.Dowodzenie NP-zupełności 34.5.Problemy NP-zupełne 34.5.1.Problem kliki 34.5.2.Problem pokrycia wierzchołkowego 34.5.3.Problem cyklu Hamiltona 34.5.4.Problem komiwojażera 34.5.5.Problem sumy podzbioru 35. Algorytmy aproksymacyjne 35.1.Problem pokrycia wierzchołkowego 35.2.Problem komiwojażera 35.2.1.Problem komiwojażera z nierównością trójkąta 35.2.2.Ogólny problem komiwojażera 35.3.Problem pokrycia zbioru 35.4.Randomizacja i programowanie liniowe 35.5.Problem sumy podzbioru Część VIII Dodatek: Podstawy matematyczne A.Sumy A.1. Wzory i własności dotyczące sum A.2. Szacowanie sum B.Zbiory i nie tylko B.1. Zbiory B.2. Relacje B.3. Funkcje B.4. Grafy B.5. Drzewa B.5.1. Drzewa wolne B.5.2. Drzewa ukorzenione i uporządkowane B.5.3. Drzewa binarne i pozycyjne C.Zliczanie i prawdopodobieństwo C.1. Zliczanie C.2. Prawdopodobieństwo C.3. Dyskretne zmienne losowe C.4. Rozkłady: geometryczny i dwumianowy C.5. Krańce rozkładu dwumianowego D.Macierze D.1. Macierze i operacje na macierzach D.2. Podstawowe własności macierzy