% 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,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{CS 584/684 Algorithm Design and Analysis}
\def\term{Portland State U, Winter 2021}
\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\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\texbp{5} % bonus for typing in latex
\def\hwnum{2} %
\def\issuedate{01/12/21} % 
\def\duedate{01/19/21} % 
\def\yourname{your name} % type your name here

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

\noindent \textbf{Instructions.} This problem set contains \numpages\
pages (including this cover page) and \numquestions\ questions. A
random subset of problems will be graded.

\begin{itemize}
\item 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. It is good practice to
  start any long solution with an informal (but accurate) summary that
  describes the main idea. You may opt for the ``I take 15\%'' option.

\item You need to submit a PDF file before the deadline. Either a
  clear scan of you handwriting or a typeset document is accepted. You
  will get $\texbp$ bonus points for typing in LaTeX (Download and use
  the accompany TeX file).

\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}

\newpage

\begin{questions}
  \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}

  % \begin{solution}
  %  uncomment the environment and write your solution here
  % \end{solution}

  \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 (Akinator's trick) Play the game \alg{Akinator} online
  (\url{https://en.akinator.com/}), and answer the questions below.

  \begin{parts}
    \part[10] Given a \emph{sorted} array $A$ with distinct numbers,
    we want to find out an $i$ such that $A[i] = i$ if exists. Give an
    $O(\log n)$ algorithm.
    \part[10] Consider a sorted array with distinct numbers. It is
    then rotated $k$ ($k$ is unknown) positions to the right, and call
    the resulting array $A$. (Example: (8,9,2,3,5,7) is the sorted
    array (2,3,5,7,8,9) rotated to the right by 2 positions) Design as
    efficient an algorithm as you can to find out if $A$ contains a
    number $x$.

    Exercise (do not turn in). Can you think of some real-world
    problems that the techniques in your algorithms could be useful?
  \end{parts}

  \newpage
  \question (Counting inversions) Given a sequence of $n$
  \emph{distinct} numbers $a_1,\ldots,a_n$, we call $(a_i,a_j)$ an
  \emph{inversion} if $i< j$ but $a_i > a_j$. For instance, the
  sequence $(2,4,1,3,5)$ contains three inversions $(2,1)$, $(4,1)$
  and $(4,3)$. 

  \begin{parts}
    \part[15] Given an algorithm running in time $O(n\log n)$ that
    counts the number of inversions. (Hint: does Merge-sort help?) Can
    you also output all inversions?

    \bonuspart[10] Let's call a pair a \emph{significant inversion} if
    $i<j$ and $a_i > 2a_j$. Given an $O(n\log n)$ algorithm to count
    the number of significant inversions. 
  \end{parts}

  \newpage 

\end{questions}


\end{document}
