Zaawansowane algorytmy i struktury danych/Ćwiczenia 14

Zadanie 1

Jaka jest minimalna stała $c$ taka, że dla każdego drzewa rozmiaru co najmniej 2 mamy

$|Contract(T)|\leq c\cdot |T|$

Rozwiązanie

c=2/3.

Zadanie 2

Uzasadnij, dlaczego $|T_{k}|=Fib_{k}<math>oraz<math>Contract(T_{k})=T_{k-1}$.

Rozwiazanie

Wynika to z rekurencji definiującej drzewa $T_{k}$

Zadanie 3

Udowodnij, że $TIME'(Fib_{k}+1)>k$.

Rozwiązanie

.

Weź statyczny liść $v$, dodatkowo korzeń $r$ i zbuduj drzewo, którego korzeniem jest $r$, następnikiem $r$ jest korzeń $T_{p}$, oraz dodatkowo korzeń $T_{p}$ ma syna $v$.

Zadanie 4

Udowodnij indukcyjnie punkt (b) wzmocnionego lematu o kontrakcji.

Rozwiązanie

Niech $x$ będzie pierwszym węzłem na ścieżce ze statycznego węzła do korzenia takim, że $|T_{x}|\geq FIB_{k-1}$.

Ponadto niech $T1,T2$ oraz $T3$ będą drzewami zdefiniowanymi następująco: T1 jest równy T z węzłem x jako statyczny liść (z obciętymi poddrzewami o korzeniach p,q, $T2=T_{p}\otimes x$, oraz $T3=T_{q}$. Wtedy $|T1|,|T2|\leq FIB_{k-1}$ oraz $|T3|<FIB_{k-1}$.

Po $(k-1)$-szej redukcji drzewa T1 oraz T są zredukowane do jednego węzła z jednym statycznym liściem dzięki założeniu indukcyjnemu (b) . Wszystkie węzły T3 stają się liśćmi po (k-2)-giej redukcji dzięki założeniu indukcyjnemu (b).

W konsekwencji, po redukcji k-1 korzeń całego drzewa T ma jedynego następnika $x'$ takiego, że $x'=x$ lub $x'\in T_{p}$. Następnie w k-tej redukcji korzeń ma jedyne dowiązanie do węzła statycznego $v$. Kończy to dowód indukcyjny punktu (b).

Zadanie 5

Przypuśćmy, że zmieniamy definicje kontrakcji. Najpierw wykonujemy Rake, a potem (po zakończeniu Rake) wykonujemy Compress. Udowodnij, że liczba kontrakcji jest w dalszym ciągu $O(\log n)$.

Rozwiązanie

.

Liczba zmodyfikowanych kontrakcji jest nie mniejsza niż liczba kontrakcji, które opisujemy w module, a więc w dlaszym ciągu logarytmiczna.