Autor: @Sztakler

# AiSD Egzamin Poprawkowy 2017

### Zad. 1

Mamy dwa ciągi A i B, o długości odpowiednio n i m. Niech LCS(A,B) to najdłuższy wspólny podciąg obu tych ciągów, a $A_x$ oznacza x-literowy prefiks ciągu A. Korzystamy z następującej zależności rekurencyjnej:
* $LCS(A_i, B_j) = 1 + LCS(A_{i-1}, B_{j-1})$, jeśli $A_i$ oraz $B_j$ kończą się na tą samą literę,
* $LCS(A_i, B_j) = max(LCS(A_i, B_{j-1}), LCS(A_{i-1}, B_j))$, jeśli kończą się na różne litery.

M[n][m] = 0 // wyzeruj tablicę
for i = 0 to n:
    for j = 0 to m:
        if A[i] == B[j]:
            M[i][j] = 1 + M[i-1][j-1]
        else:
            M[i][j] = max(M[i][j-1], M[i-1][j]) 
return M[n][m]            

Powyższy algorytm wyznacza długość najdłuższego wspólnego podciągu A i B. Sam LCS wyznaczamy, cofając się po tablicy, stosując tę samą zależność rekurencyjną, co wcześniej.

### Zad. 2
Operacja decreasekey zmniejsza wartość klucza i odcina go, jeśli przestaje spełniać porządek kopcowy. Jeśli ojciec tego wierzchołka wcześniej utracił syna, teraz należy odciąć także jego samego i sprawdzać rekurencyjnie kolejne wierzchołki wyżej na ścieżce do korzenia. Może się zdarzyć, że operacja przejdzie w ten sposób całą długość ścieżki do korzenia, która wynosi O(logn), ponieważ liczba wierzchołków w drzewie Fibonacciego jest wykładnicza względem rzędu.

### Zad. 3

Tak, wystarczy rozważyć drzewo o korzeniu $y$ z dwoma poddrzewami $l$ i $r$ o wysokościach $h_l$ i $h_r$. Jeśli $h_l \leq h_r$, wtedy splay na korzeniu drzewa $l$, tj. splay($x_l$) sprawi, że $x_l$ stanie się ojcem $y$, przez co wysokości $h_r$ wzrośnie o 1.

Po wykonaniu find(1):

### Zad. 4
Pamiętamy z wykładu, że dla zbioru $n$ kluczy istnieje drzewiec dla dowolnego przydziału priorytetów, co więcej, jeśli są to **różne** priorytety, wtedy taki drzewiec jest jedyny.


Oznacza to, że możemy zbudować dokładnie jeden taki drzewiec.

### Zad. 5

*Element Uniqueness* to problem polegający na określeniu, czy dany zbiór składa się z parami różnych elementów. Model liniowych drzew decyzyjnych pozwala pokazać, że dla danego zbioru danych istnieje $n!$ ścieżek, prowadzących do różnych liści, gdzie liście są odpowiedzią na pytanie zadane w problemie, tzn. "TAK" lub "NIE", a zatem długość ścieżek jest $\Omega (n\ log\ n)$. Model zwykłych drzew decyzyjnych nie pozwala nam na przeprowadzenie takiego dowodu, ponieważ wymaga on, by liście drzewa decyzyjnego były różne, np. by każdy z nich zawierał inną permutację elementów na wejściu, a problem *Element Uniqueness* zwraca jedynie dwie możliwe odpowiedzi.

### Zad. 6

Do wyznaczania położenia elementu $x$ stosujemy funkcję $h(x, i) = (h_1(x) + ih_2(x))\ mod\ m$. Sprawia ona, że w przypadku i-tej kolizji przesuniemy wyznaczoną pozycję o wartość wylosowaną przez drugą funkcję haszującą $h_2$.

### Zad. 7

Pamiętamy, że Quicksort najpierw wybiera pivot, następnie wykonuje podział tablicy na elementy mniejsze i większe od pivota, a na końcu wywołuje się rekurencyjnie na obu tych podtablicach. Oznacza to, że złożoność $T(n)$ Quicksorta dla ciągu długości n to:
$$
T(n) = 2T(n/2) + T(partition) + T(pivot)
$$

Stosując algorytm magicznych piątek jesteśmy w stanie znaleźć pivot w czasie liniowym. Partition oczywiście jest wykonywany w O(n). Stąd:
$$
T(n) = 2T(n/2) + O(n) + O(n)\\
T(n) = 2T(n/2) + O(n)\\
T(n) = O(n\ log\ n)
$$

### Zad. 8

def find_prefix_function(P):
    m = length(P)
    pi[1] = 0
    k = 0
    for i = 2 to m:
        while k > 0 && P[k+1] != P[i]:
            k = pi[i]
        if P[k+1] == P[i]:
            k = k + 1
            pi[i] = k
    return pi

