2. Klasówka 2018/19 (11.12.2018)#
Zadanie 1 (10 punktów)#
Niech S będzie skończonym podzbiorem dodatnich liczb całkowitych, a d dodatnią liczbą całkowitą.
[4 punkty] Zaprojektuj wydajny algorytm, który policzy liczbę (nieuporządkowanych) par różnych elementów z S, których suma jest nie większa od d.
[6 punktów] Załóżmy, że d jest ustalone, a S jest zbiorem dynamicznym. Zaprojektuj efektywną strukturę danych, która umożliwi wydajne wykonywanie na zbiorze S następujących operacji:
Ini(S):: S := \(\emptyset\); // operacja wykonywana raz, na samym początku obliczeń;
Insert(x, S):: \(S := S \cup \{x\}\);
Delete(x, S):: \(S := S - \{x\}\);
Pairs(S):: return \(|\{\{a,b\} \in S: a + b \le d\}|\).
Zaproponuj rozwiązanie, w którym operacje Insert i Delete są wykonywane w czasie \(O(\log |S|)\), a operacja Pairs w czasie stałym, niezależnie od wielkości d.
Zadanie 2 (6 punktów)#
Danych jest 2018 monet ułożonych w stosach na okręgu po dwie monety w każdym. Dokładamy do zbioru po jednej monecie, kładąc ją na szczycie dowolnego stosu. Jeśli po położeniu kolejnej monety stos, na którym się właśnie znalazła, będzie co najmniej dwukrotnie wyższy od KAŻDEGO z sąsiednich stosów, to przekładamy połowę monet znajdujących się na tym stosie na inne stosy, kładąc je zgodnie z ruchem wskazówek zegara po jednej monecie na KOLEJNYCH stosach, począwszy od dowolnie wybranego miejsca (możemy wielokrotnie obejść okrąg). Oszacuj zamortyzowany koszt położenia jednej monety. Za operację elementarną przyjmij położenie monet na stosie.
Zadanie 3 (5 punktów)#
(2 punkty) Jaka jest minimalna, a jaka maksymalna liczba węzłów (wewnętrznych) w AVL-drzewie o wysokości h?
(3 punkty) Załóżmy, że kluczami w AVL drzewie są kolejne liczby naturalne 1, 2, … . Jaki najmniejszy, a jaki największy klucz może znaleźć się w korzeniu AVL-drzewa o wysokości h?
Uwaga: uzasadnij poprawność swoich rozwiązań i dokonaj analizy złożoności zaproponowanych algorytmów.