###### tags: `AiSD`

# Notatka 0 Preeliminaria
1. Insert sort - czasowa O($n^2$), pamięciowa O(1)

2. Select sort - czasowa O($n^2$), pamięciowa O(1)!

3. Merge sort

procedura merge:

4. Algorytm euklidesa:

5. Rozszerzony algorytm euklidesa:

6. Algorytm DFS

7. Algorytm BFS


8. Algorytm sortowania topologicznego

9. Algorytm Kruskala:

10. Algorytm Prima

11. Algorytm Dijsktry

12. Algorytm Warshalla-Floyada

13. Mnożenie po rosyjsku:

14. Fibbonaci

# NOTATKA 1 - Kopce

- motywacja dla kopców to Algorytm Prima (kolejka priorytetowa)

- w korzeniu jest minimum/maksimum

- implementacja to tablica gdzie korzen to tab[1] (indeksujemy od 1), synowie korzenia to tab[2] i tab[3] itp.

- w tablicy synowie T[i] są pod indeksem T[2i] i T[2i +1]

- ojciec T[i] jest w T[i/2] (całkowite dzielenie)

- jeżeli element zmienił swoją wartość to może trzeba go przesunąć:
- jeśli wstawiony x jest mniejszy od starego elementu e to przesuwamy w górę (zamiana z ojcem jeśli trzeba, 1 porównanie)
- jeśli wstawiony x jest większy od starego elementu e to przesuwamy w dół (zamiana z mniejszym z synów jeśli trzeba, 2 porównania żeby znaleźć który mniejszy)

- w drzewie binarnym rozmiaru n jest sufit(n/2) liści

- budowanie drzewa ma złożoność $\theta(n)$. Budujemy go od końca (czyli wstawiając najpierw elementy na sam dół najpierw a potem idąc w górę). Czemu to jest git? No bo połowa elementów która jest na samym dole od razu jest dobrze posortowana(wstawiona bo nie było innych elementów więc nie jest zaburzony porządek kopcowy na tych nowych ścieżkach). Potem wstawimy n/4 elementy które trzeba przesunąc o maks 1 poziom w dół (czyli 2 porównania). Potem n/8 trzeba przesunąć o 2 poziomy w dół, n/16 o 3 i tak dalej

- basic heapsort: Wiemy, że minimum jest zawsze w korzeniu więc postępujemy następująco:
- minimum zamieniamy z ostatnim elementem i potem ten najmniejszy element przesuwamy w dół kopca na indeksach od 1 do n-1
- w kolejnym kroku znowu minimum zamieniamy z ostatnim elementem kopca (teraz juz ostatni jest pod indeksem n-1) i przesuwamy ten ostatni za pomocą przesuń w dół
- powtarzamy aż posortujemy tablicę (ona jest posortowana od końca).
- Zauważmy, że to przesunięcię w dół to jest około 2logn porównań (logn poziomów ale jak przesuwamy w dół to są 2 porównania)

- szybszy heapsort:
1. Najpierw wyrzucamy minimum które były w korzeniu. Powstaje nam dziura w kopcu (na samym szczycie). Wrzucamy w miejsce tej dziury mniejszego z synów (1 porównanie aby wyznaczyć który z nich jest mniejszy). Teraz dziura jset poziom niżej. Przesuwamy ją więc dalej aż dojedziemy na sam dół. Kosztuje nas to logn porównań
2. mamy juz dziurę na samym dole ale potencjalnie nie jest to kopiec (dziury w kopcu mogą być od prawej strony, nie może być sytuacji liść liść dziura liść liść). Zamieniamy zatem tą dziurę ze skrajnym prawym liściem.
3. Wszystko jest już na miejscu jednak ten zamieniony element może psuć porządek kopcowy. Trzeba więc go przesunąć wyżej. Teraz pytanie o ile (pamiętamy, że przesunięcie w górę o 1 poziom to 1 porównanie). Trzeba przesunąć maksymalnie do najwyższego wspólnego przodka tej dziury na dole i tego liścia. Oczywiście może się okazać, że to będzie np korzeń więc znowu będzie logn porównań. Okazuje się jednak, że średnio wystarczą dwa przesunięcia. Zatem koszt jednego "ruchu" to zamiast 2logn w basic heapsorcie otrzymujemy średnio logn + 2

- Pseudokody z wykładu

pytanie z egzaminu o elementy w liściach

Zakładamy ze w korzeniu jest maks

# Notatka 2 - zachłanne


- TODO: Szeregowanie zadań (na wykładzie skipnięte)

### SET COVER:
#### Strategie słabe:
- branie najliczniejszego podzbioru
- branie najtańszego podzbioru (n podzbiorów wielkości 1 o koszcie 1 i jeden wielki podzbiór który ma wszystko o koszcie 2)
#### Strategia gites
- bierzemy podzbiór o najmniejszej kwocie na niepokryty element (patrzymy które z danego podzbioru nie zostały jeszcze pokryte. Powiedzmy że dla i-tego podzbioru jest ich $x_i$. Wtedy koszt tego sposobu to koszt_podzbioru/$x_i$)
- Takie rozwiązanie jest maksymalnie o logn gorsze od OPTA

# Notatka 3 - dziel i zwyciężaj

Sortowania które używają tej strategi:
- merge sort

- quick sort

Bazowy Karatsuba (podział na 2 części)

Karatsuba (podział na 3 części)

Wzór ogólny

Znajdowanie min i max na raz
- wersja bazowa

- wersja dziel i zwyciężaj (UWAGA WERSJA NIEOPTYMALNA, UŻYWA WIĘCEJ NIŻ 3/2N -2)

# Notatka 4 - dziel i zwyciężaj v2

## Sieci przełączników:



## znajdowanie pary najbliższych punktów:

