\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*{Let's get started}

We want you to be successful. 

We will work together to build an 
environment in CSE 20 that supports your learning
in a way that respects your
perspectives, experiences, and identities.
Our goal is for you to  engage
with interesting and challenging concepts and 
feel comfortable exploring, asking questions, and thriving.

If you or someone you know is suffering from food and/or housing insecurities 
there are UCSD resources here to help:

Basic Needs Office: \href{https://basicneeds.ucsd.edu/}{https://basicneeds.ucsd.edu/}

Triton Food Pantry (in the old Student Center)
is free and anonymous, and includes produce: 

\href{https://www.facebook.com/tritonfoodpantry/}{https://www.facebook.com/tritonfoodpantry/}

Financial aid resources, the possibility of emergency grant funding, and off-campus housing referral 
resources are available: see your College Dean of Student Affairs.

If you find yourself in an uncomfortable situation, ask for help. 
We are committed to upholding University policies regarding nondiscrimination, sexual violence and sexual harassment.
Here are some campus contacts that could provide this help: 
Counseling and Psychological Services (CAPS) at 858 534-3755 or \href{http://caps.ucsd.edu}{http://caps.ucsd.edu}; 
OPHD at 858 534-8298 or ophd@ucsd.edu , \href{http://ophd.ucsd.edu}{http://ophd.ucsd.edu};
CARE at Sexual Assault Resource Center at 858 534-5793 or sarc@ucsd.edu , \href{http://care.ucsd.edu}{http://care.ucsd.edu}.


Please reach out (minnes@ucsd.edu) if you need support with extenuating circumstances affecting CSE 20.

\vfill

\newpage
\section*{Welcome to CSE 20: Discrete Math for CS in Winter 2026!}
Class website: \href{https://canvas.ucsd.edu//}{https://canvas.ucsd.edu/}
Instructor: Prof. Mia Minnes {\tiny{"Minnes" rhymes with Guinness}}, minnes@ucsd.edu, 
\href{http://cseweb.ucsd.edu/~minnes}{http://cseweb.ucsd.edu/~minnes}.
CSE 20 team: One instructor + two TAs and three tutors + all of you

Fill in contact info for students around you, if you'd like:

\vfill
\vfill

On a typical week in CSE 20: {\bf MWF} Lectures (sometimes with pre-class reading), {\bf M} Discussion + 
review quiz due, then (every second) {\bf Th} Homework due.
Office hours (hosted by instructors and TAs and tutors) where you can come to talk 
about course concepts and ask for help as you work through sample problems 
and Q+A on Piazza available throughout the week. CSE 20 has two in-term tests
and one final exam this quarter.
What you can find on the class website on \href{https://canvas.ucsd.edu/}{Canvas (https://canvas.ucsd.edu/)}:

\begin{multicols}{2}
\begin{enumerate}
\item Syllabus
\item Notes for class + annotations
\item PrairieLearn
\item Assignments (PDF, tex, solutions)
\item Gradescope
\item Piazza
\item Dates
\end{enumerate}
\end{multicols}

\vfill
There are lots of great reasons to have a laptop, tablet, or phone open during class. You might be taking notes, 
getting a photo of an important moment on the board, trying out a construction that we're developing together, working 
on the review quiz, and so on. 
The main issue with screens and technology in the classroom isn't that they might 
distract you, 
it's the distraction of other students. We ask that if you would like to use
a device in class and may have 
have unrelated content open, please sit in one of the back two rows of the 
room so that it's not adversely affecting other students.


\vfill

{\bf Pro-tip}: you can use MATH109 to replace CSE20 for prerequisites and other requirements.

\vfill

\section*{Themes and applications for CSE 20}
\begin{itemize}
\item {\bf Technical skepticism}: Know, select and apply appropriate computing knowledge and problem-solving techniques. 
Reason about computation and systems. 
Use mathematical techniques to solve problems. 
Determine appropriate conceptual tools to apply to new situations. 
Know when tools do not apply and try different approaches. 
Critically analyze and evaluate candidate solutions.
\item {\bf Multiple representations}: Understand, guide, shape impact of computing on society/the world. 
Connect the role of Theory CS classes to other applications (in undergraduate CS curriculum and beyond). 
Model problems using appropriate mathematical concepts.
Clearly and unambiguously communicate computational ideas using appropriate formalism. 
Translate across levels of abstraction.
\end{itemize}

{\bf Applications}: Numbers (how to represent them and use them in Computer Science), 
Recommendation systems and their roots in machine learning (with applications like Netflix),
``Under the hood" of computers (circuits, pixel color representation, data structures),
Codes and information (secret message sharing and error correction),
Bioinformatics algorithms and genomics (DNA and RNA).

\newpage

\subsection*{Week 1 at a glance}

\subsubsection*{We will be learning and practicing to:}
\begin{itemize}
\item Model systems with tools from discrete mathematics and reason about implications of modelling choices. Explore applications in CS through multiple perspectives, including software, hardware, and theory.
\begin{itemize}

   \item Selecting and representing appropriate data types and using notation conventions to clearly communicate choices

\end{itemize}

\item Translate between different representations to illustrate a concept.

\begin{itemize}
   \item Translating between symbolic and English versions of statements using precise mathematical language
\end{itemize}


\item Use precise notation to encode meaning and present arguments concisely and clearly
\begin{itemize}
    \item Defining important sets of numbers, e.g. set of integers, set of rational numbers
    \item Precisely describing a set using appropriate notation e.g. roster method, set builder notation, and recursive definitions
    \item Defining functions using multiple representations
\end{itemize}

\item Know, select and apply appropriate computing knowledge and problem-solving techniques. Reason about computation and systems. Use mathematical techniques to solve problems. Determine appropriate conceptual tools to apply to new situations. Know when tools do not apply and try different approaches. Critically analyze and evaluate candidate solutions.
\begin{itemize}
    \item Using a recursive definition to evaluate a function or determine membership in a set
\end{itemize}

\end{itemize}

\subsubsection*{TODO:}
\begin{list}
   {\itemsep2pt}
   \item \#FinAid Assignment on Canvas \url{https://canvas.ucsd.edu/courses/71479/quizzes/235977} (complete as soon as possible) 
   \item Review quiz based on class material (due Monday 01/12/2026)
   \item Homework assignment 1 (due Thursday 01/15/2026)
\end{list}

\newpage

\section*{Week 1 Monday: Modeling applications}


What data should we encode about each Netflix account holder to help us make effective recommendations?

\vfill
\vfill

In machine learning, clustering can be used to group similar data for prediction and recommendation.  For example,
each Netflix user's viewing history can be represented as a $n$-tuple indicating their preferences about
movies in the database, where $n$ is the number of movies in the database.  People with similar tastes in movies can then be clustered to provide recommendations
of movies for one another.  Mathematically, clustering is based on a notion of distance between pairs of $n$-tuples.
 
\vfill
\subsection*{Data Types: sets, $n$-tuples, and strings}


\begin{center}
    \begin{tabular}{|p{4.6in}p{2.6in}|}
    \hline
    {\bf  Term} & {\bf Examples}:\\
    &  (add additional examples from class)\\
    \hline 
    {\bf set} \newline
    unordered collection of elements & $7 \in \{43, 7, 9 \}$ \qquad $2 \notin \{43, 7, 9 \}$ \\
    {\it repetition doesn't matter} & \\
    {\it Equal sets agree on membership of all elements}& \\
    \hline
    {\bf $n$-tuple} \newline
    ordered sequence of elements with $n$ ``slots" ($n >0$) & \\
    {\it repetition matters, fixed length} &\\
    {\it Equal $n$-tuples have corresponding components equal}& \\
    \hline
    {\bf string} \newline
    ordered finite sequence of elements each from specified
    set (called the alphabet over which the string is defined)& \\
    {\it repetition matters, arbitrary finite length} &\\
    {\it Equal strings have same length and corresponding characters equal}\\
    \hline
    \end{tabular}
\end{center}

{\it Special cases}: 

When $n=2$, the 2-tuple is called an {\bf ordered pair}.

A string of length $0$ is called the {\bf empty string} and is denoted $\lambda$.

A set with no elements is called the {\bf empty set} and is denoted $\{\}$ or $\emptyset$. \newpage


In the table  below,  each row represents a user's ratings of movies: 
\cmark~(check) indicates the person liked the movie, \xmark~(x)
that they didn't, and $\bullet$ (dot) that they didn't rate it one way or 
another (neutral rating or didn't watch). Can encode
these ratings numerically with $1$ for \cmark~(check), $-1$ for \xmark~(x), 
and $0$ for $\bullet$ (dot).

\vfill

\begin{center}
\begin{tabular}{c|cccc||c}
Person & Superman & Wicked & KPop Demon Hunters & A Minecraft Movie & Ratings written as a $4$-tuple\\
\hline
$P_1$     & \xmark & $\bullet$ & \cmark & \phantom{$(-1, 0, 1, 1)$} \\
&&&& \\
$P_2$     & \cmark & \cmark & \xmark & \phantom{$(1, 1, -1, 1)$} \\
&&&& \\
$P_3$     & \cmark & \cmark & \cmark & \phantom{$(1, 1, 1, 1)$} \\
&&&& \\
$P_4$     & $\bullet$ & \xmark & \cmark &  \\
&&&& \\
$You$     &  &  &  &  \\
&&&& \\
\end{tabular}
\end{center} \vfill
{\bf Conclusion}: Modeling involves choosing data types to represent and organize data

\newpage
\section*{Week 1 Wednesday: Defining sets}
\subsection*{Notation and prerequisites}


\begin{center}
\begin{tabular}{|llp{9.8cm}|}
\hline
{\bf Term} & {\bf Notation Example(s)} & {\bf We say in English \ldots } \\
\hline
all reals & $\mathbb{R}$ & The (set of all) real numbers (numbers on the number line)\\
all integers & $\mathbb{Z}$ & The (set of all) integers (whole numbers including negatives, zero, and positives) \\
all positive integers & $\mathbb{Z}^+$ & The (set of all) strictly positive integers \\
all natural numbers & $\mathbb{N}$ & The (set of all) natural numbers (nonnegative integers). {\it We use the convention that $0$ is a natural number.} \\


\hline
\end{tabular}
\end{center} 

{\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}
 \newpage


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. 

 

{\bf New! Recursive Definitions of Sets}: The set $S$ (pick a name) is defined by:
\[
\begin{array}{ll}
\textrm{Basis Step: } & \textrm{Specify finitely many elements of } S\\
\textrm{Recursive Step: } & \textrm{Give rule(s) for creating a new element of } S \textrm{ from known values existing in } S, \\
& \textrm{and potentially other values}. \\
\end{array}
\]
The set $S$ then consists of all and only elements that are put in $S$ by finitely many (a nonnegative integer number) of
applications of the recursive step after the basis step. 

{\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 

\fbox{\parbox{\textwidth}{To define a set we can use the roster method, set builder notation, a recursive definition, 
and also we can apply a set operation to other sets. \\

{\bf New! Cartesian product of sets} and {\bf set-wise concatenation of sets of strings}\\


{\bf Definition}: Let $X$ and $Y$ be sets.  The {\bf Cartesian product} of $X$ and $Y$, denoted
$X \times Y$, is the set of all ordered pairs $(x,y)$ where $x \in X$ and $y \in Y$
\[
X \times Y = \{ (x,y) \mid x \in X \text{ and } y \in Y \}
\]

Conventions: (1) Cartesian products can be chained together to result in sets of $n$-tuples and 
(2) When we form the Cartesian product of a set with itself $X \times X$ we can denote that set as 
$X^2$, or $X^n$ for the Cartesian product of a set with itself $n$ times for a positive integer $n$.\\

{\bf Definition}: Let $X$ and $Y$ be sets of strings over the same alphabet. The {\bf set-wise concatenation} 
of $X$ and $Y$, denoted $X \circ Y$, is the set of all results of string concatenation $xy$ where $x \in X$ 
and $y \in Y$
\[
X \circ Y = \{ xy \mid x \in X \text{ and } y \in Y \}
\]
}}

{\bf Pro-tip}: the meaning of writing one element next to another like $xy$ depends on the data-types of $x$ and 
$y$. When $x$ and $y$ are strings, the convention is that $xy$ is the result of string concatenation. 
When $x$ and $y$ are numbers, the convention is that $xy$ is the result of multiplication. This is 
(one of the many reasons) why is it very important to declare the data-type of variables before we use them.

{\it Fill in the missing entries in the table}:

\begin{center}
\begin{tabular}{cc}
{\bf  Set} & {\bf Example elements in this set and their data type}:\\
\hline 
& \\
$B$ &\A \qquad \C \qquad \G \qquad \U \\
& \\
\hline
& \\
\phantom{$B \times B$} & $(\A, \C)$ \qquad $(\U, \U)$\\
& \\
\hline
& \\
$B \times \{-1,0,1\}$ & \\
& \\
\hline
& \\
$\{-1,0,1\} \times B$ & \\
& \\
\hline
& \\
\phantom{$\{-1,0,1\} \times \{-1,0,1\}  \times \{-1,0,1\} $} & \qquad $(0,0,0)$ \\
& \\
\hline
& \\
$ \{\A, \C, \G, \U \} \circ  \{\A, \C, \G, \U \}$& \\
& \\
\hline
& \\
\phantom{$\{G\} \circ \{G\} \circ \{G\}$} & \qquad $\G\G\G\G$ \\
& \\
\hline

\end{tabular}
\end{center}

\vfill 
\section*{Week 1 Friday: Defining functions}


\begin{center}
\begin{tabular}{|p{1.2in}p{2.8in}p{3in}|}
\hline
{\bf Term} & {\bf Notation Example(s)} & {\bf We say in English \ldots } \\
\hline
sequence & $x_1, \ldots, x_n$ & A sequence $x_1$ to $x_n$ \\
summation & $\sum_{i=1}^n x_i$ or $\displaystyle{\sum_{i=1}^n x_i}$ & The sum of the terms of the sequence $x_1$ to $x_n$ \\
&&\\
&&\\
piecewise rule definition & $f(x) = \begin{cases} \text{rule 1 for } x & \text{when~COND 1} \\ \text{rule 2 for } x & \text{when COND 2}\end{cases}$ &
Define $f$ of $x$ to be the result of applying rule 1 to $x$ when condition COND 1 is true and the result of 
applying rule 2 to $x$ when condition COND 2 is true. This can be generalized to having more than two conditions
(or cases).\\
&&\\
function application & $f(7)$ & $f$ of $7$ {\bf or} $f$ applied to $7$ {\bf or} the image of $7$ under $f$\\
                     & $f(z)$ & $f$ of $z$ {\bf or} $f$ applied to $z$ {\bf or} the image of $z$ under $f$\\
                     & $f(g(z))$ & $f$ of $g$ of $z$ {\bf or} $f$ applied to the result of $g$ applied to $z$ \\
&&\\
absolute value & $\lvert -3 \rvert$ & The absolute value of $-3$ \\
square root & $\sqrt{9}$ & The non-negative square root of $9$ \\


\hline
\end{tabular}
\end{center}

{\bf Pro-tip}: the meaning of two vertical lines $| ~~~ |$ depends on the data-types of what's between the lines.
For example, when placed around a number, the two vertical lines represent absolute value.
We've seen a single vertial line $|$ used as part of set builder definitions to represent ``such that''.
Again, this is 
(one of the many reasons) why is it very important to declare the data-type of variables before we use them.
 

\fbox{\parbox{\textwidth}{{\bf New! Defining functions} A function is defined by its (1) domain, 
(2) codomain, and (3) rule assigning each 
element in the domain exactly one element in the codomain.\\

The domain and codomain are nonempty sets.

The rule can be depicted as a table, formula, piecewise definition, or English description.

The notation is 
\begin{center}
    ``Let the function FUNCTION-NAME: DOMAIN $\to$ CODOMAIN be given by \\
FUNCTION-NAME(x) = \ldots for every $x \in DOMAIN$''.
\end{center}

or 
\begin{center}
    ``Consider the function FUNCTION-NAME: DOMAIN $\to$ CODOMAIN defined as  \\
FUNCTION-NAME(x) = \ldots for every $x \in DOMAIN$''.
\end{center}
}}

\vfill
\newpage

Example: The absolute value function 

{\bf Domain}

{\bf Codomain}

{\bf Rule}

\vfill 
 

Recall our representation of Netflix users' ratings of movies as $n$-tuples, where
$n$ is the number of movies in the database. 
Each component of the $n$-tuple is $-1$ (didn't like the movie), $0$ 
(neutral rating or didn't watch the movie), or $1$ (liked the movie).

Consider the ratings $P_1 = (-1, 0, 1, 0)$, $P_2 = (1, 1, -1, 0)$, $P_3 = (1, 1, 1, 0)$,
$P_4 = (0,-1,1, 0)$


Which of $P_1$, $P_2$, $P_3$ has movie preferences most similar to $P_4$?

One approach to answer this question: use {\bf functions} to quantify difference among user preferences.

For example, consider the function 
$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}
\]


\vfill
\vfill

\begin{comment}
    

{\it Extra example:} A new movie is released, and $P_1$ and $P_2$ watch it before $P_3$, and give it
ratings; $P_1$ gives \cmark~and $P_2$ gives \xmark.
Should this movie be recommended to $P_3$? Why or why not?

{\it Extra example:} Define a new function that could be used to compare the $4$-tuples of ratings encoding
movie preferences now that there are four movies in the database.

\vfill
\end{comment}
\newpage 

When the domain of a function is a {\it recursively defined set}, the rule assigning 
images to domain elements (outputs) can also be defined recursively.

Recall: 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.

{\bf Definition} (Of a function, recursively) A function \textit{rnalen} that computes the length of RNA strands in $S$ is defined by:
\[
\begin{array}{llll}
& & \textit{rnalen} : S & \to \mathbb{Z}^+ \\
\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{array}
\]

The domain of \textit{rnalen} is \phantom{$S$}\\

The codomain of \textit{rnalen} is \phantom{$\mathbb{Z}^+$}\\

Example function application:
\[
rnalen(\A\C\U) = \phantom{1+ rnalen(\A\C) = 1 + (1 + rnalen(\A) ) = 1 + ( 1 + 1) = 3}
\]

\vfill

{\it Example}: A function \textit{basecount} that computes the number of a given base 
$b$ appearing in a RNA strand $s$ is defined recursively:
    
\[
\begin{array}{llll}
& & \textit{basecount} : S \times B & \to \mathbb{N} \\
\textrm{Basis Step:} &  \textrm{If } b_1 \in B, b_2 \in B & \textit{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 &\textit{basecount}(~(s b_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{array}
\]

\begin{comment}
$basecount(~(\A\C\U,\A)~) = basecount( ~(\A\C, \A)~) = basecount(~(\A, \A)~) = 1$\\


$basecount(~(\A\C\U,\G)~) = basecount( ~(\A\C, \G)~) = basecount(~(\A, \G)~) = 0$\\


\vfill
{\it Extra example}: The function which outputs $2^n$ when given a nonnegative integer $n$ can be defined recursively, 
because its domain is the set of nonnegative integers.

\vfill
\end{comment}
 
\begin{comment}
\newpage
\subsection*{Review Quiz}

The review quiz is available on PrairieLearn at \url{https://us.prairielearn.com/pl/} and covers 
\begin{itemize}
\item Modeling
\item Sets and functions
\end{itemize}

\begin{enumerate}
\item Modeling
\begin{enumerate}
    \item {

Using the example movie database from class with the four movies Superman, Wicked, KPop Demon Hunters, and A Minecraft Movie which of the following is a $4$-tuple that represents the ratings of a user who liked Superman? (Select all and only that apply.)

\begin{enumerate}
\item $1$
\item $(1,0,0)$
\item $[1,1,1,0]$
\item $\{-1, 0, 0, 1\}$
\item $(1,-1,0,1)$
\item $(0,1,1, 1)$
\item $(1,1,1,1)$
\end{enumerate} }
    \item {

Using the example movie database from class with the four movies Superman, Wicked, KPop Demon Hunters, and A Minecraft Movie how many distinct (different) $4$-tuples of ratings are there? 
 }
    \item {

Colors can be described as amounts of red, green, and blue mixed together
\footnote{This RGB representation is common in web applications.  Many online tools are available to play around with mixing these colors,  e.g. \url{https://www.w3schools.com/colors/colors_rgb.asp}. }
Mathematically, a color can be represented as a $3$-tuple $(r, g, b)$ where $r$ represents the red component, $g$ the green component, $b$ the blue component and where each of $r$, $g$, $b$ must be a value from this collection of numbers:
\begin{quote}
$\{$0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 80, 81, 82, 83, 84, 85, 86, 87, 88, 89, 90, 91, 92, 93, 94, 95, 96, 97, 98, 99, 100, 101, 102, 103, 104, 105, 106, 107, 108, 109, 110, 111, 112, 113, 114, 115, 116, 117, 118, 119, 120, 121, 122, 123, 124, 125, 126, 127, 128, 129, 130, 131, 132, 133, 134, 135, 136, 137, 138, 139, 140, 141, 142, 143, 144, 145, 146, 147, 148, 149, 150, 151, 152, 153, 154, 155, 156, 157, 158, 159, 160, 161, 162, 163, 164, 165, 166, 167, 168, 169, 170, 171, 172, 173, 174, 175, 176, 177, 178, 179, 180, 181, 182, 183, 184, 185, 186, 187, 188, 189, 190, 191, 192, 193, 194, 195, 196, 197, 198, 199, 200, 201, 202, 203, 204, 205, 206, 207, 208, 209, 210, 211, 212, 213, 214, 215, 216, 217, 218, 219, 220, 221, 222, 223, 224, 225, 226, 227, 228, 229, 230, 231, 232, 233, 234, 235, 236, 237, 238, 239, 240, 241, 242, 243, 244, 245, 246, 247, 248, 249, 250, 251, 252, 253, 254, 255$\}$
\end{quote}

Select all and only the true statements below.

\begin{enumerate}
\item $(1, 3, 4)$ fits the definition of a color above.
\item $(1, 100, 200, 0)$ fits the definition of a color above.
\item $(510, 255)$ fits the definition of a color above.
\item There is a color $(r_1, g_1, b_1)$ where $r_1 + g_1 + b_1$ is greater than $765$.
\item There is a color $(r_2, g_2, b_2)$ where $r_2 + g_2 + b_2$ is equal to $1$.
\item Another way to write the collection of allowed values for red, green, and blue components is $$\{x \in \mathbb{N}\mid 0 \leq x \leq 255 \}$$.
\item Another way to write the collection of allowed values for red, green, and blue components is $$\{n \in \mathbb{Z}\mid 0 \leq n \leq 255 \}$$.
\item Another way to write the collection of allowed values for red, green, and blue components is $$\{y \in \mathbb{Z}\mid -1 < y \leq 255 \}$$.
\end{enumerate}
\vfill }
    \item {


In the definition of colors as amounts of red, green, and blue mixed together, why are $3$-tuples a convenient data structure to use rather than sets or strings?

(Select all and only relevant choices)

\begin{enumerate}
\item Ordering matters in $n$-tuples, so we can use the different components of the $3$-tuple to represent the amounts of specific colors. 
\item There are many possible values for each color amount and we don't have individual characters for each value so a string could get unwieldy.
\item It's possible to have the same value of two or all of the colors, and repetition matters in $n$-tuples.
\end{enumerate}
\vfill }
\end{enumerate}
\item Sets and functions
\begin{enumerate}
    \item {

Sets are unordered collections. In class, we saw some examples of sets
and also how to define sets using roster method and set builder 
notation.
\begin{enumerate}
    \item Select all and only the sets below that have $0$ as an element.
        \begin{enumerate}
            \item $\{-1,1\}$
            \item $\{0,0\}$
            \item $\{-1,0,1\}$
            \item $\mathbb{Z}$
            \item $\mathbb{Z}^+$
            \item $\mathbb{N}$
        \end{enumerate}
    \item Select all and only the sets below that have the ordered pair $(2, 0)$ as an element.
        \begin{enumerate}
            \item $\{ x \mid x \in \mathbb{N} \}$
            \item $\{ (x,x) \mid x \in \mathbb{N} \}$
            \item $\{ (x, x-2) \mid x \in \mathbb{N} \}$
            \item $\{ (x,y) \mid x \in \mathbb{Z}^+, y \in \mathbb{Z} \}$
        \end{enumerate}
\end{enumerate} }
    \item {

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, \G, \U \}$. 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}
\]

A function \textit{rnalen} that computes the length of RNA strands in $S$ is defined by:
\[
\begin{array}{llll}
& & \textit{rnalen} : S & \to \mathbb{Z}^+ \\
\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{array}
\]

\begin{enumerate}
\item How many distinct elements are in the set described using set builder notation as 
\[
\{ x \in S \mid rnalen(x) = 1\} \qquad ?
\]

\item How many distinct elements are in the set described using set builder notation as 
\[
\{ x \in S \mid rnalen(x) = 2\} \qquad ?
\]

\item How many distinct elements are in the set described using set builder notation as 
\[
\{ rnalen(x) \mid x \in S \text{ and } rnalen(x) = 2\} \qquad ?
\]


\item How many distinct elements are in the set obtained as the result
of the set-wise concatenation $\{ \A\A, \A\C \} \circ \{\U, \A\A \}$?

\item How many distinct elements are in the set obtained as the result
of the Cartesian product $\{ \A\A, \A\C \} \times \{\U, \A\A \}$?

\item {\bf True} or {\bf False}: There is an example of an RNA strand that is both in the set obtained as the result
of the set-wise concatenation $\{ \A\A, \A\C \} \circ \{\U, \A\A \}$ and in the set obtained as the result of the 
Cartesian product $\{ \A\A, \A\C \} \times \{\U\A, \A\A \}$

\end{enumerate}
{\it Bonus - not for credit: Describe each of the sets above using roster method.}
 }
    \item {

Recall the function which takes an ordered pair of ratings $4$-tuples and returns a measure of the difference between them
$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}
\]

Consider the function application 
\[
  d_0 (~( ~(-1,1,1, 0), (1, 0, -1, 0)~) ~)
\]
\begin{enumerate}
    \item What is the input? 
    \item What is the output?
\end{enumerate} }
\end{enumerate}
\end{enumerate}
\end{comment}

\end{document}