hw2-numbers

In this assignment,

You will practice applying functions and tracing algorithms in multiple contexts, and exploring properties of positional number representations.

Relevant class material: Week 2.

You will submit this assignment via Gradescope (https://www.gradescope.com) in the assignment called “hw2-numbers”.

For all HW assignments: These homework assignments may be done individually or in groups of up to 3 students. Please ensure your name(s) and PID(s) are clearly visible on the first page of your homework submission, start each question on a new page, and upload the PDF to Gradescope. If you’re working in a group, submit only one submission per group: one partner uploads the submission through their Gradescope account and then adds the other group member(s) to the Gradescope submission by selecting their name(s) in the “Add Group Members” dialog box. You will need to re-add your group member(s) every time you resubmit a new version of your assignment.

Each homework question will be graded either for correctness (including clear and precise explanations and justifications of all answers) or fair effort completeness. You may collaborate on “graded for correctness” questions only with CSE 20 students in your group; if your group has questions about a problem, you may ask in drop-in help hours or post a private post (visible only to the Instructors) on Piazza. For “graded for completeness” questions: collaboration is allowed with any CSE 20 students this quarter; if your group has questions about a problem, you may ask in drop-in help hours or post a public post on Piazza.

All submitted homework for this class must be typed. You can use a word processing editor if you like (Microsoft Word, Open Office, Notepad, Vim, Google Docs, etc.) but you might find it useful to take this opportunity to learn LaTeX. LaTeX is a markup language used widely in computer science and mathematics. The homework assignments are typed using LaTeX and you can use the source files as templates for typesetting your solutions.

Integrity reminders

• Problems should be solved together, not divided up between the partners. The homework is designed to give you practice with the main concepts and techniques of the course, while getting to know and learn from your classmates.

• You may not collaborate on homework questions graded for correctness with anyone other than your group members. You may ask questions about the homework in office hours (of the instructor, TAs, and/or tutors) and on Piazza (as private notes viewable only to the Instructors). You cannot use any online resources about the course content other than the class material from this quarter – this is primarily to ensure that we all use consistent notation and definitions (aligned with the textbook) and also to protect the learning experience you will have when the ‘aha’ moments of solving the problem authentically happen.

• Do not share written solutions or partial solutions for homework with other students in the class who are not in your group. Doing so would dilute their learning experience and detract from their success in the class.

Assigned questions

1. Functions and algorithms: in this question you’ll explore the properties of the (integer) power and logarithm functions. We’ll use some definitions we introduced in class this week, namely the function \(b^i\) with domain \(\mathbb{Z}^+ \times \mathbb{N}\) and codomain \(\mathbb{N}\) defined recursively by \[\begin{aligned} &\textrm{Basis Step:} \\ &b^0 = 1 \\ &\textrm{Recursive Step:}\\ &\textrm{If } i \in \mathbb{N}, b^{i+1} = b \cdot b^i \end{aligned}\] and the algorithm:

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

   1. (Graded for correctness) ¹ Choose a positive integer \(b\) between \(3\) and \(6\) (inclusive) and choose a nonnegative integer \(i\) between \(2\) and \(5\) (inclusive). Demonstrate how to calculate the result of the \(logb\) algorithm (procedure) when its input is the base \(b\) you chose and \(n = b^i\) (for the \(i\) you choose.) A complete answer will include the specific choice of \(b\) and \(i\), along with trace of the calculations of \(b^i\) and the computation of the algorithm, including (clear, correct, complete) calculations for each of the function applications and/or references to definitions and a trace table for algorithm that includes the values of all relevant variables at each iteration (See the annotated Week 2 notes for the level of detail expected in a trace of a function application and a trace table).

   2. (Graded for correctness) Now we’ll go in other order: Demonstrate how to calculate the result of \(7^y\) where \(y\) is the result of the \(logb\) algorithm (procedure) when its input is \(b=7\) and \(n=30\). A complete answer will include clearly labelled traces of the calculations of \(b^i\) and the computation of the algorithm, including (clear, correct, complete) calculations for each of the function applications and/or references to definitions and a trace table for algorithm that includes the values of all relevant variables at each iteration (See the annotated Week 2 notes for the level of detail expected in a trace of a function application and a trace table).

   3. (Graded for completeness) ² Logarithms and powers are supposed to “undo" one another. Explain whether your work in parts (a) and (b) supports that idea, whether you saw anything confusing or surprising about these calculations, and how to explain what you saw.

2. Base expansions

   1. (Graded for completeness) Pick an integer between \(50\) and \(1000\) (inclusive) that you (or one of your group members) came across at some point this week. In a sentence or two, give some context for why you’re choosing this number). Write the base expansion of your chosen number in base \(2\) (binary), base \(3\) (ternary), base \(4\), and base \(16\) (hexadecimal).

   2. (Graded for correctness) What is the smallest width \(w\) in which they could write your chosen number in base \(8\) (octal) fixed-width \(w\)? Justify your answer with reference to the definitions of fixed-width expansions and relevant calculations.

   3. (Graded for correctness) Express in roster method the set of numbers between \(1\) and \(2\) (exclusive) that be written without error (full precision) in binary fixed width expansion with integer part width \(3\) and fractional part width \(2\). Justify your answer with reference to the definitions of fixed-width expansions and relevant calculations.

   4. (Graded for correctness) Consider the strings of \(1\)s that have length \(3\), \(5\), \(7\), and \(10\). Calculate the numbers

      • \([111]_{s,3}\)

      • \([11111]_{s,5}\)

      • \([1111111]_{s,7}\)

      • \([1111111111]_{s,10}\)

      • \([111]_{2c,3}\)

      • \([11111]_{2c,5}\)

      • \([1111111]_{2c,7}\)

      • \([1111111111]_{2c,10}\)

      Justify your answers with specific reference to the definitions of sign-magnitude and \(2\)s complement expansions and relevant calculations.

   5. (Graded for completeness) What patterns do you notice in your calculations in part (d)?

