1. Klasówka 2003/04

Zadanie 1

Słowa kluczowe: struktury danych; wzbogacanie

Rozważmy zbiór punktów na płaszczyźnie \(S = \{ (x_1, y_1), \cdots, (x_n, y_n) \}\), w którym \(y_i < y_{i + 1}\), dla każdego \(0 < i < n\). Powiemy, że punkt \((x_i, y_i) \in S\) jest punktem brzegowym, jeśli półprosta \(\{(x_i, y_i) : y \geq y_i\}\) nie przecina żadnego odcinka łączącego dwa kolejne punkty z \(S\) o indeksach większych od \(i\).

1. Na początkowo pustym zbiorze punktów \(S\) wykonujemy ciąg operacji \(Wstaw(x, y)\) i \(Ile\), zawierający \(n\) operacji \(Wstaw\).

   Operacja \(Wstaw\) wstawia do \(S\) nowy punkt \((x, y)\). O wartościach \(x, y\) wiadomo, że są liczbami całkowitymi spełniającymi nierówności \(0 \leq x, y \leq n\). Dodatkowo zakładamy, że każdy kolejny argument \(y\) operacji \(Wstaw\) jest ostro większy od poprzedniego.

   Operacji \(Ile\) odpowiada na pytanie, ile jest punktów brzegowych w aktualnym zbiorze \(S\).

   Zaproponuj (efektywne) algorytmy wykonywania operacji \(Wstaw\) i \(Ile\) oraz dokonaj analizy ich kosztu zamortyzowanego.

2. Załóżmy, że wykonano \(n\) operacji \(Wstaw\) i przez każdy punkt brzegowy poprowadzono proste pionową i poziomą. Osie \(OX\) i \(OY\) oraz proste poprowadzone przez punkty brzegowe wyznaczają pewną liczbę prostokątów o parami rozłącznych wnętrzach. Zaprojektuj algorytm wyznaczający ten z prostokątów (tzn. wyznaczający współrzędne jego wierzchołków), którym w swoim wnętrzu zawiera największą liczbę punktów ze zbioru \(S\). Jeśli jest wiele takich prostokątów, to wystarczy podać tylko jeden z nich.

   Dokonaj analizy złożoności swojego algorytmu.

Zadanie 2

Słowa kluczowe: sortowanie

Zaproponuj efektywny algorytm sortowania różnowartościowego ciągu liczb \(a[1..n]\), o którym wiadomo, że można go podzielić na dwa podciągi rosnące \((n > 1)\). Dokonaj analizy złożoności swojego algorytmu - czasowej i pamięciowej.

Zadanie 3

Słowa kluczowe: struktury danych

Zaprojektuj strukturę danych dla skończonego multizbioru liczb całkowitych \(S\), umożliwiającą efektywne wykonywanie następujących operacji:

1. \(Insert(S, x)\) - dodaje \(x\) do zbioru \(S\).

2. \(Median(S)\) - podaj element, który jest medianą zbioru \(S\), tzn. jest \(\lceil \frac{|S|}{2} \rceil\)-tym elementem w kolejności niemalejącej.

3. \(DelMed(S)\) - usuń medianę z \(S\).

Najwyżej punktowaną będzie bezwskaźnikowa struktura danych ukryta w tablicy.