PS5.ProblemsECS 20: Discrete Mathematics for Computer Science
October 19, 2021
Problem Set 5 – Due Wednesday, October 27, at 5pm
1. Let x be the 32-bit IEEE 754 floating point number closest to the real number x (assume some
convention to deal with rounding). Exactly compute the 32-bit IEEE 754 product of ten and a
tenth, 10 (0.1). Exactly how far off are you from the desired answer of 1? If you like, you may use
a computer or online tool to assist you.
2. Show that each of the following languages are “regular” by writing them using nothing but con-
catenation, union, and star, applied to finite sets. Recall that the “star” operator is defined by
L∗ =
⋃
i∈N L
i.
(a) The language A of binary strings whose length is divisible by two or three
(b) The language B of all binary strings whose first two characters are the same as the last two
characters. Strings in this language must have two or more characters.
(c) The language C of all binary strings that do not contain two consecutive 1’s.
3. Recall our definition of a group G. Using just those three properties we specified, carefully prove
that:
(a) The identity element is unique (any two identities are the same).
(b) The inverse of any element is unique (any two inverses of a are the same).
4. Figure out which of the following relations ∼ are equivalence relations. As always, fully explain
your answers.
(a) x ∼ y if x and y are people who were born on the same day.
(b) x ∼ y if x and y are strings that contain a common character.
(c) x ∼ y if x and y are points in the plane that are equidistant to the origin.
(d) L ∼ L′ if L and L′ are parallel lines in the plane.
5. For a, b ∈ R define a ∼ b if a− b is an integer.
(a) Prove that ∼ is an equivalence relation.
(b) What is the equivalence class (block) containing 3? What is the equivalence class of 3.14?
That is, clearly describe the sets [3] = {y : 3 ∼ y} and [3.14] = {y : 3.14 ∼ y}.
(c) If you wanted to select for each equivalence class of ∼ a canonical representative, or name,
what name would you use? For example, what would be the canonical name for [π]?