
\documentclass[11pt]{article}
\usepackage{amsmath}
\input{/a/class/6.042/fall99/inputs/macros-course}

%\renewcommand{\solution}[1]{}

\def\brule#1{\enskip\vrule width#1 height -1.1pt depth 1.5pt\relax}
\def\medblank{\rule[-2pt]{1in}{.5pt}}
\def\relz{\mathbin{\, \rho \,}}

\newcommand{\emptybox}[3][]{%
\begin{center}
    \leavevmode\fbox{%
        \vbox to #3{%
            \vfil
            \hbox to #2 {\hfil#1\hfil}%
            \vfil
        }%
    }%
\end{center}
}

\makeatletter
\renewcommand\theenumi{\@alph\c@enumi}
\renewcommand\theenumii{\@roman\c@enumii}

\renewcommand\labelenumi{\theenumi)}
\renewcommand\labelenumii{\theenumii)}

\def\ps@myheadings{%
    \let\@oddfoot\@empty\let\@evenfoot\@empty
    \def\@evenhead{\thepage\hfil\slshape\leftmark}%
    \def\@oddhead{\rlap{\slshape\rightmark}\hfil\thepage\hfil \llap{Name:\brule{2in}}}%
    \let\@mkboth\@gobbletwo
    \let\sectionmark\@gobble
    \let\subsectionmark\@gobble
    }

\makeatother

\begin{document}

\begin{center}
{\bf Supplement to Final Fall 99}
\end{center} 

\noindent
{\bf Replace problem 3 in the final  by the following problem on invariants.}

{\bf Problem 3'}[10 points] \textbf{Invariants} 
\bparts
\ppart
Give the definition of a {\it state invariant } of a state machine?
\vspace{2in}

\ppart
Besides, the identically \texttt{false} 
and identically \texttt{true} state invariants, 
how many other logically distinct state invariants does the following machine have?
Describe them. ( Two invariants are logically distinct if there exists a state 
in which one holds and the other doesn't.)

{\bf State Machine Description:}\\
 States $Q \eqdef \set{A,B,C,D,E,F,G,H}$, transitions:
\[
\set{(A,B), (B,C), (C, A), (D,E), (E,F) (F,D), (C,D), (G,A), (B,H)}.
\]

\solution{

$\set{ABCDEFH}, \set{DEF}, \set{H}$.}

\eparts
\newpage

\noindent
{\bf Replace problem 9 in the final  by the following problem on linear
recurrence - same problem with an example .}

\noindent{\bf problem 9'}[15 points] \textbf{Linear Recurrence}

You just moved into your new house and you are throwing a housewarming
party.  You invite 5 people on the first day and tell them to invite their
friends.  Each newly invited person invites 2 people the day after they
are invited.

\bparts

\ppart

[5 points] Give a recurrence describing the total number of people invited by the $n$th
day. This includes everyone -- i.e the people you invited, and the people invited by
the people you invited etc.

(E.g. On the first day 5 people were  invited,  by the second day 15 people
were  invited including the 5 people you invited on the 1st day  and the 10 people they invited
on the 2nd day, by the third day 35 people were invited etc ).

\solution{
You know that the number of people for each day will
equal the number of people who were invited from the day before in
addition to 2 new guests for each of the new people on the day before.
T(n) = T(n-1) + 2 [ T(n-1) - T(n-2) ] = 3 T(n-1) - 2 T(n-2) }

%\vspace{2in}

\ppart 

[5 points] Describe initial conditions for the recurrence.

\solution{ You know that T(0) = 0 since no one was invited on day 0 and
T(1) = 5, since you invited 5 people on the first day.}

%\vspace{2in}

\ppart 

[5 points] Give a closed form expression equal to the number of people invited
by the $n$th day.

\solution{ Solving this recurrence $a^2 = 3a - 2$ $a^2 - 3a + 2 = 0$
$(a-2) (a-1) = 0$ $a = 2$ or $1$

$T(n) = c2^n + b1^n = c2^n + b$

Plugging in the initial conditions, gives you two equations :
$T(0)=0=c+b$
$T(1)=5=c*2 + b$
$c = 5, b = -5$

$T(n) = (5 * 2^n) - 5  $

}

%\vspace{1.5in}

\eparts

\end{document}



