\documentclass[12pt, oneside]{article}

\usepackage[letterpaper, scale=0.89, centering]{geometry}
\usepackage{fancyhdr}
\setlength{\parindent}{0em}
\setlength{\parskip}{1em}

\pagestyle{fancy}
\fancyhf{}
\renewcommand{\headrulewidth}{0pt}
\rfoot{\href{https://creativecommons.org/licenses/by-nc-sa/2.0/}{CC BY-NC-SA 2.0} Version \today~(\thepage)}

\usepackage{amssymb,amsmath,pifont,amsfonts,comment,enumerate,enumitem}
\usepackage{currfile,xstring,hyperref,tabularx,graphicx,wasysym}
\usepackage[labelformat=empty]{caption}
\usepackage{xcolor}
\usepackage{multicol,multirow,array,listings,tabularx,lastpage,textcomp,booktabs}

\lstnewenvironment{algorithm}[1][] {   
    \lstset{ mathescape=true,
        frame=tB,
        numbers=left, 
        numberstyle=\tiny,
        basicstyle=\rmfamily\scriptsize, 
        keywordstyle=\color{black}\bfseries,
        keywords={,procedure, div, for, to, input, output, return, datatype, function, in, if, else, foreach, while, begin, end, }
        numbers=left,
        xleftmargin=.04\textwidth,
        #1
    }
}
{}
\lstnewenvironment{java}[1][]
{   
    \lstset{
        language=java,
        mathescape=true,
        frame=tB,
        numbers=left, 
        numberstyle=\tiny,
        basicstyle=\ttfamily\scriptsize, 
        keywordstyle=\color{black}\bfseries,
        keywords={, int, double, for, return, if, else, while, }
        numbers=left,
        xleftmargin=.04\textwidth,
        #1
    }
}
{}

\newcommand\abs[1]{\lvert~#1~\rvert}
\newcommand{\st}{\mid}

\newcommand{\A}[0]{\texttt{A}}
\newcommand{\C}[0]{\texttt{C}}
\newcommand{\G}[0]{\texttt{G}}
\newcommand{\U}[0]{\texttt{U}}

\newcommand{\cmark}{\ding{51}}
\newcommand{\xmark}{\ding{55}}

 
\begin{document}
\begin{flushright}
    \StrBefore{\currfilename}{.}
\end{flushright} \section*{Algorithm redundancy}


Real-life representations are often prone to corruption.  Biological codes, like RNA, 
may mutate naturally\footnote{Mutations of specific RNA codons have been linked to many disorders and cancers.}
and during measurement; cosmic radiation and other ambient noise 
can flip bits in computer storage\footnote{This RadioLab podcast episode
goes into more detail on bit flips: \url{https://www.wnycstudios.org/story/bit-flip}}. 
One way to recover from corrupted data is to introduce or exploit redundancy. 

Consider the following algorithm to introduce redundancy in a string of $0$s and $1$s.
\begin{algorithm}[caption={Create redundancy by repeating each bit three times}]
procedure $\textit{redun3}$($a_{k-1} \cdots a_0$: a nonempty bitstring)
for $i$ := $0$ to $k-1$
  $c_{3i}$ := $a_i$
  $c_{3i+1}$ := $a_i$
  $c_{3i+2}$ := $a_i$
return $c_{3k-1} \cdots c_0$
\end{algorithm}

\begin{algorithm}[caption={Decode sequence of bits using majority rule on consecutive three bit sequences}]
procedure $\textit{decode3}$($c_{3k-1} \cdots c_0$: a nonempty bitstring whose length is an integer multiple of $3$)
for $i$ := $0$ to $k-1$
  if exactly two or three of $c_{3i}, c_{3i+1}, c_{3i+2}$ are set to $1$
    $a_i$ := 1
  else 
    $a_i$ := 0
return $a_{k-1} \cdots a_0$
\end{algorithm}

Give a recursive definition of the set of outputs of the $redun3$ procedure, $Out$,

\phantom{{\bf Basis step}: $000 \in Out$ and $111 \in Out$\\ {\bf Recursive step}: If $x \in Out$ then $x000 \in Out$ and $x111 \in Out$ (where $x000$ and $x111$ are the results of string concatenation).}


Consider the message $m = 0001$ so that the sender calculates $redun3(m) = redun3(0001) = 000000000111$.

Introduce $\underline{\phantom{~~4~~}} $
errors into the message so that the signal received by the 
receiver is $\underline{\phantom{010100010101}}$
but the receiver is still able to decode the original message.


{\it Challenge: what is the biggest number of errors you can introduce?} 

Building a circuit for lines 3-6 in $decode$ procedure: given three input bits, we need to determine whether the
majority is a $0$ or a $1$.

\begin{center}
\begin{multicols}{2}\begin{tabular}{ccc|c}
$c_{3i}$ & $c_{3i+1}$ & $c_{3i+2}$ & $a_i$ \\
\hline
$1$ & $1$ & $1$ & $\phantom{1}$ \\
$1$ & $1$ & $0$ & $\phantom{1}$ \\
$1$ & $0$ & $1$ & $\phantom{1}$ \\
$1$ & $0$ & $0$ & $\phantom{0}$ \\
$0$ & $1$ & $1$ & $\phantom{1}$ \\
$0$ & $1$ & $0$ & $\phantom{0}$ \\
$0$ & $0$ & $1$ & $\phantom{0}$ \\
$0$ & $0$ & $0$ & $\phantom{0}$ \\\\
\end{tabular}
\columnbreak

Circuit 
\end{multicols}
\end{center} \vfill
\section*{Algorithm rna mutation insertion deletion}


Recall that $S$ is defined as the set of all RNA strands, nonempty strings made of the bases in 
$B = \{\A,\U,\G,\C\}$. 
We define the functions 
\[
  \textit{mutation}: S \times \mathbb{Z}^+ \times B \to S
\qquad \qquad
  \textit{insertion}: S \times \mathbb{Z}^+ \times B \to S
\]
\[
  \textit{deletion}: \{ s\in S \mid rnalen(s) > 1\} \times \mathbb{Z}^+ \to S
  \qquad \qquad \textrm{with rules}
\]

\begin{algorithm}
procedure $\textit{mutation}$($b_1\cdots b_n$: $\textrm{a RNA strand}$, $k$: $\textrm{a  positive integer}$, $b$: $\textrm{an  element of } B$)
for $i$ := $1$ to $n$
  if $i$ = $k$
    $c_i$ := $b$
  else
    $c_i$ := $b_i$
return $c_1\cdots c_n$ $\{ \textrm{The return value is a RNA strand made of the } c_i \textrm{ values}\}$
\end{algorithm}

\begin{algorithm}
procedure $\textit{insertion}$($b_1\cdots b_n$: $\textrm{a RNA strand}$, $k$: $\textrm{a  positive integer}$, $b$: $\textrm{an  element of } B$)
if $k > n$
  for $i$ := $1$ to $n$
    $c_i$ := $b_i$
  $c_{n+1}$ := $b$
else 
  for $i$ := $1$ to $k-1$
    $c_i$ := $b_i$
  $c_k$ := $b$
  for $i$ := $k+1$ to $n+1$
    $c_i$ := $b_{i-1}$
return $c_1\cdots c_{n+1}$ $\{ \textrm{The return value is a RNA strand made of the } c_i \textrm{ values}\}$
\end{algorithm}

\begin{algorithm}
procedure $\textit{deletion}$($b_1\cdots b_n$: $\textrm{a RNA strand with } n>1$, $k$: $\textrm{a  positive integer}$)
if $k > n$
  $m$ := $n$
  for $i$ := $1$ to $n$
    $c_i$ := $b_i$
else
  $m$ := $n-1$
  for $i$ := $1$ to $k-1$ 
    $c_i$ := $b_i$
  for $i$ := $k$ to $n-1$
    $c_i$ := $b_{i+1}$
return $c_1\cdots c_m$ $\{ \textrm{The return value is a RNA strand made of the } c_i \textrm{ values}\}$
\end{algorithm}
 \vfill
\section*{Alternating quantifiers order rna examples}


{\bf Alternating nested quantifiers}



$$\forall s \in S ~\exists n \in \mathbb{N} ~(~basecount(~(s,\U)~) = n~)$$

In English: For each strand, there is a nonnnegative integer that counts the number of occurrences of $\U$ in that 
strand.\\

$$\exists n \in \mathbb{N} ~\forall s \in S ~(~basecount(~(s,\U)~) = n~)$$

In English: There is a nonnnegative integer that counts the number of occurrences of $\U$ in every 
strand.\\

\vfill

Are these statements true or false?

\newpage

$$\forall s \in S ~\exists b\in B ~(~basecount(~(s,b)~) = 3~)$$

In English: For each RNA strand there is a base that occurs 3 times in this strand.\\

Write the negation and use De Morgan's law to find a 
logically equivalent version where the negation is applied only to the 
$BC$ predicate (not next to a quantifier).

\vspace{60pt}


Is the original statement {\bf True} or {\bf False}?

\vfill
 \vfill
\section*{Predicate rna example}


{\bf Example predicates on $S$, the set of RNA strands (an infinite set)}


$L_{\A}: S \to \{T, F\}$  defined recursively by: 

~~Basis step: $L_{\A}(\A) = T$, $L_{\A}(\C) = L_{\A}(\G) = L_{\A}(\U) = F$

~~Recursive step: If $s \in S$ and $b \in B$, then $L_{\A}(sb) = L_{\A}(s)$.

Example where $L_{\A}$ evaluates to $T$ is \underline{\phantom{$\A\C\G$~\hspace{1in}}}

\vfill

Example where $L_{\A}$ evaluates to $F$ is \underline{\phantom{$\U\A\C\U$\hspace{1in}}}

\vfill


$H: S \to \{T, F\}$ where $H(s) = T$ for all $s$.

Truth set of $H$ is \underline{\phantom{$S$\hspace{1in}}}

\vfill
 \vfill
\section*{Predicates example rnalen basecount}




$L$ with domain $S \times \mathbb{Z}^+$ is defined by, for $s \in S$ and $n \in \mathbb{Z}^+$,
\[
L( ~(s, n)~) = \begin{cases}
T &\qquad\text{if $rnalen(s) = n$}\\
F &\qquad\text{otherwise}\\
\end{cases}
\]
In other words, $L(~(s,n)~)$ means $rnalen(s) = n$


\vfill

$BC$ with domain $S \times B \times \mathbb{N}$ is defined by, 
for $s \in S$ and $b \in B$ and $n \in \mathbb{N}$,
\[
BC(~(s, b, n)~) = \begin{cases}
T &\qquad\text{if $basecount(~(s,b)~) = n$}\\
F &\qquad\text{otherwise}\\
\end{cases}
\]
In other words, $BC(~(s,b,n)~)$ means $basecount(~(s,b)~) = n$


\vfill


Example where $L$ evaluates to $T$: $\underline{\phantom{(\A, 1)\hspace{1in}}}$  Why?

\vfill


Example where $BC$ evaluates to $T$: $\underline{\phantom{(\A, \A1)\hspace{1in}}}$  Why?

\vfill


Example where $L$ evaluates to $F$: $\underline{\phantom{(\A, 2)\hspace{1in}}}$ Why?

\vfill


Example where $BC$ evaluates to $F$: $\underline{\phantom{(\A, \C, 1)\hspace{1in}}}$ Why? 

\vfill

\[\exists t ~BC(t) \qquad \qquad 
\exists (s,b,n) \in S \times B \times \mathbb{N}~ (basecount(~(s,b)~) = n)\]

In English: \phantom{There exists an ordered $3$-tuple 
at which the predicate $BC$ evaluates to $T$.}

\vspace{30pt}

Witness that proves this existential quantification is true:\phantom{$(\G\G, \G, 2)$ or $(\G\A\U\G, \G, 2)$)}


\[\forall t ~BC(t) \qquad \qquad 
\forall(s,b,n) \in S \times B \times \mathbb{N} ~(basecount(~(s,b)~) = n)\]

In English:\phantom{For all ordered $3$-tuples
the predicate $BC$ evaluates to $T$.}

\vspace{30pt}

Counterexample that proves this universal quantification is false: \phantom{$(\G\G, \A, 2)$ or $(\G\A\U\G, \G, 3)$)}
 \vfill
\section*{Alternating quantifiers strategies rna examples}


{\bf Alternating nested quantifiers}

$$\forall s \in S ~\exists b\in B ~(~basecount(~(s,b)~) = 3~)$$

In English: For each RNA strand there is a base that occurs 3 times in this strand.\\

Write the negation and use De Morgan's law to find a 
logically equivalent version where the negation is applied only to the 
$BC$ predicate (not next to a quantifier).

\vspace{60pt}


Is the original statement {\bf True} or {\bf False}?



\vfill



$$\exists s \in S ~\forall b \in B ~\exists n \in \mathbb{N} ~(~basecount(~(s,b)~) = n~)$$

In English: There is an RNA strand so that for each base there is some nonnegative
integer that counts the number of occurrences of that base in this strand.\\

Write the negation and use De Morgan's law to find a 
logically equivalent version where the negation is applied only to the 
$BC$ predicate (not next to a quantifier).

\vspace{60pt}


Is the original statement {\bf True} or {\bf False}?



\vfill
 \vfill
\section*{Alternating quantifiers proofs rna examples}


Which proof strategies could be used to prove each of the following statements?

{\it Hint: first translate the statements to English and identify the main logical structure.}


$\forall b \in B~\exists s \in S~(~basecount(~(s,b)~)~ > 0~)$

\vfill

$\exists s \in S~\forall b \in B~(~basecount(~(s,b)~)~ > 0~)$

\vfill

$\exists s \in S \, (\textit{rnalen(s)} = \textit{basecount}(~(s, \A)~)$

\vfill

$\forall s \in S ~\exists b\in B ~(~basecount(~(s,b)~) > 0~)$

\vfill

$\forall s \in S \, (\textit{rnalen(s)} \geq \textit{basecount}(~(s, \A)~))$

\vfill

$\forall s \in S~(~rnalen(s) > 0~)$

\vfill
 \vfill
\section*{Defining functions more examples}


Let's practice with functions related to some of our applications so far.

Recall: We model the collection of user ratings of the four movies Superman, Wicked, KPop Demon Hunters, A Minecraft Movie as the set
$\{-1,0,1\}^4$ . One function that compares pairs of ratings is
$$d_0: \{-1,0,1\}^4 \times \{-1,0,1\}^4 \to \mathbb{R}$$
given by
\[
d_0 (~(~ (x_1, x_2, x_3, x_4), (y_1, y_2, y_3, y_4) ~) ~) = \sqrt{ (x_1 - y_1)^2 + (x_2 - y_2)^2 + (x_3 -y_3)^2 + (x_4 -y_4)^2}
\]

Notice: any ordered pair of ratings is an okay input to $d_0$.

Notice: there are (at most) 
\[
(3 \cdot 3 \cdot 3 \cdot 3)\cdot (3 \cdot 3 \cdot 3 \cdot 3) = 3^8 = 6561
\]
many pairs of ratings. There are therefore lots and lots of real numbers that are not the output of $d_0$.

\vfill

Recall: RNA is made up of strands of four different bases that encode genomic information
in specific ways.\\
The bases are elements of the set 
$B  = \{\A, \C, \U, \G \}$. The set of RNA strands $S$ is defined (recursively) by:
\[
\begin{array}{ll}
\textrm{Basis Step: } & \A \in S, \C \in S, \U \in S, \G \in S \\
\textrm{Recursive Step: } & \textrm{If } s \in S\textrm{ and }b \in B \textrm{, then }sb \in S
\end{array}
\]
where $sb$ is string concatenation.

\vfill

{\bf Pro-tip}: informal definitions sometime use $\cdots$ to indicate ``continue the pattern''. Often, 
to make this pattern precise we use recursive definitions.
\newpage
\begin{center}
\begin{tabular}{p{0.65in}ccp{2.4in}p{2.4in}}
{\scriptsize {\bf Name}} & {\scriptsize {\bf  Domain}} & {\scriptsize {\bf Codomain}} & {\scriptsize {\bf Rule}} &{\scriptsize {\bf Example}}\\
\hline 
$rnalen$ & $S$ & $\mathbb{Z}^+$ & 
    {\begin{align*}    
    &\textrm{Basis Step:} \\
    &\textrm{If } b \in B\textrm{ then } \textit{rnalen}(b) = 1 \\
    &\textrm{Recursive Step:}\\
    &\textrm{If } s \in S\textrm{ and } b \in B\textrm{, then  }\\
    &\textit{rnalen}(sb) = 1 + \textit{rnalen}(s)
    \end{align*}} & 
    {\begin{align*}
        rnalen(\A\C) &\overset{\text{rec step}}{=} 1 +rnalen(\A) \\ 
        &\overset{\text{basis step}}{=} 1 + 1 = 2
    \end{align*}}\\
\hline
$basecount$ & $S \times B$ & $\mathbb{N}$ & 
{\begin{align*}    
    &\textrm{Basis Step:} \\
    &\textrm{If } b_1 \in B, b_2 \in B \textrm{ then} \\
    &basecount(~(b_1, b_2)~) = \\
    &\begin{cases}
        1 & \textrm{when } b_1 = b_2 \\
        0 & \textrm{when } b_1 \neq b_2 \\
    \end{cases}\\
    &\textrm{Recursive Step:}\\
    &\textrm{If } s \in S, b_1 \in B, b_2 \in B\\
    &basecount(~(sb_1, b_2)~) = \\
    &\begin{cases}
        1 + \textit{basecount}(~(s, b_2)~) & \textrm{when } b_1 = b_2 \\
        \textit{basecount}(~(s, b_2)~) & \textrm{when } b_1 \neq b_2 \\
    \end{cases}
    \end{align*}} & 
    {\begin{align*}
        basecount(~(\A\C\U, \C)~) = 
    \end{align*}}\\
\hline
``$2$ to the power of''& $\mathbb{N}$ & $\mathbb{N}$ & 
{\begin{align*}    
&\textrm{Basis Step:} \\
&2^0= 1 \\
&\textrm{Recursive Step:}\\
&\textrm{If } n \in \mathbb{N}, 2^{n+1} = \phantom{2 \cdot 2^n}
\end{align*}}\\
\hline
``$b$ to the power of $i$''& $\mathbb{Z}^+ \times \mathbb{N}$ & $\mathbb{N}$ & 
{\begin{align*}    
&\textrm{Basis Step:} \\
&b^0 = 1 \\
&\textrm{Recursive Step:}\\
&\textrm{If } i \in \mathbb{N}, b^{i+1} = b \cdot b^i
\end{align*}}
\end{tabular}
\end{center}

\fbox{\parbox{\textwidth}{
    $2^0 = 1$~~\hfill $2^1=2$~~\hfill $2^2=4$~~\hfill $2^3=8$~~
    \hfill $2^4=16$~~\hfill $2^5=32$~~
    \hfill $2^6=64$~~\hfill $2^7=128$~~
    \hfill $2^8=256$~~\hfill $2^9=512$~~
    \hfill $2^{10}=1024$}}
\newpage \vfill
\section*{Defining sets}


{\it To define sets:}

To define a set using {\bf roster method}, explicitly list its elements. That is,
start with $\{$ then list elements of 
the set separated by commas and close with $\}$.

\vfill

To define a set using {\bf set builder definition}, either form 
``The set of all $x$ from the universe $U$ such that $x$ is ..." by writing
\[\{x \in U \mid ...x... \}\]
or form ``the collection of all outputs of some operation when the input ranges over the universe $U$"
by writing
\[\{ ...x... \mid x\in U \}\]

\vfill

We use the symbol $\in$ as ``is an element of'' to indicate membership in a set.\\

\newpage 

{\bf Example sets}: For each of the following, identify whether it's defined using the roster method
or set builder notation and give an example element.

Can we infer the data type of the example element from the notation?

\begin{itemize}
    \item[]$\{ -1, 1\}$
    \vfill
    \item[]$\{0, 0 \}$
    \vfill
    \item[]$\{-1, 0, 1 \}$
    \vfill
    \item[]$\{(x,x,x) \mid x \in \{-1,0,1\} \}$
    \vfill
    \item[]$\{ \}$
    \vfill
    \item[]$\{ x \in \mathbb{Z} \mid x \geq 0 \}$
    \vfill
    \item[]$\{ x \in \mathbb{Z}  \mid x > 0 \}$
    \vfill
    \item[]$\{ \smile, \sun \}$
    \vfill
    \item[]$\{\A,\C,\U,\G\}$
    \vfill
    \item[]$\{\A\U\G, \U\A\G, \U\G\A, \U\A\A \}$
    \vfill
\end{itemize}
 \vfill
\section*{Rna motivation}


RNA is made up of strands of four different bases that encode genomic information
in specific ways.\\
The bases are elements of the set 
$B  = \{\A, \C, \U, \G \}$.
Strands are ordered nonempty finite sequences of bases.

Formally, to define the set of all RNA strands, we need more than roster
method or set builder descriptions. 

 \vfill
\section*{Set recursive examples}


{\bf Definition} The set of nonnegative integers $\mathbb{N}$ is defined (recursively) by: 
\[
\begin{array}{ll}
\textrm{Basis Step: } & \phantom{0 \in \mathbb{N}} \\
\textrm{Recursive Step: } & \phantom{\textrm{If } n \in \mathbb{N} \textrm{, then } n+1 \in \mathbb{N}}
\end{array}
\]

Examples: 

{\bf Definition} The set of all integers $\mathbb{Z}$ is defined (recursively) by: 
\[
\begin{array}{ll}
\textrm{Basis Step: } & \phantom{0 \in \mathbb{Z}} \\
\textrm{Recursive Step: } & \phantom{\textrm{If } x \in \mathbb{Z} \textrm{, then } x+1 \in \mathbb{Z}
\textrm{ and } x-1 \in \mathbb{Z}}
\end{array}
\]

Examples: 

\vfill

{\bf Definition} The set of RNA strands $S$ is defined (recursively) by:
\[
\begin{array}{ll}
\textrm{Basis Step: } & \A \in S, \C \in S, \U \in S, \G \in S \\
\textrm{Recursive Step: } & \textrm{If } s \in S\textrm{ and }b \in B \textrm{, then }sb \in S
\end{array}
\]
where $sb$ is string concatenation.

Examples: 

\vfill

{\bf Definition} The set of bitstrings (strings of 0s and 1s) is defined (recursively) by:
\[
\begin{array}{ll}
\textrm{Basis Step: } & \phantom{\lambda \in X} \\
\textrm{Recursive Step: } & \phantom{\textrm{If } s \in X \textrm{, then } s0 \in X \text{ and } s1 \in X}
\end{array}
\]

{\it Notation:} We call the set of bitstrings $\{0,1\}^*$ and we say 
this is the set of all strings over $\{0,1\}$.

Examples: 

\vfill \vfill
\end{document}