Egzamin 2010/11 (28.01.2011)#
Zadanie 1 [11 punktów]#
Dana jest tablica a[1..n] parami różnych elementów pochodzących ze zbioru z liniowym porządkiem. Należy posortować tablicę a rosnąco. Jedyną operacją służącą do porównywania elementów między sobą jest funkcja ile(x,y), której wynikiem jest liczba całkowita k zdefiniowana tak, że \(|k| = |\{1 \le i \le n: \min(x,y) \le a[i] \le \max(x,y)\}|\). Wartość k jest ujemna tylko wtedy, gdy x jest mniejsze od y.
[3 punkty] Udowodnij, że każdy algorytm sortujący a wywoła funkcję ile w pesymistycznym przypadku co najmniej n-1 razy.
[8 punktów] Zaproponuje algorytm sortowania a w miejscu za pomocą co najwyżej O(n) wywołań funkcji ile i O(n) zamian.
Zadanie 2 [15 punktów]#
W tym zadaniu rozważamy algorytm QuickSort użyty do posortowania permutacji liczb 1, 2, …, n zapisanej w tablicy a[1..n], przy założeniu, że funkcja podziału działa w następujący sposób:
elementem dzielącym jest zawsze pierwszy element dzielonego fragmentu tablicy,
podczas podziału elementy z danego fragmentu są porównywane tylko z elementem dzielącym,
po wykonaniu podziału zarówno elementy mniejsze od elementu dzielącego, jak i elementy większe, występują w takiej samej kolejności, co przed podziałem.
Dla danej permutacji proces sortowania można przedstawić za pomocą drzewa binarnego, w którym w węzłach znajdują się elementy dzielące, a poddrzewa odpowiadają wywołaniom rekurencyjnym.
[2 punkty] Narysuj drzewo sortowania dla permutacji 3, 2, 5, 1, 4, 6, 7, 9, 8.
[2 punkty] Uzasadnij, że suma głębokości węzłów w drzewie jest równa liczbie wykonywanych porównań podczas sortowania.
[11 punktów] Zaproponuj algorytm, który dla danej permutacji a[1..n] obliczy w czasie \(O(n \log n)\) liczbę porównań wykonywanych przez QuickSort podczas sortowania a.
Zadanie 3 [7 punktów]#
Dany jest (przez listy sąsiedztwa) graf G=(V,E) oraz wyróżniony wierzchołek s. Każdemu wierzchołkowi przypisano dodatnią liczbę całkowitą. Zaproponuj algorytm, który obliczy długość najdłuższej ścieżki o początku w s, na której liczby przypisane kolejnym wierzchołkom tworzą ciąg (ściśle) malejący.
Zadanie 4 [7 punktów]#
Dana jest tablica P[0..n] nieujemnych liczb całkowitych.
[5 punktów] Zaproponuj algorytm, który efektywnie sprawdzi, czy P jest tablicą prefiksów-sufiksów z algorytmu KMP dla pewnego słowa nad alfabetem {a,b}? Uwaga: kolejne symbole słowa są indeksowane od 1. P[0] odpowiada słowu pustemu.
[2 punkty] Czy istnieje słowo nad alfabetem {a,b}, dla którego P = [0,0,1,0,1,2,3,4,1,2] jest tablicą prefiksów-sufiksów?
Uzasadnij poprawność swoich rozwiązań i dokonaj analizy złożoności obliczeniowej zaproponowanych algorytmów.