Lab 01

Practice problems

Problems and topics listed here are for open discussion and practice. Feel free to work with a partner or ask the instructor questions. Towards the end of the lab period we may review some but not necessarily all answers. You are welcome to discuss solutions and strategies to these problems openly with classmates and the instructor outside of lab/class, on Piazza, and office hours.

Check the reading for next week and be sure to complete the reading, particularly 1.1-1.2, by Tuesday. Pay attention to the formal definition of the deterministic finite automata (DFA) and the formal definition of computation.

Sample Problems

You do not need to submit any solutions to these problems. This work will not be graded.

You may want to review the notes for this week. You may complete the problems in any order

True or False?

  1. $ \emptyset \subseteq \emptyset$
  2. $ \emptyset \in \emptyset$
  3. $ \emptyset \in \{ \emptyset \}$
  4. $ \emptyset \subseteq \{ \emptyset \}$
  5. $ \{ \{ a, b \} \} \in 2^{ \{ a, b , \{ a, b \} \} }$

  1. $2^{ \{ 7, 8, 9 \} } \setminus 2^{ \{ 7, 9 \} } = $?
  2. $2^\emptyset = $?

Are the following functions, relations, or neither?

  1. $\{ (a, b) : b = a^2 \}$
  2. $\{ (a, b) : a \geq b \}$
  3. $\{ (a, b) : b^2 = a \}$

The inverse of a binary relation $R \subseteq A \times B$, denoted $R^{-1}$ is a subset of $B \times A$ such that $(b,a) \in R^{-1}$ iff $(a, b) \in R$. The inverse of a relation is a relation.

  1. Is the inverse of a function a relation?
  2. Is it a function?
  3. What if $f$ is one-to-one?
  4. What if it is onto?
  5. A bijection?

Consider the alphabet $\Sigma = \{a, b, c\}$.

  1. Write all the strings of length 2 in $\Sigma^*$ in lexicographical order
  2. Write all the unique subsets of size 2 of $\Sigma$ in lexicographical order

Show that the set of integers $\mathbb{Z}=\{ \ldots, -2, -1, 0, 1, 2, \ldots \}$ is countably infinite by giving a bijection $f$ from $\mathbb{N}$ to $\mathbb{Z}$.

Prove that $n^2+n$ is divisible by 2 via induction

Prove that $n^2+n$ is divisible by 2 using a case based analysis and considering the case when $n$ is even and the case when $n$ is odd.