Idea:
1. Dzielimy zbiór punktów na dwa podzbiory A i B względem współrzędnej X.
2. Wyszukujemy najbliższą parę punktów w obu zbiorach rekurencyjnie (czyli dwa problemy rozmiaru n/2)
3. Teraz musimy sprawdzić takie pary że jeden punkt lezał w zbiorze A a drugi w zbiorze B
4. Załóżmy że odległość *d* to mniejsza z dwóch rozwiązań rekurencyjnych
5. Teraz jak mamy jakąś linię podziału zbioru A i B to bierzemy tylko punkty które są w odległości *d* od tego pasa
6. Mamy teraz coś takiego:
Czyli dwa rzędy szerokości d rodzielone linią podziału zbioru A i B
7. Teraz jedziemy punktami z A od góry i sprawdzamy punkty z B które są maksymalnie o d w dół. Znajdują się one w zacieniowanym kwadracie
8. Zastanówmy się ile jest punktów w takim kwadracie w B?
9. No jest ich maksymalnie 4 (jak umieścimy je w narożnikach)
10. Dlaczego? Bo wiemy, że punkty w B są minimalnie oddalone o *d* bo inaczej byloby inne minimum
Tu jeszcze wyjaśnienie graficzne, że w każdym takim kwadracie mogą być maks 4 punkty
11. Jako, że możemy nie wiedzieć łatwo które punkty są z A a które z B to po prostu możemy sprawdzać po kolei liste punktów (ale posortowaną względem wysokości) i dla każdego punktu sprawdzać 7 kolejnych (mogą być max 3 ze zbioru A i max 4 ze zbioru B)
12. Co ważne przed rozpoczęciem algorytmu sortujemy względem X i względem Y. Przez to złożoność to będzie O(nlogn) (sortowanie ma tyle, tak samo wywowałenie tego algosa)

Pseudokod:

# Notatka 5 - dynamiki
## Przechodzenie przez tablice najtanszym kosztem:
Zadanie - możemy iść w prawo, prawy górny i prawy dolny.
Pomysł: Zamiast trasy znajdźmy najpierw koszt najtanszego przejścia

Zauważmy, że jeśli mamy optymalną trasę i przejdziemy w niej z pola x na y to do x musieliśmy dojść optymalnie.

Uzupełniamy całą tablicę optymalnym kosztem dojścia do danego pola. Jak to robimy? wypełniamy kolumnami.

Jak potem odtworzyć trasę?

Trasę budujemy od końca. W ostatniej kolumnie znajdujemy najmniejsze pole i nazywamy je x. Potem patrzymy na 3 pola z których można było dojść do x. Wybieramy minimum z nich. Powtarzamy do ostatniej kolumny.

### zwykły LCS:
Mamy dwa ciągi X,Y które mają odpowiednio n i m znaków.

Pomysł najpierw znajdźmy długość LCS a potem spróbujmy go odtworzyć.
1. Rozpatrzmy przypadki:
1.1 Ostatnia litera obu ciągów jest taka sama. Wtedy długość takiego LCS to LCS(X_bez_ostatniej,Y_bez_ostatniej) +1.
1.2 Ostatnia litera Ostatnia litera obu ciągów jest inna. Wtedy długość takiego LCS to
max(LCS(X_bez_ostatniej,Y), LCS(X,Y_bez_ostatniej))

Algorytm: Tworzymy kwadratową tablicę gdzie tab[i][j] oznacza długość LCS dla ciągu X zbudowanego z i pierwszych liter oraz ciągu Y zbudowanego z j pierwszych liter.

Uzupełniamy wierszami (najpierw możemy uzupełnić 1 kolumny i 1 wiersz zerami bo mamy 0literowy ciąg). Teraz jeśli i-ta litera X i j-ta litera Y jest taka sama to wpisujemy w tablice 1+ tab[i-1][j-1]. W przeciwnym przypadku wpisujemy max(tab[i][j-1], tab[i-1][j])

Gdzie jest rozwiązanie? Rozwiązanie jest w ostatnim polu tablicy (tab[n][m]). Jednak co to jest za rozwiązanie? No jest to długość LCS. A jak z niego zbudować jak ten LCS wyglądał? W następujący sposób:

1. Zaczynamy z ostatniego pola tablicy (tab[n][m]) i patrzymy czy X_n i Y_m są takie same.
2. Jeśli tak to dodajemy do rozwiązania i idziemy po skosie w lewą-górę (tab[n-1][m-1])
3. Jeśli nie to wybieramy maximum z pól tab[n-1][m] i tab[n][m-1] a przechodzimy na nie.
4. Jeśli oba pola miały taką samą wartość to przechodzimy na dowolne z nich.
5. Powtarzamy aż dojdziemy do lewego górnego rogu (tab[1][1])

6. Pamiętamy, że mamy rozwiązanie "od końca" (ostatnia litera jest u nas 1)


# Notatka 6 - dynamiki v2

## Problem mnożenia macierzy:
(Macierze numerujemy od 1, tablice tez)

Założenie - macierz A rozmiaru axb oraz macierz B rozmiaru bxc -> złożoność mnożenia to axbxc a powstała macierz ma rozmiac axc

### $m_{ij}$ - optymalny koszt mnożenia macierzy 

Liczymy to dynamicznie w tabliny n x n

Najpierw dostajemy przekątną = 0 bo np koszt mnożenia M_3 x M_3 = 0

Potem uzupełniamy kolejne przekątne według wzoru na $m_{ij}$

### Jaki jest ogólny wzór na $m_{ij}$ ?


Gdzie jest wynik? W prawym górnymm narożniku (m_1n)

Złożoność:


## Odtwarzanie wyniku


No można np tak, że zapamiętujesz w każdym polu które k było optymalne
No i później bierzesz jakieś ij z wynikiem patrzysz jakie k tam jest no i czytasz rekurencyjnie jakie podziały były optymalne dla ik, k+1j
To jest takie klasyczne Catalanowe dynamikowanie się
Czyli np jak zaczynasz to bierzesz pole 1,n, no i tam masz np optymalne k=3, więc pierwszy nawias będzie po trzeciej macierzy, no i teraz nawiasujesz 1,3, 4,n, więc czytasz jakie k jest w tamtych komórkach i to Ci mówi gdzie postawić tam nawiasy i tak rekurencyjnie

