%%% Fall 2004, Make-up problem for the midterm
\documentclass[11pt]{article}
 
\usepackage{epsf}
\usepackage{pslatex}

\setlength {\topmargin}{0in}
\setlength {\headheight}{0in}
\setlength {\headsep}{0cm}
\setlength {\textheight}{9in}
\setlength {\oddsidemargin}{0in}
\setlength {\evensidemargin}{0in}
\setlength {\textwidth}{6.5in}
\setlength {\parskip}{0cm} 


\setlength{\parskip}{1ex plus 0.5ex minus 0.2ex}

\begin{document}
\thispagestyle{empty}

\begin{center}
{\bf \large ECE G205 Fundamentals of Computer Engineering} \\
{\bf Fall 2004} \\[0.5cm]
{\large \bf Midterm Make-Up: Due by Wednesday December 1 2004} \\
\end{center}

{\large
\vspace*{2cm}\noindent
\begin{itemize}

\item This test is ONLY for those students that have gotten
  less than 80 (strictly less than 80) in the midterm. 
  More specific instructions are given in the class web page.

\item The test contains $4$ problems. They allow you to earn
$100$ points.

\item Show your work, as partial credit can be given. You will be
graded not only on the correctness of your answer, but also on the
clarity with which you express it. \textbf{Be neat}.

\item {\bf No late submissions will be accepted.}

\item Only homework returned in a 9in $\times$ 12in envelope
will be accepted. (If you cannot find such envelope, ask the
Instructor.) Please, write your name and the class name (ECE
G205) on the envelope (write clearly, please).

\item For the problems below NO code has to be sent
  to the TAs.

\end{itemize}


\vspace*{3cm}
Write your name here:\ 
\hrulefill
}


\setcounter{page}{0}

%----------------------------------------------------------------------
\newpage
\begin{itemize}

\item {\bf Problem \# 1\ \ [40 points]}.  
Consider the following $2 \times 2$
matrix:

\[
  A = \left( \begin{array}{cc}
           0 & 1 \\
           1 & 1
          \end{array}
      \right)
\]

\noindent
\textbf{(a)} Write a function to \emph{efficiently} compute the 
$n$th power of $A$, namely:

\[
  A^{n} = \underbrace{A \cdot A \cdots A}_{n \mbox{ times}}.
\]

\noindent
(A linear solution \emph{won't} do \ldots)

\noindent
\textbf{(b)} Determine the time complexity of your solution.

\noindent
\textbf{(c)} How can a solution to point \textbf{(a)} be used to return the 
$n$th number of the Fibonacci sequence. (For a definition of
the Fibonacci sequence, see Homework 7.)


%----------------------------------------------------------------------
\newpage
\item {\bf Problem \# 2\ \ [20 points]}.  As seen in class,
the following is the recursive definition of the binomial
coefficient when $k \leq n$

\[
  \left( \begin{array}{c} n \\ k \end{array} \right) =
  \left\{ \begin{array}{ll}
       1 & \mbox{if $k=0$ or $k=n$} \\ \mbox{ } \\
       \left( \begin{array}{c} n - 1 \\ k - 1 \end{array} \right) +
       \left( \begin{array}{c} n - 1 \\ k \end{array} \right) &
       \mbox{if } 0 < k < n.
  \end{array} \right.  
\]

\noindent
Write a ``Dynamic Programming'' kind of function that
returns $\left( \begin{array}{c} n \\ k
\end{array} \right)$. As mentioned, the binomial coefficient $\left(
\begin{array}{c} n \\ k \end{array} \right)$ can be seen as the last
entry $c_{n,k}$ of a $(n+1) \times (k+1)$ matrix which can be filled
out line by line in the following way: $c_{0,j} = 0$, $1 \leq j \leq
k$, $c_{i,0} = 1$, $0 \leq i \leq n$, and

\[
  c_{i,j} = c_{i-1,j-1} + c_{i-1,j}, 1 \leq i \leq n, 1 \leq j \leq k.
\]

\noindent
Use this characterization (also known as \emph{Pascal's triangle}) to 
write a function that taken as input $n$ and $k$ returns 
$\left( \begin{array}{c} n \\ k \end{array} \right)$. The 
\emph{space} complexity of your solution \emph{MUST} be
linear, i.e., $O(n)$.

%----------------------------------------------------------------------
\newpage
\item {\bf Problem \# 3\ \ [30 points]}. 
Write a Dynamic Programming algorithm to compute $a^{n}$
($n$ even) based on the formula:

\[
  a^{n} = a^{n/2} a^{n/2} 
\]

%----------------------------------------------------------------------
\newpage
\item {\bf Problem \# 4\ \ [30 points]}. 
In case of small $x$ and $y$ write a C++ function that
returns $x^{y}$ in constant time.

\end{itemize}

\end{document}
