1. Klasówka 2002/03#
Zadanie 1#
Zaproponuj optymalny algorytm sortujący przez porównania \(6\) elementów. Udowodnij poprawność i optymalność swojej konstrukcji.
Zadanie 2#
Rozgrywane są zawody szachowe, w których grają \(11\)-latki, \(12\)-latki \(, \cdots, 10 + n\)-latki. Podział na grupy wiekowe jest znany. Liczba osób w każdym wieku wynosi \(m\). Chcemy wyłonić mistrzów \(a_1, \cdots, a_n\) takich, że \(a_i\) jest mistrzem w grupie do \(10+i\) lat włącznie. Zakładamy, że wyniki meczów są przechodnie. Jaka jest najmniejsza liczba partii, które należy rozegrać? Zaprojektować efektywny algorytm kojarzenia par, który pozwoli na rozegranie takiej właśnie liczby partii.
Zadanie 3#
Merlin ma czarodziejski naszyjnik składający się z \(2 \cdot n\) kamieni w kolorach białym i czarnym. Gdy chwyci naszyjnik lewą lub prawą ręką za biały kamień, to kamień zmienia kolor na czarny. Gdy chwyci lewą (prawą) ręką za czarny kamień to ten kamień oraz wszystkie czarne kamienie sąsiadujące z nim bezpośrednio z lewej (prawej) zmieniają kolor na biały. Załóżmy, że początkowo naszyjnik składa się tylko z białych kamieni. Niech kosztem dotknięcia będzie liczba kamieni, które zmieniają kolor. Oblicz zamortyzowany koszt dotknięcia.
Zadanie 4#
Zaprojektuj efektywny algorytm dla operacji \(DecreaseKey\) w kopcu lewicowym i przeanalizuj pesymistyczny koszt jej wykonania. Możesz założyć, że atrybutami każdego węzła w drzewie są klucz, wskaźniki do synów i ojca oraz odległość do najbliższego węzła zewnętrznego.