# Notatka 7- dynamiki v3

## Problem plecakowy
### z powtórzeniami

### bez powtórzeń

## Gramatyka bezkontekstowa:

Vn -> symbole nieterminalne (pomocnicze)
Vt - symbole terminalne
p -> produkcje

Interesują nas grmatyki w postaci Chomskiego:
A -> XY
A -> a

Zauważmy, że jak chcemy wyprowadzić nasze słowo n-literowe to w pierwszym kroku musieliśmy zrobić jakieś XY bo z początkowego nie możemy inaczej zrobić n-literowego słowa


Widzimy ze zredukowalismy problem ze slowa nliterowego do dwóch słów krótszych. Niestety nie wiemy gdzie nastąpi podział więc jak przy macierzach musimy sprawdzić wszystkie miejsca.


To zbiór nieterminalni z których da się wprowadzić dane słowo. Nasze rozwiązanie będzie w m1n -> musimy sprawdzić czy nasz nieterminal tam był.


# Notatka 8 -dolne granice
Drzewo binarne o wysokości x ma 2^x liści (tak mówi Loryś ale nwm czy nie jest x-1)

- Comparision model
- w liściach jest wynik

Szkic dowodu, że sortowanie wymaga nlogn złożoności:

1. Musi być n! liści bo tyle jest permutacji.
2. n! >= 2^(wysokość drzewa) - jakaś właność dzrzew binarnych
3. logn! >= wysokosc_drzewa
4. ze wzroszu szterlinga logn! >= nlogn czyli mamy wynik

UNIQNES PROBLEM

Dane: Liczby x_1, x_2, x_3, ... ,x_n

Będziemy na to patrzeć jako na punkt w R^n

Idea: Wezmiemy n! punktów które są zbudowane jako permutacja liczb od 1 do n

Widzimy, że nasz algorytm dla każdego punktu musi dać odpowiedź TAK (bo taki jeden punkt w R^n nie ma żadnej tej samej współrzędnej)

Co chcemy pokazać? Że to muszą być różne liście( przypomnienie w liściu jest wynik)

Budujemy drzewo trynarne ( > = <)

Dowód:
Weżmy 2 punkty P_i, P_j

Szukamy pierwszej pozycji w której się różnią.

Powiedzmy że jest tam wartość że w P_j jest tam wartość k. Powiedzmy również, że jest to współrzędna o indeksie r Co to oznacza? Oznacza to, że w P_i w tym samym miejscu było coś większego od k (Bo jakby było mniejsze/równe to niebyłaby to najmniejsza wartość).

Dodatkowo w miejscu w którym w P_i jest k to w P_j jest coś większego (ta sama argumentacja). Powiedzmy , że ten indeks to l.

Teraz definijemy funkcje f(<x_1,x_2,..x_n) = x_r - x_l

Teraz f(P_i) > 0 (bo na r-tej pozycji w P_i było coś większego od k a na l-tej było k)

Dodatkowo f(P_j) < 0 (bo na r-tej pozycji w P_j było k a na l-tej było coś większego)

Teraz weźmy ten zbiór punktów z którymi dojdziemy do jakiegoś v. On jest wypukły (bo każdy do którego dojdziemy jest)

Powiedzmy, że w S(v) leżą punkty P_i i P_j. Skoro mają być w tym samym liściu to tak musi być. Teraz skoro to wielokąt wypukły to odcinek pomiędzy P_i i P_j też jest w tym S(v)

Zauważmy, że funkcja f jest ciągłą czyli skoro leci od czegoś dodatniego do czegoś ujemnego to musi przejść przez 0. Co to znaczy? To znaczy, żę x_r == x_l czyli powinna w tym liściu być odpowiedź "NIE" no ale w tym wierzchołku musi być odpowiedź "TAK" bo P_i i P_j są unikalne. Mamy sprzeczność. Widzimy więc, że one nie mogą być w jednym liściu. Czyli potrzebujemy n! liści więc drzewo ma wysokość nlogn

# Notatka 9 - adwersarz

IDEA: adwersarz który tak dobiera dane żeby dowolny algorytm się męczył

przykład: wyszukanie minmaxa i pokazanie, że potrzeba conajmniej sufit(3/2n-2) porównań

1. Tworzymy 4 zbiory A B C D
2. W A są na początku wszystkie
3. Do B trafiają wszystkie które wygrały jakieś porównanie i nie przegrały żadnego
4. Do B trafiają wszystkie które przegrały jakieś porównanie i nie wygrały żadnego
5. Do D trafiają takie które coś i przegrały i wygrały
6. Algorytm może podać wynik jak A puste, D ma n-2 elementów B i C po jednym

Strategia: wszystko w B jest większe od czegokolwiek z innej grupy. Wszystko z C jest mniejsze.

Widać, że każda liczba musi przejść przez zbiór B lub C aby trafić do D. 1 porówanniem można przenieść maks 2 liczby (kiedy porównujemy A z A). Z B można przenieść do D tylko 1 liczbe na 1 porównanie tak samo z C

Widzimy, że potrzeba sufit(n/2) (z A do b+c) + n-2 (z b+c do D) czyli łączeni sufit(3/2n -2)

# Notatka 10 - Sortowanie

## 1. Counting Sort/ Sortowanie przez zliczanie

Dane: ciąg liczb całkowitych (A[1....n])

Idea:

1 Przechodzimy po tablicy i zliczamy wystąpienia danej liczby
2. Po takim przejścu tab[i] = x oznacza, że i występuję x razy w ciągu początkowym.
3. Obliczamy sumy prefixowe - Przykład [3,1,2,1] -> [3,4,6,7]
Co nam to daje? Ano teraz tab[i] = x oznacza, że ostatnia liczba "i" będzie pod indeksem x
4. Przechodzimy tablice od końca ("i" od n do 1) oraz robimy scoreTab[tab[A[i]]] = A[i], tab[A[i]] = tab[A[i]] -1 (Czyli wpisujemy ostatnie wystąpienie cyfry pod odpowieni indeks - właśnie dlatego jedziemy od końca)

Złożoność O(n+k) gdzie k to najwyższa cyfra
Jest stabilny

## 2. Bucket Sort/Sortowanie kubełkowe

Założenie dostajemy liczby z przedziału <0,1> i liczby pojawiają się z rozkładem jednostajnym

Idea: dzielimy odcinek <0,1> na n przedziałów

Tutaj zdjęcie jak możemy takie przedziały zmapować na tablice i potem umieścić daną liczbę w odpowiednium kubełku
Te przedziały będziemy nazywać kubełkami

Taki kubełek to będzie lista (więc mamy tablice list)

Schemat działania:

1. Wszystkie pola tablicy zainicjalizuj pustą listą
2. Przejdź oryginalną tablicę A i dla każdego i wstaw A[i] w odpowiednie miejsce (B[podloga(n*A[i])])
3. Każdy kubełek posortuj za pomocą select sort
4. Połącz wszystkie kubełki w jedną tablicę

Czemu by to miało działać szybko? Korzystamy tu z tego, że dane powinny pochodzić z rozkładu jednostajnego. Zatem szansa że liczba trafi do B[i] jest 1/n. Możemy więc policzyć wartość oczekiwaną E[B[i]] i wychodzi ona równa 1. Czy to znaczy, że w każdym kubełku będzie 1 liczba? Oczywiście nie

Policzmy jednak oczekiwany czas działania

Stwórzmy zmienną Z_i = liczba elementów w i-tym kubełku
sortowanie i-tego kubełka to (Z_i)^2.

Legenda głosi, że jak używając tego policzmy całkowity czas działania(jest w cormenie) to wychodzi O(n) **TODO:** SPRAWDZIĆ TO

## 3. Sortowanie leksykograficzne (ciągi tej samej długości)

Dane: A_1...A_n - ciągi elementów nad jakimś alfabetem które mają długość d

Idea: W i-tym kroku Rozrzucamy po kubełkach (gdzie każdy kubełek to symbol alfabetu) względem (d-i)tej litery (czyli jedziemy od końca)

Przykład: Krok zerowy

Po takim kroku otrzmujemy:

Teraz będziemy rozrzucać względem przedostatniej litery i otrzymamy 

Otrzymamy:

Co ważne podczas rozrzucania zostawiamy względny porządek zachowany (musi być stabilnie)

Widzimy teraz, że są posortowane względem 2 litery ale porządek względem 3 też jest zachowany czyli są posortowane względem 2 ostatnich liter. Jakbyśmy powtórzyli jeszcze raz to dostaniemy względem 3 liter czyli byłoby całościowe posortowane.

Złożoność: Zakładamy, że w kubełku sortujemy counting sortem cztyli jest sortowanie liniowo. Otrzymamy więc d iteracji (bo po każdej literze) i w takiej iteracji wykonuejmy pracę (n+k) -> mamy k-kubełków i n słów a trzeba odwiedzić każdy kubełek ( i każde słowo gdzieś wrzucić)

Sumarycznie złożoność to O(d(k+n)). Jeśli rozmiar alfabetu nie jest innego rzędu niż n to jest to liniowe względem d*n (a d*n to rozmiar naszego problemu bo mamy n słów d-literowych)

## 4 Sortowanie leksykograficzne (ciągi różnej długości)

1 Pomysł -> do słowa dorzućmy literę spoza alfabetu która jest mniejsza od każdej litery z alfabetu. Dorzucamy tak długo aż wszystkie będą tej samej długości.

Czemu odrzucamy ten pomysł?

Bo ma to złożoność n*długość_najdłuższego_słowa. A co jest rozmiarem problemu ? n*suma_długości_słów. Niestety pierwsza wartość może być nawet kwadratowo większa od drugiej

2 Pomysł -> sortujmy od końca ale pomijamy słowa które nie mają danej długości. Jak się pojawi nowe słowo (czyli zmniejszyliśmy długość i już jest takie słowo) to dorzucamy je na sam początek dzięki czemu jest zachowana zasada, że słowa są posortowane względem "i" ostatnich liter (ale tylko te które rozpatrujemy).

Problem? Dużo pustych kubełków do których trzeba zaglądać.

Rozwiązanie? Tworzymy ze słowa pary <i-ta cyfra, i-ta litera>
np abac wygeneruje <1,a><2,b><3,a><4,c>
Posortujmy to leksykograficznie (wszystkie słowa wygenerują jakąś liczbę ciągów 2 elementowych więc mamy tą samą długość każdego ciągu). Teraz sortując po i-tej literze widzimy które litery mogły się pojawić (ponieważ wszystkie wystąpienia liter na np 4 pozycji są obok siebie) więc wiemy gdzie wchodzić

## Izomorfizm drzew jako przykład użycia sortowania

Jak mamy ukorzeniowe drzewo to mozemy jechać od dołu i jakoś kodować wierzchołki a potem sortując leksograficznie łatwo porównać czy na danym poziomie jest to samo.

# Notatka 11 QuickSort

## IDEA:
Wybieramy wartość pivot i w tablicy ustawiamy na lewo elementy mniejsze równe a na prawo większe

Co jest problemem? Wybór pivota

## Sposoby wyboru pivota

1. Wybieramy 1 element w tablicy. Czy jest gites? No niedokońca bo jak już było posortowane to dostaniemy złożoność kwadratową (bo dzielimy problem na podproblemy rozmiaru 1 i n-1)

