Egzamin poprawkowy 2012/13#
Zadanie 1#
Dany jest początkowo pusty, dynamiczny ciąg elementów. Dozwolone jest dodawanie i usuwanie elementów na początku i na końcu ciągu. Zaproponuj algorytm symulujący te operacje z pomocą trzech stosów. Dokonaj analizy zamortyzowanego czasu wykonywanych operacji.
Zadanie 2#
Oto ulepszony algorytm BubbleSort sortujący niemalejąco \(n\)-elementową tablicę \(a[1..n]\):
\(i \gets n + 1\) \(i \gets i - 1\) \(posortowany \gets true\) \(a[j - 1] \leftrightarrow a[j]\) \(posortowany \gets false\)
Zaprojektuj efektywny algorytm, który dla tablicy \(a\) zawierającej permutację liczb \(1, 2, \cdots, n\) obliczy ile razy algorytm BubbleSort wykona pętlę do … until.
Zadanie 3#
Grafy klikowe to grafy spójne, w których każda dwuspójna składowa jest kliką (grafem pełnym). Pamiętaj, że pojedyncza krawędź jest kliką dwuwierzchołkową. Grafy klikowe można reprezentować w następujący sposób:
Przeglądamy graf metodą przeszukiwania w głąb, budujemy drzewo przeszukiwania i numerujemy wierzchołki \(1, 2, \cdots, n\) w kolejności odwiedzania. Wierzchołki utożsamiamy z ich numerami.
Dla każdego wierzchołka \(v > 1\) pamiętamy jego ojca \(p[v]\) oraz wierzchołek \(low[v]\) - najmniejszy wierzchołek (wierzchołek z najmniejszym numerem), do którego prowadzi co najwyżej jedna krawędź niedrzewowa od pewnego potomka \(v\). (Uwaga: \(v\) jest swoim potomkiem.) Taką reprezentację nazywamy oszczędną.
Zaproponuj efektywne algorytmy, które mając daną oszczędną reprezentację grafu klikowego obliczą:
z ilu dwuspójnych składowych składa się ten graf,
rozmiar najliczniejszego skojarzenia.
Zadanie 4#
Zaproponuj algorytm dodania do \(n\)-elementowego drzewa lewicowego \(k\) kluczy w czasie \(O(k + \log n)\).