1. Leaps and Bounds

Let T(n) denote the running time of some algorithm, where n is the size of the input. Suppose that this running time satisfies the following equations:

T(n) = 8 if n = 1

T(n) = T(bn/2c) + 9bn/3c + 4 for all n > 1

Use strong induction to prove this upper bound on the running time: for all n 1, we have T(n) 10n.

Hint: The only facts about bc that you will need are that, for all x R, bxc is an integer satisfying bxc x and, additionally, when x 1, we also have bxc 1.

(This running time could arise, for example, if the algorithm operates on an input of size n by, first, performing some work that takes 9bn/3c + 4 steps and then calling itself recursively on an input of half that size.)

2. And Then Sum

Let S be the set defined as follows.

Basis Step: 4 S; 7 S

Recursive Step: if x,y S, then x + y S.

Show that, for all integers n 18, we have n S.

Hint: Strong induction is the right tool here since the quantifier is not over S.

3. Some Strings Attached

For each of the following, write a recursive definition of the set of strings satisfying the given properties. Briefly justify why your solution is correct.

• Binary strings x {0,1} whose length |x| satisfies |x| 2 (mod 3).
• Binary strings that do not contain a substring of the form 111 with odd length.
• Binary strings that have at least one 1 and an even number of 0s.
• Strings of parentheses (i.e., over the alphabet = {(,)}) where left and right parentheses occur in matched pairs that are properly nested. E.g, (())() is included but ())(() is not: even though both have 3 left parentheses and 3 right parentheses, those in the second string are not properly nested.

4. Tied Up With Strings [Online]

For each of the following, construct regular expressions that match the given set of strings:

• Binary strings x {0,1} whose length |x| satisfies |x| 2 (mod 3).
• Binary strings that start with a 1 and have an even number of 0s. (c) [4 Points] Binary strings that have at least one 1 and an even number of 0s.
• ] Binary strings with at least two 1s.
• Binary strings with at least two 1s or at most two 0s.

5. Wish List

We then define the set Lists as follows:

Basis Elements: null Lists.

Recursive Step: for any x Z, if L Lists, then Node(x,L) Lists.

These are lists (essentially, linked lists) with integer values stored in the nodes.

The following function, which takes two lists as arguments, appends the elements from the first list to the front of the second list but in reverse order:

shift(null,R) = R for any R Lists

shift(Node(x,L),R) = shift(L,Node(x,R)) for any x Z and L,R Lists

We can then define the following function that reverses a list:

reverse(L) = shift(L,null) for all L Lists

Since the second list passed to shift is empty, the result is just the reversal of the first list.

Now, let f : Z Z be a function that takes an integer input and returns an integer output. Then, we define the following function, which takes a list containing the numbers x₁,x₂, and returns a list containing the numbers f(x₁),f(x₂),:

map_f(null) = null

map_f(Node(x,L) = Node(f(x),map_f(L))) for any x Z and L Lists

• Let f : Z Z be the function defined by f(x) := 2x + 1. Use the definitions to calculate reverse(map_f(L)), where L is the list Node(1,Node(2,Node(3,null))). Show your work.
• Prove that we have map_f(shift(L,R)) = shift(map_f(L),map_f(R)) for any L,R Lists by structural induction on L.
• Prove that map_f(reverse(L)) = reverse(map_f(L)) for all L Lists.

6. Extra Credit: Sticks And Stones

Consider an infinite sequence of positions 1,2,3, and suppose we have a stone at position 1 and another stone at position 2. In each step, we choose one of the stones and move it according to the following rule: Say we decide to move the stone at position i; if the other stone is not at any of the positions i + 1,i + 2,,2i, then it goes to 2i, otherwise it goes to 2i + 1.

For example, in the first step, if we move the stone at position 1, it will go to 3 and if we move the stone at position 2 it will go to 4. Note that, no matter how we move the stones, they will never be at the same position.

Use induction to prove that, for any given positive integer n, it is possible to move one of the stones to position n. For example, if n = 7 first we move the stone at position 1 to 3. Then, we move the stone at position 2 to 5 Finally, we move the stone at position 3 to 7.