Egzamin 2000/01
==================================

Zadanie 1
----------------

.. index:: najdłuższy podciąg rosnący

Podciągi rosnące. Oto algorytm, który w danym ciągu liczb całkowitych
:math:`<a_1, a_2, \cdots, a_n>` znajduje dla każdego :math:`i`, długość najdłuższego podciągu
(ostro) rosnącego o początku w :math:`a_i`.

:math:`max\_odl\_o\_pocz[n] \gets 1` :math:`i \gets n - 1`
:math:`max\_odl\_o\_pocz[i] \gets max((max\_odl\_o\_pocz[j]: (j > i )\ and\ (a_i > a_j))) + 1` :math:`i \gets i - 1`

Zaproponuj efektywną implementację tego algorytmu. Uzasadnij poprawność
swojego rozwiązania i przeanalizuj jego złożoność.

Zadanie 2
----------------

.. index:: struktury danych, kolejka, amortyzacja

Kolejka podwójna to lista, na której wykonywane są następujące operacje:

* :math:`\textsf{Front}(q)`:: zwróć pierwszy element listy :math:`q`;
* :math:`\textsf{Push}(q, x)`:: wstaw :math:`x` na początek listy :math:`q`;
* :math:`\textsf{Pop}(q)`:: usuń pierwszy element listy :math:`q`;
* :math:`\textsf{Rear}(q)`:: zwróć ostatni element listy :math:`q`;
* :math:`\textsf{Inject}(q, x)`:: wstaw :math:`x` na koniec listy :math:`q`;
* :math:`\textsf{Eject}(q)`:: usuń ostatni element listy :math:`q`.

Zaproponuj efektywną implementację kolejki podwójnej na trzech stosach.
Przeanalizuj dokładnie koszt zamortyzowany poszczególnych operacji.

Zadanie 3
----------------

.. index:: 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 :math:`G = (V, E)`

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

#. policzy moc najliczniejszego skojarzenia



Zadanie 4
----------------

.. index:: wyszukiwanie; max, asymptotycznie optymalny

Rozważ zadanie znajdowania maximum za pomocą porównań w
różnowartościowym :math:`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ź.