% 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{1} %
\def\issuedate{01/05/21} % 
\def\duedate{01/12/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[5] (Survey) \textbf{Attention: this problem is due Friday,
    January 08, 11:59pm PST.} Complete the survey at
  {\url{https://forms.gle/e56YsGkRnaiBHbYA6}}.

  \question[15] (Order of growth rate) Take the following list of
  functions and arrange them in ascending order of growth rate. That
  is, if function $g(n)$ immediately follows function $f(n)$ in your
  list, then it should be the case that $f(n)$ is $O(g(n))$. (Hint:
  Look up \emph{Stirling’s approximation} for factorials.)
  \begin{itemize}
  \item $f_1(n) = n^{2.5}$
  \item $f_2(n) = \sqrt{2n}$
  \item $f_3(n)= n !$
  \item $f_5(n) = 100^n$
  \item $f_6(n) = n^2 \log n$
  \item $f_7(n) = 2^{\sqrt{n}}$
  \item $f_8(n) = 2^{2^n}$
  \item $f_9(n) = n^{\log n}$
  \item $f_{10}(n) = 0.01n$    
  \end{itemize}

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

  \newpage 
  
  \question[15] (Understanding big-$O$ notation) Assume you have
  functions $f$ and $g$ such that $f(n)$ is $O(g(n))$. For each of the
  following statements, decide whether you think it is true or false
  and give a proof or counterexample.
  \begin{parts}
    \part $\log_2f(n)$ is $O(\log_2 g(n))$.
    \part $2^{f(n)}$ is $O(2^{g(n)})$.
    \part $f(n)^2$ is $O(g(n)^2)$.
  \end{parts}
  \newpage

  \question (Basic proof techniques) Read the chapter on \texttt{Proof
    by Induction} by Erickson
  (\url{http://jeffe.cs.illinois.edu/teaching/algorithms/notes/98-induction.pdf}),
  and note by Fleck
  (\url{http://mfleck.cs.illinois.edu/building-blocks/version-1.3/proofs.pdf}). Then
  do the following.

  \begin{parts}
    \part[10] Prove that for any positive $x\in\mathbb{R}$, $x + 1/x
    \ge 2$.
    \part[10] . Prove that given an unlimited supply of 6-cent coins,
    10-cent coins, and 15-cent coins, one can make any amount of
    change larger than 29 cents.
  \end{parts}

  \newpage

\end{questions}


\end{document}
