Ćwiczenia

Zawartość ćwiczeń z ASD

Ćwiczenia 1: poprawność i złożność algorytmu

Zadanie 1 (Potęgowanie binarne)

Zaprojektuj algorytm, który dla danych nieujemnej liczby całkowitej \( \displaystyle n \) i liczby całkowitej \( \displaystyle a \), policzy wartość \( \displaystyle a^n \). Przyjmij za operację dominującą mnożenie dwóch liczb całkowitych i w tym modelu:

  1. zaproponuj algorytm działający w czasie \( \displaystyle O(\log n) \),
  2. udowodnij poprawność swojego algorytmu metodą niezmienników.

Zadanie 2 (Liczby Fibonacciego)

Liczby Fibonacciego definiuje się jak następuje:
\( \displaystyle F_0 = 0, F_1 = 1 \),
\( \displaystyle F_n = F_{n-2} + F_{n-1} \), dla \( \displaystyle n > 1 \).
Dla danej nieujemnej liczby całkowitej \( \displaystyle n \), należy policzyć liczbę \( \displaystyle F_n \). Za operacje dominujące przyjmujemy operacje arytmetyczne - dodawanie, odejmowanie lub mnożenie dwóch liczb całkowitych.

  1. Ile dodawań wykonamy obliczając \( \displaystyle F_n \) rekurencyjnie?
  2. Zastosuj metodę programowania dynamicznego (tablicowania wcześniej policzonych wyników) do policzenia \( \displaystyle F_n \) w czasie \( \displaystyle O(n) \).
  3. Wiadomo, że

    4. \[
    \left[ \begin{array}{c}
    F_{n+1}\\
    F_n
    \end{array} \right]
    =
    \left[ \begin{array}{cc}
    1 & 1\\
    1 & 0 \end{array} \right]
    \left[ \begin{array}{c}
    F_n\\
    F_{n-1}
    \end{array} \right].
    \]
    Wykorzystaj powyższy fakt do zaproponowania algorytmu obliczania \( \displaystyle F_n \) w czasie \( \displaystyle O(\log n) \).

Zadanie 3 (Pary liczb)

Dana jest dodatnia liczba całkowita \( \displaystyle n \), uporządkowana niemalejąco tablica dodatnich liczb całkowitych \( \displaystyle A[0..n-1] \) oraz dodatnia liczba całkowita \( \displaystyle C \). Zaprojektuj efektywny algorytm wyznaczenia najliczniejszego zbioru rozłącznych par elementów tablicy \( \displaystyle A \) takich, że suma elementów w każdej parze jest nie większa niż \( \displaystyle C \). Uzasadnij poprawność swojego algorytmu i dokonaj analizy jego złożoności obliczeniowej.

Zadanie 4 (Inwersje I)

Niech \( \displaystyle A[0..n-1] \) będzie tablicą (ciągiem) liczb całkowitych. Parę indeksów \( \displaystyle (i,j) \), \( \displaystyle 0 \le i < j < n \), nazwiemy inwersją tablicy \( \displaystyle A \) wtedy i tylko wtedy, gdy \( \displaystyle A[i] > A[j]. \)

  1. Jaka może być najmniejsza, a jaka największa liczba inwersji w tablicy \( \displaystyle A \)?.
  2. Przy założeniu, że w tablicy \( \displaystyle A \) zapisano permutację liczb od \( \displaystyle 0, 1, \ldots, n-1 \), zaproponuj algorytm typu "dziel i rządź" wyznaczający liczbę inwersji w \( \displaystyle A \) w czasie \( \displaystyle O(n\log n) \). Uzasadnij poprawność i dononaj analizy złożoności obliczeniowej zaproponowanego algorytmu.
  3. Zaproponuj algorytm programowania dynamicznego, który dla danych liczb całkowitych \( \displaystyle k, n \) takich, że \( \displaystyle n > 0, 0 \le k \le \frac{n(n-1)}{2} \), obliczy liczbę permutacji liczb \( \displaystyle 0, 1, \ldots, n-1 \), które zawierają dokładnie \( \displaystyle k \) inwersji.

Zadanie 5 (Inwersje II)

