Monday November 29

Recall:

A relation is an equivalence relation means it is reflexive, symmetric, and transitive.

An equivalence class of an element \(a \in A\) with respect to an equivalence relation \(R\) on the set \(A\) is the set \[\{s \in A \mid (a, s) \in R \}\] We write \([a]_R\) for this set, which is the equivalence class of \(a\) with respect to \(R\).

A partition of a set \(A\) is a set of non-empty, disjoint subsets \(A_1, A_2, \cdots, A_n\) such that \[A = \bigcup_{i=1}^{n} A_i = \{ x \mid \exists i (x \in A_i) \}\]

Claim: For each \(a \in U\), \([a]_{E} \neq \emptyset\).

Proof: Towards a \(\underline{\phantom{\hspace{1.3in}}}\) consider an arbitrary element \(a\) in \(U\). We will work to show that \([a]_E \neq \emptyset\), namely that \(\exists x \in [a]_E\). By definition of equivalence classes, we can rewrite this goal as \[\exists x \in U ~( ~(a,x) \in E~)\] Towards a \(\underline{\phantom{\hspace{1.3in}}}\), consider \(x = a\), an element of \(U\) by definition. By \(\underline{\phantom{\hspace{1.3in}}}\) of \(E\), we know that \((a,a) \in E\) and thus the existential quantification has been proved.
Claim: For each \(a \in U\), there is some \(b \in U\) such that \(a \in [b]_{E}\).

Towards a \(\underline{\phantom{\hspace{1.3in}}}\) consider an arbitrary element \(a\) in \(U\). By definition of equivalence classes, we can rewrite the goal as \[\exists b \in U ~( ~(b,a) \in E~)\] Towards a \(\underline{\phantom{\hspace{1.3in}}}\), consider \(b = a\), an element of \(U\) by definition. By \(\underline{\phantom{\hspace{1.3in}}}\) of \(E\), we know that \((a,a) \in E\) and thus the existential quantification has been proved.
Claim: For each \(a,b \in U\) , \((~(a,b) \in E ~\to ~ [a]_{E} = [b]_{E}~)\) and \((~(a,b) \notin E ~\to ~ [a]_{E} \cap[b]_{E} = \emptyset~)\)

Corollary: Given an equivalence relation \(E\) on set \(U\), \(\{ [x]_{E} \mid x \in U \}\) is a partition of \(U\).

Last time, we saw that partitions associated to equivalence relations were useful in the context of modular arithmetic. Today we’ll look at a different application.

Recall that in a movie recommendation system, each user’s ratings of movies is represented as a \(n\)-tuple (with the positive integer \(n\) being the number of movies in the database), and each component of the \(n\)-tuple is an element of the collection \(\{-1,0,1\}\).

We call \(Rt_5\) the set of all ratings \(5\)-tuples.

Define \(d: Rt_5 \times Rt_5 \to \mathbb{N}\) by \[d (~(~ (x_1, x_2, x_3, x_4, x_5), (y_1, y_2, y_3, y_4, y_5) ~) ~) = \sum_{i=1}^5 |x_i - y_i|\]

Consider the following binary relations on \(Rt_5\). \[E_{proj} = \{ ( ~(x_1, x_2, x_3, x_4, x_5), (y_1, y_2, y_3, y_4, y_5)~) \in Rt_5 \times Rt_5 ~\mid~(x_1 = y_1) \land (x_2 = y_2) \land (x_3 = y_3) \}\]

Example ordered pair in \(E_{proj}\):

Reflexive? Symmetric? Transitive? Antisymmetric?

\[E_{dist} = \{ (u,v) \in Rt_5 \times Rt_5 ~\mid~ d( ~(u,v)~ ) \leq 2 \}\] Example ordered pair in \(E_{dist}\):

Reflexive? Symmetric? Transitive? Antisymmetric?

\[E_{circ} = \{ (u,v) \in Rt_5 \times Rt_5 ~\mid~ d(~ ( ~(0,0,0,0,0)~, u)~ ) = d( ~(~(0,0,0,0,0),v~)~) \}\] Example ordered pair in \(E_{circ}\):

Reflexive? Symmetric? Transitive? Antisymmetric?

The partition of \(Rt_5\) defined by \(\underline{\phantom{E_{proj}}}\) is

The partition of \(Rt_5\) defined by \(E = \underline{\phantom{E_{circ}}}\) is

\(\begin{aligned} \{ ~~ & \\ &[ ~(0,0,0,0,0)~ ]_E \\ &, [ ~(0,0,0,0,1)~ ]_E \\ &, [ ~(0,0,0,1,1)~ ]_E \\ &, [ ~(0,0,1,1,1)~ ]_E \\ &, [ ~(0,1,1,1,1)~ ]_E \\ &, [ ~(1,1,1,1,1)~ ]_E \\ \qquad\} & \\ \end{aligned}\)

How many elements are in each part of the partition?

Review

  1. Select all and only the partitions of \(\{1,2,3,4,5\}\) from the sets below.

    1. \(\{1,2,3,4,5\}\)

    2. \(\{\{1,2,3,4,5\}\}\)

    3. \(\{\{1\},\{2\},\{3\},\{4\},\{5\}\}\)

    4. \(\{ \{1\}, \{2,3\}, \{4\} \}\)

    5. \(\{ \{\emptyset, 1, 2\}, \{3,4,5\}\}\)


  2. Select all and only the correct statements about an equivalence relation \(E\) on a set \(U\):

    1. \(E \in U \times U\)

    2. \(E = U \times U\)

    3. \(E \subseteq U \times U\)

    4. \(\forall x \in U ~([x]_E \in U)\)

    5. \(\forall x \in U ~([x]_E \subseteq U)\)

    6. \(\forall x \in U ~([x]_E \in \mathcal{P}(U))\)

    7. \(\forall x \in U ~([x]_E \subseteq \mathcal{P}(U))\)

Wednesday December 1

Scenario: Good morning! You’re a user experience engineer at Netflix. A product goal is to design customized home pages for groups of users who have similar interests. Your manager tasks you with designing an algorithm for producing a clustering of users based on their movie interests, so that customized homepages can be engineered for each group.

Conventions for today: We will use \(U = \{r_1, r_2, \cdots, r_t\}\) to refer to an arbitrary set of user ratings (we’ll pick some specific examples to explore) that are a subset of \(Rt_5\). We will be interested in creating partitions \(C_1, \cdots, C_m\) of \(U\). We’ll assume that each user represented by an element of \(U\) has a unique ratings tuple.

Your idea: equivalence relations! You offer your manager three great options:

\[E_{id} = \{ ( ~(x_1, x_2, x_3, x_4, x_5), (x_1, x_2, x_3, x_4, x_5)~) \mid (x_1, x_2, x_3, x_4, x_5) \in Rt_5 \}\]

Describe how each homepage should be designed …

\[E_{proj} = \{ ( ~(x_1, x_2, x_3, x_4, x_5), (y_1, y_2, y_3, y_4, y_5)~) \in Rt_5 \times Rt_5 ~\mid~(x_1 = y_1) \land (x_2 = y_2) \land (x_3 = y_3) \}\]

Describe how each homepage should be designed …

\[E_{circ} = \{ (u,v) \in Rt_5 \times Rt_5 ~\mid~ d(~ ( ~(0,0,0,0,0)~, u)~ ) = d( ~(~(0,0,0,0,0),v~)~) \}\]

Describe how each homepage should be designed …

Scenario: Good morning! You’re a user experience engineer at Netflix. A product goal is to design customized home pages for groups of users who have similar interests. You task your team with designing an algorithm for producing a clustering of users based on their movie interests. Your team implements two algorithms that produce different clusterings. How do you decide which one to use? What feedback do you give the team in order to help them improve? Clearly, you will need to use math.

Your idea: find a way to score clusterings (partitions)

