Egzamin poprawkowy (04.03.2008)#
Zadanie 1 [8 punktów]#
Zaprojektuj algorytm sortowania w miejscu w czasie \(O(n \log n)\), w którym dopuszczalne są tylko zamiany elementów odległych co najwyżej o \(n/\log n\).
Zadanie 2 [6 punktów]#
Dane są dwa grafy nieskierowane \(G=(V,E_G)\), \(H=(V,E_H)\) w postaci list sąsiedztwa, V = {1,2, …,n}. Zaproponuj algorytm tworzenia list sąsiedztwa dla grafu F=(V,E*), gdzie E* jest iloczynem zbiorów krawędzi \(E_G\) i \(E_H\).
Zadanie 3 [6 punktów]#
Dany (w postaci list sąsiedztwa) jest regularny graf dwudzielny G o stopniu każdego wierzchołka 3. Zaproponuj algorytm, który znajdzie w G trzy różne pokrycia cyklowe. Pokryciem cyklowym grafu G nazywamy zbiór wierzchołkowo rozłącznych cykli elementarnych, które pokrywają wszystkie wierzchołki grafu.
Zadanie 4 [8 punktów]#
Zaproponuj sposób przekształcenia AVL-drzewa w taki sposób, żeby w korzeniu nie było przechylone w lewo. Twój algorytm powinien działać w czasie O(1).
Zadanie 5 [12 punktów]#
Zaproponuj algorytm, który sprawdzi, czy dwie różnowartościowe tablice liczb całkowitych a[1..n] i b[1..n] zawierają dokładnie takie same zbiory inwersji. Ile wynosi dolne ograniczenie na liczbę porównań dla tego problemu? Odpowiedź uzasadnij.
Podpowiedź
Tablice muszą być ze sobą zgodne w sensie Order Preserving (czyli dla dowolnego i, j: a[i]<a[j] wtw b[i]<b[j]).