\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{2017}
\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 Monday, January 30, \myyear. \\Submit a PDF file containing your solutions on Canvas by the beginning of class on Monday, February 6, \myyear.}
\maketitle
\input{instructions}
\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 o parentheses 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 \emph{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 (let us call it \texttt{Algo1}):
\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?
Now develop a heap-based algorithm (let us call it \texttt{Algo2}) that has a better running time. Describe your algorithm, prove its correctness, and provide an analysis of the running time. Show that the running time of \texttt{Algo1} is lower-bounded by the running time of \texttt{Algo2}, i.e., if $f_1(n, k)$ is the running time of \texttt{Algo1} and $f_2(n, k)$ is the running time of \texttt{Algo2}, then $f_1(n, k) = \Omega(f_2(n, k)$. Note that the running time of both algorithms will depend on both $n$ and $k$ since there are $nk$ numbers in total.
% \solution{
% }
\end{description}
\end{document}
%%% Local Variables:
%%% mode: latex
%%% TeX-master: t
%%% End: