HW1 Definitions and Notation

In this assignment,

You will practice reading and applying definitions to get comfortable working with mathematical language. As a result, you can expect to spend more time reading the questions and looking up notation than doing calculations.

For all HW assignments:

Weekly homework may be done individually or in groups of up to 3 students. You may switch HW partners for different HW assignments. The lowest HW score will not be included in your overall HW average. Please ensure your name(s) and PID(s) are clearly visible on the first page of your homework submission.

All submitted homework for this class must be typed. Diagrams may be hand-drawn and scanned and included in the typed document. 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 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 we will use this quarter.

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

You will submit this assignment via Gradescope (https://www.gradescope.com) in the assignment called “hw1-definitions-and-notation”.

Resources: To review the topics you are working with for this assignment, see the class material from Week 0 and 1. We will post frequently asked questions and our answers to them in a pinned Piazza post.

Assigned questions

1. (Graded for correctness²) Each of the sets below is described using set builder notation or as a result of set operations applied to other known sets. Rewrite them using the roster method.

   Remember our discussions of data-types: use clear notation that is consistent with our class notes and definitions to communicate the data-types of the elements in each set.

   ---

   Sample response that can be used as reference for the detail expected in your answer:

   The set \(\{ \texttt{A}\} \circ \{ \texttt{A}\texttt{U}, \texttt{A}\texttt{C}, \texttt{A}\texttt{G}\}\) can be written using the roster method as \[\{ \texttt{A}\texttt{A}\texttt{U}, \texttt{A}\texttt{A}\texttt{C}, \texttt{A}\texttt{A}\texttt{G}\}\] because set-wise concatenation gives a set whose elements are all possible results of concatenating an element of the left set with an element of the right set. Since the left set in this example only has one element (\(\texttt{A}\)), each of the elements of the set we described starts with \(\texttt{A}\). There are three elements of this set, one for each of the distinct elements of the right set.

   ---

   1. \[\{ x \in S \mid rnalen(x) = 1 \} \circ \{x \in S \mid rnalen(x) = 1 \}\] where \(S\) is the set of RNA strands and \(rnalen\) is the recursively defined function that we discussed in class.

   2. \[\{ (r,g,b) \in C \mid r+g+b = 1\}\] where \(C = \{ (r,g,b) \mid 0 \leq r \leq 255, 0 \leq g \leq 255, 0 \leq b \leq 255, r \in \mathbb{N}, g \in \mathbb{N}, b \in \mathbb{N} \}\) is the set that you worked with in Monday’s review quiz.

   3. \[\{ a \in \mathbb{Z} \mid a \textbf{ div } 2 = a \textbf{ mod } 2\}\]

2. (Graded for fair effort completeness³)

   1. In Wednesday’s review quiz, you considered some attempted recursive definitions for the function with domain \(\mathbb{N}\) and with codomain \(\mathbb{Z}\) which gives \(2^n\) for each \(n\). Write out a correct recursive definition of this function.

   2. How would your answer to part (a) change if we consider a new function with the same domain and rule but whose codomain is \(\mathbb{R}\)?

   3. How would your answer to part (a) change if we consider a new function with the same codomain and rule but whose domain is \(\mathbb{R}\)?

   4. Write a recursive definition of the function with domain \(\mathbb{Z}^+\), codomain \(\mathbb{Z}^+\) and which gives \(n!\) for each \(n\). The \(!\) symbol is the “factorial” symbol and means that we need to multiple \(n\) by each of the integers between it and \(1\) inclusive. For example, \(5! = 5 \cdot 4 \cdot 3 \cdot 2 \cdot 1 = 120\).

3. (Graded for correctness) Recall the function \(d_0\) which takes an ordered pair of ratings \(3\)-tuples and returns a measure of the distance between them given by \[d_0 (~(~ (x_1, x_2, x_3), (y_1, y_2, y_3) ~) ~) = \sqrt{ (x_1 - y_1)^2 + (x_2 - y_2)^2 + (x_3 -y_3)^2}\]

   ---

   Sample response that can be used as reference for the detail expected in your answers for this question:

   To give an example of two \(3\)-tuples that are \(d_0\) distance \(1\) from each other, consider the \(3\)-tuples \((1,0,0)\) and \((0,0,0)\). We calculate the function application: \[\begin{aligned} d_0 (~(~ (1, 0,0), (0,0,0) ~) ~) &= \sqrt{ (1 - 0)^2 + (0 - 0)^2 + (0 -0)^2} = \sqrt{1^2 + 0^2 + 0^2} = \sqrt{1} = 1, \end{aligned}\] which is the result required for this example.

   ---

   1. Give an example of three \(3\)-tuples \[\begin{aligned} &(x_{1,1}, x_{1,2}, x_{1,3}) \\ &(x_{2,1}, x_{2,2}, x_{2,3}) \\ &(x_{3,1}, x_{3,2}, x_{3,3}) \\ \end{aligned}\] that are all \(d_0\) distance greater than \(1\) from each other. In other words, for each \(i\) and \(j\) between \(1\) and \(3\) (with \(i \neq j\)), \[d_{0}(~(~(x_{i,1}, x_{i,2}, x_{i,3}) , (x_{j,1}, x_{j,2}, x_{j,3})~)~) > 1\]

      Your answer should include both specific values for each example \(3\)-tuple and a justification of your examples with (clear, correct, complete) calculations and/or references to definitions and connecting them with the desired conclusion.
      To think about: how will you justify that the square root of a number is greater than \(1\)? Are calculations from a calculator accurate enough to help us?

   2. What is the range of values that results from applying the function \(d_0\) to ordered pairs of \(3\)-tuple ratings? That is, what are the smallest and largest possible results?

      Your answer should include both specific values for the smallest and largest possible results and a justification of your answers with (clear, correct, complete) calculations and/or references to definitions and connecting them with the desired conclusion.