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

.

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

Zadanie 2

Zmodyfiku algorytm Huffmana dla przypadku niebinarnego alfabetu

gdy kodujemy w alfabecie k-arnym, mamy teraz symbole 0,1,\ldots, 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 aktulanie najmnieszych elementów. W pierwszym kroku być może mniej niż k, tak aby w następnych zawsze było k.

Zadanie 3

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

Rozwiązanie

.

Programowanie dynamiczne.

Zadanie 4

Znajdz wielomianowy algorytm dla kodowanie prefiskowego 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ą.