3. Multiple representations

   Recall 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 (this definition was introduced in this week’s Review quiz).

   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.

   For this question, let’s call the set of hex colors \(H\). In the Week 2 Review quiz (Question 3d), we explored a few different set builder definitions for \(H\).

   1. (Graded for completeness) Rewrite the set builder definition of a set below so that it refers to colors rather than numbers: \(\{ c \in H \mid c \mod 256 = 0\}\). A complete answer will justify the new set builder definition by connection with the definition of hex colors and how it impacts the colors that satisfy the specific property for this set.

   2. (Graded for correctness) Rewrite the set builder definition of a set below so that it refers to colors rather than numbers: \(\{ c \in H \mid c < 65536\}\). A complete answer will justify the new set builder definition by connection with the definition of hex colors and how it impacts the colors that satisfy the specific property for this set.

   3. (Graded for correctness) In art, we can mix two colors to get a new color. For example, red and blue make purple, blue and yellow make green, red and yellow make orange. A mathematical definition of hex color mixing would be a function with domain \(H \times H\) and codomain \(H\) where the result of applying this function to an input \((n_1, n_2)\) is the hex color that results from mixing the hex colors \(n_1\) and \(n_2\).

      ---

      Sample work for a related question that can be used as reference for the detail expected in your answer: Consider the attempted mathematical definition \(f_1: H\times H \to H\) given by \[f_1 (~(n_1, n_2) ~) = n_1 + n_2\] We will show that this function is not well-defined so it cannot give a hex color mixing definition. The reason it is not well-defined is that the application of the rule sometimes gives values that are not in the stated codomain. To see this, we need an example input to \(f_1\) for which the output of the rule is not in \(H\). Here is one such example: \((n_1, n_2) = (~(FFFFFF)_{16,6}, (FFFFFF)_{16,6}~)\). This example is in \(H \times H\) because \((FFFFFF)_{16,6}\) is a nonnegative integer that has a base \(16\) fixed-width \(6\) expansion so it is a hex color. We now apply the definition of the rule in \(f_1\): \[\begin{aligned} f_1 (~(n_1, n_2) ~) &= f_1 ( (~(FFFFFF)_{16,6}, (FFFFFF)_{16,6}~) ) = (FFFFFF)_{16,6} + (FFFFFF)_{16,6} \\ &= 2 \left( 15\cdot 16^5 + 15\cdot 16^4 + 15 \cdot 16^3 + 15 \cdot 16^2 + 15 \cdot 16^1 + 15 \cdot 16^0 \right) \\ &= 2 \cdot 15 \cdot (1048576 + 65536 + 4096 + 256 + 16 + 1) = 2 \cdot 15 \cdot 1118481 = 33554430 \end{aligned}\] This is not a hex color because it is greater than or equal to \(16^6 = 16777216\), so (using the Week 2 notes on which numbers can be represented with fixed-width expansions) it does not have a hexadecimal fixed width \(6\) expansion.

      ---

      In this question, we’ll look at another attempted mathematical definition for hex color mixing. We define \(f_2: H\times H \to H\) given by \[f_2 (~(n_1, n_2) ~) = (n_1 + n_2) \textbf{ div } 2\]

      This is a well-defined function. You do not need to prove this or hand it in, but it’s good practice to make sure you understand why it’s well-defined. Notice that the function application \[f_2 ( ~(~ (FF0000)_{16,6} , (FFFE00)_{16,6} ~)~)\] can be calculated as: \[\begin{aligned} f_2&(((FF0000)_{16,6}, (FFFE00)_{16,6}))= ((FF0000)_{16,6} + (FFFE00)_{16,6})) \textbf{ div } 2\\ &= \big(~ \left(15\cdot16^5 + 15\cdot16^4 + 0\cdot16^3 + 0\cdot16^2 + 0\cdot16^1 + 0\cdot16^0 \right) \\ &~~~~+~ \left((15\cdot16^5 + 15\cdot16^4 + 15\cdot16^3 + 14\cdot16^2 + 0\cdot16^1 + 0\cdot16^0\right )~\big )\textbf{ div } 2\\ &= (16711680 + 16776704) \textbf{ div } 2 = 33488384 \textbf{ div } 2 = 16744192 \end{aligned}\] Since this is less than \(16^6 = 16777216\), we can represent it using base \(16\) fixed-width \(6\):. \[(16744192)_{10} = 15\cdot16^5 + 15\cdot16^4 + 7\cdot16^3 + 15\cdot16^2 + 0\cdot16^1 + 0\cdot16^0 = (FF7F00)_{16,6}\]

      Using the web tool https://www.w3schools.com/colors/colors_rgb.asp, we can verify that \((FF0000)_{16,6}\) is red, \((FFFE00)_{16,6}\) is yellow, and \((FF7F00)_{16,6}\) is orange.

      Show that \(f_2\) does not work as a hex color mixing definition by finding another ordered pair of hex colors for which the result of applying \(f_2\) does not give the expected hex color. Include the numerical description of each colors you mention, alongside a description of them in English. Describe how you know what these colors are (if you use a web color tool, include its URL in your submission writeup; if not, describe your reasoning). Justify your example with (clear, correct, complete) calculations and/or references to definitions, and connecting them with the desired conclusion.