Programowanie 2 (Python)

Bradley N. Miller — Problem Solving with Algorithms and Data Structures Using Python, link.
Thomas Cormen, Charles Leiserson, Ronald Rivest, Clifford Stein — Wprowadzenie do algorytmów.
Dusty Phillips — Python 3 Object Oriented Programming.
Luciano Ramalho — Fluent Python: Clear, Concise, and Effective Programming.

Wstęp do analizy złożoności czasowej algorytmów. Notacja asymptotyczna: zbiory O(·), Ω(·) i Θ(·) ich podstawowe własności. Porządek na klasach Θ(·). Rozmiar danych. Przypadek pesymistyczny, optymistyczny i średni. Slajdy. Skrypt.
Analiza czasu działania algorytmów, złożoność operacji na kolekcjach Pythona. Stos i jego zastosowania: przykład weryfikacji poprawności nawiasowania. Slajdy. Przykłady: implementacja stosu, sprawdzanie nawiasowania (źródło), animacje weryfikacji nawiasowania. Skrypt (Jupyter notebook + HTML). Bonus: wypisywanie liczby w zadanej podstawie
Notacja postfiksowa (odwrotna notacja polska). Konwersja wyrażeń arytmetycznych do ONP i wyliczanie ich wartości. Kolejka i przykłady zastosowań. Materiały + skrypt.
Iteratory i generatory. Implementacja iteratora dla stosu przez klasę i przez funkcję generującą. Lista łączona i jej zastosowania: stos i kolejka. Materiały. Bonus (poza wykładem): iteratory ze zwykłych funkcji.
Algorytmy sortujące: przez wybieranie, przez wstawianie, przez scalanie, szybkie. Stabilność sortowania. Niezmiennik pętli i złożoność pamięciowa. Materiały.
Drzewa i drzewa binarne. Parsowanie wyrażeń arytmetycznych do drzew. Drzewa wyszukiwań binarnych. Materiały.