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)
(a) DOWÓD NIEPOPRAWNY! Przepisać na podstawie pomysłu z https://ita.skanev.com/13/problems/04.html
(b) "taką, że ... \pi(i)" -> ", czyli że \pi(i) jest priorytetem węzła x_i dla i=1,2,\dots, n"
", co oznacza ... prawdopodobna" -> ". Własność tę zachowuje każda permutacja odwrotna \pi^{-1}, czyli permutacja indeksów węzłów wyznaczona przez ich rosnące priorytety"
"wstawienie do niego węzłów o coraz większym priorytecie" -> "wstawianie do niego węzłów o rosnących priorytetach"
"równą" -> "rzędu"
(e) "zwiększa o 1 lewy kręgosłup" -> "zwiększa o 1 długość lewego kręgosłupa"
(f) Zamienić ze sobą numery przypadków.
zdania pod warunkami: "Zgodnie z własnościami drzepca przypadek (i) wyznacza węzły z, dla których priority[y] < priority[z]. Przypadek (ii) obejmuje węzły z z lewego poddrzewa x, które z kolei w swoich lewych poddrzewach mają y, czyli równoważnie spełniające nierówności priority[x] < priority[z] < priority[y]. Jeśli nie istnieje węzeł z\in T, który spełnia warunek (ii), to y znajduje się na prawym kręgosłupie drzewa T_x^L. Podobnie w drugą stronę, jeśli y jest na prawym kręgosłupie T_x^L, to nie istnieje węzeł z\in T_x^L, dla którego y\in Tz^L, czyli żaden z nie spełnia (ii)."
(i) ostatnim wyrazem wyprowadzenia powinno być "1-\frac{1}{n-k+1}"
(a) DOWÓD NIEPOPRAWNY! Przepisać na podstawie pomysłu z https://ita.skanev.com/13/problems/04.html (b) "taką, że ... \pi(i)" -> ", czyli że \pi(i) jest priorytetem węzła x_i dla i=1,2,\dots, n" ", co oznacza ... prawdopodobna" -> ". Własność tę zachowuje każda permutacja odwrotna \pi^{-1}, czyli permutacja indeksów węzłów wyznaczona przez ich rosnące priorytety" "wstawienie do niego węzłów o coraz większym priorytecie" -> "wstawianie do niego węzłów o rosnących priorytetach" "równą" -> "rzędu" (e) "zwiększa o 1 lewy kręgosłup" -> "zwiększa o 1 długość lewego kręgosłupa" (f) Zamienić ze sobą numery przypadków. zdania pod warunkami: "Zgodnie z własnościami drzepca przypadek (i) wyznacza węzły z, dla których priority[y] < priority[z]. Przypadek (ii) obejmuje węzły z z lewego poddrzewa x, które z kolei w swoich lewych poddrzewach mają y, czyli równoważnie spełniające nierówności priority[x] < priority[z] < priority[y]. Jeśli nie istnieje węzeł z\in T, który spełnia warunek (ii), to y znajduje się na prawym kręgosłupie drzewa T_x^L. Podobnie w drugą stronę, jeśli y jest na prawym kręgosłupie T_x^L, to nie istnieje węzeł z\in T_x^L, dla którego y\in Tz^L, czyli żaden z nie spełnia (ii)." (i) ostatnim wyrazem wyprowadzenia powinno być "1-\frac{1}{n-k+1}"