Egzamin 2007/08 (??.02.2008)#
Zadanie 1#
Zaprojektuje algorytm, który sprawdza czy w grafie G=(V,E) zadane dwie krawędzie leżą na tym samym cyklu elementarnym, i jeśli odpowiedzią jest TAK, to znajduje jeden z takich cykli. Uzasadnij poprawność swojego rozwiązania i przeprowadź analizę złożoności obliczeniowej zaproponowanego algorytmu.
Zadanie 2#
Zaproponuj strukturę danych, która umożliwia na n-wierzchołkowym grafie, początkowo nie zawierającym żadnych krawędzi, efektywne wykonywanie następującej operacji:
DodajKrawędź(u,v): jeśli u-v nie jest krawędzią w grafie, to dodaj u-v do grafu tylko wtedy, gdy nowy graf pozostaje grafem dwudzielnym.
Uzasadnij poprawność swojego rozwiązania i przeprowadź analizę złożoności czasowej i pamięciowej zaproponowanych algorytmów.
Zadanie 3#
Rozważ algorytm sortowania przez scalanie, w którym scalanie posortowanych ciągów polega na przeglądaniu ich od strony lewej do prawej i wybieranie jako kolejny element scalanego ciągu mniejszego z dwóch aktualnie oglądanych elementów. Dla przykładu przy scalaniu ciągów [1,3,7,9] z [2,4,5,8] porównywane są następujące pary elementów: <1,2>, <2,3>,<3,4>,<4,7>,<5,7>,<7,8>,<8,9>. Zaprojektuj efektywny algorytm, który dla danego ciągu różnych liczb a[1..n] i pary indeksów \(1 \le i < j \le n\), sprawdzi czy elementy a[i] oraz a[j] są ze sobą porównywane w rekurencyjnym algorytmie sortowania przez scalanie. Można założyć, że n jest postaci \(2^k\), dla pewnego k.
Zadanie 4#
Dany graf planarny G w postaci list sąsiedztwa. Zaprojektuj algorytm, który znajdzie wszystkie trójkąty (cykle długości 3) w grafie G. Wyraź złożoność swojego algorytmu w zależności od rozmiaru G i liczby znalezionych cykli.