Egzamin 2017/18 (30.01.2018)#

Zadanie 1 [8 punktów]#

Słowa kluczowe: sortowanie

W kostce \([0,n]^3\), n > 10, danych jest n różnych odcinków równoległych do osi układu współrzędnych i o końcach w punktach o współrzędnych całkowitych, każdy o długości 10. Zaproponuj efektywny algorytm obliczający liczbę punktów o współrzędnych całkowitych należących do co najmniej dwóch różnych odcinków.

Podpowiedź

Dla każdego odcinka I wyznacz zbiór punktów o współrzędnych całkowitych \(P_I\) należących do I. Ponieważ każdy odcinek ma długość 10, stąd \(|P_i|=11\). Następnie posortuj w czasie liniowym wszystkie punkty i wypisz te, które występują co najmniej dwa razy.

Zadanie 2 [16 punktów]#

Słowa kluczowe: grafy

Niech n będzie liczbą całkowitą większą od 2 i niech J będzie rodziną co najwyżej n różnych, domkniętych przedziałów liczb całkowitych zawartych w przedziale [1,n]. Grafem \(G(n,J)\) nazywamy graf ({1,2, …, n}, {i-j: istnieje przedział w J, do którego wpadają obie liczby (oba wierzchołki) i oraz j}).

  1. [2 punkty] Ile jest różnych drzew BFS o korzeniu w wierzchołku 1 w grafie G(8,J) dla J = {[1,4],[3,6],[5,8]}?

  2. [2 punkty] Ile jest różnych drzew DFS o korzeniu w wierzchołku 1 w grafie G(6,J) dla J = {[1,4],[3,6]}?

  3. [7 punktów] Zaprojektuj efektywny algorytm, który dla danej liczby całkowitej n > 2 oraz rodziny co najwyżej n różnych przedziałów J zawartych w przedziale [1,n] obliczy wysokość BFS drzewa w grafie G(n,J), o korzeniu w wierzchołku 1.

  4. [5 punktów] Zaprojektuj efektywny algorytm, który dla danej liczby całkowitej n > 2 oraz rodziny co najwyżej n różnych przedziałów J zawartych w przedziale [1,n], obliczy liczbę dwuspójnych składowych w grafie G(n,J).

Uwaga: na potrzeby tego zadania dwa drzewa przeszukiwania różnią się wtedy, gdy istnieje wierzchołek, który w obu drzewach ma różnych ojców.

Zadanie 3 [7 punktów]#

Słowa kluczowe: teksty, drzewo sufiksowe

Niech x będzie słowem binarnym o długości co najmniej 2 i zawierającym co najmniej jedno 0 (zero) oraz co najmniej jedną 1 (jedynkę). Zaprojektuj efektywny algorytm, który w słowie binarnym x znajduje dwa podsłowa o maksymalnej długości, które różnią na każdej pozycji.

Podpowiedź

Znajdź najdłuższe wspólne podsłowo x i \(x'=\textrm{neg}(x)\). Przy pomocy drzewa sufiksowego najdłuższe wspólne podsłowo można obliczyć w czasie \(O(n)\).

Zadanie 4 [9 punktów]#

Słowa kluczowe: struktury danych, wzbogacanie

Zaprojektuj strukturę danych, która umożliwia wydajne wykonywanie następujących operacji na dynamicznie zmieniającym się ciągu liczbowym \(\alpha=\langle a_1, a_2, \ldots, a_n \rangle\):

  • Ini(\(\alpha\)):: \(\alpha\) := <pusty ciąg>; //operacja wykonywana tylko raz na początku

  • Insert(\(\alpha\),a,i):: wstaw element a na pozycję i w ciągu \(\alpha\), \(1 \le i \le |\alpha|+1\)

  • Delete(\(\alpha\),i):: usuń i-ty element z ciągu \(\alpha\), \(1 \le i \le |\alpha|\)

  • Add(\(\alpha\),e,i,j):: do każdego z elementów podciągu \(\alpha[i..j]\) dodaj e, \(1 \le i \le j \le |\alpha|\)

  • MaxInc(\(\alpha\)):: podaj długość najdłuższego spójnego podciągu rosnącego w ciągu \(\alpha\)

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