Algorytmika praktyczna - ćwiczenia (semestr zimowy 2006/2007)
Perełki algorytmiki

• Zadanie 2006.I - Degrees of Separation
  W zadaniu obliczaliśmy średnicę grafu i odległości między wszystkimi parami wierzchołków. Pojawiło się pytanie, czy można to zrobić szybciej niż w czasie O(n^3). Okazuje się, że problem można sprowadzić do problemu mnożenia macierzy, co znaczy, że można go rozwiązać w czasie O(n^2.38), być może nawet szybciej. Pierwsze takie sprowadzenie podał Seidel. Algorytm Seidela ma jedną wielką wadę - działa tylko dla grafów bez wag. Ma też wielką zaletę - jest naprawdę piękny ;) Pobierz.
• Zadanie 2006.I - Degrees of Separation
  Przy okazji tego samego zadania wspomniałem o algorytmie Aingwortha, Chekuriego, Indyka i Motwaniego, który oblicza średnicę grafu oraz odległości między wszystkimi parami wierzchołków z błędem (addytywnym!) 2 w czasie O(n^2.5\sqrt{\log n}), a więc istotnie szybciej niż O(n^3) i to nie korzystając z mnożenia macierzy (które funkcjonuje trochę jak naklejka "nothing practical inside"). Ta praca wywołała w swoim czasie małe trzęsienie ziemi. Pobierz.
• Zadanie 2006.E - Bit Compressor
  W rozwiązaniu tego zadania zastosowaliśmy piękny trick pochodzący z algorytmu o złożoności O(\sqrt{2})^n) dla problemu SUBSET-SUM. Ten algorytm został omówiony na zajęciach, ale osobom zainteresowanym ładnymi sposobami zbijania złożoności algorytmów wykładniczych polecam dwie piękne prace Bjorklunda i Husfeldta (sprzed paru miesięcy!) - zasada włączeń i wyłączeń bije całe lata rachunków i kombinowania. Pobierz. Pobierz.
• Zadanie 2006.C - Ars Longa
  W rozwiązaniu tego zadania pojawiły sie jakieś makabryczne układy równań opisujące stan równowagi układu kulek i pręcików, i inne rzeczy, które raczej rzadko pojawiają się na wykładach z algorytmiki. Czasem takie fizyczne modele mogą być jednak przydatne. W załączonej pracy Linial, Lovasz i Wigderson, korzystając z nich, pokazują interesującą "wyznacznikową" charakteryzację k-spójności wierzchołkowej. Pobierz.