Niech \( \displaystyle A[0..n-1] \) będzie \( \displaystyle n\)-elementowym ciągiem liczbowym. Wektorem inwersji dla ciągu \( \displaystyle A \) nazywamy tablicę \( \displaystyle B[0..n-1] \) taką, że \( \displaystyle B[j] = |\{0 \le i < j: B[i] > B[j]\}| \).

  1. Udowodnij, że istnieje wzajemnie jednoznaczna odpowiedniość pomiędzy permutacjami \( \displaystyle A[0..n-1] \) liczb \( \displaystyle 0, 1, \ldots, n-1 \), a wektorami \( \displaystyle B[0..n-1] \) takimi, że \( \displaystyle 0 \le B[j] < j+1 \), dla \( \displaystyle j = 0, 1, \ldots, n-1 \).
  2. Dane są, dodatnia liczba całkowita \( \displaystyle n \) oraz wektor (inwersji) \( \displaystyle B[0..n-1] \), \( \displaystyle 0 \le B[j] < j+1 \), dla \( \displaystyle j = 0, 1, \ldots, n-1 \). Zaprojektuj algorytm, który w czasie \( \displaystyle O(n\log n) \) znajdzie permutację \( \displaystyle A[0..n-1] \) liczb \( \displaystyle 0, 1, \ldots, n-1 \), dla której wektorem inwersji jest \( \displaystyle B \).

Ćwiczenia 2: sortowanie, część I

Zadanie 1 (Algorytm Shella)

  1. Udowodnij, że jeżeli dwuwymiarową tablicę liczbową, posortowaną niemalejąco kolumnami, posortujemy wierszami, to nadal będzie ona posortowana kolumnami.
  2. Niech \( \displaystyle A[1..n] \) będzie tablicą liczb całkowitych i niech \( \displaystyle h \) będzie dodatnią liczbą całkowitą. Powiem, że \( \displaystyle A \) jest \( h \)-posortowana, jeżeli dla każdego \( \displaystyle i = 1, \ldots, n - h \), \( \displaystyle A[i] \le A[i+h]\). Algorytm \(h\)-sortowania nazywamy każdy algorytm, który sortuje niemalejąco i niezależnie wszystkie podtablice \( \displaystyle A[i], A[i+h], A[i+2h], \ldots \), dla \( \displaystyle i = 1, 2, \ldots, \min( n, h)\). Udowodnij, że jeżeli \(h_2\)-posortujemy \(h_1\)-posortowaną tablicę \( A \), to będzie ona nadal \(h_1\)-posortowana.
  3. Niech \( k \) będzie dodatnią liczbą całkowitą i niech \( h_1, h_2, \ldots, h_k \) będzie malejącym ciągiem dodatnich liczb całkowitych, w którym \( h_k = 1\). Rozważmy następujący algorytm sortowania:

    for i := 1 to k do
    \( \mbox{ }\) wykonaj \( h_i \)-sortowanie algorytmem sortowania przez wstawianie, niezależnie na każdym podciągu;

    Udowodnij, że powyższy algorytm sortuje.

  4. Załóżmy, że tablica \( A \) jest jednocześnie 2- i 3-posortowana. Ile wynosi maksymalna liczba inwersji w takiej tablicy?
  5. Zanalizuj złożoność algorytmu Shella przy założeniu, że ciąg \( h_1, h_2, \ldots, h_k \) składa się ze wszystkich liczb postaci \( 2^p3^q \) i mniejszych od \( n \), gdzie \( p \) i \( q \) są nieujemnymi liczbami całkowitymi.

Zadanie 2 (Przesunięcie cykliczne w miejscu)

Dana jest \(n\)-elementowa tablica \(A[1..n]\) oraz liczba całkowita \(k \in [1..n] \). Zaproponuj liniowy algorytmy przesunięcia cyklicznego elementów tablic \( A \) o \( k \) pozycji w lewo.

Przykład: ciąg \( [1,2,3,4,5] \) przesunięty cyklicznie o 2 w lewo ma postać \( [3,4,5,1,2] \).

Zadanie 3 (Proste scalanie w miejscu)

Dane są dodatnie liczby całkowite \( k, n \), \( k \le n\), oraz tablica liczb całkowitych \( A[1..n] \) taka, że podtablice \( a[1..k] \) i \( a[k+1..n] \) są uporządkowane nie malejąco. Przy założeniu, że \( k = O(\sqrt n) \) zaproponuj algorytm sortowania tablicy (scalania dwóch ciągów uporządkowanych) \( A \) w miejscu i w czasie \(O(n)\).

