Before we start

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

Basic Needs Office: https://basicneeds.ucsd.edu/

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

https://www.facebook.com/tritonfoodpantry/

Mutual Aid UCSD: https://mutualaiducsd.wordpress.com/

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.

Counseling and Psychological Services (CAPS) at 858 5343755 or http://caps.ucsd.edu

OPHD at (858) 534-8298, ophd@ucsd.edu , http://ophd.ucsd.edu. CARE at Sexual Assault Resource Center at 858 5345793 sarc@ucsd.edu http://care.ucsd.edu

Pandemic resilient instruction

Fall 2021 is a transition quarter so please be patient with us as we do our best to serve the needs of all students while adhering to the university guidelines. First and foremost is the health and safety of everyone. Please do not come to class if you are sick or even think you might be sick. Please reach out (minnes@eng.ucsd.edu) if you need support with extenuating circumstances.

Masks are required in class. All students who attend class must also be fully vaccinated against COVID-19 unless they have a university-approved exemption. Campus policy requires masks and daily “symptom screeners" for everyone and we expect all students to follow these rules.

Welcome to CSE 20: Discrete Math for Computer Science in Fall 2021!

Themes and applications for CSE 20

• 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.

• 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.

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).

Introductions

Class website: http://cseweb.ucsd.edu/classes/fa21/cse20-a

Pro-tip: the URL structure is your map to finding your course website for other CSE classes.

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

Instructor: Prof. Mia Minnes "Minnes" rhymes with Guinness, minnes@eng.ucsd.edu, http://cseweb.ucsd.edu/ minnes

Our team: Four TAs and 10 tutors + all of you

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

On a typical week: MWF Lectures + review quizzes, T HW due, W Discussion, office hours, Piazza. Project parts will be due some weeks.

All dates are on Canvas (click for link) and details are on course calendar (click for link).

Education research: CSE 20 is participating in a project on retention and sense of community in UCSD majors; see research plan. If you consent to participate in this study, no action is needed. If you DO NOT consent to participate in this study, or you choose to opt-out at any time during the a cademic year, sign and submit this form to the research contact at retentionstudy@cs.ucsd.edu.

Friday September 24

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

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.

In the table below, each row represents a user’s ratings of movies:  (check) indicates the person liked the movie,  (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  (check), \(-1\) for  (x), and \(0\) for \(\bullet\) (dot).

Conclusion: Modeling involves choosing data types to represent and organize data

Review: Week 0 Friday

1. Please complete the beginning of the quarter survey https://forms.gle/gvibFnNixxqcWbaU8

2. We want you to be familiar with class policies and procedures so you are ready to have a successful quarter. Please take a look at the class website http://cseweb.ucsd.edu/classes/fa21/cse20-a and answer the questions about it on Gradescope.

3. Modeling:

   1. Using the example movie database from class with the \(3\) movies Fyre, Frozen II, Picard, which of the following is a \(3\)-tuple that represents the ratings of a user who liked Frozen II? (Select all and only that apply.)

      1. \(1\)

      2. \((0,0,0)\)

      3. \([1,1,1]\)

      4. \(\{-1, 0, 1\}\)

      5. \((1,-1,0)\)

      6. \((0,1,1)\)

      7. \((1,1,1,1)\)

   2. Using the example movie database from class with the \(3\) movies Fyre, Frozen II, Picard, how many distinct (different) \(3\)-tuples of ratings are there?

Monday September 27

Notation and prerequisites

Data Types: sets, \(n\)-tuples, and strings

Special cases:

When \(n=2\), the 2-tuple is called an ordered pair.

A string of length \(0\) is called the empty string and is denoted \(\lambda\).

A set with no elements is called the empty set and is denoted \(\{\}\) or \(\emptyset\).

To define sets:

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

To define a set using 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 \}\]

We use the symbol \(\in\) as “is an element of” to indicate membership in a set.
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.

• \(\{ -1, 1\}\)
  

• \(\{0, 0 \}\)
  

• \(\{-1, 0, 1 \}\)
  

• \(\{(x,x,x) \mid x \in \{-1,0,1\} \}\)
  

• \(\{ \}\)
  

• \(\{ x \in \mathbb{Z} \mid x \geq 0 \}\)
  

• \(\{ x \in \mathbb{Z} \mid x > 0 \}\)
  

• \(\{\texttt{A},\texttt{C},\texttt{U},\texttt{G}\}\)
  

• \(\{\texttt{A}\texttt{U}\texttt{G}, \texttt{U}\texttt{A}\texttt{G}, \texttt{U}\texttt{G}\texttt{A}, \texttt{U}\texttt{A}\texttt{A}\}\)
  

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 = \{\texttt{A}, \texttt{C}, \texttt{U}, \texttt{G}\}\).

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

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.

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:

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:

Definition The set of RNA strands \(S\) is defined (recursively) by: \[\begin{array}{ll} \textrm{Basis Step: } & \texttt{A}\in S, \texttt{C}\in S, \texttt{U}\in S, \texttt{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:

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}\]

