\documentclass[12pt]{amsart} \usepackage{amsmath} \usepackage{amsthm} \usepackage{amstext} \usepackage{amsfonts} \usepackage{graphicx} \usepackage{latexsym} \usepackage{epsfig} % \input epsf \def\p{\partial} \def\O{\Omega} \def\c{\cal} \def\a{\alpha} \def\r{\rho} \def\e{\epsilon} \def\g{\gamma} \def\d{\delta} \def\D{\Delta} \def\t{\theta} \def\T{\Theta} \def\N{\nabla} \def\L{\Lambda} \def\l{\lambda} \def\m{\mu} \def\f{\frac} \def\dis{\displaystyle} \def\s{\sigma} \newcommand{\lx}{\left} \newcommand{\rx}{\right} \setlength{\parindent}{0in} \setlength{\parskip}{\baselineskip} \setlength{\textheight}{9.0in} \setlength{\textwidth}{6.5in} \setlength{\topmargin}{0.0in} \setlength{\evensidemargin}{0in} \setlength{\oddsidemargin}{0in} \begin{document} %( \baselineskip 24pt \title{Final Exam Cheat Sheet/Study Guide} % YOUR NAME GOES HERE under Author \maketitle You can use this as a study guide. You will also be able to use it on the Final Exam on Tuesday. If there's anything else you feel should be on this, please send me email before Monday night. \begin{enumerate} %( \item Sequences and Summations \begin{enumerate} %( \item Fibonacci sequence (1, 1, 2, 3, 5, 8, 13, $\cdots$): Recursive Definition \begin{enumerate} %( \item {\bf Base Cases:} $f_1 = f_2 = 1$ \item {\bf Recursive definition:} $f_{n} = f_{n-1} + f_{n-2}$ \end{enumerate} %) Closed Form Definition \begin{displaymath} %( f_n = \f{\lx(1+\sqrt{5}\rx)^n - \lx(1-\sqrt{5}\rx)^n}{2^n \sqrt{5}} \end{displaymath} %) \item Some summations: \begin{enumerate} %( \item $1 + 2 + 3 + 4 + \cdots + n = \f{n^2 + n}{2}$ \item $1^2 + 2^2 + 3^2 + 4^2 + \cdots + n^2 = \sum_{i=1}^n i^2 = \f{n \lx(n+1\rx) \lx(2n+1\rx)}{6}$ \item $9 + 9^2 + 9^3 + \cdots + 9^n = \f{9^{n+1} - 9}{8}$ \end{enumerate} %) \end{enumerate} %) \item Proof by Induction \begin{enumerate} %( \item Proof that $1 + 2 + 3 + \cdots + n = \f{n^2 + n}{2}$ \begin{enumerate} %( \item {\bf Base case:} $1 = \f{1^2 + 1}{2} = 1$ \item {\bf Inductive step:} Assume that $1 + 2 + 3 + \cdots + i = \f{i^2 + i}{2}$ for $i$ from 1 to $n-1$. \begin{eqnarray} %( 1 + 2 + 3 + \cdots + n & = & \lx(1 + 2 + 3 + \cdots + n-1\rx) + n \\&=& \f{\lx(n-1\rx)^2 + \lx(n-1\rx)}{2} + n \\&=& \f{n^2 -n}{2} + n \\&=& \f{n^2 -n + 2n}{2} \\&=& \f{n^2 + n}{2} \end{eqnarray} %) \end{enumerate} %) \end{enumerate} %) \item Recursion \begin{enumerate} %( \item Kevin Bacon Actors' Guild recursive definition (where $KB$ is Kevin Bacon and $A\lx(x, y\rx)$ means that $x$ and $y$ acted in a movie together): \\ $KBAG = \lx\{x| x = KB \vee \exists y \lx(y \in KBAG \wedge A\lx(x, y\rx)\rx)\rx\}$ \item The set $MA$ of all Marc's ancestors (excluding Marc) is given by the following definition (where $M$ is Marc and $p\lx(x, y\rx)$ means $x$ is $y$'s parent): $MA = \lx\{x| p\lx(x, M\rx) \vee \exists y \lx(y \in MA \wedge p\lx(x, y\rx)\rx)\rx\}$ \item $N! = 1 \cdot 2 \cdot 3 \cdots N$ \begin{enumerate} %( \item {\bf Base Case:} $0! = 1$ \item {\bf Recursive definition:} $n! = n \cdot \lx(n-1\rx)!$ \end{enumerate} %) \end{enumerate} %) \item Counting, Permutations, and Combinations \begin{enumerate} %( \item Number of TLA's (Three Letter Acronyms) $= 26^3$ \item Number of 10 digit phone numbers, excluding those that start with 0 or 1 or have 555 as their middle 3 numbers: $= 10^{10} - \lx(2\cdot 10^9 + 10^7 - 2\cdot 10^6\rx)$ \item Pigeonhole principle: If there are 27 people in the class, and 4 Starburst flavors, then at least one flavor must be the favorite of at least $\lx\lceil\f{27}{4}\rx\rceil = 7$ people. \item n Pick a = $\f{n!}{\lx(n-a\rx)!}$ \item n Choose a = ${n \choose a} = \f{n!}{\lx(n-a\rx)!a!}$ \item Number of ways to put 9 baseball players on a field (with assigned positions) out of a team of 20 = 20 Pick 9 \item Number of ways to put 6 men and 4 women on a dodgeball team (from 10 women and 12 men) where the positions don't matter $ = {10 \choose 4} {12 \choose 6}$ \item Number of ways to match exactly 3 of 6 lotto numbers (out of 49) $= {6 \choose 3} {43 \choose 3}$ \item Number of full houses in 5 card poker $= 13 {4 \choose 3} 12 {4 \choose 2}$ \item Number of ways to get a pair of kings in 5 card poker $= {4 \choose 2} {48 \choose 3}$ \item Binomial expansion: $\lx(A+B\rx)^n = \sum_{i=0}^n {n \choose i} A^iB^{n-i}$ \item Pascal's identity: ${n+1 \choose k} = {n \choose k-1} + {n \choose k}$ \item Pascal's triangle: \begin{verbatim} 1 1 1 1 2 1 1 3 3 1 1 4 6 4 1 1 5 10 10 5 1 (etc.) \end{verbatim} \item Ways to arrange letters in DELETE $= \f{6!}{3!}$, SERENDIPITY $= \f{11!}{2! 2!}$ \item Ways to make a pack of Starburst (4 flavors, 12 Starbursts in a pack) $= {12 + \lx(4-1\rx) \choose 4-1}$ \end{enumerate} %) \item Probability \begin{enumerate} %( \item Prob of 2 of 27 people having same birthday = 1 - Prob of all B-days being different $= 1 - \f{366}{366} \cdot \f{365}{366} \cdot \f{364}{366} \cdots \f{366 - 26}{366}$ = $1 - \f{366!}{\lx(366-27\rx)! \cdot 366^{27}} \approx 0.6258$ \item Discrete Probability principles (where $P\lx(E\rx)$ means the probability of event $E$).: \begin{enumerate} %( \item $0 \leq P\lx(E\rx) \leq 1$ \item If $O$ is the set of all possible outcomes $1 = \sum_{o \in O} P\lx(o\rx)$ \item $1 - P(E) = P(\sim E)$ \item $P (A \vee B) = P (A) + P(B) - P (A \wedge B)$ \item Events $A$ and $B$ are {\em independent} iff $P \lx(A \wedge B\rx) = P\lx(A\rx) P \lx(B\rx)$ \end{enumerate} %) \item Conditional Probability: \begin{enumerate} %( \item Bayes's law: $P(B|A) = \f{P(A|B)P(B)}{P(A)}$ \item $P(A \wedge B) = P(A|B)P(B)$ \item $P(A) = P(A \wedge B) + P(A \wedge \sim B) = P(A|B)P(B) + P(A|\sim B)P(\sim B)$ \end{enumerate} %) \item Bernoulli Distribution: $P(rolling~ 1)$ exactly 3 times out of 10 = $P(rolling~ 1)^3 (1 - P(rolling~ 1))^7 {10 \choose 3}$. More generally, the probability of rolling exactly $a$ 1's when rolling $b$ $n$ sided dice is $\lx(\f{1}{n}\rx)^{a} \lx(\f{n-1}{n}\rx)^{b-a} {b \choose a}$. \item Some statistics \begin{enumerate} %( \item Expected value = $E\lx[X\rx] = \sum_{x \in X} P(x) x$ \item Variance = $V\lx[X\rx] = E\lx[\lx(x - E\lx[X\rx]\rx)^2\rx] = \sum_{x \in X} P(x) \lx(x - E\lx[X\rx]\rx)^2$ \item Standard Deviation = $\sigma\lx[X\rx] = \sqrt{V\lx[X\rx]}$ \end{enumerate} %) \end{enumerate} %) \item Recurrence Relations: If the $n$th term of a recurrence relation is defined as $a_n = c_1 a_{n-1} + c_2 a_{n-2} + \cdots + c_k a_{n-k}$ (and the {\em base cases} are defined to be $a_1 = m_1$, $a_2 = m_2$, $\cdots$, $a_k = m_k$ (where $m_i$ is a constant)), then there will be a solution of the form $a_n = r^n$. The {\em characteristic equation} for $a$ is then \begin{displaymath} %( r^k - c_1 r^{k-1} - c_2 r^{k-2} - c_3 r^{k-3} - ... - c_k = 0 \end{displaymath} %) If this equation has distinct roots $r_1, \cdots r_k$, then $a_n = \alpha_1 r_1^n + \cdots + \alpha_k r_k^n$, where $\alpha_i$ is a constant. We can solve for the $\alpha$s by solving the system of linear equations given for the first $k$ $a_i$s. \item Relations \begin{enumerate} %( \item Relation $<$ on Natural numbers as a matrix \begin{verbatim} 1 2 3 4 5 ... 1 0 1 1 1 1 2 0 0 1 1 1 etc... 3 0 0 0 1 1 ... 4 0 0 0 0 1 5 0 0 0 0 0 ... ... etc... \end{verbatim} \item Number of possible relations on set $S$ = $2^{\lx|S\rx|^2}$ \item {\bf reflexive} $\forall a \in S, \lx(a, a\rx) \in R$: Examples: $\leftrightarrow$, $\leq$, $=$. Non-examples: ``Parent'', $\wedge$ \item {\bf symmetric} $\forall a, b \in S, \lx(a, b\rx) \in R \leftrightarrow \lx(b, a\rx) \in R$: Examples: ``Acted with'', ``married to'', XOR. Non-examples: ``loves'', $\implies$ \item {\bf antisymmetric} $\forall a, b \in S, \lx(a, b\rx) \in R \wedge \lx(b, a\rx) \in R \implies a = b$: Example: $\implies$, $\leq$. Non-example: XOR. \item {\bf asymmetric} $\forall a, b \in S, \lx(a, b\rx) \in R \leftrightarrow \wedge \lx(b, a\rx) \in R$: Examples: ``Parent'', $<$ \item {\bf transitive} $\forall a, b, c \in S, \lx(a, b\rx) \in R \wedge \lx(b, c\rx) \in R \implies \lx(a, c\rx) \in R$: Examples: ``Ancestor'', $<$, ``Taller than''. Non-examples: ``beats at chess'', ``Acted with''. \item Since Relations are sets, we can combine them with set operators ($\cup$, $-$, $\cap$). E.g. if $R1$ is the relation between a set of students in 203 and classes offered at UMBC that contains $\lx(s, c\rx)$ iff student $s$ has taken class $c$, and $\lx(s, c\rx) \in R2$ iff $c$ is a required course for $s$'s major, then: \begin{enumerate} %( \item $\lx(s, c\rx) \in R1 \cup R2$ means that $s$ is guaranteed to have taken $c$ by the time he/she graduates. \item $\lx(s, c\rx) \in R2 - R1$ means that $s$ needs to take $c$ yet to graduate. \item $\lx(s, c\rx) \in R1 \cap R2$ means that $s$ has taken $c$ as a required class (as opposed to an elective). \end{enumerate} %) \item Composition of Relations: $\lx(a, b\rx) \in R1 \wedge (b,c) \in R2 \implies (a,c) \in R1 \circ R2$: E.g Grandparent = Parent $\circ$ Parent \end{enumerate} %) \item Graphs \begin{enumerate} %( \item UMBC students and UMBC classes (and the edges representing that a student is taking a class) is a {\bf bipartite graph} because no class is directly connected to any other class (and no student is directly connected to another student). \item If there's a {\bf path} from every UMBC student to every class and every other student, then the UMBC student/class graph is not {\bf disjoint}. \item A graph can be represented as a {\em set} of edges, and for this reason, all the set operations can apply to graphs too. For example, the {\bf complement} of a simple undirected graph that has $n$ nodes and $e$ edges has $e - \f{n^2-n}{2}$ edges: an edge everywhere there wasn't an edge before. \item A pair of graphs $G_1$ and $G_2$ are {\bf isomorphic} if there's a mapping from the nodes of $G_1$ to the nodes of $G_2$ such that if you rename $G_1$'s nodes according to this mapping, you'll have a graph identical to $G_2$. \item A graph is {\bf planar} if the graph can be layed out on a surface without edges intersecting (edges need not be straight though). \item There are $2^{\f{n^2-n}{2}}$ possible simple undirected graphs over $n$ nodes (see the solutions for Exam 2 for a derivation of this expression). \end{enumerate} %) \item Trees \begin{enumerate} %( \item Huffman's algorithm for making an encoding tree: \begin{enumerate} %( \item Compute the letter frequencies \item Make 26 ``trees'' (assuming you have 26 characters), each with a count of the character they represent and a single node representing a character. \item ``Merge'' the 2 trees with the lowest count. This means to create a new tree whose count is the sum of the 2 other counts, and whose left branch is marked with a 0, and whose right branch is marked with a 1 (or vice versa). \item Keep merging until you have only 1 tree. \item The encoding for a character will be markings along the path from the root to the leaf that represents that character. \end{enumerate} %) \item Some discrete multi-player turn-based games (e.g., Chess, Tic-Tac-Toe) can be represented as a {\bf game tree}. The root is the starting state, and each level represents different players turns. The leaves represent final outcomes of the game. Given a complete tree for a deterministic game, one can determine an optimal strategy for each player. \end{enumerate} %) \item Boolean Algebra \begin{enumerate} %( \item For any Boolean expression (e.g. $\sim \lx(A \wedge B\rx) \implies C$) You should be able to construct a circuit using logic gates. How to represent these in \LaTeX goes beyond my expertise, but if needed for the final, I'll give the logic circuit symbols for {\bf and}, {\bf or}, {\bf not}, {\bf xor}, {\bf nand}, and {\bf nor}. \item A logical operator is {\bf universal} iff it alone can be used to construct any other logical operator. {\bf nand} and {\bf nor} are universal. {\bf and} and {\bf not} together make a {\bf universal set} because they can be used together to make any logical expression. $\implies$ combined with a {\bf True} signal makes a universal set. \end{enumerate} %) \item Languages and Grammars \begin{enumerate} %( \item \begin{verbatim} ::= A A | D D | A | D | lambda \end{verbatim} Is a grammar that generates all palindromes over the characters {\tt A} and {\tt D}. {\tt } is a non-termal, and {\tt A} and {\tt D} are terminals {\tt lambda} (or $\lambda$) is the empty string. \item The string {\tt ADDA} is in the {\bf language} of the above grammar. This means that it can be {\bf parsed} by the grammar. One (and the only in this case) parsing is \begin{verbatim} / | \ A A / | \ D | D | (lambda) \end{verbatim} \end{enumerate} %) \item Finite-State Automata \begin{enumerate} %( \item A finite state automaton (FSA) has states and transition rules. Each transition rule says if we read character $c$ while in state $x$, we transition to state $y$. One of the states is marked as the starting state and one or more states is marked as an accepting state. If, when reading a string and starting in the start state, we end in an accepting state, we say that the string is in the language of the FSA. \item For every FSA there's (at least one) regular expression and vice versa. That is, the regular expression and the FSA have the same language. \item A regular expression may contain the following: \begin{enumerate} %( \item {\tt A|B} This is {\bf or}. So {\tt ((MARC)|(B*))} would be either the string {\tt MARC} or a string of 0 or more {\tt B}s (but not both.) \item {\tt AB} I.e., one regular expression can follow another. \item {\tt A*} Also called a Kleene star. This means you may repeat the preceding regular expression 0 or more times. For example the {\tt (AA|B)*} means any string composed only of {\tt B}s and pairs of {\tt A}s. \end{enumerate} %) \end{enumerate} %) \item Turing Machines \begin{enumerate} %( \item A {\bf Turing machine} has a {\bf reader head} on an {\bf infinite tape} and a transition table where each entry says: when in state $x$ and reading a $y$ on the tape, write a $z$, move the reader head (left or right), and transition to state $w$. \item A {\bf Universal Turing machine} is one that can read a description of any other Turing machine on the tape (as well as that machine's input), then simulates running that machine on that input. A Universal Turing machine has as much computing power (though not in terms of runtime) as any computer ever built, and it's believed that no computer can ever have more computing power. \item Halting problem: It's impossible to have a function {\tt boolean halt(P)} which takes a program {\tt P} and returns true iff {\tt P} halts eventually (when started with no input). Proof by contradiction: Assume such a function existed, then we could write the program {\tt M}: \begin{verbatim} M: int i = 0 if halt(M) while(true) i = i + 1 else exit \end{verbatim} Thus {\tt M} halts iff {\tt halt(M)} is false which is a contradiction. \end{enumerate} %) \end{enumerate} %) \end{document} %)