Zadanie 4 (Sortowanie blokowe)

Niech \( \displaystyle A[1..n] \) będzie tablicą liczb całkowitych. Przyjmijmy, że \( \displaystyle n = r^2 \) dla pewnego naturalnego \( r \). Zawartość tablic \( A \) traktujemy jako zapis \( r \) rekordów (bloków). Każdy rekord-blok zajmuje spójny fragment tablicy od pozycji \( (i-1)r+1 \) do pozycji \( ir \), dla pewnego \( i \in [1..r] \). Kluczem w rekordzie jest ostatni element bloku. Zaproponuj sortowanie rekordów względem ich kluczy. Twój algorytm powinien działać w miejscu i w czasie liniowym. Kolejność elementów w rekordzie nie może ulec zmianie.

Zadanie 5 (Scalanie w miejscu)

Dane są dodatnie liczby całkowite \( k \le n \) oraz tablica liczb całkowitych \( A[1..n] \) taka, że podtablice \( A[1..k] \) i \( A[k+1..n] \) są uporządkowane nie malejąco. Zaproponuj algorytm sortowania tablicy (scalania dwóch ciągów uporządkowanych) \( A \) w miejscu i w czasie \(O(n)\).

Zadanie 6 (Sortowanie w miejscu i stabilnie)

Zaproponuj algorytm, który sortuje \(n\)-elementowe ciągi zer i jedynek w czasie \( O(n\log n)\), w miejscu i stabilnie.

Zadanie 7 (Sortowanie optymalne 5 elementów)

Zaproponuj algorytm sortujący za pomocą minimalnej liczby porównań ciągi 5-elementowe.

Ćwiczenia 3: sortowanie, część II

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 \).

Ćwiczenia 4: sortowanie "liniowe", selekcja

Zadanie 1 (sortowanie liczb całkowitych z ograniczonego przedziału)

Zaproponuj algorytm, który w czasie liniowym sortuje \( n \) liczb całkowitych z przedziału \( [0..n^3] \).

Zadanie 2 (izomorfizm drzew)

Zaproponuj algorytm, który w czasie liniowym sprawdzi, czy dane dwa \( n \)-wierzchołkowe drzewa są izomorficzne.
Wskazówka: udowodnij, że zadanie to można w czasie liniowym zredukować do zadania testowania izomorfizmu drzew ukorzenionych. Mając dwa drzewa z korzeniami przetwarzaj je poziomami, poczynając od poziomu na największej głębokości, sprawdzając, czy na każdym poziomie jest taka sama liczba drzew parami izomorficznych.

Zadanie 3 (wyznaczanie minimum)

Udowodnij, że każdy algorytm wyznaczający minimum w zbiorze \( n \)-elementowym za pomocą porównań, wymaga wykonania w pesymistycznym przypadku co najmniej \( n-1\) porównań.

Zadanie 4 (\( k \)-ty co do wielkości )

Zaproponuj algorytm wyznaczania elementu drugiego co do wielkości w zbiorze \( n \)-elementowym za pomocą co najwyżej \( n + \lceil \log n \rceil - 2 \) porównań. Uogólnij ten algorytm na algorytm znajdowania elementu \(k\)-tego co do wielkości za pomocą co najwyżej \(n- k + (k-1)\lceil \log (n-k+2) \rceil \) porównań.

Zadanie 5 (drugi co do wielkości - dolna granica)

Udowodnij, że każdy algorytm wyznaczający element drugi co do wielkości w zbiorze \( n \)-elementowym za pomocą porównań, wymaga wykonania w pesymistycznym przypadku co najmniej \( n + \lceil \log n \rceil - 2 \) porównań.
Wskazówka: pokaż, że każdy algorytm wyznaczający element drugi co do wielkości w pesymistycznym przypadku porównuje element minimalny z innymi co najmniej \( \lceil \log n \rceil \) razy.

Zadanie 6 (selekcja Hoare'a - analiza, model losowej permutacji)

Dokonaj analizy oczekiwanej złożoności obliczeniowej algorytmu selekcji Hoare'a w modelu losowej permutacji.

Ćwiczenia 5: zadania powtórkowe, część I

Poniżej zamieszczono zadania z pierwszych klasówek z ASD w latach 2007-2009. Niektóre zadania zawierają treści jeszcze nie poruszane na wykładzie i ćwiczeniach, ale dla pełności obrazu zawarto te klasówki w całości.


Klasówka 1
19.XII.2009

Zadanie 1 [8 punktów]

Dana jest tablica \(n \times n\), \(n > 1\), w której w każde pole wpisano liczbę całkowitą. Chcemy przejść z dolnego lewego rogu (z \( (1,1) \) ) do górnego prawego rogu (do \( (n,n) \) ) i wrócić, idąc w drodze z \( (1,1) \) zawsze w prawo lub w górę, a z powrotem - w lewo lub w dół. Z danego pola można przejść tylko na pola sąsiednie (współrzędne różnią się o 1 na dokładnie jednej pozycji). Żadne pole nie może się pojawić na całej trasie (czyli tam i z powrotem) więcej niż raz, poza polem (1,1), które pojawia się na początku i na końcu trasy. Zaprojektuj algorytm znajdowania najtańszej trasy, czyli takiej, na której suma wartości pól jest najmniejsza.

Zadanie 2 [7 punktów]

Niech \( n \) będzie liczbą całkowitą większą od 1, a \( X = \{ (x,y): x = 0, 1, \ldots, n-1, y = 0, 1, 2, 3, 4 \}\) zbiorem punktów na płaszczyźnie. Danych jest \( n \) różnych prostych, z których każda przechodzi przez dwa różne punkty ze zbioru \( X \), różniące się zawsze pierwszą współrzędną. Każda prosta zadana jest przez parę punktów \( [(x1,y1),(x2,y2)] \), \( x1 < x2 \). Zaprojektuj algorytm, który w czasie liniowym posortuje wszystkie proste niemalejąco względem ich kątów nachylenia do osi OX.

Zadanie 3 [5 punktów]

Podaj permutację liczb \( 1, 2, \ldots, 7 \), dla której algorytm HeapSort wykona największą liczbę porównań. Uwaga: należy wziąć pod uwagę obie fazy algorytmu – budowę kopca i właściwe sortowanie; poprawianie kopca odbywa się zawsze przez przesiewanie stosownego elementu w dół kopca; sortujemy rosnąco.

Uwaga: uzasadnij poprawność swoich rozwiązań oraz przeprowadź analizę złożoności obliczeniowej zaproponowanych algorytmów; każde zadanie rozwiązujemy na oddzielnej kartce.


Klasówka 1
21.11.2008

Zadanie 1 [5 punktów]

Oto możliwa implementacji procedury Partition w algorytmie QuickSort:

procedure Partition(le,pr: integer);
{ 1<=le<=pr<=n; a[pr+1] >= max(a[le..pr]) }
var
   i, j, s, v: integer;
begin
   if le < pr then
   begin
      s := (le + pr) div 2; v := a[s]; a[s] := a[le];
      i := le; j := pr+1;
      repeat
         repeat i := i+1 until a[i] >= v;
         repeat j := j -1 until a[j] <= v;
         if i < j then a[i] :=: a[j]; {zamiana wartości zmiennych}
     until j <= i;
     a[le] := a[j]; a[j] := v
  end
end;

a) Podaj zawartość tablicy \( a[1..n] \) dla \( n = 7 \) - permutację liczb \(1, 2, \ldots, n \), dla której algorytm QuickSort z powyższą procedurą Partition wykona:

  1. najmniejszą liczbę porównań [1 punkt]
  2. największą liczbę porównań [2 punkty]

b) Podaj zawartość tablicy \( a[1..n] \) dla \( n = 15 \) - permutację liczb \( 1, 2, \ldots, n \), dla której algorytm HeapSort buduje kopiec (pierwsza faza algorytmu) za pomocą

  1. najmniejszej liczby porównań [1 punkt]
  2. największej liczby porównań [1 punkt]

Odpowiedzi uzasadnij.
Uwaga: porównania dotyczą elementów tablicy \( a\), interesuje nas sortowanie w porządku niemalejącym.

Zadanie 2 [8 punktów]

Zaproponuj wzbogacenie kopca zupełnego w taki sposób, żeby efektywnie w czasie zamortyzowanym wykonywane były operacje: Min, DeleteMin, Insert, CountMin. Ostatnia operacja polega na podaniu aktualnej liczby elementów w kopcu o wartości równej Min. Przeprowadź analizę kosztu (zamortyzowanego) wykonania poszczególnych operacji.

