Advent of Code dla tych, co chcą się sprawdzić w rozwiązywaniu ciekawych problemów.

Materiały do laboratoriów z przedmiotu Algorytmy 2

• Krótkie przypomnienie C++ na przykładzie listy jednokierunkowej
• Harmonogram dla S1
• Konspekty do zajęć
  1. Lista (PDF) (2 tygodnie)
  2. Tablica dynamiczna (PDF) (1 tydzień)
  3. Drzewo BST (PDF) (1 tydzień)
  4. Drzewo czerwono-czarne (PDF) (2 tygodnie)
  5. Kopiec binarny (PDF) (1 tydzień)
  6. Tablica mieszająca (PDF) (1 tydzień)
  7. Sortowanie przez kopcowanie, przez zliczanie, i kubełkowe (PDF) (2 tygodnie)
  8. Algorytm Kruskala i struktura Union-Find (PDF, ZIP) (2 tygodnie)
  9. Powłoka wypukła, algorytm Grahama (PDF, ZIP) (1 tydzień)
  10. Szybka transformacja Fouriera (FFT) (PDF) (1 tydzień)
  11. Zadanie opcjonalne (do wyboru: algorytm Floyda-Warshalla, lista z przeskokami, algorytm DSW)
• Zasady zaliczenia
• C++ Core Guidelines (dla tych, co chcą tworzyć dobry kod w nowym C++)
  
• Kod (standard C++17) na przetestowanie operacji wstawiania/usuwania w binarnym drzewie poszukiwań (metoda get_min_node_data() zwraca dane z węzła minimalnego, czyli tego najbardziej na lewo):
  
  
  #include <map> #include <vector> #include <numeric> #include <algorithm> void test() { std::vector<int> v(8); std::iota(v.begin(), v.end(), 0); std::map<int, int> heights, min_node_data; do { bst<int> t; for (int i : v) t.add(i, std::less<int>{}); ++heights[t.height()]; for (int i : v) { ++min_node_data[t.get_min_node_data()]; t.remove(i, std::less<int>{}); } } while (std::next_permutation(v.begin(), v.end())); for (auto [height, cnt] : heights) std::cout << height << ": " << cnt << std::endl; std::cout << "***" << std::endl; for (auto [data, cnt] : min_node_data) std::cout << data << ": " << cnt << std::endl; }
  Oczekiwany wynik:
  4: 11360 5: 18816 6: 8352 7: 1664 8: 128 *** 0: 181440 1: 60480 2: 30240 3: 18144 4: 12096 5: 8640 6: 6480 7: 5040
• Kod (standard C++17) na przetestowanie operacji wstawiania w drzewie czerwono-czarnym (metoda get_root_data() zwraca dane z korzenia):
  
  
  #include <map> #include <vector> #include <numeric> #include <algorithm> void test() { std::vector<int> v(8); std::iota(v.begin(), v.end(), 0); std::map<int, int> heights, root_data; do { rbt<int> t; for (int i : v) t.add(i, std::less<int>{}); ++heights[t.height()]; ++root_data[t.get_root_data()]; } while (std::next_permutation(v.begin(), v.end())); for (auto [height, cnt] : heights) std::cout << height << ": " << cnt << std::endl; std::cout << "***" << std::endl; for (auto [data, cnt] : root_data) std::cout << data << ": " << cnt << std::endl; }
  Oczekiwany wynik:
  4: 40320 *** 1: 2592 2: 7200 3: 10368 4: 10368 5: 7200 6: 2592
• Operacje związane ze wstawianiem nowego węzła do drzewa czerwono-czarnego:
  
  

  Przekolorowanie		Rekonstrukcja drzewa
  Wstawiono nowy węzeł A (nowy węzeł ma zawsze kolor czerwony). Po wstawieniu węzła występuje kolizja z rodzicem (węzeł czerwony musi mieć czarne potomstwo). Ponieważ rodzic węzła A i wujek węzła A są czerwoni, trzeba dokonać przekolorowania (kolor czerwony ulegnie propagacji w górę drzewa). Czynność trzeba powtarzać tak długo, dopóki występuje konflikt kolorów i nie osiągneliśmy korzenia i wujek węzła jest czerwony.		Gdy występuje konflikt kolorów i wujek węzła jest czarny, trzeba dokonać jednej lub dwu rotacji. Gdy konflikt ma kształt LR (dziecko jest prawym potomkiem rodzica, a rodzic jest lewym potomkiem dziadka: patrz – trzeci rysunek od lewej), to trzeba dokonać lewej rotacji pary węzłów dziecko-rodzic, dzięki czemu konflikt uzyska postać LL (rysunek drugi od prawej strony) – w tym wypadku trzeba dokonać prawej rotacji pary węzłów rodzic-dziadek i odwrócić kolory rodzica i dziadka (rodzic staje się czarny, a dziadek czerwony). Konflikty RL i RR są lustrzanym odbiciem konfliktów LR i LL.
  		Struktura drzewa przed dokonaniem lewej rotacji pary węzłów B-A	Struktura drzewa przed dokonaniem prawej rotacji pary węzłów C-B	Naprawione drzewo

