Klasówka 1 z ASD
27.11.2010

Zadanie 1 [5 punktów]

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

Zadanie 2 [5 punktów]

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 [5 punktów]

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 [5 punktów]

Zaproponuj algorytm sortowania parami różnych liczb całkowitych x1, x2, …, xn, n > 2,  przez zapytania postaci

Czy xi < xj?

z odpowiedziami

-	TAK, gdy xi < xj i co najmniej jedna z liczb sortowanego ciągu leży pomiędzy xi i xj
-	NIE, gdy xj < xi a i co najmniej jedna z liczb sortowanego ciągu leży pomiędzy xj i xi
-	SĄSIEDNIE, gdy xi, xj bezpośrednio sąsiadują w posortowanym ciągu

Przykład: dla x1 = 3, x2 = 7, x3 = 5 odpowiedzią na „Czy x2 < x1?” jest NIE, natomiast odpowiedzią na „Czy x3 < x1?” jest SĄSIEDNIE.

Złożoność mierzymy liczbą zapytań.