Description
Problem 1. (25 points)
1. Give a recursive definition for the set of bitstrings that have more 0s than 1s.
2. Give a recursive definition for the set of bitstrings that have twice as many 0s as 1s.Problem 2. (25 points)
The reversal of a string w, denoted w
R, is the string consisting of the symbols of w in reverse order.
1. Give a recursive definition for the reversal of a string. Hint: First define the reversal of the empty
string. Then write a string w of length n + 1 as xy, where x is a string of length n and y ∈ Σ, and
express the reversal of w in terms of x
R and y.
2. Use structural induction to prove that (w1w2)
R = w
R
2 w
R
1
.
Problem 3. (25 points)
The set of leaves and the set of internal vertices of a full binary tree can be defined recursively.
Basis Step: The root r is a leaf of the full binary tree with exactly one vertex r. This tree has no internal vertices.
Recursive Step: The set of leaves of the tree T = T1 · T2 is the union of the sets of leaves of T1 and of
T2. The internal vertices of T are the root r of T and the union of the sets of internal vertices of T1 and of
T2.
Use structural induction to prove that ℓ(T), the number of leaves of a full binary tree T, is 1 more than i(T),
the number of internal vertices of T.Problem 4. (25 points)
1. Give a recursive algorithm for finding the reversal of a string.
2. Prove that your recursive algorithm is correct.
