---
# System prepended metadata

title: AISD

---

# 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
![image](https://hackmd.io/_uploads/Hyq7IsHBA.png)


# 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
![image](https://hackmd.io/_uploads/Sy6sXV7QC.png)


## 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:
![image](https://hackmd.io/_uploads/HkP9uLm70.png)

## Dwumian Newtona
Rekurencja:
![image](https://hackmd.io/_uploads/SJS9tI7X0.png)
Tabelka:
![image](https://hackmd.io/_uploads/SyQsKLXmA.png)

## 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:
![image](https://hackmd.io/_uploads/ByBt5547C.png)

## 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:
![image](https://hackmd.io/_uploads/Byrm8jEQA.png)


## 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.
![image](https://hackmd.io/_uploads/Hy75MOuQA.png)

Tabelka:
![image](https://hackmd.io/_uploads/rJjOzduXR.png)


# 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):
![image](https://hackmd.io/_uploads/SyyyiudX0.png)
Uzasadnienie:
![image](https://hackmd.io/_uploads/SydgoOumC.png)

## (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)
![image](https://hackmd.io/_uploads/HJfMbWc70.png)


## 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
![image](https://hackmd.io/_uploads/HyVwLZ9mC.png)
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.
![image](https://hackmd.io/_uploads/HkVDT-c7R.png)

# 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**:
![image](https://hackmd.io/_uploads/S1QerssQR.png)
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**:
![image](https://hackmd.io/_uploads/r1f_Msj7R.png)
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
![image](https://hackmd.io/_uploads/S1rIjjjXR.png)


# 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): 
```c
x = y.left 
y.left = x.right
x.right = y
```
![image](https://hackmd.io/_uploads/SkTCkd2X0.png)


## 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
![image](https://hackmd.io/_uploads/HyokQwO40.png)
2. $x$ jest **wewnętrzny** względem wujka
![image](https://hackmd.io/_uploads/HJpWQvdV0.png)

# 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
![image](https://hackmd.io/_uploads/rJ_UDfJHC.png)

## Kopce minimaksowe
*Idea*: na górze jest kopiec maksimum, na dole obrócony minium i są sklejone podstawami; reprezentacja listowa przeplata indeksy.
![image](https://hackmd.io/_uploads/BJJd9eDHC.png)
**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
![image](https://hackmd.io/_uploads/r1E__G1HR.png)

### Scalanie
**Giga proste** - wtasowujemy w siebie listy drzew od najmniejszych do największych (stopniem) i mergujemy duplikaty
![image](https://hackmd.io/_uploads/BJ_AOzJrC.png)
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)
![image](https://hackmd.io/_uploads/ByS2tM1BR.png)

### 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).
![image](https://hackmd.io/_uploads/Hkczuc4SC.png)
**Najważniejsza idea przy algorytmach operacji, to te przegrywy, które są opuszczane przez dzieci**
![image](https://hackmd.io/_uploads/BkycxIOU0.png)
![image](https://hackmd.io/_uploads/HkvigIOIC.png)


# 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}$
![image](https://hackmd.io/_uploads/HJ_e68_I0.png)


# 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ą.
![image](https://hackmd.io/_uploads/rypZeyQrC.png)
**Ś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)
![image](https://hackmd.io/_uploads/Sy_KbyQHC.png)

#### 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**:
![image](https://hackmd.io/_uploads/B1RGfymBA.png)

## 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
![image](https://hackmd.io/_uploads/H1hrUkmBC.png)
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ę)*
![image](https://hackmd.io/_uploads/Bk-t_1mrC.png)
odpowiedź:
![image](https://hackmd.io/_uploads/Bk_cdkXr0.png)

**Ewentualna wariacja, w której chyba trzeba podać dowód**
![image](https://hackmd.io/_uploads/BkfzFyXSR.png)
odpowiedź:
![image](https://hackmd.io/_uploads/rydVYJXrR.png)

# 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
![image](https://hackmd.io/_uploads/BkyNqEuUA.png)

**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
![image](https://hackmd.io/_uploads/Hk2ui4dU0.png)
*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.
![image](https://hackmd.io/_uploads/SJUm1BdUR.png)
Dlatego funkcja $\pi$ reprezentująca tablicę zmian stanów wygląda tak o:
![image](https://hackmd.io/_uploads/B1FExSOU0.png)

### Budowanie $\pi$
![image](https://hackmd.io/_uploads/BJeM-ruLC.png)


## Shift-And
0. Tworzymy słownik zaznaczający wystąpienia
![image](https://hackmd.io/_uploads/rJlQBS_UC.png)
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
![image](https://hackmd.io/_uploads/HkpELS_IC.png)

