Egzamin poprawkowy 2019/20 (19.02.2020)#

Zadanie 1 [10 punktów]#

Słowa kluczowe: sortowanie

Niech \(A = [a_1, a_2, \ldots,a_n]`\) będzie ciągiem binarnym, n > 0.

  1. [5 punktów] Zaprojektuj wydajny algorytm, który obliczy ile dokładnie porównań zostanie wykonanych w stabilnym algorytmie sortowania przez wstawianie zastosowanym do ciągu A.

  2. [5 punktów] Ile wynosi dokładna średnia liczba porównań wykonywanych w stabilnym algorytmie sortowania przez wstawianie przy założeniu, że każdy ciąg binarny pojawia się na wejściu z jednakowym prawdopodobieństwem?

Podpowiedź

  1. Niech \(Ile1(i) = |\{ j : a_j=1\ \mbox{oraz}\ j<i\}|\). Wynik to: \(n - 1 + \sum_{i=2}^n [a[i]=0]\cdot Ile1(i)\).

  2. \(\Theta(n^2)\).

Zadanie 2 [10 punktów]#

Słowa kluczowe: struktury danych, wzbogacanie, Find-Union

Niech A będzie dynamicznym zbiorem liczb całkowitych. Zaprojektuj strukturę danych umożliwiającą wydajne wykonywanie na zbiorze A następujących operacji:

  1. [5 punktów]

    • Ini(A):: zainicjuj A jako pusty;

    • Insert(a):: wstaw a do A;

    • Delete(a):: usuń a z A;

    • Largest:: podaj rozmiar największego podzbioru A zbudowanego z kolejnych liczb całkowitych \(i, i+1, i+2, \ldots\), dla pewnej liczby całkowitej i.

  2. [5 punktów]

    • Ini(A):: \(A := \{1,2, \ldots, n\}\)

    • Delete(a):: usuń a z A;

    • Largest:: podaj rozmiar największego podzbioru A zbudowanego z kolejnych liczb całkowitych \(i, i+1, i+2, \ldots\), dla pewnej liczby całkowitej i. W tym przypadku przyjmij, że ciąg operacji Delete, Largest jest dany off-line i chcemy znać odpowiedź na każde zapytanie Largest.

Podpowiedź

  1. Dla uproszczenia, dobry ciąg to ciąg postaci \(i, i+1, i+2, \ldots\). Wzbogacamy drzewo o dodatkwe atrybuty: MaxDobryPrefiks, MaxDobrySufiks i MaxDobry (odpowiednio najdłuższy dobry prefiks, sufiks i dowolny spójny fragment).

  2. W trybie off-line, możemy odwrócić kolejność operacji (to powoduje, że Delete zamienia się na Insert). Możemy użyć struktury Find-Union, każdy zbiór oznacza maksymalny dobry ciąg lub pojedynczy element, który nie należy do A.

Zadanie 3 [10 punktów]#

Słowa kluczowe: grafy

4-kaktusem nazywamy graf spójny, w którym każda dwuspójna składowa składa się z dokładnie 4 wierzchołków.

  1. [2 punkty] Ile wierzchołów jest w 4-kaktusie o dokładnie n dwuspójnych składowych?

  2. [2 punkty] Jaka jest maksymalna, a jaka minimalna wysokość DFS-drzewa w 4-katusie o n dwuspójnych składowych?

  3. [6 punktów] Dany jest 4-kaktus (przez listy sąsiedztwa) z dodatnimi wagami na krawędziach. Zaprojektuj wydajny algorytm, który dla danej pary wierzchołków u i v znajduje najlżejszą ścieżkę między nimi.

Zadanie 4 [10 punktów]#

Słowa kluczowe: teksty

Zaprojektuj wydajny algorytm, który dla danych słów x, y nad alfabetem {d, i , k, s} obliczy:

  1. [6 punktów] długość najdłuższego wspólnego podsłowa zawierającego podciąg d, i, k, s.

  2. [4 punkty] długość najkrótszego wspólnego podsłowa zawierającego podciąg d, i, k, s.

Podpowiedź

  1. Jak LCS tylko dodajmy 3 wymiar ([0..4] – jak długi prefiks słowa diks już znaleziono). Złożoność czasowa \(O(n^2)\).

  2. Zbudujmy drzewo sufiksowe dla tekstu: \(x\$y\#\). Wystarczy najpłytszy węzeł w drzewie, który: - leży w poddrzwie ścieżki diks - w poddrzewie ma zarówno sufiksy z x jak i z y. Złożoność czasowa \(O(n)\).

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