Informatyka MIMUW

Zadanie 1 (symulacja kolejki dwoma stosami)

Opracuj sposób implementacji kolejki typu FIFO z pomocą dwóch stosów w taki sposób, żeby zamortyzowany koszt operacji stosowych był stały. Dokonaj analizy kosztu metodami księgowania i funkcji potencjału.

Zadanie 2 (stos w tablicy dynamicznej)

Reprezentujemy stos w dynamicznej tablicy \(S[1..n]\), gdzie \(n = 2^m\), dla pewnego całkowitego \(m \ge 0 \). Poszczególne operacje implementujemy następująco:

1  Ini:: //wykonywana tylko raz
2  begin
3      New(S[1..1]);
4      n := 1; k := 0;
5  end;

1  Push(e)::
2  begin
3      if k = n then
4      begin
5          New(T[1..2*n]);
6          for i := 1 to n do T[i] := S[i];
7          dispose(S);
8          n := 2*n;
9          S := T
10    end;
10    k := k + 1;
11    S[k] := e
12 end;

1  Pop::
2  begin
3      if k > 0 then
4      begin
5          e := T[k];
6          k := k - 1
7      end;
8      if (n > 2) and (k = n/4) then
10    begin
11        New(T[1..n/2]); 
12        for i := 1 to k do T[i] := S[i];
13        dispose(S);
14        S := T;
15        n := n/2
15    end;
10    return e
11 end;

Załóżmy, że operacje alokacji i zwalniania pamięci wykonują się w czasie stałym. Zanalizuj koszt zamortyzowany operacji Push i Pop metodami księgowania i funkcji potencjału.

Zadanie 3

Dany jest spójny graf nieskierowany \(G=(V,E)\) z dodatnimi, całkowitoliczbowymi wagami na krawędziach oraz wyróżnione wierzchołki \( s \) i \( t \). Zaprojektuj algorytm, który spośród najlżejszych ścieżek pomiędzy \( s \) i \( t \) wyznaczy jedną, z najmniejszą liczbą krawędzi.

Zadanie 4

Dokonaj analizy kosztu pesymistycznego operacji DeleteMin, Insert oraz DecreaseKey na kopcach Fibonacciego.

Zadanie 5

Dokonaj analizy kosztu zamortyzowanego poszczególnych operacji w przypadku, gdy operacja DecreaseKey polega tylko na odcięciu węzła ze zmniejszanym kluczem od jego ojca i umieszczeniu go wraz ze swoim poddrzewem na liście korzeni.