Egzamin 2009/10#
Zadanie 1#
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ą \(\epsilon, a, b, ab, ba, aba, bab, abab, baba, ababa\)
Zadanie 2#
W \(n\)-węzłowym drzewie BST \(T\), oprócz kluczy, zapisano różnowartościowe priorytety \(1, 2,\cdots, n\). Drzewo BST można przekształcić w dowolne inne drzewo BST wykonując pojedyncze operacje.
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\).
Zaproponuj algorytm, który w czasie liniowym znajdzie ciąg rotacji, o którym mowa w punkcie (a).
Zadanie 3#
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#
Wykaż, że \(k\) nowych elementów można wstawić do uporządkowanego ciągu \(n\)-elementowego przy pomocy \(O(k \log k + n)\) porównań.
Wykaż, że dla \(k \geq n\), rozwiązanie z punktu (a) jest asymptotycznie optymalne.
Podpowiedź
Algorytm: posortuj k nowych elementów przy pomocy Heap Sort (w czasie \(O(k\log k)\)), a następnie scal oba ciągi w czasie \(O(n+k)\).