Zadanie 1 [22 punkty]#

Skierowany graf G=({1,2, …, n}, E) nazywamy grafem przedziałowym, jeżeli dla każdego wierzchołka v, zbór wierzchołków, do których prowadzą krawędzie wychodzące z v, tworzą kolejne wierzchołki od l[v] do r[v], dla pewnych $1\le l[v]\le r[v]\le n$. Graf może zawierać pętle. Jeżeli z wierzchołka nie wychodzi żadna krawędź, to l[v] = r[v] = 0. Liczba n oraz ciąg par l[v], r[v] nazywamy zwartą reprezentacją G, a n rozmiarem tej reprezentacji. Dana jest zwarta reprezentacja pewnego przedziałowego grafu G o rozmiarze n.

1. [5 punków] Ułóż algorytm sprawdzający, czy po usunięciu wszystkich pętli, graf G jest ukorzenionym drzewem, w którym krawędzie są skierowane od korzenia do liści.

2. [9 punktów] Ułóż algorytm sprawdzający, czy G jest słabo-spójny (po usunięciu orientacji na krawędziach jest spójny).

3. [8 punktów] Ułóż algorytm, który sprawdzi, czy G jest eulerowski.

Zadanie 2 [9 punktów]#

Różnowartościowy ciąg liczbowy nazwiemy k-ciągiem, jeżeli zawiera co najwyżej k inwersji.

1. [5 punków] Zaproponuj algorytm, optymalny ze względu na pesymistyczną liczbę wykonywanych porównań, który sortuje 2-ciągi o długościach równych 2016.

2. [4 punkty] Zaproponuj algorytm, optymalny ze względu na pesymistyczną liczbę wykonywanych porównań, który w 2016-ciągu o długości n > 2016 znajduje element najmniejszy.

Udowodnij optymalność swoich rozwiązań.

Zadanie 3 [9 punktów]#

W tym zadaniu rozważamy słowa nad alfabetem {d,i,k,s}. Przesunięciem cyklicznym słowa x[0..m-1] nazywamy słowo z takie, że dla pewnego k ze zbioru {0,.., m-1} i każdego i ze zbioru {0,.., m-1} zachodzi z[i]=x[(i+k) mod m]. Zaprojektuj algorytm sprawdzający, czy w słowie y[0.. n-1], $1\le m\le n$, znajduje się podsłowo będące przesunięciem cyklicznym danego słowa x.

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