Informatyka MIMUW

Zadanie 1 (HeapSort - budowa kopca)

Udowodnij, że koszt budowy kopca w algorytmie HeapSort jest liniowy.

Zadanie 2 (HeapSort - łamigłówka)

Podaj zawartość tablicy 7-elementowej, dla której algorytm HeapSort wykona największą liczbę porównań.

Zadanie 3 (QuickSort - analiza, model losowej permutacji)

Rozważamy wersję algorytmu QuckSort, w którym podział jest dokonywany za pomocą poniższego algorytmu:

1  Partition(l,r)::
2  begin
3      v := a[l]; i := l; j := r+1;
4      repeat
5      //Niezmiennik: dla każdego k=l,l+1,...,i, a[k] <=   v,
6      //             dla każdego k=j,j+1,...,r+1, a[k] >= v,
7      //             j-i >= -1.   
8         repeat i := i+1 until a[i] >= v;
9         repeat j := j-1 until a[j]  <= v;
10       if i < j then 
11         a[i] :=: a[j]; 
12    until i >= j;
13    a[l] := a[j]; a[j] := v; 
14    return j
15 end;

1. Udowodnij, że jeżeli podtablica $a[l..p]$ jest losową permutacją zawartych w niej elementów (każda permutacja jest jednakowoprawdopodobna), to podtablice $a[l..j-1]$ i $a[j+1..r]$ są też losowymi podtablicami zawartych w nich elementów.
2. Przyjmijmy bez straty ogólności, że faza podziału kosztuje dokładnie $p-l+2$ porównań, przy $p > l$. Uzasadnij, że następujące równanie jest równaniem na oczekiwaną liczbę porównań wykonywanych w algorytmie QuickSort.
   $\displaystyle A(0) = 0, A(1) = 1$,
   $\displaystyle A(n) = n + 1 + \frac{1}{n}\sum_{s = 1}^n (A(s-1) + A(n-s))$, dla $\displaystyle n > 1$.
3. Rozwiąż powyższe równanie rekurencyjne.

Zadanie 4 (Średnia liczba porównań - dolne ograniczenie)

Udowodnij, że średnia liczba porównań niezbędnych do posortowania ciągu $n$-elementowego w modelu losowej permutacji wynosi co najmniej $n\log n - 1.45n$.