# Ogólne uwagi
- to nie są kompletne notatki, raczej skróty myślowe + przewodnik po notatkach
- to nie idzie stricte równo z wykładem, a raczej tak, żeby ładniej pakowało się w tabelki (np. wszystkie sortowania razem, brak wyszczególnienia preliminariów)
- to generalnie są już takie notatki z najważniejszymi rzeczami na "dzień przed egzaminem", nie do powtarzania temat po temacie

# Notacje rzędów funkcji

# Sortowania
| nazwa | działanie | czas | pamięć |stabilność
|-----------|-----------------------------------------------------------------------------------------------------------------------------------------------|----------|---|--|
| [bubble](https://www.geeksforgeeks.org/bubble-sort/) | idziemy od pocżątku tablicy i przenosimy ciagle najwiekszy aktualnie znaleziony indeks w górę; końcówka jest posortowana i jej nie sprawdzamy | $O(n^2)$ | $O(1)$ | **tak** (nie zamieniamy równych elementów)
| [insertion](https://www.geeksforgeeks.org/insertion-sort/) | idziemy po kolejnych indeksach i jak trafiamy na nieposortowany element, to cofamy go swapami, aż trafi na miejsce | $O(n^2)$ | $O(1)$ | **tak** (nie zamieniamy miejscami równych elementów)
| [selection](https://www.geeksforgeeks.org/selection-sort/) | od każdego indeksu kolejno idziemy do końca i najmniejszy znaleziony element przenosimy na poczatek aktualnego fragmentu | $O(n^2)$ | $O(1)$ | **nie** (przenosi na poprawną pozycję zamieniając elementy)
| [heap](https://www.geeksforgeeks.org/heap-sort/) | zbuduj kopiec minimum i kolejno usuwaj elementy | $O(n \log{n})$ | $O(1)$ (w miejscu) | **nie** (informacja o kolejności elementów ginie podczas tworzenia stosu)
| [merge](https://www.geeksforgeeks.org/merge-sort/) | podziel na tablice jednostkowe i łącz po dwie rekurencyjnie (zawsze łączymy posortowane tablice) | $O(n \log{n})$ | $O(\log{n})$ lub $O(n)$ | **tak** (jeśli elementy są równe, preferujemy ten z lewej tablicy)
| [quick](https://www.geeksforgeeks.org/quick-sort/) | wybierz pivot i porozdzielaj tablicę na mniejsze i większe od niego; utworzone tablice posortuj rekurencyjnie | $O(n \log{n})$ do $O(n^2)$ | $O(\log{n})$ lub $O(n)$ (iteracyjny $O(1)$) | **nie** (wybór pivota jest "dowolny", więc elementy mogą się zamienić miejscami)
| [count](https://www.geeksforgeeks.org/counting-sort/) | stwórz tablicę prefiksowych sum (coś jak w dynamicznych algorytmach); cofaj się po orignalnej i każdy element wkładaj pod indeks wyliczony w tej tablicy prefiksów-1 i zmniejszaj jej wartości | $O(n+max(arr))$ | $O(n+max(arr))$ (tablica licznikowa + wynik) | **tak** (bo uzupełniamy fragmenty równych elementów od tyłu i przechodzimy od tyłu)
| [bucket](https://www.geeksforgeeks.org/bucket-sort-2/) | podziel elementy na w miarę równe kubełki np. wg liczby dziesiątek dla liczb dwucyfrowych i wewnątrz kubełków posortuj dowolnym algorytmem *sort* | $n*O(sort)$ | $O(n+k)$ (liczba kubełków? + wynik) | **zależnie od wyboru *sorta* w kubełkach**

# Przeszukiwania grafów (BFS, DFS)
| **nazwa** | **struktura** | **czas** | **pamięć** | **zastosowania**
|-----------|---------------|----------|------------|------------|
| [BFS](https://www.geeksforgeeks.org/breadth-first-search-or-bfs-for-a-graph/) | kolejka | $O(V+E)$ | $O(V)$ | - odległości od wierzchołka w grafie bez wag
| [DFS](https://www.geeksforgeeks.org/depth-first-search-or-dfs-for-a-graph/) | stos | $O(V+E)$ | $O(V)$ | - sortowanie topologiczne

# Znajdowanie MST (Prim, Kruskal, Boruvka)
- działają dla grafów z ujemnymi wagami
- dla Boruvki ma być graf nieskierowany i spójny

| nazwa | działanie | złożoność |
|-----------|---------------------------------------------------------------------------------------------------------------------------|---------------|
| [Kruskal](https://www.geeksforgeeks.org/kruskals-minimum-spanning-tree-algorithm-greedy-algo-2/) | - idziemy kolejno po liście krawędzi posortowanej od najlżejszej <br>- jeżeli nie utworzy cyklu, dodajemy ją do MST | $O(logV+E)$ |
| [Prim](https://www.geeksforgeeks.org/prims-minimum-spanning-tree-mst-greedy-algo-5/) | - startujemy od dowolnego wierzchołka <br>- idziemy po najlżejszej krawędzi, która nie tworzy cyklu, do kolejnego wierzchołka | $O(logV+E)$ |
| [Boruvka](https://www.geeksforgeeks.org/boruvkas-algorithm-greedy-algo-9/) | - przejrzyj wszystkie wierzchołki i dla każdego wybierz najlżejszą krawędź <br>- od teraz spójne składowe traktuj jako wierzchołki i zacznij kolejną iterację | $O(logV+E)$ |

# Znajdowanie najkrótszych ścieżek (Dijkstra, Bellman-Ford, Warshall-Floyd)

Znajdowanie ścieżki o najmniejszym koszcie z wierzchołka startowego do każdego innego.
- zapamiętujemy ścieżkę, pamiętając w tablicy poprzednik każdego wierzchołka
- początkowo koszty dojścia do każdego wierzchołka są ustawione na $\infty$ (oprócz startowego, gdzie jest 0), a poprzedniki na $N/A$

| **nazwa** | **działanie** | **cechy** | **złożoność** |
|--------------|-----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------|---------------------------------------------------------------|-----------------------------------------|
| [Dijkstra](https://www.geeksforgeeks.org/dijkstras-shortest-path-algorithm-greedy-algo-7/) | - tworzymy zbiory Q (wierzchołki grafu) i S (pusty); wierzchołek startowy: $v$<br>- wybieramy z Q wierzchołek $u$ o najmniejszym koszcie dojścia i przenosimy do S<br>- dla wszystkich sąsiadów $u$ sprawdzamy, czy ścieżka $\overrightarrow{vu} + e$ nie jest mniejsza niż dotychczas znaleziona | - nie działa dla ujemnych krawędzi <br> - jest zachłanny | naiwna: $O(V^2)$<br>kopiec: $O(E logV)$ |
| [Bellman-Ford](https://www.geeksforgeeks.org/bellman-ford-algorithm-dp-23/) | - powtarzamy $V-1$ razy<br>- przechodzimy po wszystkich wierzchołkach (0 - startowy)<br>- dla każdego sąsiada aktualnego wierzchołka sprawdzamy, czy ścieżka nie jest mniejsza niż dotychczas znaleziona | - zadziała dla ujemnych krawędzi, o ile nie ma ujemnych cykli przez źródło | $O(VE)$ |

**Warshall-Floyd**
- wyszukiwanie najkrótszych ścieżek między **wszystkimi parami** wierzchołków (macierz)
- może zawierać ujemne wagi, ale nie cykle
- wpisujemy do macierzy krawędzie
- dla każdej pary wierzchołków sprawdzamy każdy możliwy wierzchołek pośredni, czy nie skróci on ścieżki
- czas $O(n^3)$

# Przepływy (Ford-Fulkerson)
- czas $O(E V^2)$
https://www.youtube.com/watch?v=LdOnanfc5TM

# Algorytmu zachłanne
## Pokrycie zbioru
*Idea:* Dla każdego podzbioru obliczamy średnią cenę jego elementu (uwzględniając tylko elementy, których nam jeszcze brakuje, dlatego musimy to robić co iterację) i wybieramy ten z najniższą.

# Algorytmy dziel i zwyciężaj
## Główne twierdzenie

## Algorytm Karatsuby
Złożoność: $O(n^{\log_{2}{3}})$

a = 1234567
b = 987654

1. Podziel liczbę na część lewą i prawą (zaokrąglij do mniejszej z nich)

s = min(len(a), len(b))/2 = 3
a = 1234|567
b = 987|654
a1 = 1234, a0 = 567
b1 = 987, b0 = 654

2. Wywołania rekurencyjne

p1 = a0 * b0
p2 = (a1 + a0)*(b1 + b0)
p3 = a1 * b1

3. Wynik

W = p3 * 10^2s + (p2 - p1 - p3) * 10^s +p1

## Para najbliższych punktów
*Idea:* Dzielimy zbiór poziomą kreską na pół i robimy to rekurencyjnie, aż do dwupunktowych zbiorów.
W każdym kroku wracajac z rekurencji przekazujemy pare najbliższych punktów ($d$ - odległość między nimi), po czym porównujemy ze sobą dodatkowo punkty "w otoczeniu" prostej przedzielającej (tzn. znajdujące się w odległości nie większej niż $d/2$ od niej).
Sprawdzamy odległości tylko dla punktów znajdujących się $d$ w górę/dół od rozpatrywanego.
$d$ jest najmniejszą odległością, więc takich punktów może być max. 8 (kwadrat z 4 kratkami). Czyli na każdy punkt przypada stała liczba operacji.
*Złożoność:* $O(n \log{n}) = 2T(\frac{n}{2})+O(n)$

## Min i max
*Idea*: Dobieramy elementy obok siebie w pary, mniejszy z nich przenosimy do $S_{min}$, większy do $S_{max}$. W $S_{min}$ szukamy normalnie (liniowo) minimum, w $S_{max}$ - maksimum. Dzięki temu mamy $\frac{3}{2}n-2$ porównań.

# Algorytmy dynamiczne
## Palindromy
Rekurencja:
$$dp[i][j]=
\left\{
\begin{array}{ccc}
dp[i-1][j+1]+2&\mbox{dla}&word[i]=word[j]\\
max(dp[i][j+1], dp[i-1][j])&\mbox{wpw.}
\end{array}
\right.$$
Tabelka:

## Dwumian Newtona
Rekurencja:
Tabelka:

## Mnożenie macierzy
Czas: $O(n^3)$
Pamięć: $O(n^2)$ / $O(n)$
Rekurencja:
$$dp[i][j]=
\left\{
\begin{array}{ccc}
0&\mbox{dla}&i=j\\
min_{i \le k \lt j}(dp[i][k] + dp[k+1][j]+r_{i-1} \cdot r_k \cdot r_j)&\mbox{wpw.}
\end{array}
\right.$$
Tabelka:

## Dyskretny problem plecakowy
Czas: $O(nW)$ <- pseudowielomianowy, bo zależny też od stałej (wielkości plecaka)
*W każdym kroku rozważamy plecak objętości $i$ i $j$-ty element do wyboru - o ile się mieści rozważam, czy bardziej opłaca się go dodać do plecaka w ktorym juz sa elementy o masie zmniejszonej o jego wagę, czy zostawić bez niego.*
### Z powtórzeniami
Rekurencja:
$$dp[i]=
\left\{
\begin{array}{ccc}
0&\mbox{dla}&i=0\\
max_{j:w[j] \le i}(dp[i-w[j]]+v[j])&\mbox{wpw.}
\end{array}
\right.$$

### Bez powtórzeń
Rekurencja:
$$dp[i][j]=
\left\{
\begin{array}{ccc}
0&\mbox{dla}&w[j]<i\\
max(dp[i-w[j]][j-1]+v[j], dp[i][j-1])&\mbox{wpw.}
\end{array}
\right.$$
Tabelka:

## CYK
Rekurencja:
Ciężko ją opisać, bo sprawdzamy wszystkie możliwe pary jakby z różnych rzędów, to już mi się nie chce teraz rozpisywać ładnie.

Tabelka:

# Dolne granice

## Dowody przez grę z adwersarzem
*Idea*: Złośliwy adwersarz chce zmusić algorytm do wykonania jak największej liczby porównań. Uzasadnienie, że jest to najbardziej złośliwy przypadek robimy opisując, ile maksymalnie elementów przekładamy/usuwamy/porównujemy w każdym kroku. Przykład (szukanie min i max):
Uzasadnienie:

## (Zwykłe) drzewa decyzyjne
Wykonują po jednym porównaniu na każdej krawędzi i zwracają zerojedynkowe odpowiedzi.

## Liniowe drzewa decyzyjne
Nie rozumiem ich przepraszam XD

# Sortowanie ciągów

## Jednakowej długości
### Bucket sort
Jest chujowy, chociaż może działać dla ciągów różnej długości, co na plus.
Czas: $O(dn)$
Pamięć: $O(n^2)$

### Counting sort (Radix sort)
Czas: $O(d \cdot counting-sort)=O(d \cdot (n+k))$; d-długość ciągu, k-liczba znaków w alfabecie, n
Pamięć: $O(n)$
Stabilność: Tak (korzystamy ze stabilnosci count sorta)

## Różnej długości
Możemy sprowadzić go do poprzedniego podproblemu na trzy sposoby (ostatni najlepszy).
1. Dopełniamy ciągi z prawej strony spacją lub 0 (znakiem uprzywilejowanym)
2. Dzielimy na kubełki zależne od długości słowa i w nich sortujemy leksykograficznie
3. Grupujemy słowa zależnie od długości. Sortujemy najpierw najdłuższe długości $d$, następnie z przodu tej posortowanej tablicy dodajemy o 1 krótsze i teraz sortujemy counting sortem wg pozycji $d-1...1$, następnie dodajemy te długości $d-2$ i sortujemy wg pozycji $d-2...1$ itd. aż $d=1$.

## Izomorfizm drzew ukorzenionych
Żeby zrobić izomorfizm nieukorzenionych, możemy je ukorzenić w wierzchołkach centralnych, co ma czas liniowy.

*Idea:* Idziemy od liści i każdemy z nich nadajemy identyfikator 1. Powiedzmy, że 1 wierzchołek ma 2 dzieci-liście, czyli odpowiada liście {1, 1}, drugi też ma ich 2 więc odpowiada liscie {1, 1}, a trzeci ma tylko jedno więc odpowiada liscie {1}. Listy {1, 1} i {1} są różne, więc dajemy im identyfikatory odpowiednio 2 i 3 (identyfikatorami równie dobrze mogłyby być literki, znaczki, cokolwiek). Po prostu myślimy jak o mapie:

1: {}
2: {1, 1}
3: {1}

Rodzic tych trzech, o których pisałam wcześniej ma więc listę {2, 2, 3} (dbajmy zawsze o posortowanie list, bo to, które drzewo jest po lewej, a które po prawej, nas nie obchodzi!) i takiej listy też wcześniej nie mieliśmy, więc dajemy jej id=4 itd. Korzenie drzew, które porównujemy, powinny mieć jednakowe listy.

# Problem selekcji
https://wazniak.mimuw.edu.pl/index.php?title=Algorytmy_i_struktury_danych/Selekcja

**Problem**: Chcemy znaleźć $k$-ty największy element (oczywisty przykład: szukanie mediany), ale chcemy uniknąć sortowania całego ciągu i brania $k$-tego indeksu, bo to dużo niepotrzebnej roboty. Musimy więc znaleźć inny sposób na to.

## Drugi największy
*Idea*: Znajdujemy największy `max`, ale do tego musimy sklasyfikować $n-1$ elementów jako mniejsze od niego, czyli potrzebujemy $n-1$ porównań. Robiąc to drzewowo, żeby znaleźć drugi największy, porównujemy ze sobą tylko te, które przegrały z `max` (bo nie przegrały z żadnym innym), co daje nam dodatkowo $\lceil \log{n} \rceil - 1$ porównań.

## Algorytm Hoare'a
*Idea*: Podobnie jak w quicksorcie, bierzemy pivot i robimy podział ($s$ - indeks podziału). Opieramy się na idei, że do znalezienia $k$-tego elementu musimy $k-1$ elementów sklasyfikować jako mniejsze od niego.
Jeżeli $k=s$, to znaleźliśmy ten element!
Jeżeli $k<s$, musimy szukać $k$-tego elementu lewej tablicy
Jeżeli $k>s$, musimy szukać w prawej tablicy $(k-s)$-ego elementu, bo $s$ elementów już "wyprzedziliśmy" (sklasykowaliśmy jako mniejsze od szukanego).

**Rekurencja średniego przypadku**:
1. $\frac{1}{2}T(\frac{3n}{4})$ - mamy połowę szans na "dobrego" pivota (dobry = odrzuca nam przynajmniej $\frac{1}{4}$ danych w kroku)
2. $\frac{1}{2}T(n)$ - mamy też połowę szans na "złego" pivota (a on w najgorszym wypadku odrzuca tylko 1 element - siebie)
3. $O({n})$ - operacja podziału tablicy

*Problem:* W najgorszym wypadku czas działania to będzie $O(n^2)$... wybranie pivota w mądry sposób, by mogło przyspieszyć.

## Algorytm magicznych piątek
*Idea:* Chcemy ulepszyć algorytm Hoare'a przez bardziej zrównoważony wybór elementu dzielącego. Kroki wyboru pivota:
1. Dzielimy ciąg na ciągi 5-elementowe
2. Każdy z nich sortujemy (czas stały, bo wiemy, ile mają elementów)
3. Wybieramy z każdego z nich środkowy element - tworzymy w ten sposób podciąg
4. Wywołujemy *Hoare'a* na tym podciągu, żeby wybrać medianę

**Rekurencja**:
1. $T(\frac{n}{5})$ - dzielimy na $\frac{n}{5}$ podzbiorów i z każdego mamy 1 medianę i na zbiorze tych median wywołujemy się rekurencyjnie
2. $T(\frac{7n}{10})$ - znaleziona mediana median w danym kroku jest większa od 3 elementów z każdego z $\frac{1}{2} \cdot \lceil \frac{n}{5} \rceil$ (bo w połowie podzbiorów były mediany mniejsze od znalezionej, czyli one i jeszcze dwa elementy przez nie "wyprzedzone" są mniejsze), czyli odrzucamy (klasyfikujemy jako mniejsze) w każdym kroku $\lfloor \frac{3n}{10} \rfloor$ elementów
3. $O({n})$ - koszt znalezienia mediany z każdego podzbioru

*Osiągnięcie:* W najgorszym wypadku podział będzie na $\frac{7n}{10}$ i $\frac{3n}{10}$

## Lazy select
*Idea*: Ja to dokończę obiecuję, ale tak mi się nie chce, bo tego nawet na liscie nie było

# Drzewa (BST, AVL, B drzewa, splay, czerwono-czarne, drzewce, dwumianowe)
| rodzaj | charakterystyka | cechy | wstawianie | usuwanie |
|-----------------|--------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------|-------------------------------------------------------------------------------------------------------------------------------------------------|-------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------|-----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------|
| bst | zwykłe, niezbalansowane | - lewy syn jest mniejszy od ojca, a prawy większy | schodź w dół porównaniami, aż dojdziesz do liścia i tam wstawiaj | - jeśli **jest liściem**, po prostu usuń<br>- jeśli ma **jednego syna**, przepnij wskaźnik na niego<br>- jeśli ma **dwójkę synów**, bierzemy **następnik** i wstawiamy go w to miejsce, a z oryginalnego rekurencyjnie usuwamy | |
| avl | wysokość lewego i prawego poddrzewa różni się co najwyżej o 1 | - $h \le 1,44\log{n}$<br>- drzewo mające $n$ kluczy wysokość max obliczamy z $F(h+2) \le n+1$ | - wstaw jak do bst<br>- dla ścieżki po drodze wylicz rekurencyjnie balans<br>- w razie potrzeby starczą max 2 rotacje | [wizualizacja](https://www.cs.usfca.edu/~galles/visualization/AVLtree.html) [geeksy](https://www.geeksforgeeks.org/avl-trees-containing-a-parent-node-pointer/?ref=lbp) | |
| b-drzewa | - w każdym wierzchołku może mieć max $k$ posortowanych wartości i "między nimi" $k+1$ dzieci<br>- każdy węzeł oprócz korzenia musi mieć co najmniej $\lceil \frac{k}{2} \rceil$ dzieci (korzeniowi starczą 2)<br>- wszystkie liście są na tym samym poziomie | - $h \le \log_{t}{\frac{n+1}{2}}$<br>- max. $2h$ operacji dyskowych | - jeśli **element się mieści w liściu**, wstaw go<br>- jeśli **się nie mieści**, dodaj go "z nadmiarem", weź środek powstałej tablicy, przenieś go w górę i w tym miejscu zrób podział | [wizualizacja](https://www.cs.usfca.edu/~galles/visualization/BTree.html) [geeksy](https://www.geeksforgeeks.org/delete-operation-in-b-tree/) | |
| czerwono-czarne | - każdy węzeł jest czerwony lub czarny<br>- korzeń i liście są czarne<br>- jeśli węzeł jest czerwony, to jego dzieci są czarne<br>- każda ścieżka od korzenia do liścia ma tyle samo czarnych węzłów | - najkrótsza możliwa ścieżka będzie mieć same czarne wierzchołki<br>- najdłuższa jest max 2 razy dłuższa od najkrótszej<br>- $h \le 2\log{n+1}$ | - dodajemy czerwony wierzchołek jak do bst<br>- jeżeli **jest ok**, na tym kończymy; wpw<br>- jeżeli **wujek jest czerwony**:<br>-- ```dziadek <- czerwony```<br>-- ```wujek, ojciec <- czarny```<br>-- wywołujemy rekurencyjnie dla dziadka<br>- jeżeli **wujek jest czarny**:<br>-- kolorowanie i max dwie rotacje (opisane osobno) | [wizualizacja](https://www.cs.usfca.edu/~galles/visualization/RedBlack.html) [geeksy](https://www.geeksforgeeks.org/introduction-to-red-black-tree/) | |
| splay | - ostatnio przeglądany element **wynurzamy rotacjami** do korzenia </br> - wynurzanie odbywa się przy każdej operacji </br> - wynurzanie zaczynamy **od dołu** (od elementu, który wynurzamy) | - operacja ```splay(x)``` wynurza wierzchołek $x$, a jeśli on nie występuje, to wybiera ten najbliższy $x$owi (liść przez który "wypadliśmy" szukając go) </br> - w najgorszym wypadku mamy aż $n$ rotacji (jak wynurzamy najniższy element z listy) | - wynurz wierzchołek $y$ najbliżej $x$ (```splay(x)```) </br> - $y<x$ zrzuć $y$ z lewym poddrzewem jako lewego syna $x$, jako prawego ustaw $y.right$ </br> - $y>x$ na odwrót, $y$ zrzucam na prawo </br> - w każdym wypadku $x$ to nowy korzeń | - ```splay(x)``` </br> - złącz lewe i prawe poddrzewo (wynurz największy element z lewego ```splay(inf)``` i podepnij mu po prawej prawe) | |
| drzewce | - **wartości** ułożone jak w drzewie **bst** </br> - **priorytety** ustawione jak w **kopcu** (binarnym) | - może okazać się liniowy, ale jest na to bardzo mała szansa ($\frac{2}{n!}$) </br> - dla każdego **setu** kluczy i priorytetów mamy tylko 1 możliwy drzewiec </br> - liczba rotacji po usunięciu klucza z drzewca jest sumą długości **skrajnej prawej ścieżki lewego syna** klucza i **skrajnie lewej ścieżki prawego syna** klucza. | - wstawiamy jak do bst </br> - rotacjami przywracamy porządek kopcowy | - rotacjami spychamy w dół </br> - zawsze rodzic jest zastępowany dzieckiem o **wyższym priorytecie** | |
| dwumianowe | - każde drzewo dwumianowe stopnia $k$ jest zbudowane z dwóch drzew dwumianowych stopnia $k-1$ | - korzeń ma $k$ dzieci </br> - wysokość (krawędziowa) wynosi $k$ </br> - drzewo ma $2^k$ wierzchołków | to nie jest ważne, ich się używa tylko w kopcach dwumianowych | ||

## Rotacje
W prawo (w lewo będzie na odwrót):

x = y.left 
y.left = x.right
x.right = y


## Przypadki wstawiania do drzewa czerwono-czarnego
analogicznie jak jest odbicie lustrzane; zauważmy, że drugi krok drugiego przypadku, to pierwszy przypadek.
1. $x$ jest **zewnętrzny** względem wujka
2. $x$ jest **wewnętrzny** względem wujka

# Kopce (min, max, min-max, dwumianowe, fibonacciego)
https://hackmd.io/_76DTW1vRxewe-M3eBSjpA?view

## Kopiec min/max
### Ogólne spostrzeżenia
- popierdoli mnie, bo na egzaminie nigdzie nie piszą, czy mowa o kopcu minimum czy maksimum i trzeba się domyślać z kontekstu, która wersja zadania jest trudniejsza XD
- indeksujemy [1..n]
- ostatni rząd jest wypełniany od lewej

### Indeksowanie
| wierzchołek | $k$ |
|-------------|--------|
| lewy syn | $2k$ |
| prawy syn | $2k+1$ |
| ojciec | $k//2$ |

### Budowanie kopca
- tu opisuję dla kopca maksimum (korzeń - największy)
- pojedyncza operacja wstawiania ma $O(\log{n})$, bo to max. wysokość kopca
- pamiętaj o sprawdzaniu granic tablicy!

| sposób | idea | kroki algorytmu | złożoność |
|--------|-------------------------------------------------------------------------------------------------------|----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------|-------|
| od góry | dodajemy element najbardziej na dół po prawej (koniec tablicy) i przesuwamy w górę | - idziemy po kolejnych wierzchołkach $2 \rightarrow n$<br>- jak wierzchołek jest większy od ojca, to je zamieniamy<br>- kontynuujemy aż nie będzie zmiany | $\sum_{i=1}^{n} \log{n} = O(n \cdot \log{n})$ |
| od dołu | budujemy kopiec od dołu, czyli dla każdej pary kopców (początkowo jednoelementowych) dodajemy im ojca | - idziemy od połowy tablicy $\frac{n}{2} \rightarrow 1$, "dodając" kolejnym parom synów kolejnych ojców<br>- spychamy nowego ojca w dół zamieniając go z większym z synów<br>- kontynuujemy aż nie będzie zmiany | $\sum_{h=1}^{\log{n}} h \cdot {\frac{n}{2^{h+1}}} = O(n)$ |

### Usuwanie korzenia
- opisuję dla kopca minimum (korzeń - najmniejszy)
- ten z dziurą zwykle lepszy

| sposób | działanie | złożoność |
|-----------------|-------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------|------------------------------------------------------------------------------------------------------------------------------------------------------|
| ostatni na górę | - ostatni element wstawiamy do korzenia<br>- przesuwamy go w dół, aż trafi na miejsce | $=2 \log{n}$<br>- dokładna wartość<br>- 2 porównania w każdym kroku w dół |
| z dziurą | - uznajemy, że w korzeniu jest "dziura"<br>- w każdym kroku zamieniamy dziurę z mniejszym z synów, aż stanie się liściem<br>- jak struktura się zaburzyła, to wstawiamy w dziurę ostatni element<br>- w razie potrzeby wciągamy go w górę | $\le 2 \log{n}$<br>- 1 porównanie w każdym kroku dziury w dół<br>- 1 porównanie w przesuwaniu ostatniego w górę, ale on raczej nie wróci za wysoko |

### Złożoność operacji

## Kopce minimaksowe
*Idea*: na górze jest kopiec maksimum, na dole obrócony minium i są sklejone podstawami; reprezentacja listowa przeplata indeksy.
**Reprezentacja**: ```[13, 1, 11, 2, 12, 3, 7, 4, 8, 5, 9, 6, 10]```

### Indeksowanie
- żeby sprawdzić, czy syn jest prawy czy lewy, używamy $\mod{4}$
- na styku kopców, dzieci mają indeksy $k+1$

| wierzchołek $k$ | kopiec min | kopiec max |
|----------------------------|------------|------------|
| indeksy | parzyste |nieparzyste |
| lewy syn |$2k$ | $2k+1$ |
| prawy syn |$2k+2$ | $2k+3$ |
| ojciec dla lewego syna |$k/2$ | $(k-1)/2$ |
| ojciec dla prawego syna |$(k-2)/2$ | $(k-3)/2$ |

## Kopce dwumianowe
Kopiec dwumianowy składa się z listy drzew dwumianowych. Dodatkowo:
- **stopnie** drzew są **unikatowe**
- w drzewach jest zachowany **porządek kopcowy** (np. rodzic mniejszy od dzieci)
- **korzenie** drzew są **połączone** listą dwukierunkową
- **dzieci** każdego węzła w każdym drzewie **połączone** są listą dwukierunkową
- każdy kopiec można opisać **liczbami binarnymi** i dodawanie zachodzi dla scalania (intuicja: propagacja bitu to scalenie drzew)
- **wysokość najwyższego drzewa** w kopcu to $k=\lfloor \log{n} \rfloor + 1$
- kopiec zawierający $n$ elementów składa się z co najwyżej $\lceil \log{n} \rceil$ różnych drzew

### Scalanie
**Giga proste** - wtasowujemy w siebie listy drzew od najmniejszych do największych (stopniem) i mergujemy duplikaty
Uwaga: scalanie odpowiada operacji przeniesienia na liczbach binarnych, tzn. wystarczy przedstawić kopce jako liczby i zliczyć, ile jest operacji przeniesienia przy dodawaniu pisemnym.

### Usuwanie minimum
Minimum jest na pewno w korzeniu **któregoś** z drzew zawieszonych na liście wiązanej. W najgorszym przypadku (wymagającym najwięcej operacji) będzie w największym.
Prawy (bezdzietny) wierzchołek wstawiamy na miejsce starego wierzchołka, a resztę poddrzew podpinamy pod główną listę wiązaną (i później sprzątamy, jak w insercie)

### Wersja *lazy*
Działa tak samo, z tym, że porządkuje drzewo dopiero przy usuwaniu minimum, czyli może mieć kilka takich samych drzew.

### Porównanie czasów
| rodzaj | min | meld | insert | merge | delete min |
|--------|--------------|--------------|---------|--------------|--------------|
| eager | $O(\log{n})$ | $O(\log{n})$ | $O(1)*$ | $O(\log{n})$ | $O(\log{n})$ |
| lazy | $O(1)$ | $O(1)$ | $O(1)$ | $O(1)$ | $O(\log{n})$|

## Kopce Fibonacciego
*Idea*: podobne do kopców dwumianowych (lazy), ale niekoniecznie składają się z drzew dwumianowych (drzewa muszą być unikalne, ale niekoniecznie są dwumianowe).
**Najważniejsza idea przy algorytmach operacji, to te przegrywy, które są opuszczane przez dzieci**

# Union Find
*Pamięciówka jebana bo tego nie czaję*
- **Union** ma koszt $O(1)$
- Find **bez kompresji** ma $O(\log{n})$
- Find **z kompresją** ma $O(\log{^*n}=\log{(\log{(\log{(...\log{n})})})})$- czas stały zamortyzowany!!
- czyli ciąg $n$ operacji dla zbalansowanego *uniona* i *finda* z kompresją ma czas $O(n)$
- **Rząd wierzchołka** - wysokość w lesie utworzonym po wykonaniu ciągu *Unionów* (dokładniej: po wykonaniu ciągu operacji, z którego usunęliśmy wszystkie *Findy*)
- Dla **zbalansowanego Uniona** drzewo o wysokości $h$ ma min. $2^h$ wierzchołków
- Jest max. $\frac{n}{2^r}$ **wierzchołków rzędu** $r$
- Każdy wierzchołek ma **rząd** max. $\log{n}$
- Rzędy wierzchołków dzielimy na grupy - rząd $r$ umieszczamy w grupie $\log{^*r}$

# Hashowanie
*Idea*: Każdemu elementowi z listy chcemy przyporządkować indeks (w zwykle większej tablicy), używając jakiejś funkcji (jakby "szyfrując" go z jej użyciem). Musimy się jednak pogodzić z tym, że nie znając wcześniej wartości elementów:
- w wynikowej tablicy może zostać sporo pustych miejsc
- kilku elementom może zostać przyporządkowana ta sama wartość (*kolizje*)

## Oznaczenia
*Wiem, że mogą być jakiekolwiek, ale ja muszę mieć spójność, bo inaczej będę się mylić*
$n$ - liczba elementów (kluczy) umieszczonych w tablicy (hashującej)
$m$ - rozmiar tablicy hashującej
$\alpha = \frac{n}{m}$ - współczynnik wypełnienia (intuicja - szansa na kolizję)
$h, h_1, h'$ itd. - funkcje hashujące

## Metody hashowania

### Listowanie (separate chaining)
*Idea*: tam, gdzie wystąpiły kolizje, dołączamy kolejny element tworząc listę wiązaną.
**Średni koszt**: $\Theta(1+\alpha)$

### Adresowanie otwarte
*Idea*: gdy następuje kolizja, szukamy następnego wolnego miejsca; dzięki użyciu modulo, nie zwiększamy długości tablicy.
#### Rodzaje (sposoby rozwiązywania konfliktów)

#### Wzory
- Oczekiwana liczba kolizji przy wstawianiu $n$ kluczy do tablicy rozmiaru $m$: ${n \choose 2} \cdot \frac{1}{m}$
- Oczekiwana liczba kolizji **z rzędu**: $\le \frac{1}{1-\alpha}$

#### Usuwanie elementów
Jeżeli usuwamy element z tablicy hashującej, musimy oznaczyć miejsce, w którym się znajdował, jako *nagrobek*, bo inaczej wszystkie kolejne nam się też przesuną i już nie będą odpowiadały tamtej funkcji hashującej. Dzięki temu też wiemy, że jeżeli usunęliśmy $k$-tą komórkę, to elementy, które chcielibyśmy do niej przypisać, muszą iść do następnej.
**Zadania o tym**:
- https://github.com/ithrasil/AiSD/blob/master/egzaminy/CZ%201/2013/zasadniczy/4.md
- https://github.com/ithrasil/AiSD/blob/master/egzaminy/CZ%201/2019/poprawkowy/13.md
- https://github.com/ithrasil/AiSD/blob/master/egzaminy/CZ%201/2018/poprawkowy/9.md
- https://github.com/ithrasil/AiSD/blob/master/egzaminy/CZ%201/2019/zasadniczy/13.md

### Słownik statyczny
*Idea*: rozrzuć elementy do kubełków, sprawdź, czy to rozrzucenie ma sens, a na koniec w każdym kubełku osobno zrób drugie hashowanie (dlatego to się nazywa dwupoziomowe).

**Algorytm**:

## Rodzina uniwersalnych funkcji hashujących
Niech $H$ będzie rodziną funkcji hashujących z $U$ (zbiór elementów-kluczy) w $\{0, 1, ..., m-1\}$ (zbiór indeksów tablicy).
Rodzinę $H$ nazywamy uniwersalną, jeśli **dla każdej** pary **różnych** elementów $\{x, y\}$ zachodzi $|\{ h \in H : h(x) = h(y)\}| = \frac{|H|}{m}$

## Rodzaje zadań "obliczeniowych" i "dowodowych"
*są też czasem "podaj definicję", ale te definicje są wyżej*

### Pamięć w słowniku statycznym
Musimy pamiętać kubełki, z których każdy zajmuje ${n_i}^2$ pamięci ($i$ - indeks kubełka) oraz $m+1$ funkcji hashujących (dla każdego kubełka + ta jedna, co rozrzuciła do nich elementy na początu). Łącznie:
$\sum_{0}^{m-1}{n_i}^2 + m + 1$.

### Oczekiwana liczba kolizji
*czyli zawsze to samo zadanie sformułowane na 10 różnych sposobów <3 (zabije się)*
odpowiedź:

**Ewentualna wariacja, w której chyba trzeba podać dowód**
odpowiedź:

# Wyszukiwanie wzorców

## Karp Rabin
1. Traktujemy znaki alfabetu jako liczby (indeksy)
2. Hashujemy słowa jako liczby w systemie o podstawie mocy zbioru znaków w alfabecie

Z = {a, b, c}
a=0, b=1, c=2, |Z|=3
przykład:
cab = 3^2 * c.index + 3^1 * a.index + 3^0 * b.index = 9*2 + 3*0 + 1*1 = 19

**Zaleta**: Łatwo się przesuwa w długim ciągu

**Wada**: Jak liczby wychodzą za duże, to często bierze się modulo i później nie wiadomo, czy równe hasze reprezentują te same słowa; dlatego, jak hasze się zgodzą, musimy jeszcze sprawdzić fragment literka po literce w $O(n+m)$.

## Maszyna stanów
*Idea*:
1. Zaczynamy szukanie, jak trafimy na `a`, to jesteśmy w stanie 1
2. Jak po `a` jest `b`, to przechodzimy do stanu 2, jak nie to spadamy znów do 0
...
4. Jak po stanie 4 będzie `c`, to skończyliśmy, jak `b`, to cofamy się tylko do 2 (czyli jakby mamy znów tylko `ab`), wpw. idziemy do początku
**Uwaga w kontekście KMP**: zauważmy, że w czwartym stanie nie musimy wcale rozważać trzech przypadków, a dwa
\- jeśli kolejna jest `c`, to sukces
\- jeśli nie, to cofamy się do stanu 1, po czym kolejny raz sprawdzamy tę samą literkę; jeśli jest to `b`, pójdziemy automatycznie do przodu, a jak nie, to wywali nas znowu na 0

## KMP
Maszyna stanów jest fajna koncepcyjnie, ale implementacyjnie to chuj. Spróbujmy ją zautomatyzować.
Na podstawie **uwagi** z poprzedniego podpunktu widzimy, że każdy stan możemy rozważać zero-jedynkowo - albo idziemy do przodu o 1 stan, albo cofamy się do określonego, wcześniejszego stanu.
Dlatego funkcja $\pi$ reprezentująca tablicę zmian stanów wygląda tak o:

### Budowanie $\pi$

## Shift-And
0. Tworzymy słownik zaznaczający wystąpienia
Następnie w każdej iteracji:
1. Robimy shift w lewo na `state` z dodaniem 1 na koniec
2. Kodujemy aktualną literę na nasz słownik
3. `And`ujemy zakodowaną literę i `state` i to jest nowy stan
...
4. Kończymy jak przepchniemy 1 na początek