#LyX file created by tex2lyx 1.6.4
\lyxformat 264
\begin_document
\begin_header
\textclass article
\begin_preamble
\usepackage{fancyheadings}\usepackage{enumerate}\usepackage{xspace}\chead{CS4104(Fall2009):Homework4}
\newcommand{\solution}[1]{\textbf{Solution:} #1}\newcommand{\cut}[1]{\ensuremath{\mathnormal{}{cut}(#1)}}\newcommand{\calg}{\ensuremath{{\cal G}}\xspace}\newcommand{\calo}{\ensuremath{{\cal O}}\xspace}
\end_preamble
\language english
\inputencoding auto
\font_roman default
\font_sans default
\font_typewriter default
\font_default_family default
\font_sc false
\font_osf false
\font_sf_scale 100
\font_tt_scale 100
\graphics default
\paperfontsize default
\spacing single
\papersize default
\use_geometry false
\use_amsmath 1
\use_esint 1
\cite_engine basic
\use_bibtopic false
\paperorientation portrait
\secnumdepth 3
\tocdepth 3
\paragraph_separation indent
\defskip medskip
\quotes_language english
\papercolumns 1
\papersides 1
\paperpagestyle fancy
\tracking_changes false
\output_changes false
\end_header
\begin_body
\begin_layout Title
\begin_inset VSpace -0.5in
\end_inset
\series bold
Homework 5
\series default
\end_layout
\begin_layout Author
CS 4104 (Fall 2009)
\end_layout
\begin_layout Date
Assigned on Monday, October 5, 2009.
\newline
Hardcopy due at the beginning of class on Monday, October 12, 2009.
\end_layout
\begin_layout Paragraph
Instructions:
\end_layout
\begin_layout Itemize
You are not allowed to consult any sources other than your textbook, the slides on the course web page, your own class notes, the TA, and the instructor. In particular, do not use a search engine.
\end_layout
\begin_layout Itemize
Do not forget to typeset your solutions.
\emph on
Every mathematical expression must be typeset as a mathematical expression, e.g., the square of
\begin_inset Formula $n$
\end_inset
must appear as
\begin_inset Formula $n^2$
\end_inset
and not as
\begin_inset Quotes eld
\end_inset
n‸2
\begin_inset Quotes erd
\end_inset
.
\emph default
Students using LaTeX\InsetSpace \space{}
or LyX can use the corresponding versions of the homework problems to start entering their solutions.
\end_layout
\begin_layout Itemize
Describe your algorithms as clearly as possible. The style used in the book is fine, as long as your description is not ambiguous. Explain your algorithm in words. A step-wise description is fine.
\emph on
However, if you submit detailed pseudo-code without an explanation, we will not grade your solutions.
\emph default
\end_layout
\begin_layout Itemize
Do not make any assumptions not stated in the problem. If you do make any assumptions, state them clearly, and explain why the assumption does not decrease the generality of your solution.
\end_layout
\begin_layout Itemize
Do not describe your algorithms only for a specific example you may have worked out.
\end_layout
\begin_layout Itemize
You must also provide a clear proof that your solution is correct (or a counter-example, where applicable). Type out all the statements you need to complete your proof.
\emph on
You must convince us that you can write out the complete proof. You will lose points if you work out some details of the proof in your head but do not type them out in your solution.
\emph default
\end_layout
\begin_layout Itemize
Analyse your algorithm and state the running time. You will only get partial credit if your analysis is not tight, i.e., if the bound you prove for your algorithm is not the best upper bound possible.
\end_layout
\begin_layout Description
Problem 1 (15 points) Solve the recurrence
\begin_inset Formula $T(n) = T( \lfloor
\sqrt{n} \rfloor) +
1$
\end_inset
. In words, the
\begin_inset Formula $T(n)$
\end_inset
is the running time of an algorithm that creates one sub-problem of the size equal to the square root of
\begin_inset Formula $n$
\end_inset
, solves this sub-problem recursively, and spends one more unit of time. You can assume that
\begin_inset Formula $T(2) = 1$
\end_inset
and that
\begin_inset Formula $n \geq 2$
\end_inset
.
\end_layout
\begin_deeper
\begin_layout Standard
\begin_inset ERT
status collapsed
\begin_layout Standard
%
\backslash
solution{
\end_layout
\begin_layout Standard
\end_layout
\end_inset
\end_layout
\begin_layout Standard
\begin_inset ERT
status collapsed
\begin_layout Standard
% }
\end_layout
\begin_layout Standard
\end_layout
\end_inset
\end_layout
\end_deeper
\begin_layout Description
Problem 2 (40 points) You are given three algorithms to solve the same problem of size
\begin_inset Formula $n$
\end_inset
. Analyse each algorithm in
\begin_inset Formula $O()$
\end_inset
notation. Provide a clear proof of the analysis. Which algorithm would you choose and why? In other words, write down which algorithm is asymptotically the fastest and provide a proof why this algorithm is asymptotically the fastest of all three. If you can directly apply a formula we discussed in class, feel free to do so. For some sub-problems, you will have to come up with proofs from scratch, although your proofs will follow the general outlines we have used in class. Remember to prove your solution by induction, even if you use the
\begin_inset Quotes eld
\end_inset
unrolling
\begin_inset Quotes erd
\end_inset
method to guess a solution.
\end_layout
\begin_deeper
\begin_deeper
\begin_layout Standard
[(i)]
\end_layout
\end_deeper
\begin_layout Enumerate
Algorithm A solves the problem by dividing it into five sub-problems of half the size, recursively solving each sub-problem, and then combining the solutions in linear time.
\end_layout
\begin_layout Enumerate
Algorithm B solves the problem by dividing it into two sub-problems of size
\begin_inset Formula $n - 1$
\end_inset
, recursively solving each subproblem, and then combining the solutions in constant time.
\end_layout
\begin_layout Enumerate
Algorithm C solves the problem by dividing it into three sub-problems of size
\begin_inset Formula $n/3$
\end_inset
, recursively solving each sub-problem, and then combining the solutions in
\begin_inset Formula $O(n^2)$
\end_inset
time.
\end_layout
\end_deeper
\begin_deeper
\begin_layout Standard
\begin_inset ERT
status collapsed
\begin_layout Standard
%
\backslash
solution{
\end_layout
\begin_layout Standard
\end_layout
\end_inset
\end_layout
\begin_layout Standard
\begin_inset ERT
status collapsed
\begin_layout Standard
% }
\end_layout
\begin_layout Standard
\end_layout
\end_inset
\end_layout
\end_deeper
\begin_layout Description
Problem 3 (45 points) Solve exercise\InsetSpace ~
3 in Chapter\InsetSpace ~
5 (pages\InsetSpace ~
246--247) of your textbook. Let us call the equivalence class with more than
\begin_inset Formula $n/2$
\end_inset
cards the
\emph on
important
\emph default
class. It is enough for your algorithm to return a card that belongs to this class, if it exists, or no card at all. Note that the problem specifies that the only operation you can perform on a pair of cards is to decide if they are equivalent. You cannot perform any other operation, e.g., compare them in order to sort them. Your proof of correctness must clearly address why your algorithm will find a set of important class, if it exists. For instance, if you divide the cards into two sets of
\begin_inset Formula $n/2$
\end_inset
cards each and find the important class in each subset, why should the important class(es) found by the recursive calls have any relation to the important class for all
\begin_inset Formula $n$
\end_inset
cards?
\end_layout
\begin_deeper
\begin_layout Standard
\begin_inset ERT
status collapsed
\begin_layout Standard
%
\backslash
solution{
\end_layout
\begin_layout Standard
\end_layout
\end_inset
\end_layout
\begin_layout Standard
\begin_inset ERT
status collapsed
\begin_layout Standard
% }
\end_layout
\begin_layout Standard
\end_layout
\end_inset
\end_layout
\end_deeper
\end_body
\end_document