Algorytmy i struktury danych 1000-213aASD

1. Metody projektowania algorytmów: dziel i zwyciężaj, programowanie dynamiczne, algorytmy zachłanne, nawracanie, algorytmy randomizacyjne.
2. Analiza algorytmów: modele obliczeń (RAM - maszyna o dostepie swobodnym, drzewa decyzyjne), złożoność czasowa i pamięciowa, złożoność pesymistyczna i oczekiwana, analiza kosztu zamortyzowanego, analiza probalistyczna, dolne ograniczenia (złożonośc problemu a złożoność algorytmu).
3. Sortowanie i wybieranie: sortowanie za pomocą porównań (sortowanie przez wstawianie, sortowanie szybkie, sortowanie stogowe, sortowanie przez scalanie), dolne ograniczenia złożoności sortowania, algorytmy wyboru (algorytm Hoare'a i magisznych piątek), srotowanie pozycyjne i leksykograficzne, sortowanie zewnętrzne, kolejki priorytetowe (kopce binarne, dwumienne i Fibonacciego).
4. Wyszukiwanie: wyszukiwanie binarne, słowniki, drzewa wyszukiwań binarnych, drzewa zrównoważone, (drzewa AVL, drzewa czerwono-czarne), wyszukiwanie zewnętrzne, haszowanie, wyszukiwanie pozycyjne.
5. Problem Find-Union: definicja, struktury danych, koszt zamortyzowany, zastosowania.