2. Wybieramy losowy element. Prawdopodobnie nie będzie to czas kwadratowa (jakaś trudna matma) ale może się tak zdarzyć

3. Wybieramy mediane. Jaki jest problem? No trzeba znaleźć mediane w czasie liniowym. Da się ale stała nas nie zadowala

## Analiza losowego wyboru pivota

Przyjrzymy się jednak losowemu elementowi


Z prawdopodobieństwem 1/2 zrobimy podział w którym dłuższa część ma max 3/4 elementów. Potem znowu 3/4 z 3/4 itp. Jednak to sie dalej złoży do logarytmu (tylko inna podstawa). Widzimy też, że z wielkim prawdopodobieństwiem powinniśmy co jakiś czas trafić dobrze. Co się stanie jak np co 10 - no dalej dostaniemy logarytm (tylko zamiast lgn dostaniemy 11logn).

Teraz jakaś magia z oszacowaniem złożoności

1. Rząd elementu w tablicy -> rank(x) to liczba elementów które są nie większe od x (w tablicy)

Tak rozkładają się podziały na 2 tablice w zależności od ranka pivota
Po prawej prawdopodobieństwo wystąpienia podziału

W tym wzroku są po prostu wszystkie przypadki

Teraz możemy wywalić to T(1) + T(n-1) bo T(1) ma stałą złożoność a T(n-1) maksyamlnie kwadratową. Jak przemnożymy przez 1/n to dosatniemy coś liniowe więc wrzucamy w O(n)

Mamy więc coś takiego:
Widzimy że każdy skłądnik jest dwa razy bo T(1) + T(n-1) to to samo co T(n-1) + T(1) (odpowiednio d=1 i d=n-1). Czyli możemy skleić coś takiego

Teraz robimy oszacowanie z góry (no bo podejrzewamy, że to powinno działać w nlogn)


Co teraz? Najpierw bierzemy b większe od T(1) - czemu? Żeby dno rekursji które wykonuje się w czasie stałym było ograniczone przez to b

i teraz dzieje się jakaś magia

# Notatka 12 Selekcja

## Szkic problemu:
Szukamy algorytmu który szybko wyznaczy nam k-ty co do wielkości element ciągu T.

## Algorytm magicznych 5
1. Algorytm magicznych piątek - dzielismy zbiór na zbiory 5 elementowe. W każdym zbiorze znajdujemy mediane. Potem znajdujemy mediane tych median i nazywamy ją x. Dzięki temu mamy zbiór w którym jest na pewno conajmniej 3/10 elementów większych od x oraz zbiór w którym jest na pewno conajmniej 3/10 elementów mniejszych od x.

Po co nam to? Ano dlatego że chcemy napisać SELECTION(k) który zwraca k-ty element Tablicy


Co jest problemem tego algorymtu? Wyznaczenie p. Zauważmy, że od niego zależy redukcja rozmiaru problemu. Jeśli wybierzemy p takie, że będzie tylko 1 element w U to mamy redukcje z n do n-1 czyli słabo.

## Użycie magicznych 5 w selection

I tutaj wlatują magiczne 5 wraz z dodatkowym pytaniem. Jak znajdujemy mediane median. Robimy to używając funkcji SELECTION do wybrania środkowego elementu (tak dobrze widzicie do napisania SELECTION potrzebujemy magicznych_5 które potrzebują SELECTION). Teraz zastanówmy się jaka następuje redukcja problemu. (Przy założeniu, że to działa)

Mamy problem rozmiaru n. Możemy zapewnić, że w U będzie conajmniej 3/10n elementów. Wybieramy gorszą opcję czyli, że rozwiązanie znajduje się w pozostałych 7/10. Czy to już pełna redukcja? Nie - na każdym poziomie musimy jeszcze znaleźć mediane median więc wykonujemy selection na zbiorze o rozmiarze n/5 (bo tyle jest tych median). Czyli na każdy poziom przypada redukcja z n do 9/10n. Czyli stonks mamy super nierównośc i wynik z kosmosu, że to jest liniowe


## Algorytm Hoare'a
Algorytm Hoare'a - to samo co Selection tylko element dzielący wybieramy losowo.

Uznajmy, że dobry wybór p to taki, że co najmniej 1/4 elementów jest mniejsza/większa. Szansa na taki strzał to 1/2 więc co jakiś czas musimy trafić dobrze i to już starczy (Przykładowo szansa,że nie trafimy 100 razy jest już znikoma. Zatem możemy "założyć", że co ten 100 na pewno trafimy i dostaniemy wtedy co 100 kroków logarytmiczne zejście czyli stała razy logarytm).

## Lazy select:
Idea: Wybieramy jakąś próbke z głównego zbioru i ten nowy podzbiór nazywamy R. Oczekujemy, że jeśli uczciwie losowaliśmy elementy do tego R to na środku powinna być mediana.

Chcemy wyznaczyć takie elementy d i u w tym zbiorze R, że jest mało elementów takich, że: 
Teraz co to znaczy mało? To znaczy, że C można posortować w liniowym czasie. Z drugiej strony w C ma być jednak na tyle dużo elementów, że do C należy mediana głównego zbioru.

Jak duży jest podzbiór R? Zawiera on n^(3/4) elementów (ale losuje ze zwracaniem więc można kilka razy ten sam wylosować)

Teraz na środku R powinna być mediana więc wybieramy gdzie jest d i u. Stwierdzamy, że będzie to pierwiastek(n) od środka

Co jeśli jednak w tym przedziale nie ma mediany albo jest za dużo elementów w C? No jak za 1 razem jest duża szansa na sukces to za drugim będzie większa. Zatem warto powtórzyć.

To też działa liniwo bo jeden przebieg jest liniowy, a oczekiwana wartość powtórzeń to 2.


# Notatka 13 - Drzewo AVL

Słownik - struktura która pamięta klucze
operacje: insert,delete,find

