Egzamin 2000/01#
Zadanie 1#
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\_odl\_o\_pocz[n] \gets 1\) \(i \gets n - 1\) \(max\_odl\_o\_pocz[i] \gets max((max\_odl\_o\_pocz[j]: (j > i )\ and\ (a_i > a_j))) + 1\) \(i \gets i - 1\)
Zaproponuj efektywną implementację tego algorytmu. Uzasadnij poprawność swojego rozwiązania i przeanalizuj jego złożoność.
Zadanie 2#
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#
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#
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ź.