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.

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.

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.

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.