Marcin Sydow - Algorytmy i Struktury Danych - strona kursu

• "Wprowadzenie do algorytmów" (CLRS), T.Cormen et al., PWN 2018
• "Algorytmy i struktury danych" (BDR), L.Banachowski, K.Diks, W.Rytter, PWN 2018
• "Algorithms and Datastructures. The Basic Toolbox" (MS), K.Mehlhorn P.Sanders, Springer 2008
• "Algorithm Desing" (KT), J.Kleinberg E.Tardos, Pearson 2006

1. "Poprawność algorytmu" - Wprowadzenie, algorytm, specyfikacja i poprawność algorytmów.
2. "Złożoność algorytmu" - Złożoność czasowa i pamięciowa algorytmów. Notacja asymptotyczna (O,o,Omega,omega,Theta)
3. "Wyszukiwanie" Wyszukiwanie klucza w ciągu, algorytm skoków, idea "dziel i rządź", algorytm wyszukiwania binarnego, algorytm Hoare'a (idea), statystyki pozycyjne, algorytm turniejowy
4. "Sortowanie 1" Rola sortowania. Selection Sort, Insertion Sort, Merge Sort.
5. "Sortowanie 2" Quick Sort. Dolne ograniczenie złożoności sortowania przez porównania. Count Sort. Radix Sort
6. "Rekursja" Algorytmy rekurencyjne. Rozwiązywanie niektórych równań rekurencyjnych
7. "Podstawowe struktury danych i pojęcie abstrakcyjnej struktury danych" Reprezentacja ciągów: tablice, listy dowiązaniowe. Najprostsze abstrakcyjne struktury danych: stos, kolejka. (rozdział 3 (MS))
8. "Kolejka priorytetowa" Kolejka priorytetowa, kopiec binarny i rozszerzenia.
9. "Słownik" Słownik, tablice mieszające, uporządkowany słownik, drzewo BST.
10. "Podstawowe algorytmy grafowe 1" Przypomnienie podstawowych pojęć z grafów, reprezentacje grafów
11. "Podstawowe algorytmy grafowe 2" Algorytmy BFS i DFS
12. "Najkrótsze ścieżki" Najkrótsze z jednym źródłem, algorytm sortowania topologicznego, Dijsktry i Bellmana-Forda.
13. "Minimalne drzewo rozpinające" Algorytmy Kruskala i Prima