Egzamin poprawkowy 2003/04

Zadanie 1

Słowa kluczowe: statystyki pozycyjne, asymptotycznie optymalny

Dana jest tablica \(a[1..n]\) of \(0..1\), w której wszystkie zera poprzedzają wszystkie jedynki. Zaproponuj efektywny algorytm obliczania liczby zer w tablicy \(a\) o złożoności zależnej od liczby \(\min(\#0, \#1)\).

Podpowiedź

Stosując skoki \(2^i\) wyznaczamy przybliżoną wartość min(#0, #1) (sprawdzamy wartości a[2^i] i a[n+1-2^i]). Następnie wyszukiwanie binarne.

Zadanie 2

Słowa kluczowe: grafy; kaktusy

Kaktusy to grafy, które definiujemy jak następuje:

1. cykl elementarny jest kaktusem;

2. jeśli \(K_1\) i \(K_2\) są kaktusami o dokładnie jednym wspólnym wierzchołku, to graf \(K_1 + K_2\) jest kaktusem;

3. żaden inny graf nie jest kaktusem.

4. Zaproponuj efektywny algorytm, który dla danego (przez listy sąsiedztwa) kaktusa \(K\) obliczy długość najdłuższego cyklu elementarnego w nim zawartego.

5. Przyjmijmy, że krawędziom kaktusa przypisane są dodatnie wagi i wyróżniony jest wierzchołek \(s\). Zaproponuj efektywny algorytm wyznaczenia drzewa najlżejszych ścieżek w \(K\) o korzeniu w \(s\). To znaczy, dla każdego \(v \in V - \{x\}\) wyznacz wierzchołek \(p[v]\), który leży na pewnej, najlżejszej ścieżce z \(v\) do \(s\).

Zadanie 3

Słowa kluczowe: struktury danych, BST, kopiec, Treap

Dana jest permutacja \(p[1..n]\) liczb \(1..n\), gdzie \(p[i]\) jest priorytetem klucza \(i\). Zaproponuj efektywny algorytm budowy drzewa poszukiwań binarnych dla kluczy \(1, \cdots, n\), które jest jednocześnie kopcem binarnym dla priorytetów \(p[1], \cdots, p[n]\), z najmniejszym priorytetem w korzeniu.

Zadanie 4

Słowa kluczowe: sortowanie

Tablica liczb całkowitych \(a[1..n]\) spełnia następujący warunek: dla każdego \(i = 1, \cdots, n - 1 : |a[i] - a[i + 1]| < 7\). Zaproponuj liniowy algorytm sortowania tablicy \(a\).