\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*{Sets numbers subsets}


We have the following subset relationships between sets of numbers:

\[
    \mathbb{Z}^{+} \subsetneq \mathbb{N} \subsetneq \mathbb{Z} \subsetneq \mathbb{Q} \subsetneq \mathbb{R}
\]


Which of the proper subset inclusions above can you prove?

\vspace{50pt} \vfill
\section*{Half adder circuit}


{\bf Fixed-width addition}: adding one bit at time, using the usual column-by-column and carry arithmetic, and dropping the carry from the leftmost column so the result is the same width as the summands.  In many cases, this gives representation of the correct value for the sum when we interpret the summands
in fixed-width binary or in 2s complement.

For single column:

\begin{multicols}{2}
\begin{center}
\begin{tabular}{cc|cc}
\multicolumn{2}{c|}{Input}  & \multicolumn{2}{|c}{Output}  \\
$x_0$ & $y_0$ & $c_0$ & $s_0$  \\
\hline
$1$ & $1$ & \phantom{$1$} & \phantom{$0$} \\
$1$ & $0$ & \phantom{$0$} & \phantom{$1$}\\
$0$ & $1$ & \phantom{$0$} & \phantom{$1$}\\
$0$ & $0$ & \phantom{$0$} & \phantom{$0$}\\
\end{tabular}
\end{center}
\columnbreak
\begin{center}
\includegraphics[width=1.5in]{../../resources/images/half-adder.png}
\end{center}
\end{multicols} \vfill
\section*{Two bit adder circuit}


Draw a logic circuit that implements binary addition of 
two numbers that are each represented in fixed-width binary:
\begin{itemize}
\item Inputs  $x_0, y_0, x_1, y_1$ represent $(x_1  x_0)_{2,2}$ and $(y_1 y_0)_{2,2}$
\item Outputs  $z_0, z_1, z_2$ represent $(z_2  z_1 z_0)_{2,3} = (x_1  x_0)_{2,2} + (y_1 y_0)_{2,2}$ (may require up to width  $3$)
\end{itemize}

{\it First approach}: half-adder for each column, then combine carry from right column with sum of left column


Write expressions for the circuit output values in terms of input values:

$z_0 = \underline{\phantom{x_0 \oplus y_0\hspace{3in}}}$

$z_1 = \underline{\phantom{(x_1 \oplus y_1) \oplus c_0}\hspace{2.5in}}$ \phantom{where $c_0 = x_0 \land y_0$}

$z_2 = \underline{\phantom{(c_0 \land (x_1 \oplus y_1)) \oplus c_1}\hspace{2in}}$ \phantom{where $c_1 = x_1 \land y_1$}\\

\includegraphics[width=1.7in]{../../resources/images/width-2-adder.png}


\vfill

{\it There are other approaches, for example}: for middle column, first add carry from right column to $x_1$, then add result to $y_1$

\begin{comment}
Write expressions for the circuit output values in terms of input values:

$z_0 = \underline{\phantom{x_0 \oplus y_0}\hspace{3in}}$

$z_1 = \underline{ \phantom{(c_0 \oplus x_1) \oplus y_1}\hspace{2.4in}}$ \phantom{where $c_0 = x_0 \land y_0$}

$z_2 = \underline{\phantom{(c_0 \land x_1) \oplus ((c_0 \oplus x_1)\land y_1)}\hspace{1.5in}}$

\vfill

{\it Extra example} Describe how to generalize this addition circuit for larger width inputs.
\end{comment}
 \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*{Division algorithm}


{\bf Integer division and remainders} (aka The Division Algorithm) Let $n$ be an integer 
and $d$ a positive integer. There are unique integers $q$ and $r$, with $0 \leq r < d$, such that 
$n = dq + r$. In this case, $d$ is called the divisor, $n$ is called the dividend, 
$q$ is called the quotient, 
and $r$ is called the remainder. 

Because these numbers are guaranteed to exist, the following functions are well-defined: 

$\textbf{ div } : \mathbb{Z} \times \mathbb{Z}^+ \to \mathbb{Z}$ given by $\textbf{ div } ( ~(n,d)~)$ 
is the quotient when $n$ is the dividend and $d$ is the divisor.