Notation: We call the set of bitstrings \(\{0,1\}^*\).

Examples:

Review: Week 1 Monday

1. Colors can be described as amounts of red, green, and blue mixed together¹ 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:

   \(\{\)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\(\}\)

   1. True or False: \((1, 3, 4)\) fits the definition of a color above.

   2. True or False: \((1, 100, 200, 0)\) fits the definition of a color above.

   3. True or False: \((510, 255)\) fits the definition of a color above.

   4. True or False: There is a color \((r_1, g_1, b_1)\) where \(r_1 + g_1 + b_1\) is greater than \(765\).

   5. True or False: There is a color \((r_2, g_2, b_2)\) where \(r_2 + g_2 + b_2\) is equal to \(1\).

   6. True or False: 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 \}\].

   7. True or False: 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 \}\].

   8. True or False: 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 \}\].

2. 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.

   1. Select all and only the sets below that have \(0\) as an element.

      1. \(\{-1,1\}\)

      2. \(\{0,0\}\)

      3. \(\{-1,0,1\}\)

      4. \(\mathbb{Z}\)

      5. \(\mathbb{Z}^+\)

      6. \(\mathbb{N}\)

   2. Select all and only the sets below that have the ordered pair \((2, 0)\) as an element.

      1. \(\{ x \mid x \in \mathbb{N} \}\)

      2. \(\{ (x,x) \mid x \in \mathbb{N} \}\)

      3. \(\{ (x, x-2) \mid x \in \mathbb{N} \}\)

      4. \(\{ (x,y) \mid x \in \mathbb{Z}^+, y \in \mathbb{Z} \}\)

3. Which of the following are (recursive) definitions of the set of integers \(\mathbb{Z}\)? (Select True/False for each one.)

   1. \[\begin{array}{ll} \textrm{Basis Step: } & 5 \in \mathbb{Z} \\ \textrm{Recursive Step: } & \textrm{If } x \in \mathbb{Z} \textrm{, then } x+1 \in \mathbb{Z} \textrm{ and } x-1 \in \mathbb{Z} \end{array}\]

   2. \[\begin{array}{ll} \textrm{Basis Step: } & 0 \in \mathbb{Z} \\ \textrm{Recursive Step: } & \textrm{If } x \in \mathbb{Z} \textrm{, then } x+1 \in \mathbb{Z} \textrm{ and } x-1 \in \mathbb{Z} \textrm{ and } x+2 \in \mathbb{Z} \textrm{ and } x-2 \in \mathbb{Z} \end{array}\]

   3. \[\begin{array}{ll} \textrm{Basis Step: } & 0 \in \mathbb{Z} \\ \textrm{Recursive Step: } & \textrm{If } x \in \mathbb{Z} \textrm{, then } x+2 \in \mathbb{Z} \textrm{ and } x-1 \in \mathbb{Z} \end{array}\]

   4. \[\begin{array}{ll} \textrm{Basis Step: } & 0 \in \mathbb{Z} \\ \textrm{Recursive Step: } & \textrm{If } x \in \mathbb{Z} \textrm{, then } x+1 \in \mathbb{Z} \textrm{ and } x+2 \in \mathbb{Z} \end{array}\]

Wednesday September 29

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.

Fill in the missing entries in the table:

Example: The absolute value function

Domain

Codomain

Rule

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)\), \(P_2 = (1, 1, -1)\), \(P_3 = (1, 1, 1)\), \(P_4 = (0,-1,1)\)

Which of \(P_1\), \(P_2\), \(P_3\) has movie preferences most similar to \(P_4\)?

One approach to answer this question: use functions to define distance between user preferences.

For example, consider the function \(d_0: \phantom{the Cartesian product of the set of ratings on 3 movies with itself} \to \phantom{\mathbb{R}}\) given by \[d_0 (~(~ (x_1, x_2, x_3), (y_1, y_2, y_3) ~) ~) = \sqrt{ (x_1 - y_1)^2 + (x_2 - y_2)^2 + (x_3 -y_3)^2}\]

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  and \(P_2\) gives . Should this movie be recommended to \(P_3\)? Why or why not?

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.

When the domain of a function is a 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: } & \texttt{A}\in S, \texttt{C}\in S, \texttt{U}\in S, \texttt{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.

Definition (Of a function, recursively) A function 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 rnalen is
The codomain of rnalen is
Example function application: \[rnalen(\texttt{A}\texttt{C}\texttt{U}) = \phantom{1+ rnalen(\texttt{A}\texttt{C}) = 1 + (1 + rnalen(\texttt{A}) ) = 1 + ( 1 + 1) = 3}\]

Extra example: A function 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}\]