## Drzewo avl - definicja

Czym jest drzewo AVL ? To drzewo BST w którym dla każdego wierzchołka wysokość lewego i prawego poddrzewa różni się maksymalnie o 1.

Przykładowe drzewo AVL (chyba, że loryś sie powalił)

## Analiza wysokości

Spróbujmy powiedzieć coś o złożoności

zdefiniujmy funkcję p(i) - jest to liczba pustych wskaźników w minimalnym(czyli drzewie zawierającym najmniej wierzchołków jak to możliwe) drzewie AVL o wysokości i

kilka minimalnych

drzew w raz z ich pustymi wskazniakmi (puste sa na czarno)

Czy możemy to tworzyć schematycznie? Tak - musi być wierzchołek i dwa poddrzewa jeden o wysokości i-1 a drugie o wysokości i-2. Oba te poddrzewa również muszą być minimalne

Wtedy otrzymujemy wzór p(i) = p(i-1) + p(i-2). Pierwsze dwa eleemnty wyznaczamy ręcznie żeby rekurencja nie wybuchła. Widzimy, że to wygląda jak fibonacci (może lekko przesunięty). Co o nim wiemy? Rośnie wykładniczo

Wiemy też, że jak mamy n wierzchołków to mamy n+1 pustych wskaźników. Skoro n-wierzchołkowe miało wysokość "i" oraz n+1 jest ograniczony przez mniej więcej i-tą liczbę fibonnaciego to dostaniemy że jest wysokość drzewa jest logarytmiczna

Widzimy więc, że jest o co grać bo operacje by miały złożoność logarytmiczną. Pytanie jak wykonywać inserta/delete na drzewie AVL żeby dalej było AVL

## OPERACJE NA AVL

### Operacja find
tak jak w BST czyli jak element jest większy od szuaknego to idziemy w lewo a jak mniejszy w prawo

pozostałę operacje wymagają rotacji:

### Operacja rotacji
Rotacja to operacja która zmienia korzeń nie zmieniając przy tym balansu w drzewie (czyli dalej jest BST)

Rotacje:

parametrem operacji jest wierzchołek który zmieni swoje miejsce z ojcem. Jak widać koszt takiej operacji jest stały (kilka przepięć wskaźników)

### Operacja Insert:

1. Wstawiamy normalnie jak w bst
2. W każdym wierzchołku mamy 2bitową informacje o stanie (wysokość jego dzieci może być taka sama, lewe może być o 1 większe albo o 1 mniejsze)
3. Szukamy najniższego wierzchołka na którym nastąpilo zaburzenie porządku.
4. Załóżmy, że dodaliśmy do lewego poddrzewa. Co wiemy o elementach? Sytuacja musiała być jak na rysunku
czyli w L oba podrzewa były równe a w M prawe bbyło niższe (w innym przypadku M nie byłoby najniższym wierzchołkiem na którym coś nie działa)
Rozpatrzym przypadki:

1. Dodaliśmy coś do lewego poddrzewa L (alfy) -> robimy rotacje w L i został przywrócony balans
3. Dodaliśmy coś do prawego poddrzewa L -> robimy rotacje w prawym poddrzewie L -> robimy rotacje w tym samym wierzchołku co przed chwilą.

Czy trzeba coś poprawić jeszcze? Nie - dlaczego?

Zauważmy jaka była wysokość przed wstawieniem w obu sytuacjach -> było to 2+ Beta

Widzimy, że w pierwszym przypadku po rotacjach też dojdziemy do takiej wysokości

W drugim również jest taka (bo na początku alfa = beta)

Otrzymaliśmy zatem taką samą wyskość jak przed wstawieniem Co to znaczy? No że wyżej jest gitówa bo wcześniej było dobrze to jak jest ta sama wysokość to dalej jest dobrze. Niżej też jest dobrze bo M było najniższym w którym jest źle

### Operacja Delete

Gdzie jest ten element g'? Jest to element skrajnie prawy z lewego poddrzewa. Czemu jeśli nie jest on liściem to jego syn jest? Zauważmy, że wysokość prawego poddrzewa g' to 0. Zatem lewa to maksymalnie 1 inaczej nie byłoby to AVL

W ilu wierzchołkach trzeba naprawić aby odzyskać balans? No trzeba potencjalnie na całej drodze od tego liścia do korzenia. Może się zdażyć tak, że będzie to logarytmicznie wiele

## Koszt operacji:

Wszystkie operacje mają złożoność O(logn)

Do czego można użyć AVL ? Do implemetnacji listy

# Notatka 14 - drzewa czerwono czarne i B-drzewa

## Definicja


## Czarna wysokość - definicja

Czarna wysokość - liczba czarnych wierzchołków na każdej scieżce z danego wierzchołka (ale bez tego wierzchołka)

## Dowód o czarnej wysokości

Jak pokazać, że jest to sensowna konstrukcja? Indukcja po wysokości wierzchołka
### Teza - dla każdego wierzchołka v liczba wierzchołków pod v jest >= $2^{bh(v)}-1$
Chcemy udowodnić, że

Gdzie bh(v) to czarna wysokosc

### Podstawa dla h=0
robi sie sama (jeden wierzcholek i 0 dzieci)

### Krok indukcyjny

mamy sobie wierzchołek v i jego dwóch synów u i u'
Załóżmy, że u' jest czarny a u czerwony (strzelimy dwa przypadki na raz dzieki temu)

#### Czarna wysokość dzieci v
zauważmy, że bh(v) = bh(u) (bo u czerwony więc wszystkie czarne są gdzieś niżej i wysokość v też nei wzrośnie)

widzimy też że bh(u') = bh(v) - 1 (bo u' czarny więc podbił czarną wysokość v)

