1. Klasówka 1998/99#
Zadanie 1#
Tablica \(a[1..n]\) zawiera \(n\) liczba całkowitych spełniających warunek \(|a[i] - a[i + 1]| \leq n^2\) dla każdego \(i = 1, 2, \cdots, n - 1\). Zaprojektuj efektywny (czasowo) algorytm sortowania tablicy \(a\), uzasadnij poprawność i przeanalizuj złożoność swojego algorytmu.
Podpowiedź
Zauważmy, że \(|a[1]-a[i]| \leq n^3\) stąd użyć sortowania kubełkowego (analogicznie do sortowania liczb z zakresu \(1,\ldots,n^3\)).
Zadanie 2#
Dla danego ciągu liczb całkowitych \((a_i)_{i = 1, 2, \cdots, n}\) element \(a_k\) nazywamy dominującym, gdy \(a_j < a_k\), dla każdego \(j < k\). Zaprojektuj strukturę danych, która umożliwia wykonywanie następujących operacji na dynamicznym, początkowo pustym, ciągu \(a\):
\(Dodaj(a, y)\):: dołącz na końcu ciągu \(a\) nowy element \(y\)
\(Usun(a)\):: usuń z ciągu \(a\) jego pierwszy element,
\(Led(a)\):: zwróć liczbę elementów dominujących w ciągu \(a\).
Staraj się żeby koszt zamortyzowane poszczególnych operacji były jak najmniejsze. Uzasadnij poprawność i dokonaj analizy złożoności zaproponowanych przez siebie algorytmów.
Zadanie 3#
Niech \(X\) będzie skończonym zbiorem liczb całkowitych i niech \(k\) będzie dodatnią liczbą całkowitą. Powiemy, że \(X\) jest \(k\)-zwarty, gdy zawiera co najmniej \(k\) kolejnych liczb całkowitych. Zaprojektuj efektywny algorytm, który dla danego \(n\)-elementowego zbioru \(X\) sprawdza, czy ten zbiór jest \(\lceil \frac{n}{2} \rceil\)-zwarty. Możesz założyć, że elementy zbioru \(X\) dane są w tablicy \(x[1..n]\). Uzasadnij poprawność i przeanalizuj złożoność swojego algorytmu.