\documentclass{article}
\usepackage[top=1in,bottom=1in,left=1in,right=1in]{geometry}
\usepackage{fancyheadings,enumerate,xspace,amssymb}
\pagestyle{fancy}

%\usepackage{cs5114}
% macros useful for handouts and homeworks.
\newcommand{\setcourse}[1]{\newcommand{\course}{#1\xspace}}
\newcommand{\setsem}[1]{\newcommand{\sem}{#1\xspace}}
\newcommand{\setyear}[1]{\newcommand{\myyear}{#1\xspace}}
\newcommand{\sethwnum}[1]{\newcommand{\hwnum}{#1\xspace}}

\setcourse{CS 4104}
\setyear{2016}
\setsem{Spring}
\sethwnum{1}

\chead{\course (\sem \myyear): Homework \hwnum}

\newcommand{\reals}{\ensuremath{\mathbb{R}}}
\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}

\begin{document}
\title{\vspace{-0.5in}\textbf{Homework \hwnum}}
\author{\course (\sem \myyear)}

\date{Assigned on Tuesday, January 26, \myyear. \\Submit a PDF file
  containing your solutions on Canvas by the beginning of class on
  Tuesday, February 2, \myyear.}
\maketitle

\paragraph{Instructions:} 
\begin{itemize}
\item You can pair up with another student to solve the homework. You
  are allowed to discuss possible algorithms and bounce ideas with your
  team-mate. \textbf{Do not discuss proofs of correctness or running time in
  detail with your team-mate. Do not send a written solution to your
  team-mate for any reason whatsoever. }Please form teams yourselves. Of course,
  you can ask me for help if you cannot find a team-mate. You may choose
  to work alone.  \emph{Each of you must write down your solution
    individually, and write down the name of the other member in your
    team. If you do not have a team-mate, please say so.}

\item Apart from your team-mate, you are not allowed to consult any
  sources other than your textbook, the slides on the course web page,
  your own class notes, the TAs, and the instructor. In particular, do
  not use a search engine.

\item Do not forget to typeset your solutions. \emph{Every mathematical
    expression must be typeset as a mathematical expression, e.g., the
    square of $n$ must appear as $n^2$ and not as ``n\^{}2''.} Students
  can use the \LaTeX\ version of the
  homework problems to start entering their solutions.

\item 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{However, if you submit detailed code or pseudo-code without an
    explanation, we will not grade your solutions.}

\item 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.

\item Do not describe your algorithms only for a specific example you
  may have worked out. 

\item 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{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.}

\item Describe an analysis of your algorithm and state and prove 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{itemize}


\begin{description}

\item[Problem 1] (5 points) Solve exercise 1 in Chapter 1 (page
  22 of ``Algorithm Design'' by Kleinberg and Tardos.  

  % \solution{

  % }

\item[Problem 2] (5 points) Solve exercise 2 in Chapter 1 (page
  22 of ``Algorithm Design'' by Kleinberg and Tardos.  

  % \solution{

  % }

\item[Problem 3] (30 points) Solve exercise 4 in Chapter 2 (pages
  67--68) of ``Algorithm Design'' by Kleinberg and Tardos.  Provide a
  proof for your solution. There are 21 pairs of functions. You need not
  compare every pair of functions in your proof. By judicial choice of
  which functions to compare, the number of function pairs you need to
  compare is much smaller than 21.

\emph{Notes.}
\begin{enumerate}
\item Keep in mind that in order to prove that $f(n)$ is
  $O(g(n))$, you must exhibit the constants required by the
  definition of asymptotic upper bound, and show that the inequality in
  the definition is satisfied by the functions, given these
  constants.
\item Note that $g_4(n)$ is printed before $g_3(n)$ in the textbook.
\end{enumerate}


To get you started, here is how you might prove that $g_3(n)$ is
$O(g_4(n))$. Dividing both functions by $n$, it is enough to prove that
$(\log n)^3$ is $O(n^{1/3})$.\footnote{Please note that I put a pair of
  parenthesis around $\log n$ before cubing it. Writing $\log n^3$ or
  $\log (n)^3$ to denote the cube of the logarithm of $n$ is wrong.} Let
us take the cube root of both functions. Now it suffices to show that
$\log n$ is $O(n^{1/9})$. We know from the class slides or from equation
2.8 on page 41 of the textbook that this statement is true. Note that I
will not require you to prove mathematically that $\log n$ is
$O(n^{1/9})$; you can rely on the statement in the slides/textbook.

  % \solution{

  % }

\item[Problem 4] (25 points) (20 points) Solve exercise 5 in Chapter 2
  (page 68) of ``Algorithm Design'' by Kleinberg and Tardos. If you decide
  that a statement is true, provide a short proof. Otherwise, provide a
  counterexample. \emph{Note:} If you think one of the statements is true, you
  should not prove it for your own choices of $f(n)$ and $g(n)$. Your
  proof must hold for any pair of functions $f(n)$ and $g(n)$ where $f(n)$ is $O(g(n))$.

  % \solution{
  
  % }


\item[Problem 5] (35 points). Describe an algorithm that uses a priority
  queue (heap) to merge $k$ sorted lists into one sorted list. Each
  sorted list has $n$ integers. Neither $k$ nor $n$ is a
  constant. 

  To get you started, consider the following algorithm:
  \begin{enumerate}
  \item Insert all the $kn$ numbers into a priority queue, with each
    number being its own key.
  \item Repeatedly report the smallest key in the queue and delete this
    value from the queue, until the queue becomes empty.
  \end{enumerate}
  What is the running time of this algorithm? 

  % heap-based
  Now develop an algorithm that has a better running time. Describe your
  algorithm, prove its correctness, and provide an analysis of the
  running time. Don't forget to show that your algorithm has a faster
  running time than the one described above!
  
  % \solution{

  % }

\end{description}

\end{document}

%%% Local Variables:
%%% mode: latex
%%% TeX-master: t
%%% End:
