2. Klasówka 2017/18 (11.01.2018)#
Zadanie 1 (10 punktów)#
Niech S będzie skończonym podzbiorem różnych, dodatnich liczb całkowitych, a d dodatnią liczbą całkowitą.
(5 punktów) Przyjmij, że elementy zbioru zapisano w uporządkowanej malejąco tablicy a[1..n], gdzie \(n=|S|\). 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.
Przykład Dla S={6, 5, 2, 1} i d=7, liczba takich par wynosi 4.
(5 punktów) Załóżmy, że d jest ustalone (ale może być bardzo duże), natomiast 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 liczba par różnych elementów z S, których suma jest nie większa od 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. Możesz przyjąć, że operacje arytmetyczne i porównania na liczbach są wykonywane w stałym czasie.
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 kolejno po jednej, nowej monecie, kładąc ją na szczycie dowolnego stosu. Jeśli po położeniu nowej monety na 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 z niego na inne stosy tyle monet, ile jest na wyższym z sąsiadów, umieszczają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 dołożenia jednej, nowej monety. Za operację elementarną przyjmij położenie monety na stosie.
Zadanie 3 (3 punkty)#
(1 punkt) Jaka jest maksymalna liczba węzłów (wewnętrznych) w AVL-drzewie o wysokości h?
(2 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.