Definition: For a cluster of ratings \(C = \{r_1, r_2, \cdots, r_n \} \subseteq U\), the diameter of the cluster is defined by:

\[\textit{diameter}(C) = \max_{1 \leq i, j \leq n} (d(~(r_i, r_j)~))\]

Consider \(x = (1, 0, 1, 0, 1)\), \(y = (1, 1, 1, 0, 1)\), \(z = (-1, -1, 0, 0, 0)\), \(w = (0, 0, 0, 1, 0)\).

What is \(\textit{diameter}(\{x, y, z\})\)? \(\textit{diameter}(\{x, y\})\)? \(\textit{diameter}(\{x, z, w\})\)?

diameter works on single clusters. One way to aggregate across a clustering \(C_1, \cdots, C_m\) is \(\sum_{k=1}^m diameter(C_k)\)

Is this a good score?

How can we express the idea of many elements within a small area? Key idea: “give credit” to small diameter clusters with many elements.

Definition: For a cluster of ratings \(C = \{r_1, r_2, \cdots, r_n \} \subseteq U\), the density of the cluster is defined by: \[\frac{n}{1+ diameter(C)}\]

Can you use density to decide whether the partition given by the equivalence classes of \(E_{proj}\) or \(E_{circ}\) for this task?

Looking forward

Tips for future classes from the CSE 20 TAs and tutors

CSE department course numbering system

Lower division

Upper division

Review


  1. Assume there are five movies in the database, so that each user’s ratings can be represented as a \(5\)-tuple. We call \(Rt_5\) the set of all ratings \(5\)-tuples. Consider the binary relation on the set of all \(5\)-tuples where each component of the \(5\)-tuple is an element of the collection \(\{-1,0,1\}\) \[G_1 = \{ (u,v) \mid \text{the ratings of users $u$ and $v$ agree about the first movie in the database} \}\] \[G_2 = \{ (u,v) \mid \text{the ratings of users $u$ and $v$ agree about at least two movies} \}\]

    1. True or False: The relation \(G_1\) holds of \(u=(1,1,1,1,1)\) and \(v=(-1,-1,-1,-1,-1)\)

    2. True or False: The relation \(G_2\) holds of \(u=(1,0,1,0,-1)\) and \(v=(-1,0,1,-1,-1)\)

    3. True or False: \(G_1\) is reflexive; namely, \(\forall u ~(~(u,u) \in G_1~)\)

    4. True or False: \(G_1\) is symmetric; namely, \(\forall u ~\forall v ~(~(u,v) \in G_1 \to (v,u) \in G_1~)\)

    5. True or False: \(G_1\) is transitive; namely, \(\forall u ~\forall v ~\forall w (~\left( (u,v) \in G_1 \wedge (v,w)\in G_1\right) \to (u,w) \in G_1~)\)

    6. True or False: \(G_2\) is reflexive; namely, \(\forall u ~(~(u,u) \in G_2~)\)

    7. True or False: \(G_2\) is symmetric; namely, \(\forall u ~\forall v ~(~(u,v)\in G_2 \to (v,u) \in G_2~)\)

    8. True or False: \(G_2\) is transitive; namely, \(\forall u~\forall v ~\forall w (~\left( (u,v) \in G_2 \wedge (v,w)\in G_2\right) \to (u,w) \in G_2~)\)


  2. Recall that in a movie recommendation system, each user’s ratings of movies is represented as a \(n\)-tuple (with the positive integer \(n\) being the number of movies in the database), and each component of the \(n\)-tuple is an element of the collection \(\{-1,0,1\}\).

    We call \(Rt_5\) the set of all ratings \(5\)-tuples.

    Define \(d: Rt_5 \times Rt_5 \to \mathbb{N}\) by \[d (~(~ (x_1, x_2, x_3, x_4, x_5), (y_1, y_2, y_3, y_4, y_5) ~) ~) = \sum_{i=1}^5 |x_i - y_i|\]

    For a cluster of ratings \(C = \{r_1, r_2, \cdots, r_n \} \subseteq U\), the diameter of the cluster is defined by:

    \[\textit{diameter}(C) = \max_{1 \leq i, j \leq n} (d(~(r_i, r_j)~))\]

    1. Calculate \(diameter( \{ (-1,-1,-1,-1,1), (0,0,0,0,0), (1,1,1,1,1) \} )\)

    2. What’s the greatest (possible) diameter of a collection that has exactly two (distinct) ratings \(5\)-tuples?

    3. What’s the least (possible) diameter of a collection that has exactly two (distinct) ratings \(5\)-tuples?

