Algorytmy i struktury danych I - wykład 2019/20

Na poprawkowym terminie egzaminu (czwartek, 20.02.2020 godz 10.15 sala 227) można pisać wybraną część egzaminu (algorytmy, teoria) lub obydwie części. Liczy się zawsze lepszy rezultat z wszystkich prób (pierwszego i drugiego terminu). Większość pytań z teorii to będą pytania, które już się pojawiły na pierwszym terminie.

informacje o egzaminie: EGZAMIN.html

materiał obowiązujący na egzaminie: zagadnienia z teorii

Wykład jest prowadzony wg podręcznika "Wprowadzenie do algorytmów" Cormen, Leiserson, Rivest, Stein, Wydawnictwo Naukowe PWN. Poniżej są podane wybrane uzupełniające informacje.

analiza złożoności czasowej: wprowadzenie

Sortowanie kopcowe (Heap-sort): pseudokod oraz przykład

Sortowanie szybkie (Quick-sort): pseudokod oraz przykład

Sortowanie przez zliczanie (Counting-sort) i pozycyjne (Radix-sort): pseudokod oraz teoria: dolne ograniczenie złożoności czasowej sortowania przez porównania, przykład

Listy: definicje i fragmenty pseudokodu przykład - cały program z wykładu Stosy, kolejki:

Tablice z haszowaniem: funkcje haszujące, pseudokod i przykład

Drzewa poszukiwań binarnych: definicja, pseudokod

Analiza kosztu zamortyzowanego: przykład - tablice dynamiczne

Samoorganizujące się drzewa poszukiwań binarnych (splay-trees): wizualizacja