Egzamin poprawkowy 2024/25 (20.02.2025)#
Zadanie 1 [12 punktów]#
Dla dodatniej liczby całkowitej n, zygzakiem rzędu n nazywamy każdy ciąg \(x_1, x_2, \ldots, x_n\) parami różnych liczb całkowitych spełniający warunek: dla każdego \(1 \le i < n\):
\(x_i > \max(x_{i+1}, \ldots, x_n)\) lub \(x_i < \min(x_{i+1}, \ldots, x_n)\).
Niech \(x[1,\ldots,n]\) będzie tablicą, w której zapisano pewien zygzak rzędu n, tzn. \(x[i]=x_i\).
[3 punkty] Zaproponuj wydajny algorytm, który obliczy liczbę wszystkich inwersji w tablicy x.
[5 punktów] Zaprojektuj wydajny, działający w miejscu algorytm, który w zygzaku zapisanym w tablicy \(x[1,\ldots,n]\) znajdzie dwa najbliższe sobie elementy, tzn. wartość bezwzględna ich różnicy jest najmniejsza.
[4 punkty] Niech \(P_n\) będzie zbiorem wszystkich permutacji liczb \(1, 2, \ldots, n\), które są zygzakami. Dokonaj analizy oczekiwanej liczby porównań wykonywanych podczas sortowania przez wstawianie losowego zygzaka z \(P_n\).
Podpowiedź
Ile inwersji tworzy \(x_i\) z elementami po nim, jeśli jest od nich wszystkich większy, a ile, jeśli mniejszy? Jak to rozpoznać jednym porównaniem?
Jak wyglądają w porządku posortowanym elementy „mniejsze od wszystkich dalszych”, a jak „większe od wszystkich dalszych”? Najbliższa para jest sąsiednia w porządku posortowanym - wystarczy jeden przebieg z pamięcią \(O(1)\).
Ile jest zygzaków w \(P_n\)? Losowy zygzak to n-1 niezależnych wyborów „minimum albo maksimum”. Ile elementów przed \(x_i\) jest od niego większych? Policz oczekiwaną liczbę porównań przy wstawianiu \(x_i\) i zsumuj.
Zadanie 2 [8 punktów]#
W tym zadaniu rozważamy grafy dwudzielne.
[3 punkty] Jaka może być minimalna, a jaka maksymalna wysokość DFS-drzewa w n-wierzchołkowym dwudzielnym grafie dwuspójnym, dla \(n > 3\)?
[5 punktów] Zaprojektuj strukturę danych umożliwiającą wydajne wykonanie \(m > n\) on-line operacji na dynamicznie rozrastającym się dwudzielnym multigrafie \(G=(\{1, 2, \ldots,n\}, E)\):
Ini:: \(E:= \emptyset\) // tylko raz na samym początku
Dodaj(u-v):: sprawdź, czy \(G=(V,E \cup \{u-v\})\) jest nadal dwudzielny i jeśli tak, dodaj krawędź u-v do grafu,
Ile():: podaj liczbę spójnych składowych w grafie G zawierających wierzchołek stopnia 1.
Podpowiedź
Największa: kiedy DFS może przejść ścieżką Hamiltona (rozważ osobno n parzyste i nieparzyste)? Najmniejsza: korzeń drzewa DFS grafu dwuspójnego ma tylko jedno dziecko. Czy w grafie dwudzielnym możliwa jest wysokość 2? Podaj graf, który osiąga minimum.
Find-Union z parzystością (kolor wierzchołka względem reprezentanta) wykrywa cykl nieparzysty. Dla Ile() trzymaj stopnie wierzchołków, w reprezentancie składowej liczbę jej wierzchołków stopnia 1, a globalnie liczbę składowych, w których ta liczba jest dodatnia. Co się zmienia przy dodaniu krawędzi, także wielokrotnej?
Zadanie 3 [6 punktów]#
Dany jest acykliczny graf skierowany (dag) G=(V,E). Wierzchołek \(w\in V\) jest przodkiem wierzchołka \(u\in V\), gdy istnieje skierowana ścieżka z u do w. Najbliższym wspólnym przodkiem wierzchołków \(u\in V\) i \(v \in V\) nazywamy wierzchołek \(w \in V\), który jest przodkiem u i v oraz nie istnieje inny przodek u i v, którego przodkiem jest w. Najbliższy wspólny przodek dla pary wierzchołków nie musi być jednoznacznie wyznaczony. Zaproponuj wydajny algorytm znajdujący w danym dagu G=(V,E) najbliższego wspólnego przodka dla danych wierzchołków \(u,v\in V\).
Podpowiedź
Wyznacz zbiory przodków u i v przeszukiwaniem grafu. Spośród wspólnych przodków wybierz takiego, do którego nie prowadzi ścieżka z żadnego innego wspólnego przodka - jak pomaga w tym porządek topologiczny?
Zadanie 4 [14 punktów]#
W tym zadaniu rozważmy skończone słowa nad alfabetem {a, b}. Zaproponuj wydajne algorytmy rozwiązujące następujące problemy.
[3 punkty] Dla danego słowa \(s[1,\ldots,n]\), \(n > 1\), oblicz liczbę par pozycji \(1 \le i < j \le n\) takich, że podsłowo \(s[i,\ldots,j]\) zawiera tyle samo liter a co liter b.
[7 punktów] Znajdź w słowie s podsłowo długości 2k, gdzie \(2 \le 2k < n\), które zawiera taką samą liczbę liter a i b oraz występuje w s najczęściej.
[4 punkty] Zaprojektuj strukturę danych umożliwiającą wydajne wykonanie następujących operacji na dynamicznym słowie s w trybie on-line:
Ini:: s=[] // słowo puste,
Ins(x,i):: dodaj symbol \(x\in \{a, b\}\) na i-tą pozycję w słowie,
Del(i):: usuń symbol z pozycji i-tej w słowie,
a-Strings():: podaj liczbę różnych podsłów zbudowanych tylko z liter a.
Podpowiedź
Zamień a na +1, b na -1 i policz sumy prefiksowe. Kiedy s[i..j] ma tyle samo liter a co b? Policz pary równych sum prefiksowych (wartości są z zakresu \([-n, n]\)).
Rozważ wszystkie okna długości 2k; sumy prefiksowe mówią, które są zrównoważone. Nadaj równym oknom równe identyfikatory (KMR, tablica sufiksowa albo haszowanie) i wybierz najczęstszy identyfikator wśród okien zrównoważonych.
Ile jest różnych podsłów z samych liter a, jeśli najdłuższy blok liter a ma długość L? Trzymaj słowo w zrównoważonym drzewie z niejawnymi kluczami (pozycjami), wzbogaconym o najdłuższy blok liter a oraz długości prefiksu i sufiksu z samych a w poddrzewie.