Egzamin z ASD
26.01.2010

Zadanie 1 [9 punktów]

Zaprojektuj algorytm, który dla danego tekstu t i słowa s nad alfabetem o stałym rozmiarze, niezależnym od długości t i s, wyznaczy liczbę wszystkich parami różnych podsłów tekstu t, które nie są podsłowami s. 
Dla przykładu, różnymi podsłowami słowa ababa są ε, a, b, ab, ba, aba, bab, abab, baba, ababa

Zadanie 2 [16 punktów]

W n-węzłowym drzewie BST T, oprócz kluczy, zapisano różnowartościowo priorytety 1, 2, …, n. Drzewo BST można przekształcić w dowolne inne drzewo BST wykonując pojedyncze operacje.

a)	[7 punktów] Opisz konstrukcję ciągu rotacji o długości O(n), które należy wykonać, żeby przekształcić drzewo T w drzewo BST, które będzie jednocześnie kopcem binarnym typu MAX.
b)	[9 punktów] Zaproponuj algorytm, który w czasie liniowym znajdzie ciąg rotacji, o którym mowa w punkcie a).

Zadanie 3 [8 punktów]

Dany jest spójny graf nieskierowany G=(V,E) z dodatnimi, całkowitoliczbowymi wagami na krawędziach oraz wyróżnione wierzchołki s i t. Zaprojektuj algorytm, który spośród najlżejszych ścieżek pomiędzy s i t wyznaczy jedną, z najmniejszą liczbą krawędzi.

Zadanie 4 [7 punktów]

a)	[4 punkty] Wykaż, że k nowych elementów można wstawić do uporządkowanego ciągu n-elementowego przy pomocy O(klog k + n) porównań.
b)	[3 punkty] Wykaż, że dla k ≥ n, rozwiązanie z punktu a) jest asymptotycznie optymalne.