Zadanie 3 [7 punktów]

Zaproponuj sposób wykonania operacji Inc(L) dla licznika Fibonacciego L w taki sposób, żeby po wykonaniu \(n\)-tej operacji wartość liczby \( n \) zapisanej w liczniku wynosiła \( L[0]*F_0 + L[1]*F_1 + L[2]*F_2 + \ldots \), gdzie \( L[i] \) to wartość \(i\)-tego bitu w liczniku, \( F_i \), to \( i \)-ta liczba Fibonacciego (\( F_0 = 0, F_1 = 1 \)). Operacje elementarne w rozwiązaniu, to zmiana wartości jednego bitu i odczytanie wartości jednego bitu. Zaproponuj rozwiązanie z jak najmniejszym kosztem zamortyzowanym. Dokonaj analizy kosztu zamortyzowanego metodą funkcji potencjału. Możesz założyć, że licznik jest początkowo wyzerowany.


Klasówka 1
19.XII.2007

Zadanie 1 [5 punktów]

Opracuj strukturę danych, która pozwala wykonywać następujące operacje:

  • Ini(\(k\)):: inicjacja struktury danych i ustalenie długości krotek liczb całkowitych na \( k \)
  • Insert(\( < a_1, a_2, \ldots, a_k > )\):: dodaje do struktury krotkę \( < a_1, a_2, \ldots, a_k > \)
  • Min:: podaje najmniejszą leksykograficznie krotkę w strukturze
  • ExtractMin:: usuwa najmniejszą leksykograficznie krotkę ze struktury

W Twoim rozwiązaniu operacje Insert i ExtractMin powinny by wykonywane w czasie \( O(\log n + k)\).

Zadanie 2 [5 punktów]

Udowodnij, że jeśli algorytm sortujący tablicę \( A[1..n] \) porównuje i zamienia wyłącznie elementy odległe co najwyżej o 2007 (tzn. jeśli porównuje \( A[i] \) z \( A[j] \), to \(|i-j| \le 2007\)), to jego pesymistyczny czas działania jest co najmniej kwadratowy.

Zadanie 3 [5 punktów]

Zaproponuj implementację następujących operacji na tablicy liczb naturalnych \(T[0..n+1]\), początkowo wypełnionej zerami, w taki sposób, żeby ich koszt zamortyzowany był stały.

  • Inc(\(i\)):: \( T[i] := T[i] + 1 \) // zawsze \( 0 < i < n+1 \)
  • BlockDec(\( i \)):: Jeśli \(T[i]=0\) nic nie rób. W przeciwnym przypadku znajdź najbliższy indeks \(j\) taki, że \(T[i] \ne T[j]\) (jeśli są dwa takie indeksy wybieramy mniejszy z nich). Dla każdego \(k\) pomiędzy \(i\) oraz \(j\) wykonaj \(T[k] := T[k] – 1\)

    • Zadanie 4 [5 punktów]

    Udowodnij, że dla każdego naturalnego \( n \) istnieje drzewo czerwono-czarne o co najmniej \( n \) wierzchołkach, które nie jest AVL-drzewem.

Ćwiczenia 6: najkrótsze ścieżki, kolejki priorytetowe, koszt zamortyzowany

Zadanie 1

