1. Klasówka 2010/11

Zadanie 1

Słowa kluczowe: struktury danych, kolejka dwumianowa

Zaproponuj algorytm, który do (zwykłej) \(n\)-elementowej kolejki dwumianowej wstawia \(k\) kluczy w czasie \(O(k + \log n)\).

Zadanie 2

Słowa kluczowe: optymalne porównania

Wykaż, że każdy algorytm znajdujący medianę w zbiorze \(5\)-elementowym wykona w pesymistycznym przypadku co najmniej \(5\) porównań. Zaproponuj algorytm dokonujący tego za pomocą co najwyżej \(6\) porównań.

Zadanie 3

Słowa kluczowe: grafy

Dany jest graf skierowany z nieujemnymi wagami na krawędziach i trzy różne wierzchołki \(s\), \(t\), \(r\). Zaprojektuj algorytm, który znajduje taki wierzchołek \(v\), że suma \(d(v, s) + d(v, r) + d(v, t)\) jest najmniejsza, gdzie \(d(x,y)\) jest wagą najlżejszej ścieżki między \(x\) i \(y\). Uwaga: można założyć, że takie \(v\) istnieje.

Zadanie 4

Słowa kluczowe: sortowanie

Zaproponuj algorytm sortowania parami różnych liczb całkowitych \(x_1, x_2,\cdots, x_n\) przez porównania postaci:

Czy \(x_i < x_j\)?

z odpowiedziami:

• \(TAK\), gdy \(x_i < x_j\) i żadna z liczb sortowanego ciągu nie leży pomiędzy \(x_i\) i \(x_j\)

• \(NIE\), gdy \(x_j < x_i\) i żadna z liczb sortowanego ciągu nie leży pomiędzy \(x_j\) i \(x_i\)

• \(SASIEDNIE\), gdy \(x_i\), \(x_j\) bezpośrednio sąsiadują w posortowanym ciągu

Todo

Potrzebne jest wyjaśnienie do tego zadania, przykład nie pasuje do definicji.

Przykład: dla \(x_1 = 3\), \(x_2 = 7\), \(x_3 = 5\) odpowiedzią na „Czy \(x_2 < x_1\)?” jest \(NIE\), natomiast odpowiedzią na „Czy \(x_3 < x_1\)?” jest \(SASIEDNIE\).