Wiemy, że dzieci mają spełnioną tezę indukcyjną więc mają conajmniej (wybieramy przypadek bh(u') bo daje on mniej wierzchołków) $2^{bh(v)-1}-1$ wierzchołków.

#### Oszacowanie minimalnej liczby wierzchołków w drzewie v

Czyli ile wierzchołków ma drzewo zaczynające się w v?
2 * ilość wierzchołków dzieci + 1.

Możemy to rozpisać jako $2 \cdot (2^{bh(v)-1}-1) + 1$
A to jest równe $2^{bh(v)}-1$ co kończy dowód

## Dowód na wysokość drzewa

Wiemy teraz jak liczba wierzchołków ma się do czarnej wysokości. Jednak my chcemy to porównać ze zwykłą wysokością. Chcielibysmy pokazać,że ta wysokość jest ograniczona przez log(n)

### Ograniczenie wysokości za pomocą czarnej wysokości
Zauważmy,że wysokość drzewa jest <= od $2 \cdot *bh(v)$

Skąd to wiemy? Zauważmy, że chcemy jak najbardziej wydłużyć wysokość drzewa względem czarnej wysokości. Jak to zrobić? Dodać czerwone wierzchołki. Ile możemy ich dodać? No możemy conajwyżej to poprzeplatać bo jak wierzchołek jest czerwony to jego syn musi być czarny. Czyli widzimy, że jesteśmy w stanie conajwyżej wydłużyć dwukrotnie czarną wysokość.

Czyli $\frac{h}{2} <= bh(v)$

Skoro n >= $2^{bh(v)}-1$ to korzystając z nierówności wyżej otrzymujemy n >= $2^\frac{h}{2}-1$

Otrzymujemy, że wysokość drzewa jest <= 2log(n+1)

### Wersja z cormena


## Operacje:

### Operacja Insert

- dodajemy jak w zwykłym bst i malujemy na czerwono.

Sprawdźmy które warunki mogły się zaburzyć

1. Każdy wierzchołek jest czerwony albo czarny - działa

2. Każdy liść jest czarny - dalej prawda bo liście to puste wskaźniki więc ten czerwony stworzy dwa liście

3. Jeśli wierzchołek jest czerwony to obaj synowei są czarni - to może się popsuć

4. Na każdej ścieżce z danego wierzchołka do liścia jest jednakowa liczba czarnych wierzchołków - dodaliśmy czerwony więc sie nie zmienia

## B-drzewa

motywacja, olbrzymie slowniki ktore musza byc w pamieci zewnetrznej - czesc drzewa jest w pamieci operacyjnej i jest szybka a reszta jest w pamieci zewnetrznej i tam juz dostep jest wolniejszy

### Właściwosci:
- wszystkie liście lezą na tej samej głębokości
- Każdy węzeł zawiera wiele elementów zbioru (są one uporządkowane)
- Drzewo rośnie od liści do korzenia: jeśli jakiś węzeł jest pełny to tworzony jest jego nowy brat, który przejmuje od niego połowę elementów a jeden z jego elementów (środkowy) wędruje wraz ze wskaźnikiem na nowego brata do ojca. Jeśli w ten sposób podzielony zostanie korzeń, to tworzony jest nowy korzeń, a stary będzie jednym z dwóch jego synów. Jest to jedyny moment, w którym może wzrosnąć wysokość B-drzewa

### TODO: dokończyć

# Notatka 15 - kopce dwumianowe

## Idea:

Po co ta struktura? Potrzebna jest kolejka priorytetowa złączalna

kopiec dwumianowy: wiele drzew dwumianowych ktore maja zachowany porzadek kopcowy (każda scieżka od liści do korzenia są same wartości rosnące/malejące czyli w korzeniu musi też byc maksimum/minimum)

## Definicja drzewa dwumianowego

Czym jest drzewo dwumianiowe?


ite drzewo powstaje przez połączenie dwóch drzew i-1

ite drzewo ma 2^i wierzchołków

## Rodzaje kopców dwumianowych
są dwa rodzaje kopców dwumaniowych:

- eager (klasyczna)
- lazy

## Definicja kopca dwumianowego eager
wersja eager:
kopiec będzie się składał z drzew dwumianowych (maksymalnie 1 dla każdego i). Kopiec mają 13 wierzchołków jest zbudowany z drzew dwumianowych których wierzchołki sumują się do 13

## Operacje na drzewie dwumianowym
operacje które chcemy zbudować:
- makeheap(i) -> tworzy kopiec 1 elementowy czyli 1 wierzchołek
- insert
- min/max (ekstremum)
- deletemin/max
- meld (łączenie kopców)
- join (ale to jest metoda prywatna) metoda która łączy dwa drzewa dwumianowe tego samego rzędu (Bi +Bi = B(i+1)). Te drzewa połączą się korzeniami zatem musimy tak je dobrać, żeby zachować porządek kopcami (albo pierwsze pod drugie albo drugie pod pierwsze) Koszt: O(1)

Ważne: drzewa dwumianowe to nie są drzewa binarne

## Definicja rzędu drzewa w kopcach dwumiaonych

rząd drzewa: stopień korzenia

## Sposób pamiętania drzew

Jak pamiętamy drzewa:

każdy wierzchołek pamięta klucz i wskaźnik na syna, dodatkowo każdy syn pamięta wskaźnik na jakiegoś brata (lista cykliczna)

## Przykład operacji join

Przykład joina:

## Ile jest drzew w kopcu dwumianowym
w kopcu o n kluczach jest conajwyżej log n drzew. Jak to pokazać? Zauważmy, że maksymalny rząd drzewa o n wierzchołkach jest logn. Dlaczego? bo drzewo itego rzędu ma 2^i wierzchołków. zatem jakbyśmy mieli rząd większy niz logn to dostalibyśny więcej niżn wierzchołków. A skoro dla każdego i mamy conajwyżej 1 drzewo no to od 0 do logn jest maks logn drzew

## Sposób pamiętania kopca
Dodatkowo skoro dla każdego i mamy maks 1 drzewo to możemy mieć tablice B gdzie B[i] to albo wskaźnik na i-te drzewo dwumianopwe (jeśli występuje) albo null jak nie ma takiego drzewa


## Operacje na drzewie dwumianowym eager

implementacja operacji:

### Operacja find min

Znajdowanie minimum:
przykład: kopiec dwumianiowy który ma 13 wierzchołków
Wiemy, że minimum jest w którymś z korzeni.
Żeby nie dokładać sobie pracy to oprócz kopca pamiętamy,też zmienna MIN która wskazuje na drzewo w ktorego korzeniu jest minimum

## Operacja MELD

MELD(A,B):

korzystamy z takich tablic B[i] i mamy trzy przypadki:

1) B[i] != null tylko w jednym kopcu -> do tablicy wynikowej przepisujemy ten wskaźnik który nie był nullem
2) B[i] != null w obu (mamy dwa drzewka B[i]) łączymy je, zapamiętujemy gdzieś obok drzewo B(i+1) które z nich powstało i idziemy dalej
3) B[i] != null w obu oraz mamy trzecie, zapamiętane -a dowolne z nich wpisujemy w do B[i] a pozostałe dwa łączymy i zapamiętujemy tak jak w przypadku 2

