Wymagania i kryteria oceniania
Należy zaimplementować algorytm wyznaczający najbliższego wspólnego przodka (ang. Lowest Common Ancestor, LCA) dwóch wierzchołków w drzewie oraz opanować (ze zrozumieniem) dotyczącą go teorię. Najbliższym wspólnym przodkiem wierzchołków u i v w drzewie ukorzenionym nazywamy położony najgłębiej (najdalej od korzenia) wierzchołek, który jest jednocześnie przodkiem u i v (leży na obu ścieżkach: od korzenia do u i od korzenia do v); przyjmujemy przy tym, że każdy wierzchołek jest swoim własnym przodkiem. Przez V oznaczamy liczbę wierzchołków drzewa, a przez Q – liczbę zapytań. Program powinien wczytać drzewo (np. do list sąsiedztwa) albo mieć je wprowadzone na stałe w programie, a następnie odpowiadać na kolejne zapytania; każde zapytanie zawiera parę wierzchołków, dla których należy wyznaczyć i wypisać najbliższego wspólnego przodka. Ocena zależy od wybranego wariantu.
Warianty
Algorytm bez wstępnego przetwarzania (na ocenę 3)
Algorytm odpowiadający na pojedyncze zapytanie w czasie O(V), czyli znajdujący wyniki dla wszystkich Q zapytań w czasie O(QV).
Algorytm ze wstępnym przetwarzaniem drzewa (na ocenę 4,5)
Algorytm odpowiadający na pojedyncze zapytanie w czasie O(log(V)), ze wstępnym przetwarzaniem drzewa (budową struktury wspomagającej) w czasie O(V log(V)); cały program działa więc w czasie O(V log(V) + Q log(V)).
Wariant ten można zrealizować za pomocą metody ze wskaźnikami skokowymi (ang. binary lifting).
Wyznaczanie LCA względem dowolnego korzenia (+0,5 do oceny)
Dodatkowo, poza wariantem na ocenę 4,5, można otrzymać +0,5 do oceny (tj. ocenę 5), jeśli program potrafi wyznaczyć najbliższego wspólnego przodka zadanej pary wierzchołków względem dowolnego, wskazanego w zapytaniu korzenia drzewa (a nie tylko względem z góry ustalonego korzenia), bez pogorszenia asymptotycznego czasu odpowiedzi na zapytanie ani czasu wstępnego przetwarzania drzewa.
Przykładowe pytania sprawdzające
Dla wszystkich wariantów
- Jak zdefiniowany jest najbliższy wspólny przodek dwóch wierzchołków w drzewie zakorzenionym? Czym różni się od dowolnego wspólnego przodka?
- Zilustrować działanie zaimplementowanego algorytmu dla zadanego drzewa i wskazanej pary wierzchołków.
- Jaka jest złożoność czasowa oraz pamięciowa zaimplementowanego algorytmu? Wskazać miejsca w kodzie (pętle, rekurencje), które za to odpowiadają.
- Jaka jest złożoność czasowa pojedynczego zapytania, a jaka – wstępnego przetwarzania drzewa (o ile program je wykonuje)?
- Czym różni się drzewo od grafu? Jakie własności drzewa wykorzystuje zaimplementowany algorytm?
Dla wariantu ze wstępnym przetwarzaniem drzewa (ze wskaźnikami skokowymi, ang. binary lifting)
- Jak zbudowana jest struktura wspomagająca, tj. tablica wskaźników skokowych – jakie informacje przechowuje dla każdego wierzchołka?
- Jak wyznaczyć 2^i-tego przodka wierzchołka na podstawie wskaźników obliczonych dla mniejszych wartości i? Podaj odpowiednią zależność.
- W jaki sposób wskaźniki skokowe pozwalają pominąć („przeskoczyć”) wiele wierzchołków naraz oraz wyrównać głębokość obu wierzchołków?
- Zilustrować działanie wskaźników skokowych przy odpowiedzi na przykładowe zapytanie.
- Dlaczego wstępne przetwarzanie drzewa (budowa tablicy wskaźników skokowych) ma złożoność (czasową oraz pamięciową) O(V log(V))?
- Jak działa użyty w implementacji algorytm przechodzenia drzewa (np. DFS) i jaką ma złożoność?
Dla wariantu z dowolnym korzeniem
- Jak zmienia się wynik, gdy drzewo zostanie zakorzenione w innym wierzchołku? W jaki sposób obsłużyć korzeń wskazany w zapytaniu, nie powtarzając wstępnego przetwarzania drzewa?