%%% Fall 2004, HMW 7
\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 Homework 7: Due by Monday November 29 2004} \\
\end{center}
{\large
\vspace*{2cm}\noindent
\begin{itemize}
\item This test contains $2$ 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 two 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\ \ [50 points]}. Imagine a
competition where two teams $BRS$ and $SLC$ play no more
than $2n-1$ games, the winner being the first team that
achieves $n$ victories. Assume that there are no tied
games, that the results of each match are independent and
that for any given match there is a constant probability $p$
that team $BRS$ will be the winner and hence a constant
probability $q=1-p$ that team $SLC$ will win. Using a
dynamic programming approach, compute the probability that
team $BRS$ will be the winner.
(Hint: Let $P(i,j)$ be the probability that team $BRS$ will be
the winner given that they still need $i$ more victories to
win, while team $SLC$ still needs $j$ more victories if they
are to win \ldots ... $P(n,n)$ is what you want. Why?)
Compute the time complexity of your solution.
%----------------------------------------------------------------------
\newpage
\item {\bf Problem \# 2\ \ [50 points]}. Write an iterative
and a recursive function for computing the $n$th element
$F_{n}$ of the \emph{Fibonacci} sequence. The Fibonacci
sequence is a sequence of integers so defined: $F_{0} = 0$,
$F_{1} = 1$, and $F_{n} = F_{n-1} + F_{n-2}$. Discuss the
worst case time complexity of the two solutions.
\end{itemize}
\end{document}