% Instructions: you don't need to change anything in the macros, but
% feel free to define new commands as you wish. Starting from the main
% body, change the specs (e.g., your
% name). use \begin{solution} \end{solution} environment to write your
% solutions. Don't forget to list your collaborators.

\documentclass[12pt,addpoints,answers]{exam}
%============Macros==================%
\usepackage{amsmath,amsfonts,amssymb,amsthm}
\usepackage[margin=1in]{geometry}
%--------------Cosmetic----------------%
\usepackage{mathtools}
\usepackage{hyperref}
\usepackage{fullpage}
\usepackage{microtype}
\usepackage{xspace}
\usepackage[svgnames]{xcolor}
\usepackage[sc]{mathpazo}
\usepackage{enumitem}
\setlist[enumerate]{itemsep=1pt,topsep=2pt}
\setlist[itemize]{itemsep=1pt,topsep=2pt}
%----------Header--------------------%
\def\course{CSCE629 Analysis of Algorithms}
\def\term{Texas A\&M U, Fall 2019}
\def\prof{Lecturer: Fang Song}
\newcommand{\handout}[5]{
   \renewcommand{\thepage}{\arabic{page}}
   \begin{center}
   \framebox{
      \vbox{
    \hbox to 5.78in { \hfill \large{\course} \hfill }
       \vspace{2mm}
       \hbox to 5.78in { {\Large \hfill \textbf{#5}  \hfill} }
       \vspace{2mm}
       \hbox to 5.78in { \term \hfill \emph{#2}}
       \hbox to 5.78in { {#3 \hfill \emph{#4}}}
      }
   }
   \end{center}
   \vspace*{4mm}
}
\newcommand{\hw}[4]{\handout{#1}{#2}{#3}{#4}{Homework #1}}

%-----defs and commands-----%
%\def\mG{[\textbf{G}]\xspace}
\def\veps{\varepsilon}
\newcommand{\bit}{\{0,1\}}
\newcommand{\negl}{\text{negl}}
\newcommand{\corr}[1]{{\color{blue}{#1}}}
\newcommand{\alg}[1]{\textsf{#1}}
%=======Main document==============%
\begin{document}

%----Specs: change accordingly-----%
\newif\ifstudent % comment out false
\studenttrue 
%\studentfalse

\def\hwnum{2}
\def\issuedate{09/06/19}
\def\duedate{10am, 09/13/19} % 
\def\yourname{your name} % put your name here
%------------------------------%

\ifstudent
\hw{\hwnum}{\issuedate}{Student: \yourname}{Due: \duedate}%
\else
\hw{\hwnum}{\issuedate}{\prof}{Due: \duedate}%
\fi

\noindent \textbf{Instructions.}

\begin{itemize}
\item Typeset your submission by \LaTeX, and submit in PDF
  format. Your solutions will be graded on \emph{correctness} and
  \emph{clarity}. You should only submit work that you believe to be
  correct, and you will get significantly more partial credit if you
  clearly identify the gap(s) in your solution. You may opt for the
  ``I’ll take 15\%'' option (details in Syllabus).
\item You may collaborate with others on this problem set.  However,
  you must \textbf{{write up your own solutions}} and \textbf{{list
      your collaborators and any external sources}} for each
  problem. Be ready to explain your solutions orally to a course staff
  if asked.
\item For problems that require you to provide an algorithm, you must
  give a precise description of the algorithm, together with a proof
  of correctness and an analysis of its running time. You may use
  algorithms from class as subroutines. You may also use any facts
  that we proved in class or from the book.
\end{itemize}

\noindent This assignment contains \numquestions\ questions,
\numpages\ pages for the total of \numpoints \ points and
\numbonuspoints\ bonus points. A random subset of the problems will be
graded. \medskip

\medskip

\begin{questions}
  \question (More asymptotics)
  \begin{parts}
    \part[5] Prove that for any positive numbers $a, b > 0$, we have
    $n^b = \omega(\log^a(n))$. There are several ways to approach
    this. One way is to use L'Hospital's rule for evaluating limits
    together with the following fact: $f(n) = \omega(g(n))$ if and
    only if $\lim_{n\to \infty} \frac{f(n)}{g(n)} = +\infty$.
    \part[5] Prove or disprove: If $h(n) = \lceil n \log(n)\rceil$,
    then $n = \Theta (h(n)/ \log h(n))$.
  \end{parts}

  
  \newpage
  
  \question (Recurrence) Solve the following recurrences.

  \begin{parts}
    \part[5] $A(n)=2A(n/4) + \sqrt{n}$
    \part[5] $B(n) = 2B(n/4) + n$
    \part[5] $C(n) = 3C(n/3) + n^2$    
    \bonuspart[5] $D(n) = \sqrt{n} D(\sqrt{n})+ n$
  \end{parts}

  \newpage

  \question[10] (Domain transformation) We analyzed the running time
  of \alg{Mergesort} by the recurrence $T(n) = 2T(n/2) +O(n)$. The
  actual \alg{Mergesort} recurrence is somewhat messier:
  \[T(n) = T(\lceil n/2 \rceil) + T(\lfloor n/2 \rfloor) +O(n) \, .\]
  We'll justify in this problem that ignoring the ceilings and floors
  in a recurrence is okay afterall using a technique called
  \emph{domain transformation}.

  First, because we are deriving an upper bound, we can safely
  overestimate $T(n)$, once by pretending that the two subproblem
  sizes are equal, and again to eliminate the ceiling:

  \[T(n) \le 2T(\lceil n/2 \rceil) +n \leq 2T({\color{red} n/2 + 1}) +
    n \, .\]

  Second, we define a new function $S(n) = T(n + \alpha)$ for some
  $\alpha$. \textbf{You are to complete the second step.} Show that
  you can find a nice $\alpha$ so that $S(n)\le 2S(n/2) + O(n)$ does
  hold, and conclude from there that $T(n) = O(n \log n)$. 

  [Exercise (Do not turn in). Show how to remove floors by similar
  arguments.]

  \newpage
  \question (Quicksort) We were not precise about the running time
  of Quicksort in class (for a good reason). We will give some case
  studies in this problem (and appreciate the subtlety). 

  \begin{parts}
    \part[10] Given an input array of $n$ elements, suppose we are
    unlucky and the partitioning routine produces one subproblem with
    $n-1$ elements and one with 0 element. Write down the recurrence
    and solve it. Describe an input array that costs this amount of
    running time to get sorted by \alg{Quicksort}.
    \part[5] Now suppose that the partitioning always produces a
    9-to-1 proportional split. Write down the recurrence for $T(n)$
    and solve it.
    \part[5] What is the running time of \alg{Quicksort} when all
    elements of the input array have the same value?
  \end{parts}
  \newpage
  
\question (Sumerians' multiplication algorithm) The clay tablets
discovered in Sumer led some scholars to conjecture that ancient
Sumerians performed multiplication by reduction to \emph{squaring},
using an identity like \[x\cdot y = (x^2 + y^2 - (x - y)^2)/2 \, .\] In this
problem, we will investigate how to actually square large numbers.

\begin{parts}
  \part[7] Describe a variant of Karatsuba’s algorithm that squares
  any $n$-digit number in $O(n^{\log 3})$ time, by reducing to
  squaring three $\lceil n/2 \rceil$-digit numbers. (Karatsuba
  actually did this in 1960.)

  \part[8] Describe a recursive algorithm that squares any $n$-digit
  number in $O(n^{\log_3{6}})$ time, by reducing to squaring six
  $\lceil n/3 \rceil$-digit numbers.

  \bonuspart[10] Describe a recursive algorithm that squares any
  $n$-digit number in $O(n^{log_3{5}})$ time, by reducing to squaring
  only five $(n/3 + O(1))$-digit numbers. [Hint: What is
  $(a + b + c)^2 + (a- b + c)^2$?]


  
\end{parts}

\end{questions}


\end{document}
