ASD ep 02 2005 3

Algorytmy i Struktury Danych

Egzamin poprawkowy 16 lutego 2005

Imię i nazwisko......................................................Nr indeksu.........................

Zadanie 3 Niech A i B będą zbiorami liczb naturalnych, spełniającymi warunek |A|=|B|=n. Naszym

zadaniem jest połączenie wszystkich elementów ze zbioru A z elementami ze zbioru B w pary, tak aby łączna

suma (po wszystkich parach) wartości bezwzględnych różnic elementów w parach była jak najmniejsza.

Polecenia:    ^

(a)    Podaj słowny opis strategii (metody) zachłannej rozwiązującej ten problem,

(b)    Oszacuj możliwie dokładnie złożoność rozwiązania względem parametru n (przyjmujemy, że operacją dominującą jest operacja odejmowania ),

(c)    podaj przykład danych wejściowych, dla których wynik zastosowania zaproponowanej strategii zachłannej nie będzie optymalny (oczywiście jeżeli takie dane istnieją, w przeciwnym przypadku uzasadnij fakt, że strategia jest optymalna dla rozważanego problemu).