Week 2 at a glance

We will be learning and practicing to:

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

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

  • Determining the properties of positional number representations, including overflow and bit operations

• Translate between different representations to illustrate a concept.

  • Translating between symbolic and English versions of statements using precise mathematical language

  • Tracing algorithms specified in pseudocode

  • Representing numbers using positional representations, including decimal, binary, hexadecimal, fixed-width representations, and 2s complement

• Use precise notation to encode meaning and present arguments concisely and clearly

  • Precisely describing a set using appropriate notation e.g. roster method, set builder notation, and recursive definitions

  • Defining functions using multiple representations

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

  • Using a recursive definition to evaluate a function or determine membership in a set

  • Using the definitions of the div and mod operators on integers

TODO:

Week 2 Monday: Sets, functions, and algorithms

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 Dune, Oppenheimer, Barbie, Nimona 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\).

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

Pro-tip: informal definitions sometime use \(\cdots\) to indicate “continue the pattern”. Often, to make this pattern precise we use recursive definitions.

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

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.

Example calculations:

\(20 \textbf{ div } 4\)

\(20 \textbf{ mod } 4\)

\(20 \textbf{ div } 3\)

\(20 \textbf{ mod } 3\)

\(-20 \textbf{ div } 3\)

\(-20 \textbf{ mod } 3\)

Week 2 Wednesday: Representing 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?

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

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

Trace this algorithm with inputs \(b=3\) and \(n=17\)

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

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

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

Informally: Build up to the value we need to represent in “greedy” approach, using units determined by base.

Least significant first: Start with right-most coefficient of expansion (lowest value)

Idea: (when \(k > 1\)) \[\begin{aligned} 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{aligned}\] so \(a_0 = n \textbf{ mod } b\) and \(a_{k-1} b^{k-2} + \cdots + a_1 = n \textbf{ div } b\).

Week 2 Friday: Algorithms for numbers

Find and fix any and all mistakes with the following:

• \((1)_2 = (1)_8\)

• \((142)_{10} = (142)_{16}\)

• \((20)_{10} = (10100)_2\)

• \((35)_8 = (1D)_{16}\)

Practice: write an algorithm for converting from base \(b_1\) expansion to base \(b_2\) expansion:

Definition For \(b\) an integer greater than \(1\), \(w\) a positive integer, and \(n\) a nonnegative integer \(\underline{\phantom{\hspace{1in}}}\),   the base \(b\) fixed-width \(w\) expansion of \(n\) is \[(a_{w-1} \cdots a_1 a_0)_{b,w}\] where \(a_0, a_1, \ldots, a_{w-1}\) are nonnegative integers less than \(b\) and \[n = \sum_{i=0}^{w-1} a_{i} b^{i}\]

