Zaawansowane algorytmy i struktury danych/Ćwiczenia 2

Zadanie 1

Pokazaż, że algorytm Maksymalny-Sufiks wykonuje co najwyżej 2.|x| porównań symboli.

Rozwiązanie

.

Zanalizuj zachowanie się sumy i+j, suma ta wynosi co najwyżej 2n.

Zadanie 2

Zmodyfikuj algorytm Huffmana dla przypadku niebinarnego alfabetu, gdy kodujemy w alfabecie $k$-arnym. Mamy teraz symbole $0,1,\dots ,k-1$. W algorytmie jednorazowo możemy sklejać więcej niż dwa elementy.

Rozwiązanie

.

Postępujemy zachłannie, tak jak w przypadku binarnym, za każdym razem sklejamy $k$ aktualnie najmnieszych elementów. W pierwszym kroku być może mniej niż $k$, tak aby w następnych zawsze było $k$.

Zadanie 3

Znajdź wielomianowy algorytm dla kodowanie prefiksowego z symbolami kodowymi nierównej długości dla małych $c$ ($c=2$ lub $c=3$).

Rozwiązanie

.

Programowanie dynamiczne.

Zadanie 4

Znajdź wielomianowy algorytm dla kodowania prefiksowego z symbolami kodowymi nierównej długości dla przypadku, gdy wagi wszystkich liści drzewa są takie same.

Rozwiązanie

.

Skonstruuj jak najbardziej pełne, regularne drzewo.

Zadanie 5

Oblicz minimalny okres słowa w czasie liniowym i pamięci stałej.

Rozwiązanie

.

Skorzystaj z technik używanych w string-matchingu ze stałą pamięcią.