Kurs algorytmów i struktur danych w Pythonie

Lekcja 1 • Funkcje i zakres widoczności

Definiuje funkcje wielokrotnego użytku z parametrami, wartościami zwracanymi i regułami zakresu widoczności. Przygotowuje studentów do hermetyzacji logiki DSA w czystych, testowalnych jednostkach.

Lekcja 2 • Sterowanie przepływem i iteracja

Uczy rozgałęzień if/elif/else, pętli for i while oraz instrukcji sterowania pętlami. Umożliwia studentom wyrażanie logiki algorytmicznej w Pythonie.

Lekcja 3 • Obsługa błędów i debugowanie

Wprowadza wyjątki, bloki try/except i narzędzia do debugowania. Wyposaża studentów w umiejętność pisania odpornego na błędy kodu i diagnozowania awarii w złożonych programach.

Lekcja 4 • Podstawowe typy danych i zmienne

Obejmuje liczby całkowite, zmiennoprzecinkowe, łańcuchy znaków, wartości logiczne i rzutowanie typów. Dostarcza prymitywów danych używanych w każdej implementacji algorytmu.

Lekcja 1 • Iteratory, generatory i leniwa ewaluacja

Wyjaśnia protokół iteratora, funkcje generatora i instrukcję yield. Umożliwia wydajną pamięciowo nawigację po dużych zbiorach danych w problemach DSA.

Lekcja 2 • Listy i krotki w szczegółach

Bada indeksowanie, wycinanie, mutację i niezmienność krotek. Te typy sekwencyjne stanowią podstawę tablicowych struktur danych omawianych później.

Lekcja 3 • Słowniki i zbiory

Obejmuje przechowywanie oparte na haszowaniu, operacje klucz-wartość i algebrę zbiorów. Bezpośrednio wspiera implementacje tablic mieszających i list sąsiedztwa grafów.

Lekcja 4 • Wyrażenia składane list i słowników

Uczy zwięzłej składni wyrażeń składanych do filtrowania i przekształcania kolekcji. Redukuje kod szablonowy w implementacjach algorytmów w trakcie kursu.

Lekcja 1 • Wprowadzenie do analizy algorytmów

Definiuje poprawność algorytmów, wydajność i potrzebę formalnej analizy. Kładzie nastawienie analityczne stosowane do każdej struktury danych i algorytmu w dalszej części kursu.

Lekcja 2 • Big-O, Big-Omega i Big-Theta

Formalizuje notację asymptotyczną i typowe klasy złożoności. Zapewnia słownictwo używane do opisu każdego algorytmu w kolejnych rozdziałach.

Lekcja 3 • Analiza pętli i wywołań rekurencyjnych

Uczy zliczania kroków dla pętli i relacji rekurencyjnych dla rekurencji. Bezpośrednio przygotowuje studentów do analizy algorytmów sortowania i drzewiastych.

Lekcja 4 • Profilowanie kodu w Pythonie

Używa modułów timeit, cProfile i memory_profiler do mierzenia rzeczywistej wydajności. Łączy teoretyczną złożoność z mierzalnym zachowaniem wykonania Pythona.

Lekcja 1 • Porównanie złożoności struktur liniowych

Porównuje złożoność czasową i pamięciową wszystkich badanych struktur liniowych. Umożliwia świadomy wybór struktury do problemów projektowania algorytmów.

Lekcja 2 • Listy powiązane pojedyncze i podwójne

Buduje klasy węzłów i operacje na listach, w tym wstawianie, usuwanie i przechodzenie. Wprowadza myślenie wskaźnikowe niezbędne dla drzew i grafów.

Lekcja 3 • Stosy: implementacja i zastosowania

Implementuje stosy za pomocą list i list powiązanych, a następnie stosuje je do rzeczywistych problemów. Demonstruje semantykę LIFO używaną w rekurencji, parsowaniu i cofaniu.

Lekcja 4 • Kolejki, deki i kolejki priorytetowe

Obejmuje kolejki FIFO, deki dwustronne i kolejki priorytetowe oparte na kopcu. Przygotowuje studentów do problemów BFS, szeregowania i algorytmów zachłannych.

Lekcja 1 • Kwadratowe algorytmy sortowania

