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 the definitions of the div and mod operators on integers
#FinAid Assignment on Canvas (complete as soon as possible)
Review quiz based on Week 0 and 1 class material (due Monday)
Homework assignment 1 (due Tuesday)
Review quiz based on Week 2 class material (due Monday next week)
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.
| Base \(b\) | Collection of possible coefficients in base \(b\) expansion of a positive integer |
|---|---|
| Binary (\(b=2\)) | \(\{0,1\}\) |
| Ternary (\(b=3\)) | \(\{0,1, 2\}\) |
| Octal (\(b=8\)) | \(\{0,1, 2, 3, 4, 5, 6, 7\}\) |
| Decimal (\(b=10\)) | \(\{0,1, 2, 3, 4, 5, 6, 7, 8, 9\}\) |
| 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}\) |
Examples:
\((1401)_{2}\)
\((1401)_{10}\)
\((1401)_{16}\)
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}\]
| Decimal | Binary | Binary fixed-width \(10\) | Binary fixed-width \(7\) | Binary fixed-width \(4\) |
| \(b=10\) | \(b=2\) | \(b=2\), \(w = 10\) | \(b=2\), \(w = 7\) | \(b=2\), \(w = 4\) |
| \((20)_{10}\) | ||||
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'}\]
| \(3.75\) in fixed-width binary, | |
| integer part width \(2\), | |
| fractional part width \(8\) | |
| \(0.1\) in fixed-width binary, | |
| integer part width \(2\), | |
| fractional part width \(8\) | |
Note: Java uses floating point, not fixed width representation, but similar rounding errors appear in both.
Representing \(0\): Which of the representations so far allow us to represent \(0\)?
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}\)
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\]
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\}\)
Trace this algorithm with inputs \(b=3\) and \(n=17\)
| \(b\) | \(n\) | \(i\) | \(n > b-1\)? | |
|---|---|---|---|---|
| Initial value | \(3\) | \(17\) | ||
| After 1 iteration | ||||
| After 2 iterations | ||||
| After 3 iterations | ||||
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.
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 \}\)
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\).
procedure \(\textit{basebleast}\)(\(n, b\): positive integers with \(b > 1\)) \(k\) := \(0\) \(q\) := \(n\) while \(q \neq 0\) \(a_{k}\) := \(q\) mod \(b\) \(k\) := \(k+1\) \(q\) := \(q\) div \(b\) return \((a_{k-1}, \ldots, a_0) \{(a_{k-1} \ldots a_0)_b~\textrm{ is the base } b \textrm{ expansion of } n \}\)
Practice: write an algorithm for converting from base \(b_1\) expansion to base \(b_2\) expansion:
Representing negative integers in binary: Fix a positive integer width for the representation \(w\), \(w >1\).
| To represent a positive integer \(n\) | To represent a negative integer \(-n\) | ||
|---|---|---|---|
| \([ 0a_{w-2} \cdots a_0]_{s,w}\), where \(n = (a_{w-2} \cdots a_0)_{2,w-1}\) | \([1a_{w-2} \cdots a_0]_{s,w}\) , where \(n = (a_{w-2} \cdots a_0)_{2,w-1}\) | ||
| Example \(n=17\), \(w=7\): | Example \(-n=-17\), \(w=7\): | ||
| \([0a_{w-2} \cdots a_0]_{2c,w}\), where \(n = (a_{w-2} \cdots a_0)_{2,w-1}\) | \([1a_{w-2} \cdots a_0]_{2c,w}\), where \(2^{w-1} - n = (a_{w-2} \cdots a_0)_{2,w-1}\) | ||
| Example \(n=17\), \(w=7\): | Example \(-n=-17\), \(w=7\): | ||
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.
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. Does this give the right value for the sum?
\[\begin{align*} & [2~ 6]_{10,2}\\ + & [8~ 4]_{10,2}\\ &\overline{\phantom{[0~0]_{10,2}}}\\ \end{align*}\]
3 \[\begin{align*} & (1~ 1~ 0~ 1~ 0~ 0)_{2,6}\\ + & (0~ 0~ 0~ 1~ 0~ 1)_{2,6}\\ &\overline{\phantom{(1~1~1~0~0~1)_{2,6}}}\\ \end{align*}\]
\[\begin{align*} & [1~ 1~ 0~ 1~ 0~ 0]_{s,6}\\ + & [0~ 0~ 0~ 1~ 0~ 1]_{s,6}\\ &\overline{\phantom{(1~1~1~0~0~1)_2}}\\ \end{align*}\]
\[\begin{align*} & [1~ 1~ 0~ 1~ 0~ 0]_{2c,6}\\ + & [0~ 0~ 0~ 1~ 0~ 1]_{2c,6}\\ &\overline{\phantom{(1~1~1~0~0~1)_2}}\\ \end{align*}\]
Can fixed-width addition be used to calculate \(17 + (-17) = 0\)? Hint: use 5 bits and 2s complement.
In a combinatorial circuit (also known as a logic circuit), we have logic gates connected by wires. The inputs to the circuits are the values set on the input wires: possible values are 0 (low) or 1 (high). The values flow along the wires from left to right. A wire may be split into two or more wires, indicated with a filled-in circle (representing solder). Values stay the same along a wire. When one or more wires flow into a gate, the output value of that gate is computed from the input values based on the gate’s definition table. Outputs of gates may become inputs to other gates.
2
| Inputs | Output | |
| \(x\) | \(y\) | \(x \text{ AND } y\) |
| \(1\) | \(1\) | \(1\) |
| \(1\) | \(0\) | \(0\) |
| \(0\) | \(1\) | \(0\) |
| \(0\) | \(0\) | \(0\) |
2
| Inputs | Output | |
| \(x\) | \(y\) | \(x \text{ XOR } y\) |
| \(1\) | \(1\) | \(0\) |
| \(1\) | \(0\) | \(1\) |
| \(0\) | \(1\) | \(1\) |
| \(0\) | \(0\) | \(0\) |
2
| Input | Output |
| \(x\) | \(\text{NOT } x\) |
| \(1\) | \(0\) |
| \(0\) | \(1\) |
Example digital circuit:
2
Output when \(x=1, y=0, z=0, w = 1\) is Output when \(x=1, y=1, z=1, w = 1\) is Output when \(x=0, y=0, z=0, w = 1\) is
Draw a logic circuit with inputs \(x\) and \(y\) whose output is always \(0\). Can you use exactly 1 gate?