Ctrl+K

Egzamin 2012/13 (01.02.2013)

Egzamin 2012/13 (01.02.2013)#

Zadanie 1 [15 punktów]#

Słowa kluczowe: struktury danych

W prostokątnym układzie współrzędnych danych jest n odcinków równoległych do osi OX lub do osi OY, o końcach w punktach o współrzędnych całkowitych z przedziału [0,n^3] i długościach nie większych od 5.

  1. [5 punktów] Zaproponuj strukturę danych o rozmiarze \(O(n)\), która umożliwi odpowiadanie w czasie \(O(\log n)\) na pytanie, czy punkt (a,b) o współrzędnych całkowitych jest pokrywany przez któryś z podanych odcinków.

  2. [5 punktów] Zaproponuj liniowy algorytm, który w czasie \(O(n)\) oblicza liczbę wszystkich punktów pokrywanych przez zadanie odcinki.

  3. [5 punktów] Zaproponuj liniowy algorytm, który policzy liczbę wszystkich par przecięć odcinków pionowych z poziomymi.

Zadanie 2 [7 punktów]#

Słowa kluczowe: sortowanie, Selection Sort

Oto algorytm SelectionSort sortujący n-elementową tablicę a[1..n]:

for i := n downto 2 do begin
    max := 1;
    for j := 2 to i do
        if a[j] > max then max := j;
    a[i] := a[max] // zamiana elementów
end

Zaprojektuj efektywny algorytm, który dla danej tablicy a obliczy ile razy algorytm SelectionSort zamienia elementy w tablicy.

Zadanie 3 [9 punktów]#

Słowa kluczowe: grafy

Grafy trójkątne to grafy spójne, w których każda dwuspójna składowa jest trójkątem (cyklem długości 3).

  1. [3 punkty] Udowodnij, że każdy graf trójkątny jest 3-kolorowalny.

  2. [3 punkty] Zaproponuj efektywny algorytm 3-kolorowania grafów trójkątnych.

  3. [3 punkty] Zaproponuj efektywny algorytm obliczania rozmiaru najliczniejszego skojarzenia w danym grafie trójkątnym.

Zadanie 4 [9 punktów]#

Słowa kluczowe: struktury danych, kopiec

Zaproponuj algorytm dodania do n-elementowego, zupełnego kopca binarnego k kluczy jednocześnie w czasie \(O(k + \log^2 n)\).

Uwaga: w rozwiązaniu każdego zadania uzasadnij poprawność swojej odpowiedzi oraz dokonaj analizy złożoności obliczeniowej zaproponowanych algorytmów.

Zawartość