Zadanie 1#

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(\mathrm{\#}0,\mathrm{\#}1)$.

Zadanie 2#

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#

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#

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$.