Egzamin 2025/26 (26.01.2026)
============================


Zadanie 1 [10 punktów]
----------------------

.. index:: sortowanie, permutacje, operacje na tablicach

W tym zadaniu rozważamy tablicę *a[1..n]* zawierającą n parami różnych liczb całkowitych, gdzie *n* jest
liczbą całkowitą większą od 1. Jeżeli :math:`a = [e_1, e_2, \ldots, e_n]`, to przez
*Revers(i)*, :math:`1 \le i \le n`,
oznaczamy operację odwrócenie kolejności występowania pierwszych *i* elementów w tablicy *a*.
Po wykonaniu *Revers(i)*
mamy :math:`a = [e_i, e_{i-1}, \ldots, e_1,\ e_{i+1}, \ldots, e_n]`.

a) [2 punkty] Udowodnij, że tablicę a zawsze można posortować rosnąco za pomocą liniowej
   liczby (względem *n*) operacji Revers.
b) [3 punkty] Wiadomo, że na uporządkowanej rosnąco tablicy a wykonano dokładnie jedną
   operację Revers. Zaproponuj asymptotycznie optymalny ze względu na porównania
   algorytm sortujący rosnąco tablicę *a*.
c) [5 punktów] Zaproponuj efektywny algorytm, który dla danej tablicy *a* wyznaczy liniowy ciąg
   operacji Revers, po wykonaniu których tablica *a* zostanie posortowana rosnąco.

Zadanie 2 [10 punktów]
----------------------

.. index:: grafy, DAG, źródła, ujścia, spójność

DAG to graf skierowany bez cykli. Niech *G = (V, E)* będzie DAGiem. Ujściem w *G* nazywamy każdy
wierzchołek bez wychodzących krawędzi, natomiast źródłem - każdy wierzchołek bez wchodzących
krawędzi.

a) [2 punkty] Jaka może być najmniejsza a jaka największa liczba krawędzi w n wierzchołkowym
   słabo spójnym DAGu o *p* źródłach i *q* ujściach, gdzie :math:`n > 1` oraz :math:`p + q \le n`.
b) [3 punkty] Zaproponuj wydajny algorytm, który dla danego słabo spójnego DAGu o n > 1
   wierzchołkach i *p* źródłach oraz *q* ujściach, wyznaczy zbiór nie więcej niż *p + q* krawędzi, po
   dodaniu których dostaniemy graf silnie spójny (:math:`p + q \le n`).
c) [5 punktów] Wiemy, że w DAGu *G* istnieje dokładnie jedno źródło *s* i dokładnie jedno ujście *u*.
   Zaproponuj wydajny algorytm, który wyznaczy ścieżkę z *s* do *u* (o ile istnieje), której długość
   jest podzielna przez 26.

Zadanie 3 [10 punktów]
----------------------

.. index:: ciągi znaków, tablica prefikso-sufiksów, słowa kwadratowe

a) [2 punkty] Udowodnij, że dla każdego całkowitego *n > 0* istnieje słowo nad alfabetem {a,b},
   dla którego suma elementów odpowiadającej mu tablicy prefikso-sufiksów wynosi *n*.

   [Bonus] Potrafisz skonstruować najkrótsze takie słowo?

b) [3 punkty] Słowo x nazywamy kwadratowym wtedy i tylko wtedy, gdy jest złączeniem dwóch takich
   samych słów. Dla przykładu słowo `abbabb` jest słowem kwadratowym, natomiast słowo
   `abaabb` już nie jest. Dla *n = 4k*, *k > 0*, podaj przykład słowa kwadratowego nad alfabetem {a,b}
   zawierającego obie litery a, b i o największej sumie wartości z odpowiadającej mu tablicy
   prefikso-sufiksów.

c) [5 punktów] Zaproponuj wydajny algorytm, który dla danego słowa *x* nad alfabetem {d,i,k,s}
   o długości co najmniej 2 i dodatniej liczby całkowitej :math:`k \le |x|/2`, znajdzie liczbę różnych słów
   kwadratowych o długości *2k* występujących w słowie *x*.

Zadanie 4 [10 punktów]
----------------------

.. index:: struktury danych, drzewa binarne, maksymalne poddrzewa

Niech n będzie dodatnią liczbą całkowitą. W tym zadaniu rozpatrujemy ustalone z góry n-węzłowe
drzewo binarne T, którego węzły zostały ponumerowane w kolejności "preorder" (korzeń, lewe
poddrzewo, prawe poddrzewo). Węzły utożsamiamy z ich numerami. W każdym węźle drzewa
przechowujemy jedną z dwóch wartości – 0 lub 1. Każde maksymalne poddrzewo binarne drzewa T
(bez możliwości rozszerzenia), w węzłach którego są same jedynki, nazywamy poddrzewem
jedynkowym. Korzeniem poddrzewa jedynkowego jest zawsze węzeł o najmniejszym numerze w
numeracji "preorder".

a) [4 punkty] Zaprojektuj strukturę danych, która umożliwia wydajne wykonanie on-line ciągu
   co najmniej n następujących operacji na drzewie T, które na początku zawiera same zera:

   * Ini() :: zainicjuj strukturę danych;
   * Korzeń(i):: jeśli w węźle i jest jedynka ("1") podaj korzeń drzewa jedynkowego zawierającego
     ten węzeł;
   * DodajJedynkę(i):: zapisz jedynkę w węźle o numerze i.

b) [6 punktów] Zaprojektuj strukturę danych, która umożliwia wydajne wykonanie on-line ciągu
   co najmniej n następujących operacji na drzewie T, które na początku zawiera same jedynki:

   * Ini() :: zainicjuj strukturę danych;
   * Korzeń(i):: jeśli w węźle i jest jedynka ("1") podaj korzeń drzewa jedynkowego zawierającego
     ten węzeł;
   * UsuńJedynkę(i):: zapisz zero w węźle o numerze i.

**Uwaga: Uzasadnij poprawność swoich rozwiązań i dokonaj analizy złożoności obliczeniowej
zaproponowanych algorytmów.**