<html><head><meta name="color-scheme" content="light dark"></head><body><pre style="word-wrap: break-word; white-space: pre-wrap;">\documentclass[11pt]{article}
\usepackage[polish]{babel}
\usepackage[latin2]{inputenc}
\usepackage[T1]{fontenc}
\begin{document}
\begin{enumerate}

\item[(10 pkt)]
Danych jest $n$ s"l"ow o takiej samej d"lugo"sci $k$, zbudowanych ze znak"ow
$n$-elementowego, uporz"adkowanego alfabetu. Rozmiarem zadania w tym przypadku jest $R = nk$.
\begin{enumerate}
\item[(4 pkt)]
Zaproponuj algorytm, kt"ory dla danego $i$, $1\leq i \leq k$, obliczy w czasie $O(R)$ liczb"e wszystkich par s"l"ow, kt"ore r"o"rni"a si"e
tylko na $i$-tej pozycji.
\item[(6 pkt)]
Zaproponuj algorytm, kt"ory obliczy w czasie $O(R)$ liczbę wszystkich par s"l"ow, kt"ore r"o"rni"a si"e tylko na dok"ladnie
jednej pozycji.
\end{enumerate}
\item[(10 pkt)]
W tym zadaniu rozwa"ramy $n$-elementowe ci"agi $k$-uporz"adkowane ($i$-ty element ci"agu jest nie wi"ekszy od elementu $i+k$), $1\leq k \leq n$.
\begin{enumerate}
\item[(5 pkt)]
Udowodnij, "re ka"rdy algorytm sortuj"acy przez por"ownania wymaga w pesymistycznym przypadku $\Omega(n\log k)$ por"owna"n do posortowania
$n$-elementowego ci"agu $k$-uporz"adkowanego.
\item[(5 pkt)]
Zaproponuj algorytm sortuj"acy takie ci"agi w czasie $O(n\log k)$.
\end{enumerate}

\end{enumerate}

\end{document}











</pre></body></html>