• Drzewo czerwono-czarne z przykładu:
  

  Wynik polecenia dot -Tpng -o rbt.png rbt.gv	Zawartość pliku rbt.gv
  	digraph { "{62, a}" [color=black]; "{55, q}" [color=black]; "{35, d}" [color=red]; "{57, n}" [color=red]; "{72, v}" [color=red]; "{69, u}" [color=black]; "{83, i}" [color=black]; "{74, x}" [color=red]; "{62, a}" -> "{55, q}" "{55, q}" -> "{35, d}" "{55, q}" -> "{57, n}" "{62, a}" -> "{72, v}" "{72, v}" -> "{69, u}" "{72, v}" -> "{83, i}" "{83, i}" -> "{74, x}" }

  ---

• Dla chętnych — operacja usuwania węzła z drzewa czerwono-czarnego. Pomocna może okazać się ta lub ta prezentacja. W rzeczywistej implementacji nie trzeba wprowadzać dodatkowego koloru — proponuję napisać metodę, która przyjmuje węzeł traktowany jako podwójnie czarny i naprawia drzewo.
  
  • Przypadek I — usuwany węzeł nie ma potomków.
    Jeżeli usuwany węzeł jest koloru czerwonego, to zwyczajnie go usuń (jak w binarnym drzewie poszukiwań), a przeciwnym wypadku oznacz usuwany węzeł jako podwójnie czarny (chwilowo potraktujmy go jako podwójnie czarny pusty liść), dokonaj naprawy drzewa i usuń tenże węzeł (jak BST).
  • Przypadek II — usuwany węzeł ma jednego potomka.
    Zwyczajnie usuń węzeł (jak w BST). Jeżeli jego potomek lub on sam był koloru czerwonego, to zmień kolor jego potomka na czarny i zakończ. W przeciwnym razie oznacz tego potomka jako podwójnie czarny, dokonaj naprawy drzewa i zakończ.
  • Przypadek III — usuwany węzeł ma dwóch potomków.
    Znajdź kandydata do jego zastąpienia (jak w BST), przenieś dane z kandydata do usuwanego węzła, a następnie usuń kandydata (kandydat będzie miał co najwyżej jednego potomka).
  
  
• Naprawianie węzła podwójnie czarnego:
  • Przypadek I — brat podwójnie czarnego węzła jest koloru czerwonego.
    W tym przypadku zmień kolor brata na czarny, kolor rodzica na czerwony i dokonaj rotacji brata (w wyniku przekolorowania i rotacji powstanie przypadek II lub III), a następnie rekurencyjnie wywołaj naprawianie podwójnie czarnego węzła z tym samym parametrem.
    
    

    Drzewo przed korektą	Drzewo po korekcie

    
    
  • Przypadek II — brat podwójnie czarnego węzła jest koloru czarnego i potomkowie brata są koloru czarnego.
    Zmień kolor brata na czerwony. Jeżeli rodzic podwójnie czarnego węzła jest koloru czerwonego, to zmień kolor rodzica na czarny i zakończ naprawianie. W przeciwnym razie rekurencyjnie wywołaj naprawianie podwójnie czarnego węzła, przekazując węzeł rodzicielski jako parametr (kolor podwójnie czarny pójdzie poziom wyżej) — jeśli dojdziesz do korzenia, to zakończ procedurę.
    
    

    Przypadek czerwonego rodzica		Przypadek czarnego rodzica
    Drzewo przed korektą	Drzewo po korekcie	Drzewo przed korektą	Drzewo po korekcie

    
    
  • Przypadek III — brat podwójnie czarnego węzła jest koloru czarnego i jeden z potomków brata jest koloru czerwonego.
    Podobnie jak w konflikcie czerwony-czerwony przy wstawianiu węzła, możemy mieć do czynienia z jednym z czterech przypadków, z czego dwa stanowią lustrzane odbicie, dlatego omówione zostaną pozostałe dwa.
    Jeżeli przypadek ma kształt LR (czerwony węzeł jest prawym potomkiem brata, a brat jest lewym potomkiem rodzica węzła podwójnie czarnego), to należy dokonać lewej rotacji pary węzłów brat-czerwony węzeł i odwrócić kolory rotowanych węzłów, dzięki czemu przypadek przybierze kształt LL (patrz rysunek niżej). W przypadku LL wystarczy rotacja w prawo pary węzłów brat-rodzic i przekolorowanie. Należy zwrócić uwagę, że rodzic (węzeł A) może być koloru czerwonego lub czarnego, więc po korekcie nowy rodzic (węzeł B) musi być tego samego koloru co poprzedni, z kolei węzeł E może nie istnieć.
    
    

    Drzewo przed korektą	Drzewo po korekcie

    
    
