Egzamin 2000/01#
Zadanie 1 [10 punktów]#
Podciągi rosnące. Oto algorytm, który w danym ciągu liczb całkowitych \(<a_1, a_2, \cdots, a_n>\) znajduje dla każdego \(i\), długość najdłuższego podciągu (ostro) rosnącego o początku w \(a_i\).
max_dl_o_pocz[n] := 1;
for i := n-1 downto 1 do
max_dl_o_pocz[i] := max({max_dl_o_pocz[j] : (j > i) AND (a_j > a_i)}) + 1;
Zaproponuj efektywną implementację tego algorytmu. Uzasadnij poprawność swojego rozwiązania i przeanalizuj jego złożoność.
Zadanie 2 [10 punktów]#
Kolejka podwójna to lista, na której wykonywane są następujące operacje:
\(\textsf{Front}(q)\):: zwróć pierwszy element listy \(q\);
\(\textsf{Push}(q, x)\):: wstaw \(x\) na początek listy \(q\);
\(\textsf{Pop}(q)\):: usuń pierwszy element listy \(q\);
\(\textsf{Rear}(q)\):: zwróć ostatni element listy \(q\);
\(\textsf{Inject}(q, x)\):: wstaw \(x\) na koniec listy \(q\);
\(\textsf{Eject}(q)\):: usuń ostatni element listy \(q\).
Zaproponuj efektywną implementację kolejki podwójnej na trzech stosach. Przeanalizuj dokładnie koszt zamortyzowany poszczególnych operacji.
Zadanie 3 [10 punktów]#
Grafem trójkątnym nazywamy graf, w którym każda dwuspójna składowa jest trójkątem. Zaproponuj efektywny algorytm, który w danym grafie trójkątnym \(G = (V, E)\)
znajdzie długość najdłuższej ścieżki elementarnej,
policzy moc najliczniejszego skojarzenia
Zadanie 4 [10 punktów]#
Rozważ zadanie znajdowania maximum za pomocą porównań w różnowartościowym \(n\)-elementowym ciągu liczbowym. Na co najwyżej jedno pytanie o wynik porównania możemy dostać błędną odpowiedź.
Podaj efektywny algorytm na znajdowanie maximum w takim przypadku.
Ile co najmniej pytań trzeba zadać w pesymistycznym przypadku? Uzasadnij formalnie swoją odpowiedź.