Płatki śniegu Porównywanie parami Zmniejszenie liczby wykonywanych operacji Tablice mieszające Chaos w hasłach Sprawdzanie wszystkich haseł Użycie tablicy mieszającej Sprawdzanie pisowni — usuwanie litery Rozważania o zastosowaniu tablic mieszających Rozwiązanie doraźne Halloweenowy łup Drzewa binarne Zbieranie wszystkich cukierków Przechodzenie minimalnej liczby ulic Odczyt danych wejściowych Dlaczego korzystać z rekurencji? Odległość pomiędzy potomkami Odczyt danych wejściowych Liczba potomków w odległości d od wierzchołka Liczba potomków dla wszystkich wierzchołków Sortowanie wierzchołków Wyświetlanie wyników Funkcja main MEMOIZACJA I PROGRAMOWANIE DYNAMICZNE Burgerowa gorączka Określenie planu rozwiązania problemu Określanie optymalnego rozwiązania Zastosowanie rekurencji Memoizacja Programowanie dynamiczne Struktura optymalnego rozwiązania Rozwiązanie rekurencyjne Memoizacja Programowanie dynamiczne Skąpcy Określanie optymalnego rozwiązania Rekurencja Memoizacja Rywalizacja hokejowa Rozważania dotyczące rywalizacji Określenie optymalnego rozwiązania Programowanie dynamiczne Optymalizacja zużycia pamięci ZAAWANSOWANA MEMOIZACJA I PROGRAMOWANIE DYNAMICZNE Skoczek Analiza wstecz Analiza w przód Sposoby budowy Stosowanie „dokładnych” podproblemów Dodawanie kolejnych podproblemów GRAFY I PRZESZUKIWANIE WSZERZ Pogoń skoczka Grafy i przeszukiwanie wszerz Grafy a drzewa Algorytm BFS na grafach Grafy a programowanie dynamiczne Wspinaczka po linie Poszukiwanie ruchów Nowy model Tłumaczenie książek Wczytywanie nazw języków Budowanie grafu Implementacja algorytmu BFS Koszt całkowity NAJKRÓTSZE ŚCIEŻKI NA GRAFACH WAŻONYCH Myszy w labiryncie Zostawiamy algorytm BFS Znajdowanie najkrótszej ścieżki na grafach ważonych Implementacja algorytmu Dijkstry Dwie optymalizacje Algorytm Dijkstry Efektywność działania algorytmu Dijkstry Krawędzie o wagach ujemnych Planowanie odwiedzin u babci Macierz sąsiedztwa Konstruowanie grafu Analiza przypadku testowego dziwacznych ścieżek Najkrótsze ścieżki Liczba najkrótszych ścieżek Karmienie mrówek Wczytywanie danych wejściowych Sprawdzanie wykonalności Poszukiwanie rozwiązania Wyszukiwanie binarne Wydajność działania algorytmu wyszukiwania binarnego Określanie wykonalności Przeszukiwanie tablicy posortowanej Skok przez rzekę Koncepcja zachłanności Testowanie wykonalności Poszukiwanie rozwiązania Wczytywanie danych wejściowych Jakość życia

Sortowanie wszystkich prostokątów Sprawdzanie wykonalności Szybsze sprawdzanie wykonalności Drzwi w jaskini Zastosowanie wyszukiwania liniowego Stosowanie wyszukiwania binarnego KOPCE I DRZEWA SEGMENTÓW Promocja w supermarkecie Wartość maksymalna i minimalna w tablicy Kopce maksymalne Kopce minimalne Kopce Wybór struktury danych Budowanie drzewców Rekurencyjne wyświetlanie drzewców Sortowanie na podstawie etykiet Rekurencja Pytania o sumę zakresu Drzewa segmentów Drzewa segmentów Suma dwóch Wypełnianie drzewa segmentów Znajdowanie odpowiedzi z użyciem drzewa segmentów Aktualizacja drzewa segmentów Funkcja main STRUKTURA ZBIORÓW ROZŁĄCZNYCH Sieć społecznościowa Modelowanie danych w formie grafu BFS Struktura zbiorów rozłącznych Struktura zbiorów rozłącznych Łączenie na podstawie wielkości Skracanie ścieżek Struktura zbiorów rozłącznych Wybieranie struktury zbiorów rozłącznych Przyjaciele i wrogowie Rozszerzenie: Struktura zbiorów rozłącznych Funkcja main Operacje find i union Operacje UstawJakoPrzyjaciół i UstawJakoWrogów Operacje CzySąPrzyjaciółmi i CzySąWrogami Problem 3.: Kłopot z szufladami Równoważne szuflady Implementacja operacji find i union RANDOMIZACJA Yōkan Losowy wybór kawałka Generowanie liczb losowych Określanie liczby kawałków Odgadywanie smaków Wypełnianie tablic smaków Randomizacja Algorytmy typu Monte Carlo Algorytmy typu Las Vegas Algorytmy deterministyczne a probabilistyczne Kapsle i butelki Rozwiązywanie podzadania Rekurencja Dodanie randomizacji Sortowanie szybkie Implementacja algorytmu sortowania szybkiego Efektywność najgorszego przypadku i oczekiwana EFEKTYWNOŚĆ ALGORYTMÓW Notacja dużego O Czas liniowy Czas stały Czas kwadratowy Płatki śniegu: niejawne listy połączone Burgerowa gorączka: rekonstrukcja rozwiązania Pogoń skoczka: kodowanie ruchów Algorytm Dijkstry: stosowanie kopca Myszy w labiryncie: śledzenie z użyciem kopców Myszy w labiryncie: implementacja z użyciem kopca Skracanie skracania ścieżek Żadnych więcej operatorów trójargumentowych Bardziej czytelne operatory przypisania Wyjaśnienie rekurencji Kapsle i butelki: sortowanie w miejscu

WE1225n