\documentclass[12pt, oneside]{article}

\usepackage[letterpaper, scale=0.8, centering]{geometry}
\usepackage{fancyhdr}
\setlength{\parindent}{0em}
\setlength{\parskip}{1em}

\pagestyle{fancy}
\fancyhf{}
\renewcommand{\headrulewidth}{0pt}
\rfoot{{\footnotesize Copyright Mia Minnes, 2026, Version \today~(\thepage)}}

\usepackage{titlesec}

\author{CSE20W26}

\newcommand{\instructions}{{\bf For all HW assignments:} 
These homework assignments may be done individually or in groups of up to four 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, {\it 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.

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.

{\bf Integrity reminders}
\begin{itemize}
\item 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.
\item Use only resources explicitly allowed for each assignment. Resources not affiliated with this quarter's version of the class may use inconsistent notation or definitions. When consulting resources, balance
getting the help you need while also protecting the learning experience you will have when the `aha' moments of solving the problem authentically happen.
\item 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.
\end{itemize}

When evaluating your homework solutions, we will be considering:
\begin{itemize}
\item The correctness of any final answers.
\item Whether ideas are presented clearly and logically. You should explain how you arrived at your conclusions, using
mathematically sound reasoning. Whether you use formal proof techniques or 
write a more informal argument
for why something is true, your answers should always be well-supported. 
Your goal should be to convince the
reader that your results and methods are sound. A rule of thumb for the level of detail to include is to imagine someone who is taking the class alongside you but missed about a week's worth of content: does your writeup have enough detail for them to learn from it?
\end{itemize}
To demonstrate your honest effort in answering homework questions, we 
expect you to include your attempt to answer *each* part of the question. 
If you get stuck with your attempt, you can still demonstrate 
your effort by explaining where you got stuck and what 
you did to try to get unstuck (e.g. reviewing annotated notes from class, checking the relevant textbook sections, looking up comparable questions on the relevant weekly review quizzes, asking questions on Piazza, 
attending (instructor/TA/tutor) office hours, consulting generative AI tools, etc.). 
}



\usepackage{amssymb,amsmath,pifont,amsfonts,comment,enumerate,enumitem}
\usepackage{currfile,xstring,hyperref,tabularx,graphicx,wasysym}
\usepackage[labelformat=empty]{caption}
\usepackage{xcolor}
\usepackage{multicol,multirow,array,listings,tabularx,lastpage,textcomp,booktabs}

\lstnewenvironment{algorithm}[1][] {   
    \lstset{ mathescape=true,
        frame=tB,
        numbers=left, 
        numberstyle=\tiny,
        basicstyle=\rmfamily\scriptsize, 
        keywordstyle=\color{black}\bfseries,
        keywords={,procedure, div, for, to, input, output, return, datatype, function, in, if, else, foreach, while, begin, end, }
        numbers=left,
        xleftmargin=.04\textwidth,
        #1
    }
}
{}
\lstnewenvironment{java}[1][]
{   
    \lstset{
        language=java,
        mathescape=true,
        frame=tB,
        numbers=left, 
        numberstyle=\tiny,
        basicstyle=\ttfamily\scriptsize, 
        keywordstyle=\color{black}\bfseries,
        keywords={, int, double, for, return, if, else, while, }
        numbers=left,
        xleftmargin=.04\textwidth,
        #1
    }
}
{}

\newcommand\abs[1]{\lvert~#1~\rvert}
\newcommand{\st}{\mid}

\newcommand{\A}[0]{\texttt{A}}
\newcommand{\C}[0]{\texttt{C}}
\newcommand{\G}[0]{\texttt{G}}
\newcommand{\U}[0]{\texttt{U}}

\newcommand{\cmark}{\ding{51}}
\newcommand{\xmark}{\ding{55}}

  
\title{hw2-numbers}
\date{Due: 01/29/26 at 5pm (no penalty late submission until 8am next morning)}
\begin{document}
\maketitle
\thispagestyle{fancy}


{\bf In this assignment,}

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

{\bf Relevant class material}: Week 2 and Week 3.

You will submit this assignment via Gradescope
(\href{https://www.gradescope.com}{https://www.gradescope.com}) 
in the assignment called ``hw2-numbers''.

\instructions

{\bf Assigned questions}

\begin{enumerate}[labelindent=0pt, leftmargin=0pt]
\item 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 and review quiz, namely the function
$b^i$ with domain $\mathbb{Z}^+ \times \mathbb{N}$ and codomain $\mathbb{N}$ defined recursively by
\begin{align*}    
&\textrm{Basis Step:} \\
&b^0 = 1 \\
&\textrm{Recursive Step:}\\
&\textrm{If } i \in \mathbb{N}, b^{i+1} = b \cdot b^i
\end{align*}
and the algorithm:


\begin{algorithm}[caption={Calculating integer part of base $b$ logarithm}]
   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\}$
\end{algorithm} 

    \begin{enumerate}
    \item 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 and the review quiz for the level of detail expected
    in a trace of a function application and a trace table).
    \item Now we'll go in the other direction: 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).    
    \item 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.
    \end{enumerate}

\item Base expansions
    \begin{enumerate}
        \item 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).
        \item What is the {\bf 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.
        \item 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.
        \item Consider the strings of $1$s that have length $3$, $5$, $7$, and $10$.
        Calculate the numbers 
        \begin{multicols}{2}
            \begin{itemize}
            \item[] $[111]_{s,3}$
            \item[] $[11111]_{s,5}$
            \item[] $[1111111]_{s,7}$
            \item[] $[1111111111]_{s,10}$
            \item[] $[111]_{2c,3}$
            \item[] $[11111]_{2c,5}$
            \item[] $[1111111]_{2c,7}$
            \item[] $[1111111111]_{2c,10}$
            \end{itemize}
        \end{multicols}
        Justify your answers with specific reference to the definitions of sign-magnitude and $2$s complement expansions and relevant calculations and discuss any patterns you notice.
    \end{enumerate}

\item 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 a recent Review quiz question).

{\bf Definition}: A {\bf 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 $HC$. In the Week 2 Review quiz, 
we explored a few different set builder definitions for $HC$.

\begin{enumerate}
\item Rewrite the set builder definition of a set below so that it 
refers to colors rather than numbers: $\{ c \in HC \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.
\item Rewrite the set builder definition of a set below so that it 
refers to colors rather than numbers: $\{ c \in HC \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.
\item  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 {\bf hex color mixing} would be a function with domain $HC \times HC$
and codomain $HC$ 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$.


\rule{0.5\textwidth}{.4pt}

{\it 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: HC\times HC \to HC$ 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 $HC$.
Here is one such example: $(n_1, n_2) = (~(FFFFFF)_{16,6}, (FFFFFF)_{16,6}~)$. 
This example is in $HC \times HC$
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{align*}
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{align*}
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 {\bf fixed width $6$} expansion.

\rule{0.5\textwidth}{.4pt}

In this question, we'll look at another attempted mathematical definition for hex color mixing. 
We define $f_2: HC\times HC \to HC$ 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{align*}
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{align*}
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 \url{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.
\end{enumerate}
        \item Fixed-width addition.  
        \begin{enumerate}
            \item Choose example width $5$ first summand and width $5$ second summand so that 
            in the  binary fixed-width addition (adding one bit at time, using 
            the usual column-by-column and carry arithmetic, and ignoring the carry 
            from the  leftmost column), the example satisfies all three conditions below simultaneously
            \begin{itemize}
            \item[(1)] When interpreting each of the summands and the result in binary fixed-width 5, 
            the result represents the actual value of the sum of the summands {\bf and}
            \item[(2)] when interpreting each of the summands and the sum in sign-magnitude width 5, the result  
            represents the actual value of the sum of the summands {\bf and}
            \item[(3)] when interpreting each of the summands and the sum in 2s complement width 5, the result 
            represents the actual value of the sum of the summands.
            \end{itemize}
            \item Choose an example width $5$ first summand and second summand so that 
            in the binary fixed-width addition (adding one bit at time, using 
            the usual column-by-column and carry arithmetic, and ignoring the carry 
            from the  leftmost column),  the example satisfies all three conditions below simultaneously
            \begin{itemize}
            \item[(1)] When interpreting each of the summands and the result in binary fixed-width 5, 
            the result {\bf does not} represent the actual value of the sum of the summands {\bf and}
            \item[(2)] when interpreting each of the summands and the sum in sign-magnitude width 5, the result  
            {\bf does not} represents the actual value of the sum of the summands {\bf and}
            \item[(3)] when interpreting each of the summands and the sum in 2s complement width 5, the result 
            represents the actual value of the sum of the summands.
            \end{itemize}
            A complete solution will clearly specify each summand and the result of binary fixed-width addition 
            with this choice of summands; will specify  the value of each summand and the result for 
            binary fixed-width 5, 
            sign-magnitude width 5, and 2s complement width 5 (and include calculations connecting with the 
            definitions of these representations to explain these values); and a conclusion connecting
            the calculations to the properties laid out in the question.
        \end{enumerate}  
\end{enumerate}
\end{document}