###### tags: `AiSD`
# Egz część 1.

## 1. Jaka jesty oczekiwana liczba kolizji podczas umieszczania n elementów w tablicy haszującej o $n^{\frac{3}{2}}$ elementach przy użyciu funkcji losowo wybranej z uniwersalnej rodziny funkcji haszujących


m - rozmiar tablicy haszującej

1/m

$$\sum_{i=0}^{n-1} i \cdot \frac{1}{n^{3/2}}$$

$$ {n \choose 2} \cdot \frac{1}{n^{3/2}}$$

n po 2 * 1/n^(3/2)


## 2. Czy algorytm heapsort sortuje stabilnie

- NIE (2a, 2b,2c) -> (2b,2c,2a)

Jak mamy heapsort to on w trakcie działania jedyne co robi to patrzy czy priorytety są mniejsze/większe - usuwa ekstremum i wrzuca coś na jego miejsce. To jest miejsce, w którym może zepsuć kolejność. Dodatkowo coś może się zepsuć przy budowaniu kopca.

## 3. Do kopca wstawiono klucze 1,2,3,...,$2^{k-1}$. Wypisz wszystkie klucze które na pewno nie znajdują się w liściach tego kopca.

Załóżmy, że w korzeniu jest maksimum.

k = 3

1, 2, 3, 4

4 3 1 2

4 3 2 1
4 2 3 1

Skoro drzewo ma $2^{k-1}$ kluczy, czyli ma wysokość $k$.

Możemy zbudować ścieżkę prowadzącą od korzenia (maksimum) do liścia, taka ścieżka ma wysokość k-1 (krawędzi). Załóżmy, że na takiej ścieżce leżą elementy różniące się od siebie o 1, tzn. max, max-1, max-2, itd. Wtedy widać, że w liściach nie mogą leżeć te elementy.

## 4. Jakiej złożoności algorytm mnożenia liczb możemy otrzymać modyfikując algorytm Karatsuby w ten sposób, że liczby dzielimy na pięć części (a nie na dwie). Odpowiedź uzasadnij.


k = liczba części podziału

## 5. Podaj optymalny pod względem liczby wykonanych porównań algorytm znajdujący drugi co do wielkości element ciągu.

Robimy n-1 porównań, by znaleźć maksimum (zapamiętujemy informację o tym, kto wygrał i przegrał dane porównanie). Następnie szukamy maksimum w zbiorze elementów, które przegrały tylko z maksimum. W pierwszym kroku możemy zrobić turniej (drzewo binarne) o wysokości log(n), gdzie n to liczba elementów ciągu. Wysokość tego drzewa to log(n), zatem elementów, które przegrały tylko z maksem jestm log(n)-1. Czyli łącznie mamy n+log(n)-2 porównania

## 6. Przedstaw pseudokod operacji wstawiania klucza do drzewa splay używający jedynie stałej liczby operacji Splay() i stałej liczby operacji niskiego rzędu.


## 7. Ile operacji join wykona się podczas łączenia kopców dwumianowych (wersja eager) zawierających odpowiednio 53 i 35 elementów.

110101 100011

1  111    // przeniesienia
 110101
 100011
 +_____
1011000

Będą 4 operacje join. W ogólności wykona się ich tyle ile jest dodawań 1+1 lub 1+przeniesienie w dodawaniu binarnym liczby wierzchołków (ile jest dwóch jedynek nad sobą przy dodawaniu pisemnym).

## 8. O ile co najwyżej może zwiększyć się liczba drzew w kopcu Fibonacciego, zawierającym n kluczy wskutek wykonania pojedynczej operacji decrease key?
Podobno n-1

## 9. Ilu maksymalnie rotacji może wymagać wykonanie operacji delete w drzewcu pamiętającym n kluczy

O(dlugosc skrajnie lewej sciezki prawego syna + dlugosc skrajnie prawej sciezki lewego syna)

## 10. Po napotkaniu niezgodoności między literą tekstu oraz literą wzorca, algorytm KMP korzysta z funkcji $\pi$ by dokonać przesunięcia wzorca. Podaj przykład wzorca o długości 11, dla którego algorytm:
- może wykonać 6 takich przesunięc wzorca, zanim przejdzie do kolejnej litery tekstu i
- nigdy nie wykona więcej niż 6 przesunięć wzorca nad jedną literą tekstu


rozwiązanie: aaa aaa bba bb


## 11. Oszacuj z dokładnością do $\Omega()$ złożoność poniższego fragmentu pogramu

res <- 0
for i <- 1 to n do:
	j <- i
	while (j jest parzyste) j <- j/2
	res <- res + j

Zamortyzowany koszt to $\Omega(m)$ - pytanie brzmi dlaczego


Zauważamy, że każda liczba jest obarczona kosztem stałym, nie wliczającym się w koszt wykonania pętli -- jednostka. Liczba postaci n = 2k jest obarczona dodatkowym kosztem 1 -- koszt podzielenia jej jeden raz przez 2. Liczba n = 4k jest obarczona kosztem 3 -- koszt podzielenia dwukrotnie przez 2. Ogólnie liczba postaci $n = 2^m * k$ jest obarczona kosztem k. Zauważamy, że wszystkich liczb jest n, liczb podzielnych przez 2 jest n/2, podzielnych przez 4 jest n/4, ogólnie podzielnych przez 2^m jest n/2^m. Stąd możemy zapisać łączny koszt jako sumę kosztów jednostkowych przypisanych liczbom z danej grupy, tzn. $\sum_{i=1}^{log(n)} n / 2^i < 2n$. Innymi słowy, przypisujemy liczbie tyle jednostek kosztu, do ilu grup podzielności należy, np. 12 przypiszemy koszt 3, bo należy do grup liczb podzielnych przez 1, 2 i 4.