$\textbf{ mod } : \mathbb{Z} \times \mathbb{Z}^+ \to \mathbb{Z}$ given by $\textbf{ mod } ( ~(n,d)~)$ 
is the remainder when $n$ is the dividend and $d$ is the divisor.

Because these functions are so important, we sometimes use the notation
$n \textbf{ div } d = \textbf{ div } ( ~(n,d)~)$ and $n \textbf{ mod } d = \textbf{ mod } (~(n,d)~)$.


{\bf Pro-tip}: The functions $\textbf{ div }$ and $\textbf{ mod }$ are similar to (but not exactly the same as) 
the operators $/$ and $\%$ in Java and python.

\vfill

{\it Example calculations}:

$20 \textbf{ div } 4$

\vspace{20pt}

$20 \textbf{ mod } 4$

\vspace{20pt}

$20 \textbf{ div } 3$

\vspace{20pt}

$20 \textbf{ mod } 3$

\vspace{20pt}

$-20 \textbf{ div } 3$

\vspace{20pt}

$-20 \textbf{ mod } 3$

\vfill \vfill
\section*{Why represent numbers}


Modeling uses data-types that are encoded in a computer.
The details of the encoding impact the efficiency of algorithms
we use to understand the systems we are modeling and the 
impacts of these algorithms on the people using the systems.
Case study: how to encode numbers?

\phantom{
Positional representation with familiar (decimal) number encodings
\vspace{30pt}
}
\vfill \vfill
\section*{Base expansion definition}


{\bf Definition} For $b$ an integer greater than $1$ and $n$ a positive integer, 
the {\bf base $b$ expansion of $n$}  is
\[
(a_{k-1} \cdots a_1 a_0)_b
\]
where $k$ is a positive integer, $a_0, a_1, \ldots, a_{k-1}$ 
are (symbols for) nonnegative integers less than $b$, $a_{k-1} \neq  0$, and
\[
n =  \sum_{i=0}^{k-1} a_{i} b^{i}
\]

Notice: {\it The base $b$ expansion of a positive integer $n$ is a string over the alphabet 
$\{x \in \mathbb{N} \st x < b\}$
whose leftmost character is nonzero.}

\begin{center}
\begin{tabular}{|c|c|}
\hline
Base $b$ & Collection of possible coefficients in base $b$ expansion of  a positive integer \\
\hline
& \\
Binary ($b=2$) & $\{0,1\}$ \\
\hline
& \\
Ternary ($b=3$) & $\{0,1, 2\}$ \\
\hline
& \\
Octal ($b=8$) & $\{0,1, 2, 3, 4, 5, 6, 7\}$\\
\hline
& \\
Decimal ($b=10$) & $\{0,1, 2, 3, 4, 5, 6, 7, 8, 9\}$\\
\hline
& \\
Hexadecimal ($b=16$) &  $\{0,1, 2, 3, 4, 5, 6, 7, 8, 9, A, B, C, D, E, F\}$\\
& letter coefficient symbols represent numerical values $(A)_{16} = (10)_{10}$\\
&$(B)_{16} = (11)_{10} ~~(C)_{16} = (12)_{10} ~~
 (D)_{16} = (13)_{10} ~~ (E)_{16} = (14)_{10} ~~ (F)_{16} = (15)_{10} $\\
\hline
\end{tabular}
\end{center}

 \vfill
\section*{Base expansion examples}




{\it Examples}:

$(1401)_{2}$

\vfill

$(1401)_{10}$

\vfill
\vfill
\vfill


$(1401)_{16}$

\vfill
\vfill
\vfill
 \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 expansion review}


Find and fix any and all mistakes with the following:
\begin{itemize}
\item[(a)] $(1)_2 = (1)_8$
\item[(b)] $(142)_{10} = (142)_{16}$
\item[(c)] $(20)_{10} = (10100)_2$
\item[(d)] $(35)_8 = (1D)_{16}$
\end{itemize} \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
\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
\section*{Base expansion final review}


Convert $(2A)_{16}$ to 
\begin{itemize}
\item binary (base \underline{\phantom{~~~2~~}})

\vspace{50pt}

\item decimal (base \underline{\phantom{~~10~~}})

\vspace{50pt}

\item octal (base \underline{\phantom{~~~8~~}})

\vspace{50pt}

\item ternary (base \underline{\phantom{~~~3~~}})

\vspace{50pt}

\end{itemize} \vfill
\end{document}