1. Klasówka 2013/14#
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.