Egzamin 2002/03#
Zadanie 1#
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#
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#
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#
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\):
\(Insert(x, i) ::\) \(Z := Z \cup \{(x, i)\}, i \in \{-1, 1\}\);
\(Delete(x, i) ::\) \(Z := Z \setminus \{(x, i)\}, i \in \{-1, 1\}\);
\(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.