Here are some questions about computing theory.

The questions are attached in the file

 

 

B401: Fundamentals of Computing Theory
Spring 2017
Assignment 1, due February 1st at the beginning of class
Exercise 1. Exercise 0.3 from Sipser, 2nd edition.
Exercise 2. For each of the following binary relations on Z, state whether they are
reflexive, symmetric, or transitive (they may be more than one or none):
• (a) <
• (b) ≤
• (c) {⟨x, y⟩ | x mod 3 = y mod 3}
• (d) {⟨x, y⟩ | |x − y| < 1}
• (e) {⟨x, y⟩ | |x − y| ≤ 1}
• (f) {⟨x, y⟩ | |x − y| > 1}
• (g) {⟨x, y⟩ | |x − y| = 1}
Exercise 3. Exercise 0.8 from Sipser, 2nd edition.
Exercise 4. Concisely describe what problem arises from considering “the set of all
sets” to be a valid set?
Exercise 5. Is “the total number of all natural numbers” a natural number? Concisely prove why or why not.
Exercise 6. Show that ∪ distributes over ∩, and ∩ distributes over ∪.
Exercise 7. Let’s define the set of binary trees as follows:
1. A tree with a single root r is in B
1 2. If r is a node and T1 ∈ B and T2 ∈ B (that is, T1 and T2 are binary trees), then
the tree T = (r, T1 , T2 ) ∈ B. T is the tree with root r, and r having T1 as its
left child and T2 as its right child.
Define a node of a binary tree to be full if it has both a non-empty left and a
non-empty right child. Prove by induction that the number of full nodes in a binary
tree is 1 less than the number of its leaves.
Exercise 8. Prove that for any undirected graph the number of odd-degree vertices
is even, and the sum of the degrees of all vertices is even.
Exercise 9. Let p be a prime number. Prove that √ p is an irrational number. Exercise 10. Decide if the following proof holds, and if not precisely identify what
part(s) are fallacious (e.g. “ Base case, statement 1, because I don’t think it’s trivial”
is not a correct or good answer, but is the form we’re looking for):
Claim: All food tastes the same! (Note that for the sake of this proof we assume
that the number of kinds of food in the universe is finite – which is NOT the issue
you are searching for in this exercise.)
Proof We will prove this claim by induction on the number of kinds of food k.
• Base Case (k = 0):
Show: For the base case we must demonstrate that for a set of 0 foods, all of
those foods taste the same. 1. The base case is trivial, since the claim is vacuously true when we are
considering 0 kinds of food.
• Inductive Hypothesis (IH): For any set of foods of fixed but arbitrary size
k, those k foods all taste the same.
• Inductive Step:
Show: For the inductive step, we must demonstrate that when assuming the
inductive hypothesis (IH), we can then prove that all foods in a set of k + 1
kinds of food indeed also all taste the same.
This part of the proof is straight forward as well:
2 1. Consider an arbitrary set of food F of size k.
2. By IH, all foods in F taste the same.
3. We want to show that we can add an arbitrary new kind of food f (where
f∈
/ F ) to F and that resulting set (F ∪ {f }) of size k + 1 is a set of food
that all tastes the same.
4. Note that if we remove an element f0 from F we get a set of size k − 1.
Call this set F ′ .
5. We can add f to this smaller set F ′ and get a set of size k.
6. By IH, F ′ ∪ {f } is a set food that all tastes the same.
7. Since the original set of food which tastes the same (F ) included f0 , then
f0 tastes the same as the food in F ′ which tastes the same (as we have
just shown) as the new food f , and since the property of “tasting the
same” is obviously transitive, then f0 tastes the same as f and thus the
set F ∪ {f }, which is of size k + 1, also all tastes the same.
8. Thus we have shown that adding a new arbitrary element to our arbitrary
set of size k (F ) maintains the “tastes the same” property and we have
constructed a suitable set of size k + 1 as we sought out to. QED 3

Attachments:

• 1493883385-mytaskOne.pdf