1. Klasówka 2011/12

Zadanie 1

Słowa kluczowe: teksty

Danych jest \(n\) słów o takiej samej długości \(k\), zbudowanych ze znaków \(n\)-elementowego, uporządkowanego alfabetu. Rozmiarem zadania w tym przypadku jest \(R = nk\).

• Zaproponuj algorytm, który dla danego \(i\), \(1 \le i \le k\), obliczy w czasie \(O(R)\) liczbę wszystkich par słów, które różnią się tylko na \(i\)-tej pozycji.

• Zaproponuj algorytm, który obliczy w czasie \(O(R)\) liczbę wszystkich par słów, które różnią się tylko na dokładnie jednej pozycji.

Zadanie 2

Słowa kluczowe: sortowanie

W tym zadaniu rozważamy \(n\)-elementowe ciągi \(k\)-uporządkowane (\(i\)-ty element ciągu jest nie większy od elementu \(i + k\)), \(1 \le k \le n\).

• Udowodnij, że każdy algorytm sortujący przez porównania wymaga w pesymistycznym przypadku \(\Omega(n \log k)\) porównań do posortowania \(n\)-elementowego ciągu \(k\)-uporządkowanego.

• Zaproponuj algorytm sortujący takie ciągi w czasie \(O(n \log k)\).

Podpowiedź

Zauważmy, że ciąg \(k\)-uporządkowany rozpada się na \(k\)-posortowanych ciągów (np. \(a_1, a_{1+k}, a_{1+2k},\ldots\)). Takie ciągi możemy scalić w czasie \(O(n\log k)\) za pomocą kopca rozmiaru k.