\documentclass{article}
\usepackage{ccfonts}
\usepackage{amsmath,amsfonts,graphics}
\renewcommand{\bfseries}{\scshape}
\usepackage{fullpage}
\title{\textbf{Draft:} CSC165, Summer 2005,
  Assignment 4\\
  {\large Due: Thursday July 28th, 10 am}}
\author{Danny Heap}
\renewcommand{\today}{~}

\begin{document}
\maketitle

\section*{Instructions}
\label{instructions}

Please work on all questions.  Turn in the outline and structure of a
solution, even if you cannot provide every step, and we will
try to assign some part marks.  However, if there is any question you
cannot see how to even begin, leave it blank and you will receive 20\%
of the marks for that question.

Be sure to give full credit to any sources you consult (other than
course notes, TAs, and the instructor) in preparing this problem set.
If you try to pass off somebody else's work as your own for credit,
you are committing an academic offense, and that can entail serious
consequences.  Any ideas that you do not attribute to someone else are
assumed to be the ideas of the author(s) listed below, and will be
evaluated for grading.

Write your name(s) and student number(s) (maximum of two names and two
student numbers) in the space below.\vspace{2\baselineskip}

\noindent Name\hfill
\rule{0.8\textwidth}{1pt}\\[2\baselineskip]
\noindent Student \#\hfill
\rule{0.8\textwidth}{1pt}\\[2\baselineskip]
\noindent Name\hfill
\rule{0.8\textwidth}{1pt}\\[2\baselineskip]
\noindent Student \#\hfill
\rule{0.8\textwidth}{1pt}
\newpage

\begin{enumerate}
\item Complete the methods \texttt{toBiNeg(int n)},
  \texttt{toInt(String s)}, and \texttt{compare(String bn1, String
    bn2)} from \texttt{BiNegUtil.java} (on the web page).  Do not
  import any packages, and do not convert \texttt{bn1} or \texttt{bn2}
  to integers in \texttt{compare}.

\item Consider the base $-2$ representation, where $b_i\in \{0,1\}$, and
  \begin{displaymath}
    (b_n b_{n-1} \cdots b_1 b_0)_{-2} = \sum_{i=0}^n b_i (-2)^i.
  \end{displaymath}

  \begin{enumerate}
  \item How many positive integers can be written in an $n$-digit base
  $-2$ representation (including representations with leading zeros on
  the left)?  How many negative numbers can be written in an
  $n$-digit base $-2$ representation (including representations with
  leading zeros on the left).  Justify your answer.

\item For natural number $k$, what is the minimum number of digits
  needed to represent $k$ in base $-2$ representation?  Justify your
  answer.
  \end{enumerate}
\item Examine the method \texttt{mult(m,n)} in \texttt{BiNegUtil.java}
  (on the web page). Prove or disprove that if the loop invariant is
  true at the beginning of a loop iteration, then it is true at the
  end of a loop iteration.  Your proof should be in the structured
  proof format from class.

\item Let $f:\mathbb{N}\rightarrow \mathbb{R}^{\geq 0}$, and let
  \begin{displaymath}
    O(f)=\{g:\mathbb{N}\rightarrow \mathbb{R}^{\geq 0} |
    \exists c\in \mathbb{R}^+, \exists B\in\mathbb{N}, \forall
    n\in\mathbb{N}, n\geq B\rightarrow g(n)\geq cf(n)\}
  \end{displaymath}
  Prove or disprove (in structured proof form) the following claims:

  \begin{enumerate}
  \item Suppose $f,g:\mathbb{N}\rightarrow \mathbb{R}^{\geq 0}$. Then
  $g\in
  O(f)\Rightarrow g(n^3)\not\in O(f)$

  \item Suppose $f,g,h:\mathbb{N}\rightarrow \mathbb{R}^{\geq 0}$.
    Then $(g\in O(f)\wedge h\in O(f)) \Rightarrow \max(g,h)\in O(f)$.

  \item Suppose $f,f',g,g':\mathbb{N}\rightarrow \mathbb{R}^{\geq 0}$,
  and $f\circ g(n)=f(g(n))$, $f'\circ g'(n)=f'(g'(n))$.  Then $(f\in O(f')
  \wedge g\in O(g')) \Rightarrow f\circ g \in O(f'\circ g')$.

  \item Suppose $f,g,h:\mathbb{N}\rightarrow \mathbb{R}^{\geq 0}$ and
    $gh(n)=g(n)h(n)$. Then $(g\in O(f) \wedge h\in O(f))\rightarrow gh
    \in O(f)$.

  \item Suppose $f,g:\mathbb{N}\rightarrow \mathbb{R}^{\geq 0}$ and
  $f'(n)=\lfloor f(n)\rfloor$, $g'(n)=\lfloor g(n)\rfloor$.  Then
  $g\in O(f)\rightarrow g'\in O(f')$.
  \end{enumerate}
\end{enumerate}
\end{document}