Egzamin z ASD
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 ≤ i ≤ n: min(x,y) ≤  a[i] ≤ max(x,y)}|.
Wartość k jest ujemna tylko wtedy, gdy x jest mniejsze od y.

1a) [3 punkty] Udowodnij, że każdy algorytm sortujący a wywoła funkcję ile w pesymistycznym przypadku co najmniej n-1 razy.

1b) [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. 

2a) [2 punkty]  Narysuj drzewo sortowania dla permutacji 3, 2, 5, 1, 4, 6, 7, 9, 8. 

2b) [2 punkty] Uzasadnij, że suma głębokości węzłów w drzewie jest równa liczbie wykonywanych porównań podczas sortowania.

2c) [11 punktów] Zaproponuj algorytm, który dla danej permutacji a[1..n] obliczy w czasie O(nlog 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. 

4a) [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.

4b) [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.