Definition For \(b\) an integer greater than \(1\), \(w\) a positive integer, \(w'\) a positive integer, and \(x\) a real number the base \(b\) fixed-width expansion of \(x\) with integer part width \(w\) and fractional part width \(w'\) is \((a_{w-1} \cdots a_1 a_0 . c_{1} \cdots c_{w'})_{b,w,w'}\) where \(a_0, a_1, \ldots, a_{w-1}, c_1, \ldots, c_{w'}\) are nonnegative integers less than \(b\) and \[x \geq \sum_{i=0}^{w-1} a_{i} b^{i} + \sum_{j=1}^{w'} c_{j} b^{-j} \hfill \textrm{\qquad and \qquad} \hfill x < \sum_{i=0}^{w-1} a_{i} b^{i} + \sum_{j=1}^{w'} c_{j} b^{-j} + b^{-w'}\]

Note: Java uses floating point, not fixed width representation, but similar rounding errors appear in both.

Representing negative integers in binary: Fix a positive integer width for the representation \(w\), \(w >1\).

For positive integer \(n\), to represent \(-n\) in \(2\)s complement with width \(w\),

• Calculate \(2^{w-1} - n\), convert result to binary fixed-width \(w-1\), pad with leading \(1\), or

• Express \(-n\) as a sum of powers of \(2\), where the leftmost \(2^{w-1}\) is negative weight, or

• Convert \(n\) to binary fixed-width \(w\), flip bits, add 1 (ignore overflow)

Challenge: use definitions to explain why each of these approaches works.

Representing \(0\):

So far, we have representations for positive and negative integers. What about \(0\)?

Review Quiz

1. Functions and algorithms

   1. What is a recursive definition of the set \(\mathbb{Z}^+ \times \mathbb{N}\) that is the domain of the function “\(b\) to the power of \(i\)”? For convenience, we’ll refer to this set as \(X\) in the options below.

      1. Basis step: \((1,0) \in X\). Recursive step: If \((m,n) \in X\) then \((m+1, n+1) \in X\) too.

      2. Basis step: \((1,0) \in X\). Recursive step: If \((m,m-1) \in X\) then \((m+1, m) \in X\) too.

      3. Basis step: \((b,0) \in X\) for each \(b \in \mathbb{Z}^+\). Recursive step: If \((m,n) \in X\) then \((m+1, n+1) \in X\) too.

      4. Basis step: \((b,0) \in X\) for each \(b \in \mathbb{Z}^+\). Recursive step: If \((m,n) \in X\) then \((m, n+1) \in X\) too.

      5. None of the above.

   2. When running the algorithm \(logb\) for calculating the integer part of base \(b\) logarithm with inputs \(b=4\) and \(n=25\), which of the following calculations are helpful? Select all and only the calculations that are both relevant to the algorithm trace and are correct.

      1. \(25 \textbf{ div } 4 = 5\)

      2. \(25 \textbf{ div } 4 = 6\)

      3. \(25 \textbf{ div } 4 = 1\)

      4. \(4 \textbf{ div } 25 = 0\)

      5. \(4 \textbf{ div } 25 = 5\)

      6. \(4 \textbf{ div } 25 = 1\)

      7. \(6 \textbf{ div } 4= 1\)

      8. \(5 \textbf{ div } 4= 1\)

      9. \(4 \textbf{ div } 4= 1\)

2. Base expansions

   1. 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}\)

   2. Recall the definitions from class for number representations for base \(b\) expansion of \(n\), base \(b\) fixed-width \(w\) expansion of \(n\), and base \(b\) fixed-width expansion of \(x\) with integer part width \(w\) and fractional part width \(w'\).

      For example, the base \(2\) (binary) expansion of \(4\) is \(\qquad (100)_2 \qquad\) and the base \(2\) (binary) fixed-width \(8\) expansion of \(4\) is \(\qquad (00000100)_{2,8} \qquad\) and the base \(2\) (binary) fixed-width expansion of \(4\) with integer part width \(3\) and fractional part width \(2\) of \(4\) is \(\qquad (100.00)_{2,3,2} \qquad\)

      Compute the listed expansions. Enter your number using the notation for base expansions with parentheses but without subscripts. For example, if your answer were \((100)_{2,3}\) you would type (100)2,3 into Gradescope.

      1. Give the binary (base \(2\)) expansion of the number whose octal (base \(8\)) expansion is \[(371)_8\]

      2. Give the decimal (base \(10\)) expansion of the number whose octal (base \(8\)) expansion is \[(371)_8\]

      3. Give the octal (base \(8\)) fixed-width \(3\) expansion of \((9)_{10}\) .

      4. Give the ternary (base \(3\)) fixed-width \(8\) expansion of \((9)_{10}\) .

      5. Give the hexadecimal (base \(16\)) fixed-width \(6\) expansion of \((16711935)_{10}\) .¹

      6. Give the hexadecimal (base \(16\)) fixed-width \(4\) expansion of \[(1011~ 1010 ~ 1001~ 0000 )_2\] Note: the spaces between each group of 4 bits above are for your convenience only. How might they help your calculations?

      7. Give the binary fixed width expansion of \(0.125\) with integer part width \(2\) and fractional part width \(4\).

      8. Give the binary fixed width expansion of \(1\) with integer part width \(2\) and fractional part width \(3\).

   3. Select all and only the correct choices below.

      1. Suppose you were told that the positive integer \(n_1\) has the property that \(n_1 \textbf{ div } 2 = 0\). Which of the following can you conclude?

         1. \(n_1\) has a binary (base \(2\)) expansion

         2. \(n_1\) has a ternary (base \(3\)) expansion

         3. \(n_1\) has a hexadecimal (base \(16\)) expansion

         4. \(n_1\) has a base \(2\) fixed-width \(1\) expansion

         5. \(n_1\) has a base \(2\) fixed-width \(20\) expansion

      2. Suppose you were told that the positive integer \(n_2\) has the property that \(n_2 \textbf{ mod } 4 = 0\). Which of the following can you conclude?

         1. the leftmost symbol in the binary (base \(2\)) expansion of \(n_2\) is \(1\)

         2. the leftmost symbol in the base \(4\) expansion of \(n_2\) is \(1\)

         3. the rightmost symbol in the base \(4\) expansion of \(n_2\) is \(0\)

         4. the rightmost symbol in the octal (base \(8\)) expansion of \(n_2\) is \(0\)

   4. Recall the definitions of signed integer representations from class: sign-magnitude and 2s complement.

      1. Give the 2s complement width 6 representation of the number represented in binary fixed-width 5 representation as \((00101)_{2,5}\).

      2. Give the 2s complement width 6 representation of the number represented in binary fixed-width 5 representation as \((10101)_{2,5}\).

      3. Give the 2s complement width 4 representation of the number represented in sign-magnitude width 4 as \([1111]_{s,4}\).

      4. Give the sign magnitude width 4 representation of the number represented in 2s complement width 4 as \([1111]_{2c,4}\).

      5. Give the sign magnitude width 6 representation of the number represented in sign magnitude width 4 as \([1111]_{s,4}\).

      6. Give the 2s complement width 6 representation of the number represented in 2s complement width 4 as \([1111]_{2c,4}\).

3. Multiple representations

   We saw last week that, 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 from the collection \(\{x \in \mathbb{N}\mid 0 \leq x \leq 255 \}\). As an alternative representation, in this assignment we’ll use base \(b\) fixed-width expansions to represent colors as individual numbers.

   Definition: A hex color is a nonnegative integer, \(n\), that has a base \(16\) fixed-width \(6\) expansion \[n = (r_1r_2g_1g_2b_1b_2)_{16,6}\] where \((r_1r_2)_{16,2}\) is the red component, \((g_1g_2)_{16,2}\) is the green component, and \((b_1b_2)_{16,2}\) is the blue.

   1. What is the hex color corresponding to full black? Namely, this means setting the value in each of the red, green, and blue components to be the minimum \(0\).

      1. \(0\)

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

      3. \(15^{5}+15^4+15^3+15^2+15^1+1\)

      4. \(15\cdot 16^{5}+15\cdot 16^4+15\cdot 16^3+15 \cdot 16^2+15 \cdot 16^1+15\)

      5. \(16^{5}+16^4+16^3+16^2+16^1+1\)

   2. What is the hex color corresponding to full white? Namely, this means setting the value in each of the red, green, and blue components to be the maximum \(255\).

      1. \(0\)

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

      3. \(15^{5}+15^4+15^3+15^2+15^1+1\)

      4. \(15\cdot 16^{5}+15\cdot 16^4+15\cdot 16^3+15 \cdot 16^2+15 \cdot 16^1+15\)

      5. \(16^{5}+16^4+16^3+16^2+16^1+1\)

   3. Select all and only correct representations of the hex color which is full green (so the red and blue components are \(0\) and green is set to \(255\)).

      1. \((00FF00)_{16,6}\)

      2. \((00FF00)_{16}\)

      3. \(255\)

      4. \(255\cdot 256\)

      5. \(255\cdot 16^2\)

      6. \(65280\)

   4. Which of the following is a definition using set builder notation for the set of hex colors. (Select all and only correct choices)

      1. \(\{ x \in \mathbb{Z} \mid 0 \leq x \leq 16777215\}\)

      2. \(\{ x \in \mathbb{Z} \mid 0 \leq x \leq 16^6 -1\}\)

      3. \(\{ x \in \mathbb{N} \mid x \leq 16777215\}\)

      4. \(\{ x \in \mathbb{N} \mid x \leq 16^6 -1\}\)