Egzamin z ASD
4.03.2010

Zadanie 1 [17 punktów]

Dane są, dodatnia liczba całkowita n oraz tablica liczb całkowitych a[1..n]. Dla każdego podzbioru S zbioru indeksów {1,2, …, n} wagą w(S) nazywamy sumę elementów tablicy a o indeksach z tego zbioru. Przyjmujemy, ze wagą zbioru pustego jest 0. Zbiór indeksów nazwiemy niezależnym, jeśli nie zawiera dwóch kolejnych indeksów.

a: [7 punktów]
Zaproponuj algorytm, który obliczy wagę najcięższego zbioru niezależnego S.

b: [10 punktów]
Na tablicy a wykonujemy operacje:

NewVal(i,x):: a[i] := x; // 1 ≤ i ≤ n, x – liczba całkowita,
MaxWeight:: podaje wagę najcięższego zbioru niezależnego S.

Zaproponuj strukturę danych, która umożliwi efektywne wykonywanie operacji NewVal i MaxWeight.

Zadanie 2 [10 punktów]

Dana jest n-węzłowa kolejka dwumianowa Q oraz k nowych kluczy. Zaproponuj algorytm, który w czasie O(k + log n) rozszerzy Q o nowe klucze.

Zadanie 3 [7 punktów]

Zaproponuj algorytm, który dla danego tekstu T i dodatniej liczby całkowitej k wyznaczy liczbę niepustych podsłów pojawiający się w T co najmniej k razy.

Zadanie 4 [6 punktów]

Niech n będzie dodatnią liczbą całkowitą. Drabiną rzędu n nazywamy graf o wierzchołkach 1,2, …, 2n i krawędziach łączących wierzchołki 2k-1 z 2k, dla k = 1,2, …, n, oraz 2k-1 z 2k+1 i 2k z 2(k+1), dla k = 1,2, …, n-1. Ile różnych drzew DFS o korzeniu w wierzchołku 1 można zbudować dla drabiny rzędu n.