Zadanie 1 [7 punktów]#

Blokiem w ciągu binarnym nazywamy każdy maksymalny, spójny podciąg złożony z tych samych cyfr - zer (0) lub jedynek (1). Kompresją binarnego zapisu nieujemnej liczby całkowitej n nazywamy skończony ciąg nieujemnych liczb całkowitych K(n) zdefiniowany następująco:

• jeśli n = 0, to K(n) = <0>;

• dla n > 0, $K(n)=<e_1,e_2,\dots ,e_k(n)>$, gdzie $e_1$ jest długością bloku zbudowanego z najmniej znaczących

zer, $e_2$ jest długością następnego bloku zbudowanego z jedynek, $e_3$ jest długością następnego bloku zbudowanego z zer itd. na przemian długości bloków jedynek i zer. Ostatni element ciągu $e_k(n)$ jest długością bloku zbudowanego z najbardziej znaczących jedynek. Gdy najmniej znaczącą cyfrą jest jedynka, to $e_1$ jest zawsze równe 0.

Przykład

K(0) = <0>, K(1) = <0, 1>, K(2) = <1, 1>, K(3) = <0, 2>, K(13) = <0, 1, 1, 2>.

Zaprojektuj strukturę danych, która umożliwia efektywne wykonywanie następujących operacji na kompresji K(n) dynamicznie zmieniającej się liczby n:

• Ini:: $n:=0$; {operacja jest wykonywana tylko raz na samym początku}

• Dodaj(j):: $n:=n+2^j$ gdzie j jest nieujemną liczbą całkowitą;

• Odejmij(j):: $n:=n-2^j$, gdzie j jest nieujemną liczbą całkowitą taką, że $2^j\le n$;

• Mod(j):: $n:=n\mathrm{mod}{2}^j$, gdzie j jest nieujemną liczbą całkowitą;

• MaxBlok():: podaj długość najdłuższego bloku w K(n).

Zadanie 2 [6 punktów]#

Grafem trójkątów nazywamy graf spójny, w którym każda dwuspójna składowa jest cyklem o długości 3.

1. [2 punkty] Rozważmy następujący graf trójkątów:

   

   Zaznacz w tym grafie DFS-drzewa odpowiednio o najmniejszej i największej wysokości.

2. [4 punkty] Zaprojektuj efektywny algorytm, który dla danego grafu trójkątów oblicza wysokość możliwie najwyższego DFS-drzewa.

Zadanie 3 [7 punktów]#

Powiemy, że AVL-drzewo T jest wysoce niezrównoważone, jeśli dla każdego wierzchołka w drzewie T różnego od liścia (bez następników), wysokości jego poddrzew zawsze się różnią.

1. [2 punkty] Podaj wszystkie wartości $n\le 100$, dla których istnieją wysoce niezrównoważone AVL-drzewa zawierające n wierzchołków.

Liczbę n, dla której istnieje n-wierzchołkowe wysoce niezrównoważone AVL-drzewo nazywamy liczbą wyjątkową. Niech n będzie liczbą wyjątkową i niech $⟨k_1,k_2,\dots ,k_n⟩$ będzie permutacją liczb 1, 2, ldots, n. Do początkowo pustego AVL-drzewa wstawiamy kolejno klucze $k_1,k_2,\dots ,k_n$.

2. [4 punkty] Zaproponuj efektywny algorytm, który wyznaczy permutację $<k_1,k_2,\dots ,k_n>$, dla której dostaniemy wysoce niezrównoważone AVL-drzewo.

3. [1 punkt] Dla ilu permutacji $<k_1,k_2,k_3,k_4>$ budując 4-wierzchołkowe AVL-drzewo nie wykonamy żadnej rotacji.