Egzamin 2000/01

Zadanie 1

Słowa kluczowe: najdłuższy podciąg rosnący

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

Słowa kluczowe: struktury danych, kolejka, amortyzacja

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

Słowa kluczowe: grafy

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)\)

1. znajdzie długość najdłuższej ścieżki elementarnej,

2. policzy moc najliczniejszego skojarzenia

Zadanie 4

Słowa kluczowe: wyszukiwanie; max, asymptotycznie optymalny

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ź.

1. Podaj efektywny algorytm na znajdowanie maximum w takim przypadku.

2. Ile co najmniej pytań trzeba zadać w pesymistycznym przypadku? Uzasadnij formalnie swoją odpowiedź.