\(basecount(~(\texttt{A}\texttt{C}\texttt{U},\texttt{A})~) = basecount( ~(\texttt{A}\texttt{C}, \texttt{A})~) = basecount(~(\texttt{A}, \texttt{A})~) = 1\)
\(basecount(~(\texttt{A}\texttt{C}\texttt{U},\texttt{G})~) = basecount( ~(\texttt{A}\texttt{C}, \texttt{G})~) = basecount(~(\texttt{A}, \texttt{G})~) = 0\)
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.

Review: Week 1 Wednesday

1. 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 = \{\texttt{A}, \texttt{C}, \texttt{G}, \texttt{U}\}\). The set of RNA strands \(S\) is defined (recursively) by:

   \[\begin{array}{ll} \textrm{Basis Step: } & \texttt{A}\in S, \texttt{C}\in S, \texttt{U}\in S, \texttt{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 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}\]

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

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

   3. 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 ?\]

   4. How many distinct elements are in the set obtained as the result of the set-wise concatenation \(\{ \texttt{A}\texttt{A}, \texttt{A}\texttt{C}\} \circ \{\texttt{U}, \texttt{A}\texttt{A}\}\)?

   5. How many distinct elements are in the set obtained as the result of the Cartesian product \(\{ \texttt{A}\texttt{A}, \texttt{A}\texttt{C}\} \times \{\texttt{U}, \texttt{A}\texttt{A}\}\)?

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

   Bonus - not for credit: Describe each of the sets above using roster method.

2. Recall the function \(d_0\) which takes an ordered pair of ratings \(3\)-tuples and returns a measure of the distance between them given by \[d_0 (~(~ (x_1, x_2, x_3), (y_1, y_2, y_3) ~) ~) = \sqrt{ (x_1 - y_1)^2 + (x_2 - y_2)^2 + (x_3 -y_3)^2}\] Consider the function application \[d_0 (~( ~(-1,1,1), (1, 0, -1)~) ~)\]

   1. What is the input?

   2. What is the output?

3. To give the rule for a recursive definition of the function with codomain \(\mathbb{Z}\) which gives \(2^n\) for a nonnegative integer \(n\), fill in each step below.

   1. Basis Step: \(2^0 = \underline{\phantom{1in}}\)

   2. Recursive Step: If \(n \in \mathbb{N}\), then

      1. \(2^{n} = 2^{n}\)

      2. \(2^{n+1} = n+2\)

      3. \(2^{n+1} = 2n\)

Friday October 1 (Zoom)

Today’s session is on Zoom, log in with your @ucsd.edu account https://ucsd.zoom.us/j/97431852722 Meeting ID: 974 3185 2722

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?

Definition For \(b\) an integer greater than \(1\) and \(n\) a positive integer, the 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 nonnegative integers less than \(b\), \(a_{k-1} \neq 0\), and \[n = \sum_{i=0}^{k-1} a_{i} b^{i}\]

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

Examples:

\((1401)_{2}\)

\((1401)_{10}\)

\((1401)_{16}\)

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. We write \(q=n \textbf{ div } d\) and \(r=n \textbf{ mod } d\).

Extra example: How do \(\textbf{ div }\) and \(\textbf{ mod }\) compare to \(/\) and \(\%\) in Java and python?

Two algorithms for constructing base \(b\) expansion from decimal representation

Most significant first: Start with left-most coefficient of expansion

Least significant first: Start with right-most coefficient of expansion

Review: Week 1 Friday

1. For many applications in cryptography and random number generation, dividing very large integers efficiently is critical. Recall the definitions known as 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. We write \(q=n \textbf{ div } d\) and \(r=n \textbf{ mod } d\).

   One application of the Division Algorithm is in computing the integer part of the logarithm. When we discuss algorithms in this class, we will usually write them in pseudocode or English. Sometimes we will find it useful to relate the pseudocode to runnable code in a programming language. We will typically use Java or python for this.

   2

   procedure \(\textit{log}\)(\(n\): a positive integer) \(r\) := \(0\) while \(n\) > \(1\) \(r\) := \(r + 1\) \(n\) := \(n\) div \(2\) return \(r\) \(\{ r~\textrm{holds the result of the}~\log~\textrm{operation}\}\)

   int log(int n) if (n < 1) throw new IllegalArgumentException(); int result = 0; while(n > 1) result = result + 1; n = n / 2; return result;

   1. Calculate \(2021 \textbf{ div } 20\). You may use a calculator if you like.

   2. Calculate \(2021 \textbf{ mod } 20\). You may use a calculator if you like.

   3. How many different possible values of \(r\) (results of taking \(n \textbf{ mod } d\)) are there when we consider positive integer values of \(n\) and \(d\) is \(20\)?

   4. What is the smallest positive integer \(n\) which can be written as \(16q+7\) for \(q\) an integer?

   5. What is the return value of log\((457)\)? You can run the Java version in order to calculate it.

2. Give the value (using usual mathematical conventions) of each of the following base expansions.

   1. \((10)_{2}\)

   2. \((10)_{4}\)

   3. \((17)_{16}\)

   4. \((211)_{3}\)

   5. \((3)_{8}\)