Egzamin 2023/24 (03.02.2024)#

Zadanie 1 [5 punktów]#

Do początkowo pustej listy wstawiamy n elementów o wartości 1, gdzie każda operacja wstawienia (operacja Wstaw) ma koszt stały. Następnie wykonujemy (n-1) operacji Połącz(i). Operacja Połącz(i), 1 le i < długość listy, usuwa z listy elementy i-ty (\(a_i\)) oraz (i+1)-szy (\(a_{i+1}\)) i wstawia w ich miejsce jeden element będący sumą \(a_i + a_{i+1}\), który staje się i-tym elementem listy. Oznacza to, że po każdym połączeniu lista staje się o 1 krótsza, a po (n-1) operacjach Połącz na liście jest już tylko jeden element (o wartości n). Przyjmujemy, że koszt operacji Połącz to \(\min(a_i, a_{i+1})\). Dokonaj analizy kosztów zamortyzowanych operacji Wstaw i Połącz przy założeniu, że bezpośrednie operacje na liście (wstawianie i usuwanie) są wykonywane w czasie stałym.

Zadanie 2 [12 punktów]#

Danych jest k uporządkowanych rosnąco ciągów \(A_1, A_2, \ldots, A_k\). Zaprojektuj asymptotycznie optymalny algorytm sortujący wszystkie elementy w ciągach przy założeniu, że

  1. [8 punktów] \(|A_i| = i\),

  2. [4 punkty] \(|A_i| = 2^i\).

W obu przypadkach rozmiarem zadania n jest suma długości ciągów do posortowania.

Zadanie 3 [7 punktów]#

Zaprojektuj efektywny algorytm, który dla danego słowa x nad alfabetem \(\{d,i,k,s\}\) i liczby całkowitej s, \(1 \le s \le |x|\), znajdzie liczbę różnych podsłów, które w słowie x występują dokładnie s razy.

Zadanie 4 [8 punktów]#

Niech \(X = {1, \ldots, 2^k}\) dla pewnej liczby naturalnej k. Zaprojektuj strukturę danych, reprezentującą rodzinę \(n \ge 1\) zbiorów \(S_i \subseteq X\), \(i=1,\ldots,n\), umożliwiającą wydajne wykonywanie następujących operacji:

  • Ini():: utwórz n pustych zbiorów \(S_i\), \(i=1,\ldots,n\);

  • Dodaj(i,x):: \(S_i := S_i \cup \{x\}\), \(1 \le i \le n\) oraz \(x \in X\);

  • Usuń(i,x):: \(S_i := S_i \ \{x\}\), \(1 \le i \le n\) oraz \(x \in X\);

  • Wolny(i,j):: jeśli \(|S_i|+|S_j| < |X|\), to podaj dowolny element ze zbioru \(X \ (S_i \cup S_j)\), wpp. nic nie rób.

Maksymalną liczbę punktów można uzyskać za pesymistyczne złożoności:

  • Ini: \(O(n*|X|)=O(n*2^k)\);

  • Dodaj/Usuń/Wolny: \(O(\log|X|)=O(k)\).

Zadanie 5 [8 punktów]#

Niech G=(V,E) będzie n-wierzchołkowym dynamicznym grafem spójnym, gdzie \(V = {1, 2, \ldots, n}\). Początkowo G jest drzewem zadanym przez n-1 krawędzi \(a_1-b_1,\ \ldots,\ a_{n-1}-b_{n-1}\). Zaprojektuj strukturę danych, która umożliwi efektywne wykonywanie co najmniej n następujących operacji na grafie G:

  • Ini():: inicjowanie struktury danych reprezentującej graf (tylko raz na samym początku);

  • Dodaj(a, b):: dodaj krawędź a—b do grafu G, o której wiadomo, że w momencie dodawania nie jest krawędzią grafu;

  • W_dwuspójnej(a, b, c, d):: sprawdź, czy krawędzie a—b i c—d należą do tej samej dwuspójnej składowej grafu G (o a—b i c—d wiadomo, że są krawędziami grafu).

Uwaga: W każdym zadaniu uzasadnij poprawność swojego rozwiązania i dokonaj analizy złożoności zaproponowanych algorytmów.