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

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

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 2s 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\)?