1. Klasówka 2008/09#
Zadanie 1#
Oto możliwa implementacji procedury Partition w algorytmie QuickSort:
\(s \gets (le + pr) / 2\) \(v \gets a[s]\) \(a[s] \gets a[le]\) \(i \gets le\) \(j \gets pr + 1\) \(i \gets i + 1\) \(a[i] \geq v\) \(j \gets j - 1\) \(a[j] \leq v\) \(a[i] \leftrightarrow a[j]\) \(j \leq i\) \(a[le] \gets a[j]\) \(a[j] \gets a[v]\)
Podaj zawartość tablicy \(a[1..n]\) dla \(n = 7\) - permutację liczb \(1, 2, \cdots, n\), dla której algorytm QuickSort z powyższą procedurą Partition wykona:
najmniejszą liczbę porównań
największą liczbę porównań
Podaj zawartość tablicy \(a[1..n]\) dla \(n = 15\) - permutację liczb \(1, 2, \cdots, n\), dla której algorytm HeapSort buduje kopiec (pierwsza faza algorytmu) za pomocą:
najmniejszej liczby porównań
największej liczby porównań
Odpowiedzi uzasadnij. Uwaga: porównania dotyczą elementów tablicy \(a\), interesuje nas sortowanie w porządku niemalejącym.
Zadanie 2#
Zaproponuj wzbogacenie kopca zupełnego w taki sposób, żeby efektywnie w czasie zamortyzowanym wykonywane były operacje: \(Min\), \(DeleteMin\), \(Insert\), \(CountMin\). Ostatnia operacja polega na podaniu aktualnej liczby elementów w kopcu o wartości równej \(Min\). Przeprowadź analizę kosztu zamortyzowanego wykonania poszczególnych operacji.
Podpowiedź
Możemy użyć zwykłego kopca zupełnego typu Min, jednak dodatkowo wzbogacamy każdy węzeł o atrybut \(CountEq\): który oznacza liczbę elementów w poddrzewie węzła o tej samej wartości. Łatwo zauważyć, że przy rotacjach ten atrybut można aktualizować w kopcu w czasie \(O(1)\).
Zadanie 3#
Zaproponuj sposób wykonania operacji \(Inc(L)\) dla licznika Fibonacciego \(L\) w taki sposób, żeby po wykonaniu \(n\)-tej operacji wartość liczby \(n\) zapisanej w liczniku wynosiła \(L[0] \cdot F_0 + L[1] \cdot F_1 + L[2] \cdot F_2 + \cdots\), gdzie \(L[i]\) to wartość \(i\)-tego bitu w liczniku, \(F_i\) to \(i\)-ta liczba Fibonacciego \((F_0 = 0, F_1 = 1)\). Operacje elementarne w rozwiązaniu, to zmiana wartości jednego bitu i odczytanie wartości jednego bitu. Zaproponuj rozwiązanie z jak najmniejszym kosztem zamortyzowanym. Dokonaj analizy kosztu zamortyzowanego metodą funkcji potencjału. Możesz założyć, że licznik jest początkowo wyzerowany.