Friday December 3

Convert \((2A)_{16}\) to

The bases of RNA strands are elements of the set \(B = \{\texttt{A}, \texttt{C}, \texttt{G}, \texttt{U}\}\). 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.

Each of the sets below is described using set builder notation. Rewrite them using the roster method.

Certain sequences of bases serve important biological functions in translating RNA to proteins. The following recursive definition gives a special set of RNA strands: The set of RNA strands \(\hat{S}\) is defined (recursively) by

\[\begin{aligned} {2} \text{Basis step:} & & \texttt{A}\texttt{U}\texttt{G}\in \hat{S}\\ \text{Recursive step:} & \qquad& \text{If } s \in \hat{S} \text{ and } x \in R \text{, then } sx\in \hat{S}\\ \end{aligned}\] where \(R = \{ \texttt{U}\texttt{U}\texttt{U}, \texttt{C}\texttt{U}\texttt{C}, \texttt{A}\texttt{U}\texttt{C}, \texttt{A}\texttt{U}\texttt{G}, \texttt{G}\texttt{U}\texttt{U}, \texttt{C}\texttt{C}\texttt{U}, \texttt{G}\texttt{C}\texttt{U}, \texttt{U}\texttt{G}\texttt{G}, \texttt{G}\texttt{G}\texttt{A}\}\).

Each of the sets below is described using set builder notation. Rewrite them using the roster method.

Let \(W = \mathcal{P}( \{ 1,2,3,4,5\})\). Consider the statement \[\forall A \in W~ \forall B \in W ~ \forall C \in W~ ((A \cap B = A \cap C) \to (B=C) )\] Translate the statement to English. Negate the statement and translate this negation to English. Decide whether the original statement or its negation is true and justify your decision.

The set of linked lists of natural numbers \(L\) is defined by \[\begin{aligned} {2} \text{Basis step:} & &[] \in L \\ \text{Recursive step:} & \qquad& \text{If } l \in L \text{ and } n \in \mathbb{N} \text{, then } (n,l) \in L\\ \end{aligned}\] The function \(length: L \to \mathbb{N}\) that computes the length of a list is \[\begin{aligned} {2} \text{Basis step:} & &length([]) = 0\\ \text{Recursive step:} & \qquad& \text{If $l \in L$ and $n \in \mathbb{N}$, then } length( ( n,l) ) = 1 + length(l)\\ \end{aligned}\]

Prove or disprove: the function \(length\) is onto.

Prove or disprove: the function \(length\) is one-to-one.

Suppose \(A\) and \(B\) are sets and \(A \subseteq B\):

True or False? If \(A\) is infinite then \(B\) is finite.

True or False? If \(A\) is countable then \(B\) is countable.

True or False? If \(B\) is infinite then \(A\) is finite.

True or False? If \(B\) is uncountable then \(A\) is countable.

Compute the last digit of \[(42)^{2021}\]

Extra Describe the pattern that helps you perform this computation and prove it using mathematical induction.

Review


  1. Please complete the CAPE and TA evaluations. Once you have done so complete the custom feedback form for this quarter: https://forms.gle/pbYWSRDP2znkciM46

    Then, (we’re using the honor system here), write out the statement “I have completed the end of quarter evaluations" and you’ll receive credit for this question.

  1. iclickers are used in many classes to encourage active participation in class. They’re remotes that allow you to respond to multiple choice questions and the instructor can show a histogram of responses in real time.↩︎