Implementuje sortowanie bąbelkowe, przez wybór i przez wstawianie z analizą krok po kroku. Zapewnia punkt odniesienia O(n²), względem którego mierzone są szybsze sortowania.

Lekcja 2 • Algorytmy wyszukiwania

Implementuje wyszukiwanie liniowe i binarne z dowodami złożoności. Łączy wyszukiwanie z wymaganiami dotyczącymi posortowanych danych i rzeczywistymi problemami rekrutacyjnymi.

Lekcja 3 • Podstawy rekurencji

Definiuje przypadki bazowe, przypadki rekurencyjne i stos wywołań. Buduje model myślowy wymagany dla przechodzenia drzew i algorytmów dziel i zwyciężaj.

Lekcja 4 • Sortowanie liniowe i hybrydowe

Obejmuje sortowanie przez zliczanie, sortowanie pozycyjne i Timsort używany we wbudowanym sortowaniu Pythona. Poszerza zestaw narzędzi studentów poza sortowanie oparte na porównaniach.

Lekcja 1 • Drzewa poszukiwań binarnych (BST)

Implementuje wstawianie, wyszukiwanie i usuwanie w BST ze średnią analizą O(log n). Pokazuje przechowywanie i wyszukiwanie uporządkowanych danych za pomocą struktury drzewa.

Lekcja 2 • Drzewa trie i drzewa prefiksowe

Konstruuje drzewo trie do wstawiania, wyszukiwania i dopasowywania prefiksów łańcuchów. Umożliwia wydajne rozwiązania autouzupełniania i wyszukiwania w słowniku.

Lekcja 3 • Drzewa binarne i przechodzenie

Definiuje terminologię drzew i implementuje przechodzenie inorder, preorder i postorder. Ustanawia wzorzec rekurencyjnego przechodzenia używany we wszystkich algorytmach drzewiastych.

Lekcja 4 • Kopce i operacje na kopcach

Buduje kopiec maksymalny i minimalny, implementuje operacje heapify i sortowanie kopcowe. Bezpośrednio wspiera implementacje kolejki priorytetowej i algorytmów zachłannych.

Lekcja 1 • Zaawansowane problemy grafowe

Obejmuje silnie spójne składowe, sprawdzanie dwudzielności i podstawy przepływu w sieci. Rozszerza umiejętności grafowe na złożone kategorie problemów ze świata rzeczywistego.

Lekcja 2 • Reprezentacje grafów i terminologia

Definiuje grafy skierowane, nieskierowane, ważone i cykliczne za pomocą list i macierzy sąsiedztwa. Ustanawia fundament dla wszystkich implementacji algorytmów grafowych.

Lekcja 3 • Algorytmy najkrótszej ścieżki

Implementuje algorytmy Dijkstry i Bellmana-Forda dla grafów ważonych. Wyposaża studentów w umiejętność rozwiązywania problemów routingu i minimalizacji kosztów.

Lekcja 4 • Minimalne drzewa rozpinające

Implementuje algorytmy Kruskala i Prima z użyciem union-find i kolejek priorytetowych. Rozwiązuje problemy projektowania sieci wymagające łączności o minimalnym koszcie.

Lekcja 1 • Algorytmy zachłanne i z powrotami (backtracking)

Implementuje strategie zachłanne dla szeregowania zadań i kodowania Huffmana oraz backtracking dla problemu N-Hetmanów i podzbiorów. Uzupełnia podstawowy zestaw narzędzi do projektowania algorytmów.

Lekcja 2 • Tablicowanie i DP oddolne

Buduje tablice DP iteracyjnie dla problemów wymiany monet, wchodzenia po schodach i ścieżek w siatce. Eliminuje narzut rekurencji i wyjaśnia logikę przejść między stanami.

Lekcja 3 • Wprowadzenie do programowania dynamicznego

Definiuje nakładające się podproblemy i optymalną podstrukturę jako warunki wstępne DP. Porównuje DP z metodą dziel i zwyciężaj, aby wyjaśnić, kiedy każda z nich ma zastosowanie.

Lekcja 4 • Memoizacja i DP odgórne

Konwertuje naiwną rekurencję na rozwiązania z memoizacją za pomocą słowników i functools.lru_cache. Pokazuje dramatyczną redukcję złożoności na przykładzie ciągu Fibonacciego i podobnych problemów.