All topics from Lectures 0 􀀀 12 are relevant for the midterm, including regular expressions
(but not including the pumping lemma). You should, in particular be comfortable with all
questions that have appeared in the rst two assignments, or have been solved during the
tutorials. Below, I am listing some additional practice questions.

Problem 1.

Recall that we use the notation $[n]$ to denote the set $\{1,2,3, \ldots, n\}$ of natural numbers from 1 to $n$. For the following pairs of sets $A$ and $B$, determine their relation (that is show if one of $\subseteq, \subsetneq,=$ or none of these holds between them. Further determine their intersections. (a) $A=\{n \in \mathbb{Z} \mid \exists k \in \mathbb{Z}, k \geq 0$ such that $n=3 k$ and $n \leq 20\}$ and $B=\{3,6,9,12,15,18\}$. (b) $A=\{1,3\} \times\{1,2\}$ and $B=\{(1,1),(2,1),(3,1)\}$. (c) $A=\{3,6,9,12,15,18\} \cap\{n \in \mathbb{N} \mid n$ even $\}$ and $B=[20] \backslash\{n \in \mathbb{N} \mid n$ odd $\}$ (d) $A=\mathcal{P}(\{1,2\} \times\{1\})$ and $B=\{1,2\}^2 \cup\{\emptyset\}$

(a) $A$ is the set of all integers that are multiples of 3 and are less than or equal to 20. Thus $A={3,6,9,12,15,18}$. Since $A$ contains only six elements and each of them is also an element of $B$, we have $A \subseteq B$. On the other hand, $B$ contains only elements that are multiples of 3 and less than or equal to 18, whereas $A$ contains an additional element 20 that is not in $B$. Hence $B \subsetneq A$. The intersection of $A$ and $B$ is $A \cap B = {3,6,9,12,15,18}$.

(b) $A$ is the set of all ordered pairs $(1,1)$, $(1,2)$, $(3,1)$, and $(3,2)$, whereas $B$ is the set of ordered pairs $(1,1)$, $(2,1)$, and $(3,1)$. Thus $B$ is a proper subset of $A$, and we have $B \subsetneq A$. The intersection of $A$ and $B$ is $A \cap B = {(1,1),(3,1)}$.

Problem 2.

Let $G=(V, E)$ be a graph. (By default we assume an undirected graph.) Show that being connected by a path is an equivalence relation on the vertices of the graph (consider each vertex to be connected by a path of length 0 to itself). Is being connected by a (directed) path also an equivalence relation in a directed graph?

To show that being connected by a path is an equivalence relation on the vertices of an undirected graph $G=(V,E)$, we need to show that it satisfies the following three properties:

1. Reflexivity: Every vertex is connected to itself by a path of length 0.
2. Symmetry: If vertex $u$ is connected to vertex $v$ by a path, then vertex $v$ is connected to vertex $u$ by a path.
3. Transitivity: If vertex $u$ is connected to vertex $v$ by a path and vertex $v$ is connected to vertex $w$ by a path, then vertex $u$ is connected to vertex $w$ by a path.

Proof:

1. Reflexivity: Every vertex is connected to itself by a path of length 0. Therefore, being connected by a path is reflexive.
2. Symmetry: Let $u$ and $v$ be two vertices in $G$ such that $u$ is connected to $v$ by a path. Let $P$ be a path in $G$ from $u$ to $v$. We can simply reverse the order of the vertices in $P$ to obtain a path from $v$ to $u$. Therefore, being connected by a path is symmetric.
3. Transitivity: Let $u$, $v$, and $w$ be three vertices in $G$ such that $u$ is connected to $v$ by a path and $v$ is connected to $w$ by a path. Let $P_1$ be a path in $G$ from $u$ to $v$ and let $P_2$ be a path in $G$ from $v$ to $w$. We can concatenate $P_1$ and $P_2$ to obtain a path from $u$ to $w$. Therefore, being connected by a path is transitive.

Since being connected by a path satisfies all three properties of an equivalence relation, it is indeed an equivalence relation on the vertices of an undirected graph.

For a directed graph, being connected by a path is not necessarily an equivalence relation. Specifically, it may not be symmetric. For example, consider the directed graph with vertices $u$, $v$, and $w$ and edges $(u,v)$ and $(v,w)$. Vertex $u$ is connected to vertex $v$ by a path, and vertex $v$ is connected to vertex $w$ by a path, but vertex $w$ is not connected to vertex $u$ by a path. Therefore, being connected by a (directed) path is not an equivalence relation in a directed graph.

Problem 3.

Consider the pairs of sets $A$ and $B$ from the first question. For which ones does the exist a function $f: A \rightarrow B$ that is one-to-one? For which ones does there exist a function $g: A \rightarrow B$ that is onto?

To determine whether there exists a one-to-one function $f:A\rightarrow B$, we need to check whether each element of $A$ is assigned to a distinct element of $B$. If there exists such a function, we say that $A$ can be injected into $B$.

To determine whether there exists an onto function $g:A\rightarrow B$, we need to check whether every element of $B$ is the image of at least one element of $A$. If there exists such a function, we say that $A$ can be surjected onto $B$.

(a) $A = {1, 2, 3, 4}$ and $B = {1, 2, 3}$.

There exists a one-to-one function $f:A\rightarrow B$ if and only if $|A|\leq |B|$. In this case, we have $|A|=4$ and $|B|=3$, so there cannot exist a one-to-one function from $A$ to $B$.

There exists an onto function $g:A\rightarrow B$ if and only if $|A|\geq |B|$. In this case, we have $|A|=4$ and $|B|=3$, so there cannot exist an onto function from $A$ to $B$.

(b) $A = {a, b, c}$ and $B = {1, 2, 3, 4}$.

There exists a one-to-one function $f:A\rightarrow B$ if and only if $|A|\leq |B|$. In this case, we have $|A|=3$ and $|B|=4$, so there exists a one-to-one function from $A$ to $B$. For example, we can define $f(a)=1$, $f(b)=2$, and $f(c)=3$.

There exists an onto function $g:A\rightarrow B$ if and only if $|A|\geq |B|$. In this case, we have $|A|=3$ and $|B|=4$, so there cannot exist an onto function from $A$ to $B$.

Problem 4.

Prove that in any graph that is a tree, we have
$$|V|=|E|+1 .$$

Let $G=(V,E)$ be a tree. We can prove the given result by induction on the number of vertices in $G$.

Base Case: If $G$ has only one vertex, then there are no edges, and $|V|=1$ and $|E|=0$. Hence, $|V|=|E|+1$ holds.

Inductive Step: Assume that for any tree $T$ with $k$ vertices, we have $|V|=|E|+1$. Now, let $G$ be a tree with $k+1$ vertices. Choose any leaf vertex $v$ of $G$. By definition of a leaf, $v$ has degree 1, and is connected to only one other vertex $u$. Let $G’$ be the tree obtained from $G$ by removing $v$ and the edge $(u,v)$. Then, $G’$ has $k$ vertices and $k-1$ edges. By the induction hypothesis, we have $|V(G’)|=|E(G’)|+1$.

Now, adding the vertex $v$ and the edge $(u,v)$ back to $G’$ forms the tree $G$ with $k+1$ vertices and $k$ edges. Thus, \begin{align*} |V(G)| &= |V(G’)| + 1 \ &= |E(G’)| + 2 && \text{(by induction hypothesis)}\ &= k-1 + 2 \ &= k+1 \ &= |E(G)| + 1. \end{align*} Therefore, the equation $|V|=|E|+1$ holds for any tree $G=(V,E)$, by induction on the number of vertices.

QR分解，Schmidt正交化,least sqaure method代写成功案例