Description
1. Leaps and Bounds (16 points)
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 b · c 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 (20 points)
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 (20 points)
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.
(a) [5 Points] Binary strings x ∈ {0, 1}
∗ whose length |x| satisfies |x| ≡ 2 (mod 3).
(b) [5 Points] Binary strings that do not contain a substring of the form “11 · · · 1” with odd length.
(c) [5 Points] Binary strings that have at least one 1 and an even number of 0s.
(d) [5 Points] 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.
1
4. Tied Up With Strings [Online] (20 points)
For each of the following, construct regular expressions that match the given set of strings:
(a) [4 Points] Binary strings x ∈ {0, 1}
∗ whose length |x| satisfies |x| ≡ 2 (mod 3).
(b) [4 Points] 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.
(d) [4 Points] Binary strings with at least two 1s.
(e) [4 Points] Binary strings with at least two 1s or at most two 0s.
Submit and check your answers to this question here:
https://grinch.cs.washington.edu/cse311/regex
Think carefully about your answer to make sure it is correct before submitting.
You have only 5 chances to submit a correct answer.
5. Wish List (24 points)
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 x1, x2, . . . and returns a list containing the
numbers f(x1), f(x2), . . . :
mapf
(null) = null
mapf
(Node(x, L) = Node(f(x), mapf
(L))) for any x ∈ Z and L ∈ Lists
(a) [4 Points] Let f : Z → Z be the function defined by f(x) := 2x + 1. Use the definitions to calculate
reverse(mapf
(L)), where L is the list Node(1, Node(2, Node(3, null))). Show your work.
(b) [16 Points] Prove that we have mapf
(shift(L, R)) = shift(mapf
(L), mapf
(R)) for any L, R ∈ Lists by
structural induction on L.
(c) [4 Points] Prove that mapf
(reverse(L)) = reverse(mapf
(L)) for all L ∈ Lists.
2
6. Extra Credit: Sticks And Stones (0 points)
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.
3
