Ćwiczenia 6: najkrótsze ścieżki, kolejki priorytetowe, koszt zamortyzowany

Zadanie 1

\(d\)-kopcem typu MIN, \( d \ge 2\), nazywamy zupełne drzewo \(d\)-arne z kluczami rozmieszczonymi w porządku kopcowym typu MIN.

  • Zaproponuj wydajną implementację \(d\)-kopca w tablicy i dokonaj analizy złożoności obliczeniowych operacji kolejki priorytetowej: Build, Min, DeleteMin i DecreasKey.
  • W jaki sposób dobrać \(d\), żeby dostać jak najszybszą implementację algorytmu Dijkstry w zależności od liczby krawędzi.
  • Zadanie 2

    Drzewem lewicowym nazywamy drzewo binarne, w którym dla każdego wierzchołka długość skrajnie prawej ścieżki w jego lewym poddrzewie jest nie mniejsza od długości skrajnie prawej ścieżki w jego prawym poddrzewie. Kopcem lewicowym typu MIN nazywamy drzewo lewicowe z kluczami rozmieszczonym w porządku kopcowym typu MIN.
    Zaproponuj efektywne implementacje operacji kolejki priorytetowej (Build, Min, DeleteMin, DecraseKey) z użyciem kopców lewicowych.

    Zadanie 3

    Dana jest rodzina \(n\) niepustych podzbiorów zbioru \( \{1, 2, \ldots, n \}\), z których każdy to całkowitoliczbowy przedział postaci \([i,j]\), \(i \le j\). Zaprojektuj efektywny algorytm sprawdzania, czy zadana rodzina posiada system różnych reprezentantów, a jeśli tak, to podaje jeden z nich.

    Zadanie 4

    W algorytmie Dijkstry ciąg wartości otrzymywanych w wyniku wywołań funkcji Min jest niemalejący. Wykorzystaj ten fakt i zaproponuj implementację implementację algorytmu Dijkstry w czasie \( O(m + kn) \), gdy wagi krawędzi są liczbami całkowitym z przedziału \( [1..k ] \).

    Zadanie 5: rozgłaszanie w drzewie

    Dane jest drzewo z wyróżnionym wierzchołkiem \(s \) - źródłem rozgłaszania.

  • Zaprojektuj efektywny algorytm obliczający optymalny ze względu na czas schemat rozgłaszania ze źródła \( s \). Rozgłaszanie jest synchroniczne. W jednym takcie węzeł znający informację źródłową - na początku zna ją tylko źródło - może ją przesłać do co najwyżej 1 sąsiada. Celem jest rozesłanie informacji ze źródła do wszystkich węzłów w drzewie.
  • Zaprojektuj algorytm, który w czasie liniowym wyznaczy najlepsze źródło rozgłaszania w drzewie - tzn. taki węzeł, dla którego czas rozgłaszania w drzewie jest najmniejszy.