Solutions to exercises and problems from "Introduction to Algorithms", Second Edition by Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest and Clifford Stein (in Polish)
Notka: "zamiast testowania ... ." -> "druga nierówność powinna być nieostra: key[j]\le k."
"na listach" -> "wśród"
(a) "następuje przesunięcie ... L" -> "indeks i przesuwany jest o jedną pozycję w przód, dopóki nie osiągnie on końca listy L albo pozycji elementu o kluczu większym bądź równym k"
"Zauważmy ... Compact-List-Search'." -> "Zauważmy, że w q-tej iteracji pętli while w procedurze Compact-List-Search indeks i może być tylko dalej od głowy listy L, niż indeks i w q-tej iteracji pętli while procedury Compact-List-Search'."
(c) Cały pierwszy paragraf wraz z wyprowadzeniem Pr(X_t \ge r): "Zdarzenie X_t\ge r zachodzi wtedy, gdy dla każdej zwróconej przez wywołanie Random(1,n) liczby j, element o indeksie j znajduje się na liście L po elemencie o kluczu k albo co najmniej r pozycji przed nim (według wskaźników next). Dla każdego j zakres pozycji tablicy sprzyjający temu zdarzeniu wynosi n-r. Oczywiście każde z t wywołań procedury Random jest niezależne, zatem możemy napisać:
\Pr(Xt \ge r) = \prod{q=1}^t \frac{n-r}{n} = (1-\frac{r}{n})^t."
usunąć "i z powyższego oszacowania"
(e) Wyciągnąć \frac{1}{n^t} przed sumę zamiast robić duży ułamek, i potem w kolejnym wyrażeniu.
(g) "w wierszu" -> "z wiersza"
"że w procedurze ... i \gets next[i]" -> "że po wykonaniu tego skoku zostanie wykonanych jeszcze co najwyżej t skoków z wiersza 8"
"będąca celem ostatniego skoku" -> "osiągana w wyniku wykonania ostatniego skoku"
"będzie w rzeczywistości działać" -> "w rzeczywistości działa"
"do pozycji ... istnieje" -> "do pozycji elementu y o najmniejszym kluczu większym niż k albo do pozycji ogona listy plus 1, w przypadku, gdy y nie istnieje" (SPRAWDZIĆ CZY TAKIE SFORMUŁOWANIE JEST OK)
Notka: "zamiast testowania ... ." -> "druga nierówność powinna być nieostra: key[j]\le k." "na listach" -> "wśród"
(a) "następuje przesunięcie ... L" -> "indeks i przesuwany jest o jedną pozycję w przód, dopóki nie osiągnie on końca listy L albo pozycji elementu o kluczu większym bądź równym k" "Zauważmy ... Compact-List-Search'." -> "Zauważmy, że w q-tej iteracji pętli while w procedurze Compact-List-Search indeks i może być tylko dalej od głowy listy L, niż indeks i w q-tej iteracji pętli while procedury Compact-List-Search'." (c) Cały pierwszy paragraf wraz z wyprowadzeniem Pr(X_t \ge r): "Zdarzenie X_t\ge r zachodzi wtedy, gdy dla każdej zwróconej przez wywołanie Random(1,n) liczby j, element o indeksie j znajduje się na liście L po elemencie o kluczu k albo co najmniej r pozycji przed nim (według wskaźników next). Dla każdego j zakres pozycji tablicy sprzyjający temu zdarzeniu wynosi n-r. Oczywiście każde z t wywołań procedury Random jest niezależne, zatem możemy napisać: \Pr(Xt \ge r) = \prod{q=1}^t \frac{n-r}{n} = (1-\frac{r}{n})^t." usunąć "i z powyższego oszacowania" (e) Wyciągnąć \frac{1}{n^t} przed sumę zamiast robić duży ułamek, i potem w kolejnym wyrażeniu. (g) "w wierszu" -> "z wiersza" "że w procedurze ... i \gets next[i]" -> "że po wykonaniu tego skoku zostanie wykonanych jeszcze co najwyżej t skoków z wiersza 8" "będąca celem ostatniego skoku" -> "osiągana w wyniku wykonania ostatniego skoku" "będzie w rzeczywistości działać" -> "w rzeczywistości działa" "do pozycji ... istnieje" -> "do pozycji elementu y o najmniejszym kluczu większym niż k albo do pozycji ogona listy plus 1, w przypadku, gdy y nie istnieje" (SPRAWDZIĆ CZY TAKIE SFORMUŁOWANIE JEST OK)