Zadanie 1 [2 punkty]#

Podaj największe takie d, że każde AVL-drzewo o wysokości $h=2023$ do głębokości d jest pełnym drzewem binarnym. Uwaga: głębokości i wysokości drzew liczymy w liczbach krawędzi.

Zadanie 2 [6 punktów]#

Zaprojektuj strukturę danych, która na początkowo pustym, dynamicznym zbiorze S dodatnich liczb całkowitych, pozwala wydajnie wykonywać następujące operacje:

• INI():: $S:=\mathrm{\varnothing }$ (wykonywana tylko raz, na samym początku)

• INSERT(n):: $S:=S\cup \{n\}$

• DELETE(n):: $S:=S-\{n\}$

• SEARCH(n):: sprawdź, czy n jest w zbiorze S

• MAX():: jeśli S jest niepusty, to podaj największą liczbę w zbiorze S

• INCREASE(i):: jeśli S jest niepusty dodaj MAX() do i najmniejszych elementów w zbiorze, $1\le i\le |S|$

Zadanie 3 [12 punktów]#

Grafem klikowym nazywamy spójny, nieskierowany graf, w którym każda dwuspójna wierzchołkowo składowa jest kliką (grafem pełnym).

1. [2 punkty] Jaka jest maksymalna, a jaka minimalna wysokość DFS-drzewa w 2023- wierzchołkowym grafie klikowym, zawierającego dokładnie 3 dwuspójne składowe.

2. [10 punktów] Dla liczby całkowitej $n>1$ i liczby całkowitej k, $1\le k<n$, rozważmy n-wierzchołkowy graf klikowy G o zbiorze wierzchołków $\{1,2,\dots ,n\}$, w którym dwuspójne składowe ponumerowano $1,2,\dots ,k$. Zwartą reprezentacją grafu G, oznaczaną przez Z(G), nazywamy zbiór wszystkich par $(v,s_v)$ takich, że v jest wierzchołkiem grafu, natomiast $s_v$ jest numerem dwuspójnej składowej, do której należy wierzchołek v.

   1. [2 punkty] Jaki jest rozmiar zbioru Z(G)?

   2. [2 punkty] Uzasadnij, że wysokość DFS-drzewa budowanego algorytmem rekurencyjnym na grafie zadanym przez listy sąsiedztwa zależy od kolejności wierzchołków na listach.

   3. [6 punktów] Dana jest zwarta reprezentacja Z(G) grafu G. Zaproponuj wydajny algorytm, który wyznaczy DFS-numerację wierzchołków grafu (numerujemy wierzchołki w kolejności pierwszych odwiedzin) przy przeszukiwaniu od wierzchołka o numerze 1 i przy założeniu, że listy sąsiedztwa grafu G byłyby uporządkowane rosnąco.

Uwaga: uzasadnij poprawność swoich odpowiedzi i dokonaj analizy złożoności obliczeniowej zaproponowanych algorytmów.