Czas działania tej procedury to O(m). Zauważmy, że pętla for wykona się m-1 razy. W każdym z jej obrotów wykonuje się pętla while, jednak zauważmy, że wykona się ona co najwyżej tyle razy, ile wynosi k, ponieważ w każdej jej iteracji możemy zmniejszyć k o co najmniej 1. Zauważmy jednak, że w każdej iteracji for k moze wzrosnąć o co najwyżej 1 (podstawienie za niego pi[i] może je tylko zmniejszyć, bo pi[i] < k). Oznacza to, że łączna liczba obrotów pętli while to suma spadków wartości k, która jest ograniczona przez sumę wzrostów k, czyli wynosi co najwyżej n. W takim razie cała procedura musi mieć złożoność O(n).

### Zad. 9

### Zad. 10
Mamy dany zbiór $P$ $n$ różnych elementów $p$, gdzie $p_i$ ma wagę $w_i$ i wartość $v_i$, oraz plecak $K(W)$, gdzie $W$ to pojemność plecaka. Szukamy takiego zestawu przedmiotów z $P$, że mieszczą się w plecaku i mają łącznie największą wartość. Każdy przedmiot możemy umieścić w plecaku tylko raz.

Zauważamy, że mając plecak o zerowej pojemności nie możemy dodać do niego więcej przedmiotów. Mając plecak o pojemności $W>0$ i chcąc dodać do niego przedmiot $p_i$ możemy wrzucić go do plecaka i wtedy wartość plecaka jest sumą wartości plecaka o pojemności $W-w_i$ oraz wartości $v_i$, tzn. $K(W) = K(W-w_i)+v_i$. Możemy też nie wrzucać go do plecaka i wtedy wartość plecaka jest równa wartości plecaka, do któego nie będziemy już próowali wrzucić przedmiotu $p_{i}$, czyli ograniczamy rozmiar zbioru przedmiotów do $i-1$. Interesuje nas maksymalna wartość plecaka, czyli większa z tych wartości. Możemy to zapisać jako zależność rekurencyjną:

$K(W,i) = 0$, jeśli $W=0$ lub $i=0$,
$K(W, i) = max(K(W-w_i, i-1) + v_i, K(W, i-1))$, w p.p.

Algorytm zachłanny polegałby na zbudowaniu tablicy indeksowanej po pojemnościach plecaka, tzn. od 0 do W, stosując powyższą zależność rekurencyjną. W ukończonej tablicy znajdziemy odpowiedź na pytanie o największą wartość plecaka. Możemy również zapamiętywać indeksy elementów wybieranych przez algorytm do plecaka, czyli poznamy też jego zawartość.

v[n] // wektor wartości
w[n] // wektor wag
K[n][W] // tablica
for i = 0 to n:
    for w = 0 to W:
        if i == 0 || w == 0:
            K[i][w] = 0
        else:
            K[i][w] = max(K[i-1][W-w] + v[i], K[i-1][W])
return K[n][W]

Zauważamy, że algorytm można zoptymalizować, pamiętając jedynie dwa wiersze lub dwie kolumny tej tablicy -- pozostałe nie są potrzebne.

Złożoność algorytmu to $O(Wn)$, czyli jest pseudowielomianowa, bo zależy wielomianowo od **wartości danych** -- $W$.

### Zad. 11

a) Shift-And dla długich wzorców nie jest optymalny, ponieważ operuje na wektorach bitowych o długości zależnej od długości wzorca. Oznacza to, że działa najszybciej dla krótkich wzorców, które mogą być pamiętane, np. na jednym słowie maszynowym.
b) użycie go dla wzorców w długich tekstach jest sensowne, ponieważ czas działania tego algorytmu jest liniowy, o ile wzorzec nie jest zbyt długi. Również w przypadku bardzo dużego alfabetu czas preprocessingu może być zbyt duży.

### Zad. 12

Rozważmy sytuację, gdzie lewe poddrzewo zawiera maksymalną liczbę wierzchołków, a prawe minimalną. Niech całe drzewo o korzeniu $v$ ma wysokość $h$.

**Lewe**
Jest ono wysokości $h-1$. Oczywiście liczba wierzchołków w tym poddrzewie jest nie większa niż $2^h-1$.

**Prawe**
Jest wysokości $h-1$. Zauważmy, że jest to drzewo minimalne, tzn. jego prawe i lewe poddrzewo również są minimalnymi drzewami AVL. Oznacza to, że liczba wierzchołków w tym poddrzewie $n(h-1) = 1+ n(h-2) + n(h-3)$, gdzie $n(0) = 1$, $n(1)=2$.

n(2) = 1 + 2 + 1 = 4
n(3) = 1 + 2 + 4 = 7
n(4) = 1 + 4 + 7 = 12
Indukcyjnie załóżmy, że $n(k)=F(k+2)-1$ dla $k < i$. Wtedy:
$n(i) = 1 + n(i-1) + n(i-2) = 1 + F(i+1) - 1 + F(i) - 1$
$n(i) = F(i+2) - 1$, czyli zależność jest spełniona.

