\documentstyle[12pt,fullpage]{article}
%\textwidth 15cm
%\textheight 22cm
\topmargin -1cm
\oddsidemargin -0.2cm
\begin{document}
\parskip
\baselineskip
\bigskip

\begin{center}
{\Large {\bf Data Structures}}
\end{center}
\begin{center}
{\Large {\bf Exercise 1, part 1}}
\end{center}
{\bf Submition deadline: April 3}
\begin{enumerate}
\item For each function $f(n)$ and time $t$ in the list below, determine the largest 
size $n$ of a problem that can be solved in time $t$, assuming that the algorithm to solve the problem takes
$f(n)$ microseconds.
\begin{itemize}
\item $f(n) = \log{n}, \sqrt{n}, n, n\log{n}, n^2$.
\item $t = 1$ second, $1$ hour, $1$ month, $1$ century.
\end{itemize}

\item Although merge sort runs in $\Theta(n\log{n})$ worst-case time and insertion sort runs
in $\Theta(n^2)$ worst-case time, the constant factors in insertion sort make
it faster for small $n$. Thus, it makes sense to use insertion sort within merge sort
when subproblems become sufficiently small. Consider a modification to merge sort  in which 
$\frac{n}{k}$ sublists of length $k$ ase sorted using insertion sort
and then merged using the standard  merging mechanizm, where $k$ is the value
to be determined.
\begin{itemize}
\item Show that the $\frac{n}{k}$ sublists, each of length $k$, can be sorted by insertion
sort in $\Theta(nk)$ worst case time.
\item Show that the sublists can be merged in $\Theta(n\log{\frac{n}{k}})$ worst-case time.
\item Given that the modified algorithm runs in $\Theta(nk + n\log{\frac{n}{k}})$ worst-case
time, what is the largest asymtotic ($\Theta$-notation) value of $k$ as a function
of $n$ for which the modified algorithm has the same asymptotic running time as 
standard merge sort?
\item How should $k$ be chosen in practice?
\end{itemize}
\item Write a program in Java language to the problem described in previous exercise.
The input of the program is the sequence of a numbers and a number $k$.
The output of the problem is the {\em sorted} sequence of the numbers and the
number of comparisons performed during program's running.
\end{enumerate}
\begin{center}
{\Huge {\bf Good Luck!}}
\end{center}
\end{document}