Zadanie 1#

Zaprojektuj optymalny algorytm pod względem pesymistycznej liczby porównań, który znajduje dwa środkowe elementy w zbiorze czterech elementów. Dowiedź poprawności swojego rozwiązania.

Zadanie 2#

Drzewem klasówkowym nazywamy pełne drzewo binarne, w którym klucze są rozmieszczone zgodnie z następującą regułą: dla każdego węzła $x$ najmniejszy klucz w poddrzewie o korzeniu $x$ znajduje się w jego lewym podrzewie. Zaproponuj implementację drzewa klasówkowego w sposób, który umożliwia wydajne wykonywanie operacji kolejki priorytetowej:

• $Ini$:: mając dane $n=2^k-1$ kluczy zbuduj $n$-węzłowe drzewo klasówkowe

• $Min$:: podaj wartość najmniejszego klucza w drzewie

• $ChangeKey(x,k)$:: zmień wartość klucza we wskazanym węźle $x$ na $k$

Zadanie 3#

Danych jest $k$ uporządkowanych list o długościach będących parami różnymi potęgami dwójki. Zaproponuj wydajny algorytm scalenia tych list w jedną listę uporządkowaną. Uzasadnij poprawność swojego algorytmu i dokonaj analizy jego złożoności obliczeniowej ze względu na liczbę porównań wykonywanych podczas scalania.