---
# System prepended metadata

title: Untitled

---


# ZAISD 

## Wykład 1
+ P vs NP 
+ Tw Cooka 
+ Rozwiązywanie równań rekurencyjnych typu T(n) <= a^n  
+ Problem plecakowy, Schropper-Shamir Algorithm (meet in the middle) 

## Wykład 2 -- NP trunde problemy v2  
+ Parametryzacja
+ Kernelizacja 
+ Color coding, k-path problem

## Wykład 3 -- TSP & programowanie liniowe 
+ TSP 
+ Programowanie liniowe 
+ Aproksymacja (np do set cover) 
+ Bin packing first fit approx 
+ PTAS (liczby atnypierwsze), FPTAS  


+ Siec przepływowa, przepływ   
+ Przerój 

## Wykład 4
+ Tw Forda Fulkersona 
+ Przepustowość residualna 
+ Metoda Forda-Fulkersona
+ Tw o Całkowitości maksymalnego przepływu 
+ Alg Edmondsa-Carpa 


## Wykład 5 lepsze przepływy
+ Alg Hoprcofta-Karpa 
+ Algorytm Dinica 
+ Potencjał wierzchołka, Pseudoprzepływy 
+ Framework do zadań optymalizacyjnych, konwersja na min-cut 

## Wykład 6 
+ Postać standardowa programu liniowego
+ Slack form 
+ Certyfikat optymalności 
+ Dualność LP 

## Wykład 7 
+ Ważona sieć przepływowwa, 
+ framework na min-cost max-flow 
+ Alg Johnsona 

## Wykład 8 -- zabawy na przedziałach 
+ SQRT Tree, 
+ LCA 
+ RMQ (preprocessing O(n), lookup O(1), RMQ->LCA-> RMQ1) 
+ Metoda 4 rosjan 
 
## Wykład 9 -- UF intro & Akkerman 
+ UF
+ f. akkermana 
+ Problem sum częściowych 

## Wykład 10 -- UF 
+ Heurystyka 1 (laczenie wedlug rang) e
+ Heurystyka 2 (kompresja sciezki) 
+ Rank forest 
+ Oszacowanie na log* 

## Wykład 11 (extra?) 
+ Global MinCut 
+ Guess MinCut 
+ BetterGuessMinCut/algorytm Kargera (rekurencyjne powtarzanie drugiej 'połowy' 4-krotnie) 
+ Filtry Blooma 
 
## Wykład 12 -- skojarzenia w grafach niedwudzielnych 
+ Tw Tutte-Berga 
+ Blossom algorithm  
+ E-G Dekompozycja 

## Wykład 13 Haszowanie1 
+ Własność dystrybucji
+ 2-niezależność 
+ Frequency estimator 
+ Cardinality estimator 
+ Hyperloglog 

## Wykład 14 -- Haszownanie 2 
+ Kolizja pierwotna, kolizja wtórna
+ Analiza dla 2-niezależnej funkcji i 3-niezależnej funcji O(log n) 
+ X-fast-trie, Y-fast-trie 

## Wykład 15 -- Haszownanie 3 
+ closed addresing, open addresing 
+ FKS z aisd1 (słownik statyczny) 
+ Cokoo hashing 