\(d\)-kopcem typu MIN, \( d \ge 2\), nazywamy zupełne drzewo \(d\)-arne z kluczami rozmieszczonymi w porządku kopcowym typu MIN.

  • Zaproponuj wydajną implementację \(d\)-kopca w tablicy i dokonaj analizy złożoności obliczeniowych operacji kolejki priorytetowej: Build, Min, DeleteMin i DecreasKey.
  • W jaki sposób dobrać \(d\), żeby dostać jak najszybszą implementację algorytmu Dijkstry w zależności od liczby krawędzi.

    • Zadanie 2

    Drzewem lewicowym nazywamy drzewo binarne, w którym dla każdego wierzchołka długość skrajnie prawej ścieżki w jego lewym poddrzewie jest nie mniejsza od długości skrajnie prawej ścieżki w jego prawym poddrzewie. Kopcem lewicowym typu MIN nazywamy drzewo lewicowe z kluczami rozmieszczonym w porządku kopcowym typu MIN.
    Zaproponuj efektywne implementacje operacji kolejki priorytetowej (Build, Min, DeleteMin, DecraseKey) z użyciem kopców lewicowych.

    Zadanie 3

    Dana jest rodzina \(n\) niepustych podzbiorów zbioru \( \{1, 2, \ldots, n \}\), z których każdy to całkowitoliczbowy przedział postaci \([i,j]\), \(i \le j\). Zaprojektuj efektywny algorytm sprawdzania, czy zadana rodzina posiada system różnych reprezentantów, a jeśli tak, to podaje jeden z nich.

    Zadanie 4

    W algorytmie Dijkstry ciąg wartości otrzymywanych w wyniku wywołań funkcji Min jest niemalejący. Wykorzystaj ten fakt i zaproponuj implementację implementację algorytmu Dijkstry w czasie \( O(m + kn) \), gdy wagi krawędzi są liczbami całkowitym z przedziału \( [1..k ] \).

    Zadanie 5: rozgłaszanie w drzewie

    Dane jest drzewo z wyróżnionym wierzchołkiem \(s \) - źródłem rozgłaszania.

  • Zaprojektuj efektywny algorytm obliczający optymalny ze względu na czas schemat rozgłaszania ze źródła \( s \). Rozgłaszanie jest synchroniczne. W jednym takcie węzeł znający informację źródłową - na początku zna ją tylko źródło - może ją przesłać do co najwyżej 1 sąsiada. Celem jest rozesłanie informacji ze źródła do wszystkich węzłów w drzewie.
  • Zaprojektuj algorytm, który w czasie liniowym wyznaczy najlepsze źródło rozgłaszania w drzewie - tzn. taki węzeł, dla którego czas rozgłaszania w drzewie jest najmniejszy.

    • Ćwiczenia 7: kolejki priorytetowe, koszt zamortyzowany - część 2

    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.

    Ćwiczenia 8: drzewa wyszukiwań binarnych

    Zadanie 1 (rotacje)

    Danych jest \(n\) par liczb całkowitych, które się parami różnią na każdej pozycji. Pierwsze elementy para to klucze, drugie to priorytety.

    • Wykaż, że istnieje dokładnie jedno drzewo binarne, które jest drzewem wyszukiwań binarnych ze względu na klucze i jednocześnie kopcem typu MAX ze względu na priorytety.
    • Niech \( T \) będzie wyszukiwań drzewem binarnych ze względu na klucze. Opisz konstrukcję ciągu rotacji o długości \(O(n)\), które należy wykonać, żeby przekształcić drzewo \(T\) w drzewo BST, które będzie jednocześnie kopcem binarnym typu MAX ze względu na priorytety.
    • Zaproponuj algorytm, który w czasie liniowym znajdzie ciąg rotacji, o którym mowa w poprzednim punkcie

      • .

    Zadanie 2 (AVL-drzewa)

    • Opisz sposób wykonywania operacji Delete dla AVL-drzew
    • Do początkowo pustego AVL-drzewa wstawiamy kolejno elementy pewnej permutacji liczb \(1, 2, \ldots, n\). Dla \( n = 12 \) podaj permutacje dla których uzyskamy odpowiednio najniższe i najwyższe AVL-drzewo.
    • Podaj przykład AVL-drzewa, w którym usunięcie klucza wymaga \(\Omega (\log n)\) rotacji.

    Zadanie 3 (selekcja)

    Zaproponuj wzbogacenie drzewa wyszukiwań binarnych o możliwość wyszukiwania \(k\)-tek klucza co do wielkości w drzewie. Czy wzbogacenie można przeprowadzić na AVL-drzewach.

    Zadanie 4 (drzewa typu "splay")

    Wykaż, że jeżeli budujemy drzewo typu "splay" poprzez wstawienie \(n\) kluczy do początkowo pustego drzewa, to możemy otrzymać drzewo binarne o wysokości liniowej.

    Ćwiczenia 9: zadania powtórkowe, część II

    Poniżej zamieszczono zadania z klasówek nr 2 z lat poprzednich.


    Klasówka 2
    16.I.2009

    Zadanie 1 [10 punktów]

    a) [6 punktów] Drzewo AVL nazywamy wysmukłym jeśli zawiera minimalną liczbę wierzchołków wśród drzew AVL o wysokościach równych wysokości tego drzewa. Udowodnij, że wierzchołki każdego wysmukłego AVL-drzewa można pokolorować w taki sposób, żeby otrzymać drzewo czerwono-czarne.

    b) [2 punkty] Podaj ciąg różnych liczb całkowitych, które po wstawieniu do początkowo pustego drzewa dadzą wysmukłe AVL-drzewo o wysokości 4. Kolejność liczb powinna być taka, żeby podczas całego procesu wstawiania wystąpiła dokładnie jedna pojedyncza rotacja.

    c) [2 punkty] Podaj przykład 9-wierzchołkowego drzewa czerwono-czarnego, które nie jest AVL-drzewem.

    Zadanie 2 [10 punktów]

    Niech \( G \) będzie grafem dwuspójnym wierzchołkowo o co najmniej 3 wierzchołkach i niech \( T \) będzie DFS-drzewem rozpinającym grafu \( G \). Przez \(H(G,T)\) oznaczamy graf zorientowany otrzymany z \( G\) przez zorientowanie wszystkich krawędzi drzewowych w kierunku od ojca do syna, a krawędzi niedrzewowych w kierunku od potomka do przodka. Dla każdego wierzchołka \( v \) w grafie \( G \) definiujemy liczbę powrotną \( p(v) \) jako minimalną liczbę krawędzi niedrzewowych na ścieżce zorientowanej w \( H(G,T) \), prowadzącej z \( v \) do korzenia drzewa \( T \). Załóżmy, że graf G jest reprezentowany przez listy sąsiedztwa. Zaproponuj algorytm, który w czasie liniowym wyznacza pewne DFS-drzewo \( T \) w grafie \( G \) i oblicza dla każdego wierzchołka jego liczbę powrotną w \( H(G,T) \).

    Uwaga: uzasadnij poprawność swoich rozwiązań oraz przeprowadź analizę złożoności obliczeniowej zaproponowanych algorytmów; każde zadanie rozwiązujemy na oddzielnej kartce.


    Klasówka 2
    16.I.2008

    Zadanie 1 [5 punktów]

    Zaprojektuj (efektywny) algorytm, który sprawdza, czy w danym grafie (zadanym przez listy sąsiedztwa) istnieje cykl bez powtarzających się krawędzi o długości parzystej.

    Zadanie 2 [9 punktów]

    Dany jest skierowany multigraf \( G=(V,E) \), reprezentowany przez listy sąsiedztwa. \( G \) jest regularny, co oznacza, że dla dowolnych dwóch wierzchołków \( u, v \), ich stopnie wejściowe oraz ich stopnie wyjściowe są takie same i parzyste.

    Opisz algorytm, który podzieli zbiór krawędzi grafu \( G \) na 2 rozłączne zbiory \( E_1 \) i \( E_2 \) w taki sposób, że multigrafy \( G_1=(V, E_1) \) i \( G_2=(V, E_2) \) są regularne, oraz dla dowolnych wierzchołków \( u, v \), liczby krawędzi od \( u \) do \( v \) w \( G_1 \) i \( G_2 \) różnią się co najwyżej o 1.

    Uwaga: na liście krawędzi wychodzących z wierzchołka \( u \), każda multikrawędź \( u \rightarrow v \) jest reprezentowana przez swój koniec \( v \) i liczbę określającą jej krotność. Tak więc rozmiar danych wynosi co najwyżej \( O(n^2) \).

    Zadanie 3 [6 punktów]

    Niech \( W \) będzie \( n \)-kątem wypukłym, którego wierzchołki ponumerowano kolejno \( 1, 2, \ldots, n \), zgodnie z ruchem wskazówek zegara. Zaproponuj strukturę danych, która umożliwi (wydajne) wykonywanie następujących operacji:

    \( Przekątna(u,v) \):: sprawdza, czy w wielokącie \( W \) jest przekątna łącząca wierzchołki \(u, v\).

    \( DodajPrzekątną(u,v)\):: umieść w wielokącie \( W \) przekątną łączącą wierzchołki \( u, v \), jeśli tylko takiej przekątnej nie ma w wielokącie i nowa przekątna nie przetnie się z żadną inną przekątną we wnętrzu wielokąta.

    \( UsuńPrzekątną(u,v)\):: usuń przekątną łączącą \(u\) z \(v\), jeśli tylko taka przekątna jest w wielokącie.

    Początkowo w wielokącie nie umieszczono żadnej przekątnej.

    Uwaga: uzasadnij poprawność swoich rozwiązań oraz przeprowadź analizę złożoności obliczeniowej zaproponowanych algorytmów; każde zadanie rozwiązujemy na oddzielnej kartce.

    Ćwiczenia 10: zadania egzaminacyjne

    Poniżej zadania z egzaminów teoretycznych z lat ubiegłych. Archiwum zadań z egzaminów praktycznych można za to znaleźć pod adresem: http://smurf.mimuw.edu.pl/drupal6/node/766


    Egzamin z ASD
    27.I.2010

    Zadanie 1 [12 punktów]

    Dane jest \( n \)-węzłowe drzewo binarne z \( n \) różnymi kluczami w węzłach. Rozważamy następujący algorytm rekurencyjny przywracania porządku kopcowego w takim drzewie:

    Jeśli drzewo składa się z co najwyżej jednego węzła, to porządek kopcowy jest przywrócony.
    W przeciwnym przypadku znajdujemy w drzewie węzeł z najmniejszym kluczem i zamieniamy klucze z korzenia i ze znalezionego węzła, a następnie rekurencyjnie przywracamy porządek kopcowy w lewym i prawym poddrzewie korzenia.

    a) [4 punkty] Przyjmijmy, że węzeł z najmniejszym kluczem znajdujemy jedną z metod obchodzenia drzewa (preorder, inorder lub postorder).

    a1) [1 punkt] Jaka jest (asymptotycznie) pesymistyczna złożoność przywracania porządku kopcowego wyrażona jako funkcja \(n\)?
    a2) [3 punkty] Jaka jest złożoność powyższego algorytmu dla drzewa o wysokości \(\lfloor \log n \rfloor\)?

    b) [8 punktów] Zaproponuj strukturę danych, które umożliwi efektywne wykonywanie następujących operacji na \( n \)-węzłowym drzewie binarnym:

    \(Min(v)\):: znajdź w poddrzewie o korzeniu \(v\) węzeł z najmniejszym kluczem;
    \(Exch(u,v)\):: zamień klucze z węzłów \(u i v\).

    Zadanie 2 [18 punktów]

    Zaprojektuj strukturę danych umożliwiającą wykonywanie następujących operacji na \( n \)-wierzchołkowym lesie \( G \) (grafie nieskierowanym bez cykli):

    \(Init(G)\):: utwórz strukturę danych dla grafu \(G\) zadanego przez listy sąsiedztwa (możesz przyjąć \(V(G) = \{1,2, …, n\}\);
    \(Remove(u,v)\):: usuń krawędź \(u--v\) z grafu \(G\);
    \(Path(u,v)\):: sprawdź, czy w grafie \( G \) istnieje ścieżka pomiędzy wierzchołkami \( u \) i \( v \).

    a) [10 punktów] Zaprojektuj takie rozwiązanie, w którym całkowity koszt wykonania operacji \( Init \) i \( k \) operacji \(Remove/Path\) nie przekracza \(O(k + nlog n)\).
    b) [8 punktów] Załóżmy, że cały ciąg \( k \) operacji jest dany „off line” (tzn. jest znany w całości z góry), a celem jest obliczenie wyników wszystkich operacji \( Path \). Zaproponuj algorytm, który zrobi to w czasie \(o(nlog n)\), gdy \(k = O(n)\).

    Zadanie 3 [10 punktów]

    Zaproponuj efektywną strukturę danych, z pomocą której można wykonywać następujące operacje na dynamicznym zbiorze \( S \) odcinków domkniętych na prostej rzeczywistej:

    \(Init(S)\):: utwórz pusty zbiór odcinków (wykonywana tylko raz na początku algorytmu);
    \(Add(S,I)\):: dodaj do zbioru \(S\) nowy odcinek \(I\), ale tylko wtedy, gdy dla każdego odcinka \(J\) z \(S\), odcinek \(I\) ma puste przecięcie z \( J \) lub \( I \) jest zawarty w \( J \) lub \( J \) jest zawarty w \( I \);
    \( Delete(S,I) \):: usuń \( I \) z \( S \);
    \( Incl(S,I)\):: podaj ile odcinków z \(S\) jest zawartych w odcinku \(I\).

    Uwaga: uzasadnij poprawność swoich rozwiązań oraz przeprowadź analizę złożoności obliczeniowej zaproponowanych algorytmów; każde zadanie rozwiązujemy na oddzielnej kartce.