Jak widać dla każdego i jest koszt stały. Musimy przejść po wszystkich "i". Mamy maks logn kluczy więc koszt melda to logn.
Co Warto zauważyć?

Po 1 korzystamy że jak mamy jakieś większe drzewo i małe drzewo no to jak przepiszemy wszystko z małego + to się przełączyło (??????? nie wiem o co tu chodzi)

### Operacja insert

insert(i,k): przyjmuje on wartość do wstawienia i numer kopca do którego wstawiamy (potencjalnie może być wiele kopców bo robimy tą strukturę żeby łączyć kopce)

musimy zachować, że drzewa każdego rzędu jest maksymalnie 1

insert(i,k) -> meld(k,makeheap(i))

### Delete min
Delete min:

Wiemy w którym drzewie jest minimum. w korzeniu tego drzewa jest minimum. Jeśli drzewo ma rząd r to w korzeniu są dzieci o stopniach od 0 do r-1

Widać to na tym zdjęciu, że jak utniemy w ostatnim które ma r=3 korzeń to zostanie r=0,1,2

Jak widzimy dostaniemy drugi kopiec zbudowany z drzewo od 0 do r-1.

Robimy meld i mamy koszt O(logn)

## Szacowanie kosztu operacji insert (eager)
Zatem koszt inserta to też logn bo meld ma logn maksymalnie.

Pytanie czy jest to dobre szacowanie -> jak robimy dużo insertów (dajmy na to n) to czy koszt będzie nlogn?

No więc zauważmy, że jak łączymy dwa kopce to niekoniecznie musimy je przejść oba całe -> jeśli to mniejsze się skończy i dodatkowo już nie pamiętamy nic na boku (czyli czegoś co powstało z przypadku 2 lub 3) to dalej przepiszemy dokładnie to co jest w większej. Więc po co to przepisywać lepiej skorzystać z tej tablicy w której to jest.

Możemy to zatem sprowadzic do zmiany cyfr w dodawaniu binarnym -> to co pamiętamy z boku to przeniesienie, null to 0 a brak nulla 1.


## Kopiec dwumianowy wersja lazy

Kopce w wersji lazy:

Co chcemy osiągnąć? Żeby każda operacja oprócz delete min trwała czas stały a delete min trwał logn. Czyli meld musi trwać O(1)

## Lazy vs eager - główna róznica
Co się zmienia? Nie ma ograniczenia na liczbe drzew B[i] w kopcu

## Budowa kopca dwumianowego lazy
Teraz kopiec nie będzie tablicą drzew a listą (nieuporządkowaną cykliczną)

## Operacje na kopcu dwumianowym lazy
operacje:

### Operacja meld
Meld(k,h) -> łączymy listy i wybieramy nowe minimum czyli czas stały

### Operacja insert

insert dalej tak samo czyli stały

czyli:
insert(i,k) -> meld(k,makeheap(i))

### Operacja findmin
findmin dalej tak samo

czyli:

Mamy wskaźnik na drzewo które pamięta minimum. Jest ono pamiętane w korzeniu tego drzewa. Zatem mamy stały dostęp do pola z tym wskaźnikiem i nie musimy szukać

### Operacja delete min

delete min: (tu zaczyna się zabawa i analiza zamrtyzowana.)

Operacja dziala tak ze musi znalezc drzewo ktore ma mina (łatwe bo mamy wskaznik) usunąć roota i dodać nowe drzewa. Dodatkowo tutaj chcemy aby po takim delete min było to samo co było cały czas w wersji eager czyli maks 1 drzewo każdego rodzaju (każdego i). Widzimy, że może tak nie być bo po prostu nowe drzewa wrzucamy do listy nie sprawdzając czy taki rząd już był.

## Analiza operacji delete min w wersji lazy

Widzimy, że jednostkowy koszt delete min może być rzędu O(n) np jak zrobilismy n insertów i nic więcej (czyli mamy n drzew 1 wierzchołkowych)

Zamortyzowany kosz delete min to O(logn)

Dowód się robi na kredytach - jeśli uda się utrzymać niezmiennik kredytowy bez oszukiwania to udowodniliśmy

### niezmiennik kredytowy

Tutaj niezmiennikiem będzie, że każdy korzeń drzewa ma 1 kredyt

### Kredyty na poszczególne operacje

### Ile drzew maksymalnie może dodać delete min (eager)
Uwaga do screena - czemu delete min może dodać co najwyżej logn drzew? No bo maksymalny rząd to logn więc maksymalnie tyle nowych drzew powstanie

Ten dowód kredytowy to jest ukryta indukcja.

aisd 2: https://hackmd.io/CjMKVKx2SDSe-m26mXx8og