## 12. Zapisz w pseudokodzie procedurę znajdowania następnika elementu tu w strukturę van Emde Boasa. Napisz, jaką ma ona złożoność. Odpowiedź uzasadnij




Min i max jest trzymany osobno wiec nie trzeba sie wywolywac zeby go odczytać

## 13. Opisz redukcję (typu dziel i zwyciężaj) wykorzystywaną w algorytmie FFT.

A\[0](z) = a0 + a2 * z +a4 * z^2 + … +a(n-2) * z^(n/2 -1)

A\[1](z) = a1 + a3 * z +a5 * z^2 + … + a(n-1) * z^(n/2 -1)

A(x) = A\[0](x^2) + xA\[0](x^2)

Widzimy, że znika połowa punktów (bo liczymy to w pierwiastkach z jedności a zbiór n pierwiastków z jedności podniesiony do kwadratu da nam n/2 pierwiastków) oraz liczymy na wielomianach o połowę krótszych

Zatem złożoność to
$$
T(n) = T(n/2) + T(n/2).
$$


## 14. Przedstaw ideę konstrukcji sieci komparatorów, która sortuje ciągi bitoniczne. Jaka jest głębokość tej sieci.


## 15. W analizie problemu Union-Find wykorzystywaliśmy pojęcie rzędu wierzchołka. Ile conajwyżej może być wierzchołków o rzędzie $r$ po wykonaniu $n$ operacji UNION gdy te operacje wykonywane były:
- (a) w sposób zbalansowany
- (b) w dowolny sposób (tj. bez zbalansowania)

a) jest conajwyżej n/(2^r) wierzchołków rzędu r (bo wierzchołki o rzędzie r muszą być rozłączne więc może być ich tyle maks)

b) Może być ich liniowo wiele bo możemy zrobić coś takiego

Chyba jednak $\frac{n}{r}$

## 16. Narysuj drzewo decyzyjne dla klasycznego algorytmu scalania dwóch ciągów uporządkowanych A = <$a_1$,$a_2$> B = <$b_1$,$b_2$>


## 17. Napisz w pseudokodzie algorytm sortowania ciągów jednakowej długości. Jaka jest złożoność tego algorytmu.

1. Iterujemy po literach od końca.
2. Sortujemy stabilnie w czasie liniowym po kolejnych literach (np. counting sort).

Złożoność to $O(n*m)$, gdzie m to liczba ciągów, a n to ich długość, czyli złożoność jest liniowa względem **liczby** liter.

12345...n }
1234....n }
1234....n } m
1234....n }
1234....n }

## 18. Ile razy może zostać wywołana funkcja SELECTION w wierzu (d) poniższego algorytmu, jeśli tabli $T$ ma $n$ elementów?

Procedure SELECTION(k,T)
    (a) If |T| małe then sort(T) & return(T[k])
    (b) p <- "mediana median" jak w algorytmie magicznych piątek
    (c) U <- elementy T mniejsze od p
    (d) if K $<=$ U then return SELECTION(k,U)
        else return SELECTION(k - |U|, T \ U)

Uwaga: Zakładamy (na użytek tego zadania), że wyznaczenie p w wierszu (b) odbywa się bez wywołania funkcji SELECTION

T(n) = T(n/5) + T(7n/10) (normalnie )
T(n) = T(7n/10) (tyle bo nie liczymy mediany piatek)

n -> 7n/10 -> 49n/100 -> 7^3 / 10^3 -> ... -> 1 | $log_{7/10}n$

n -> n/2 -> n/4 -> ... -> 1 | $log_2n$

## 19. W algorytmie wyznaczającym optymalną kolejność mnożenia macierzy, opartym na programowaniu dynamicznym wyliczana jest wartość $m_{ij}$ równa optymalnemu kosztowi obliczenia iloczynu macierzy $M_i$ X ... X $M_j$. Podaj sposób obliczenia wartości $m_{ij}$


$m_{ij} = min_{i <= k <j}\{m_{i, k} + m_{k+1, j} + d(i-1)kj\}$

## 20. Podaj kolejnośćm w jakiej podzbiory będą dołączone do rozwiązania przez podany na wykładzie zachłanny algorytm dla problemu Pokrycia Zbioru (Set Cover) dla następujących danych:

- Uniwersum U = {$e_1, e_2,e_3, e_4,e_5$}
- podzbiory z ich wagami:
- $S_1 = {e_1, e_2,e_3} : w(S_1) = 9$
- $S_2 = {e_1, e_2,e_3, e_4,e_5} : w(S_2) = 12$
- $S_3 = {e_4,e_5} : w(S_3) = 5$
- $S_4 = {e_1, e_3,e_5} : w(S_4) = 6$

Koszt na element (niepokryty) = Koszt zbioru / |Niepokryte w tym zbiorze|.