2. Klasówka 2016/17 (19.01.2017)#

Zadanie 1 (11 punktów)#

Słowa kluczowe: struktury danych, wzbogacanie

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:

  1. [4 punkty] d=2,

  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)#

Słowa kluczowe: grafy

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.

  1. [4 punkty] Zaprojektuj wydajny czasowo algorytm, który w kaktusie nieparzystym znajduje najliczniejsze skojarzenie.

  2. [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.