2. Klasówka 2016/17 (19.01.2017)#
Zadanie 1 (11 punktów)#
Zaprojektuj strukturę danych, która implementuje standardowe operacje słownika reprezentującego zbiór S liczb całkowitych (Insert, Delete, Find) oraz dodatkowo operację:
MaxSubset(d, S):: podaj rozmiar maksymalnego podzbioru zbioru S, w którym każde dwie liczby różnią się co najmniej o d, gdzie d jest zadaną z góry stałą całkowitą.
Podaj rozwiązanie dla:
[4 punkty] d=2,
[7 punktów] d=10.
Uzasadnij poprawność swoich rozwiązań i przeanalizuj złożoność czasową poszczególnych operacji na strukturze danych względem n (aktualnego rozmiaru struktury).
Zadanie 2 (9 punktów)#
Kaktusem nazywamy graf, w którym każda dwuspójna składowa jest krawędzią lub cyklem, Kaktus jest nieparzysty, gdy każda jego dwuspójna składowa jest cyklem o długości nieparzystej.
[4 punkty] Zaprojektuj wydajny czasowo algorytm, który w kaktusie nieparzystym znajduje najliczniejsze skojarzenie.
[5 punktów] Załóżmy, że krawędziom kaktusa przypisano całkowitoliczbowe wagi. Zaprojektuj wydajny czasowo algorytm, który w ważonym kaktusie G=(V,E) znajduje minimalną wagę DFS drzewa rozpinającego zakorzenionego w zadanym wierzchołku s. Uwaga: DFS drzewo rozpinające, to drzewo ukorzenione i takie, że krawędzie niedrzewowe łączą tylko potomków z przodkami w tym drzewie.