\documentclass{article} \begin{document} \title{CS577 - Midterm 1 - Regrade Notes} \author{Zak Smith } \maketitle \newcommand{\A}{{\it a}} \newcommand{\B}{{\it b}} \newcommand{\n}{{\it n}} Problem 3. I believe I have the correct solution. It was difficult to grade because I used different notation than was suggested in the problem description. Here is what I wrote on my exam (minus the line numbers): \begin{verbatim} 1. N(n) = number of words which do not contain "aa" 2. N(n) = Ea(n-1) + 2*Eb(n-1) 3. Ea(n) = Eb(n-1) <--- end in a 4. Eb(n) = N(n-1) <--- end in b -------------------------- 5. discussion 6. N(n) is: 7. . . . . . a | b 8. . . . . . b | a 9. . . . . . b | b 10. Ea(n) is 11. . . . . . b | a 12. Eb(n) is 13. . . . . . a | b 14. . . . . . b | b \end{verbatim} \noindent The only difference between this and the reference solution was that instead of using Wa and Wb, which were the sets which {\it started} with \A~ and \B, respectively, I used Ea and Eb, which {\it ended} with \A~ and \B, respectively (hence the ``E''). I denoted this definition in lines 3 and 4. Line 3 says: the number of valid words which end in \A~ of length $n$ (Ea) is equal to the number of valid words of length $n-1$ which end in \B. I ``graphically'' show this in line 10 and 11, which show the $n-1$ elements ending in \B, and the new \A~ tacked on the end. Similarly, for Eb, line 4 says: the number of valid words of length $n$ which end in \B~ is equal to the number of valid words of length $n-1$, which is N(n-1). I defined $N(n) = Ea(n-1) + 2*Eb(n-1)$ on line 2. As shown on lines 6 -- 9, the number of valid words of length $n$ is: the number of valid words of length $n-1$ which end in \A~ plus twice the number of valid words of length $n-1$ which end in \B. Note that the definition of Ea corresponds to Wa, and Eb corresponds to Wb. They have the same meaning. Given lines 2, 3, and 4, it is easy to prove that my answer is the same as the given answer of $N(n) = N(n-1) + N(n-2)$. Starting with my definitions: $$ Ea(n) = Eb(n-1) $$ $$ Eb(n) = N(n-1)$$ $$ N(n) = Ea(n-1) + 2*Eb(n-1)$$ Now, we expand the $Ea$ and $Eb$ terms once... $$ N(n) = Eb(n-2) + 2*N(n-2) $$ and then twice... $$ N(n) = N(n-3) + 2*N(n-2) $$ Now it is easy to prove this is equal to the given solution: $$N(n) = N(n-1) + N(n-2)$$ by simply expanding $N(n-1)$: $$ N(n) = N(n-1) + N(n-2) $$ $$ = [ N(n-2) + N(n-3) ] + N(n-2) $$ $$ = N(n-3) + 2*N(n-2) $$ And I have simply proven that my answer: $$ N(n) = Ea(n-1) + 2*Eb(n-1)$$ $$ Ea(n) = Eb(n-1) $$ $$ Eb(n) = N(n-1)$$ which yields: $$ N(n) = N(n-3) + 2*N(n-2) $$ is equivalent to the provided solution: $$N(n) = N(n-1) + N(n-2)$$ Thank you for your time. \end{document} |

[Zak Smith] [zak@computer.org] [/~zak/documents/college/cs577-bitch/tex]

$Id: documents,v 1.5 2000/09/28 21:20:39 zak Exp zak $

documents was last modified Mon 07 Apr 2014 0:16:32

All

documents took 5.35 msec and 1 queries to generate, at Thu 09 Jul 2020 20:55:14.