Zaawansowane algorytmy i struktury danych/Ćwiczenia 14

Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania

Zadanie 1

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

Rozwiązanie


Zadanie 2

Uzasadnij, dlaczego .

Rozwiazanie

Zadanie 3

Udowodnij, że .


Rozwiązanie


Zadanie 4

Udowodnij indukcyjnie punkt (b) wzmocnionego lematu o kontrakcji.

Rozwiązanie


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 .

Rozwiązanie