Analiza algorytmów II 2009/10

Pytania egzaminacyjne

Wymagany jest stopień szczegółowości opisu algorytmu pozwalajacy bez wątpliwości zanalizować jego złożoność. Analiza poszczególnych algorytmów i dowody twierdzeń obowiązują w zakresie jak na wykładzie.

  1. Kopce Fibonacciego, operacja Extract_min i jej analiza
  2. Kopce Fibonacciego, operacja Decrease_key i jej analiza
  3. Kopce Fibonacciego, oszacowanie maksymalnego stopnia wierzchołka
  4. MST, algorytm round-robin, realizacja za pomocą kopców Fibonacciego
  5. Drzewa lewicowe jako kolejka priorytetowa, wykorzystanie w algorytmie round-robin
  6. Kopce skośne (skew heaps), wykorzystanie w algorytmie round-robin
  7. Równoważność problemów RMQ i LCA
  8. Optmalne rozwiązanie problemu RMQ w wersji (+1,-1)
  9. Drzewo sufiksów Trie i jego efektywna konstrukcja, drzewo sufiksowe, DAWG, rozmiar tych struktur
  10. Algorytm Weinera konstrukcji drzewa sufiksowego
  11. Algorytm Ukkonena konstrukcji drzewa sufiksowego
  12. Algorytm konstrukcji grafu podsłów DAWG, w tym algorytm klasyfikacji izomorficznych poddrzew
  13. Tablice sufiksowe: konstrukcja z drzewa sufiksowego, obliczanie funkcji LCP[] oraz LCP[][]
  14. Tablice sufiksowe: wyszukiwanie podsłowa w czasie O(m+lg n)
  15. Tablice sufiksowe: konstrukcja algorytmem Karkkainena-Sandersa