• Kod (standard C++17) na przetestowanie operacji wstawiania/usuwania w drzewie czerwono-czarnym (metoda get_min_node_data() zwraca dane z węzła minimalnego, czyli tego najbardziej na lewo):
  #include <map> #include <vector> #include <numeric> #include <algorithm> void test() { std::vector<int> v(8); std::iota(v.begin(), v.end(), 0); std::map<int, int> heights, min_node_data; do { rbt<int> t; for (int i : v) t.add(i, std::less<int>{}); for (int i : v) { ++heights[t.height()]; ++min_node_data[t.get_min_node_data()]; t.remove(i, std::less<int>{}); } } while (std::next_permutation(v.begin(), v.end())); for (auto [height, cnt] : heights) std::cout << height << ": " << cnt << std::endl; std::cout << "***" << std::endl; for (auto [data, cnt] : min_node_data) std::cout << data << ": " << cnt << std::endl; }
  Oczekiwany wynik:
  1: 40320 2: 80640 3: 115872 4: 85728 *** 0: 181440 1: 60480 2: 30240 3: 18144 4: 12096 5: 8640 6: 6480 7: 5040

• ---

  Mini-prezentacja dotycząca struktury zbiorów rozłącznych
  Oczekiwane wyniki:
  

  g1.txt	g2.txt	g3.txt
  union by rank: false, path compression: false Number of edges: 19 Sum of edges: 3.4878153 Sorting time: 0.6 s Kruskal time: 0.3 s Total find_set operation counter: 124 union by rank: false, path compression: true Number of edges: 19 Sum of edges: 3.4878153 Sorting time: 0.6 s Kruskal time: 0.3 s Total find_set operation counter: 108 union by rank: true, path compression: false Number of edges: 19 Sum of edges: 3.4878153 Sorting time: 0.6 s Kruskal time: 0.3 s Total find_set operation counter: 108 union by rank: true, path compression: true Number of edges: 19 Sum of edges: 3.4878153 Sorting time: 0.6 s Kruskal time: 0.3 s Total find_set operation counter: 104	union by rank: false, path compression: false Number of edges: 99 Sum of edges: 7.5233176 Sorting time: 0.47 s Kruskal time: 0.37 s Total find_set operation counter: 3099 union by rank: false, path compression: true Number of edges: 99 Sum of edges: 7.5233176 Sorting time: 0.48 s Kruskal time: 0.21 s Total find_set operation counter: 1496 union by rank: true, path compression: false Number of edges: 99 Sum of edges: 7.5233176 Sorting time: 0.47 s Kruskal time: 0.30 s Total find_set operation counter: 1736 union by rank: true, path compression: true Number of edges: 99 Sum of edges: 7.5233176 Sorting time: 0.43 s Kruskal time: 0.16 s Total find_set operation counter: 1288	union by rank: false, path compression: false Number of edges: 9999 Sum of edges: 66.24773 Sorting time: 0.79207 s Kruskal time: 0.13965 s Total find_set operation counter: 6650303 union by rank: false, path compression: true Number of edges: 9999 Sum of edges: 66.24773 Sorting time: 0.83117 s Kruskal time: 0.929 s Total find_set operation counter: 271836 union by rank: true, path compression: false Number of edges: 9999 Sum of edges: 66.24773 Sorting time: 0.79653 s Kruskal time: 0.1410 s Total find_set operation counter: 389327 union by rank: true, path compression: true Number of edges: 9999 Sum of edges: 66.24773 Sorting time: 0.80484 s Kruskal time: 0.626 s Total find_set operation counter: 213224

• Mini-prezentacja dotycząca algorytmu Grahama
• Kolejność odwiedzania punktów w przypadku points1.txt: 8 5 2 7 3 13 9 12 10 1 11 17 18 19 15 14 6 16 0 4, zaś na otoczkę składają się punkty: 8 5 13 10 14 6 0 4. Dwa dodatkowe zbiory: points6.txt oraz points7.txt.
• Dane do (nieobowiązkowego) zadania związanego z algorytmem Floyda-Warshalla znajdują się tutaj (-1 oznacza nieskończoną odległość). Należy zaimplementować algorytm z rekonstrukcją najkrótszych ścieżek.