Egzamin 2002/03

Zadanie 1

Słowa kluczowe: struktury danych, listy

Na liście jednokierunkowej \(L\) o \(n + 2\) rekordach (\(liczba\), \(nast\)) zapisano wszystkie \(n\) liczb całkowitych z przedziału \(1..n\) - jedna z liczb pojawia się trzykrotnie lub dwie liczby występują dwukrotnie. Zaprojektuj efektywny algorytm, który w miejscu znajdzie wartość pojawiającą się na liście \(L\) więcej niż raz. Uzasadnij poprawność swojego algorytm i przeanalizuj jego złożoność.

Zadanie 2

Słowa kluczowe: sortowanie, asymptotycznie optymalny

Rozważamy sortowanie przez porównania ciągów długości \(n\) i zawierających \(O(n^{3/2})\) inwersji. Podaj ograniczenie dolne (w notacji \(\Omega\)) na liczbę porównań w pesymistycznym przypadku, niezbędną do posortowania ciągu takiej postaci. Odpowiedź uzasadnij. Zaproponuj algorytm sortowania takich ciągów.

Zadanie 3

Słowa kluczowe: grafy; najkrótsze ścieżki

Wyjaśnij, w jaki sposób zmodyfikować algorytm Dijkstry, żeby w przypadku istnienia wielu minimalnych ścieżek (ze względu na sumy wag krawędziach) z \(s\) do \(v\) znajdował ścieżkę najkrótszą ze względu na liczbę krawędzi.

Zadanie 4

Słowa kluczowe: struktury danych, wzbogacanie

Dane są dwie proste, równoległe do osi \(x\)-ów: \(P_1 : y = -1\) i \(P_2 : y = 1\). Zaprojektuj strukturę danych, która umożliwi efektywne wykonanie następujących operacji na skończonym zbiorze \(Z\) punktów leżących na prostych \(P_1 \cup P_2\):

1. \(Insert(x, i) ::\) \(Z := Z \cup \{(x, i)\}, i \in \{-1, 1\}\);

2. \(Delete(x, i) ::\) \(Z := Z \setminus \{(x, i)\}, i \in \{-1, 1\}\);

3. \(MinDist() ::\) return \(min\{dist(p_1, p_2): p_1 \in P_1 \cap Z, p_2 \in P_2 \cap Z\}\).

Uzasadnij poprawność swojego rozwiązania i przeanalizuj złożoność poszczególnych operacji.