\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*{Algorithm definition}


\fbox{\parbox{\textwidth}{{\bf New!} An algorithm is a finite sequence of precise instructions for solving a problem.
\hfill
}}

Algorithms can be expressed in English or in more formalized descriptions like pseudocode or fully executable programs.


Sometimes, we can define algorithms whose output matches the 
rule for a function we already care about. Consider the (integer) logarithm function
\[
logb  : \{b \in \mathbb{Z} \mid b >1 \}  \times \mathbb{Z}^+ ~~\to~~ \mathbb{N}
\]
defined by 
\[
logb (~ (b,n)~) =  \text{greatest integer } y \text{ so that } b^y  \text{ is less than or equal to } n 
\]



\begin{algorithm}[caption={Calculating integer part of base $b$ logarithm}]
   procedure $logb$($b$,$n$: positive integers with $b > 1$)
   $i$ := $0$
   while $n$ > $b-1$
     $i$ := $i + 1$
     $n$ := $n$ div $b$
   return $i$ $\{ i$ holds the integer part of the base $b$ logarithm of $n\}$
\end{algorithm} 
Trace this algorithm with inputs $b=3$ and $n=17$

\vfill
  \begin{tabular}{l|c|c|c|c}
  & $b$ & $n$ & $i$  & $n > b-1$?\\
  \hline 
  Initial value & ~$3$~ & $17$ & \phantom{$0$} & \phantom{~Yes~}\\
  After 1 iteration  & \phantom{$3$} & \phantom{$5$} & \phantom{$1$} & \phantom{T}\\
  After 2 iterations & \phantom{$3$} & \phantom{$1$} & \phantom{$2$} & \phantom{F}\\
  After 3 iterations &  &  & & \\
  &&&&\\
  \end{tabular}

\vfill

\vfill

Compare: does the output match the rule for the (integer) logarithm function?


\newpage \vfill
\section*{Base expansion algorithms}


{\bf Two algorithms for constructing base $b$ expansion from decimal representation}

{\bf Most significant first}: Start with left-most coefficient of expansion (highest value)

{\it Informally}: Build up to the value we need to represent in ``greedy'' approach, using 
units determined by base.

\vfill




\begin{algorithm}[caption={Calculating base $b$ expansion, from left}]
procedure $\textit{basebmost}$($n, b$: positive integers with $b > 1$)
$v$ := $n$
$k$ := $1 + $ output of $logb$ algorithm with inputs $b$ and $n$
for $i$ := $1$ to $k$
  $a_{k-i}$ := $0$
  while $v \geq b^{k-i}$
    $a_{k-i}$ := $a_{k-i} + 1$
    $v$ := $v -  b^{k-i}$
return $(a_{k-1}, \ldots, a_0) \{(a_{k-1} \ldots a_0)_b~\textrm{ is the base } b \textrm{ expansion of } n \}$
\end{algorithm}
 


\vfill
\vfill

\newpage
{\bf Least significant first}: Start with right-most coefficient of expansion (lowest value)

Idea: {\tiny(when $k > 1$)} 
    \begin{align*}
      n &= a_{k-1} b^{k-1} + \cdots + a_1 b + a_0 \\
        &= b ( a_{k-1} b^{k-2} + \cdots + a_1) + a_0\end{align*}
    so $a_0 = n \textbf{ mod } b$ and $a_{k-1} b^{k-2} + \cdots + a_1 = n \textbf{ div } b$.





\begin{algorithm}[caption={Calculating base $b$ expansion, from left}]
procedure $\textit{basebmost}$($n, b$: positive integers with $b > 1$)
$v$ := $n$
$k$ := $1 + $ output of $logb$ algorithm with inputs $b$ and $n$
for $i$ := $1$ to $k$
  $a_{k-i}$ := $0$
  while $v \geq b^{k-i}$
    $a_{k-i}$ := $a_{k-i} + 1$
    $v$ := $v -  b^{k-i}$
return $(a_{k-1}, \ldots, a_0) \{(a_{k-1} \ldots a_0)_b~\textrm{ is the base } b \textrm{ expansion of } n \}$
\end{algorithm}
 



\vfill
\vfill
\newpage \vfill
\section*{Base conversion algorithm}




Practice: write an algorithm for converting from base $b_1$ expansion to base $b_2$ expansion:

\phantom{
Earlier, we saw (two different) algorithms for, given 
a target base $b$, converting from decimal to base $b$ expansions. 
We will use either one of these as a subroutine in this algorithm.\\
Given a base expansion in base $b_1$:\\
Step 1: Use the definition of base expansion to calculate the value of
    this number (in decimal).\\
Step 2: Use the Least Significant First algorithm to write this value in 
    base $b_2$ and output the result.
}
\vspace{200pt} \vfill
\end{document}