## 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.