Stąd maksymalna różnica między liczbą wierzchołków w lewym i prawym poddrzewie $v$ wynosi $2^{h}-1 - n(h-1) = 2^{h}-1 - F(h+1)-1$. Stąd różnica tych wysokości może być $\Omega(n)$.

### Zad. 13

Usuwany jest korzeń drzewa dwumianowego, na który wskazuje wskaźnik $min$ w kopcu $H$. Następnie wszystkie poddrzewa tego korzenia są dodawane na listę drzew nowego kopca $H'$. Uruchamiana jest procedura $meld(H, H')$, która łączy oba kopce. W jej wyniku otrzymamy kopiec $H$ zawierajacy co najwyżej log(n) różnych drzew dwumianowych, gdzie n to liczba wierzchołków w kopcu. Koszt tej operacji to potencjalnie O(n), jednak jej złożoność zamortyzowana to jedynie O(logn) -- rozpatrując niezmiennik kredytowy, w którym korzeń każdego drzewa w kopcu zawiera jedną jednostkę kredytową, wtedy operacja deletemin wymaga jedynie 2logn jednostek, by zachować ten niezmiennik.

### Zad. 14
Poznaliśmy na zajęciach wielomianowy algorytm, rozwiązujący ten problem, czyli jest on klasy P, zatem także klasy NP. Nie jest ani NP-zupełny, ani NP-trudny, o ile P i NP są różne.

### Zad. 15
$4n$ na samą tablicę oraz dodatkowe $3n+3$ na zapamiętanie parametrów funkcji haszującej na pierwszym poziomie oraz funkcji haszujących dla wszystkich podtablic.

### Zad. 16

Mamy spełnione założenie, że prawdopodobieństwo kolizji to $1/m$, gdzie $m$ to rozmiar tablicy. Stąd oczekiwana liczba kolizji to:

$$
\sum_{i=0}^{n-1}i\cdot \frac{1}{m}
$$
W naszym przypadku $n=100$, $m=1000$, czyli:
$$
\sum_{i=0}^{99}i\cdot \frac{1}{1000} = \frac{1}{1000}\sum_{i=0}^{99}i\\
\frac{1}{1000} \frac{99-0}{2}99=\frac{99\cdot 99}{1000} \approx 4.9
$$

### Zad. 17
Wartość tego elementu to $(\omega_n^i)^j$, gdzie $\omega$ to n-ty pierwiastek zespolony z jedności.
Składowe wektora y są wartościami wielomianu o współczynnikach z wektora a w punktach z macierzy A.
### Zad. 18
Pamiętamy, że dla zbalansowanego Uniona drzewa rzędu r mają co najmniej $2^r$ wierzchołków. r jest utożsamiany z wysokością drzewa utworzonego po ciągu samych operacji union (bez find), zatem jest to nasza sytuacja. Oznacza to, że dla n-elementowego drzewa jego wysokość może być co najwyżej logn. Udowodnijmy to indukcyjnie po rzędach:

**Podstawa**
Dla r = 0 mamy drzewo jednoelementowe, czyli ma ono 2^0=1 wierzchołek, dla r=1 mamy drzewo dwuwierzchołkowe, zatem 2^1=2.

**Krok**
Załóżmy, że działa dla $k<r$. Pokażmy, że wtedy działa dla $r+1$.
Weźmy t -- minimalne drzewo o rzędzie r+1. By utworzyć drzewo o rzędzie r+1 potrzebujemy dwóch drzew o mniejszym rzędzie -- t1 i t2. Załóżmy, że t1 jest większe od t2. Skoro podpinamy mniejsze pod większe i otrzymaliśmy drzewo wysokości r+1, to t1 i t2 musiały być co najmniej rzędu r. Zauważmy też, że t1 nie mogło być większego rzędu niż r, bo inaczej to ono byłoby minimalnym drzewem o rzędzie r+1. Również t2 nie mogło być większego rzędu niż r, inaczej to t1 byłoby podwieszone pod t2. Zatem oba muszą być rzędu r.

Zatem liczba wierzchołków w t to:

$\nu(t) = \nu(t1)+\nu(t2)$, ale rząd t1 i t2 to r, czyli z zał. indukcyjnego mamy
$\nu(t) \geq 2^r + 2^r = 2^{r+1}$

Zatem drzewo o rzędzie $r$ ma co najmniej $2^r$ wierzchołków, więc wysokość takiego drzewa nie może być większa niż $O(logn)$.

### Zad. 19

W tej strukturze operacje insert oraz successor są rekurencyjne. Pamiętanie tych dwóch wartości dla każdej podstruktury sprawia, że możemy uniknąć niepotrzebnych wywołań rekurencyjnych, co zmniejsza złożoność obu tych operacji do $O(log\ log\ n)$.

### Zad. 20