Egzamin poprawkowy 2016/17 (18.02.2017)#
Zadanie 1 [13 punktów]#
Dana jest dodatnia liczba całkowita n oraz tablica a[1..n+1] różnych liczb całkowitych, z których a[n+1] jest największa.
[5 punktów] Zaproponuj wydajny algorytm, który dla każdego \(i = 1, \ldots, n\) wyznaczy najmniejsze takie \(j > i\), że \(a[j] > a[i]\).
[8 punktów] Zaproponuj strukturę danych, która dla dynamicznie zmieniającej się zawartości tablicy a umożliwia wydajne wykonywanie następujących operacji:
Ini:: inicjacja struktury danych dla początkowej zawartości tablicy a (wykonywana tylko raz na samym początku)
Zmiana(i,v):: a[i] := v (\(1 \le i \le n\))
NaPrawo(i):: podaj najmniejsze \(j > i\) takie, że \(a[j] > a[i]`\)
Uwaga: możesz założyć, że element \(a[n+1]\) jest zawsze większy od każdego elementu w tablicy \(a[1,\ldots,n]\).
Zadanie 2 [15 punktów]#
Niech G będzie spójnym grafem n-wierzchołkowym o n+4 krawędziach, \(n \ge 5\). O takich grafach powiemy, że są typu N4.
[2 punkty] Ile wynosi najmniejsza, a ile największa wysokość BFS-drzewa w grafie typu N4.
[2 punkty] Ile wynosi najmniejsza, a ile największa wysokość DFS-drzewa w grafie typu N4.
[2 punkty] Jak może być największa liczba wierzchołków stopnia co najwyżej 2 w grafie typu N4?
[9 punktów] Zaprojektuj wydajny algorytm sprawdzający, czy w danym grafie typu N4 istnieje cykl Hamiltona.
Zadanie 3 [12 punktów]#
W tym zadaniu analizujemy sortowanie 6 różnych liczb całkowitych \(x_1, x_2, x_3, x_4, x_5, x_6\), o których wiadomo, że \(x_1 < x_2 < x_3\). Zaproponuj optymalny ze względu na porównania algorytm sortujący ciągi tej postaci. W tym zadaniu możesz otrzymać maksymalnie 5 punktów za dolne ograniczenie i 7 punktów za optymalny algorytm.
Uwaga: W każdym zadaniu uzasadnij poprawność swojego rozwiązania i dokonaj analizy złożoności obliczeniowej zaproponowanych algorytmów.