211L8Solutions

Exercises

1. Consider the FindFactors algorithm in Lecture 2. Prove that the algorithm is correct by using a loop invariant. Clearly state what invariant you use.

Loop invariant:

• i <= |n|

Proof:

• This algorithm starts where i is 1. If this is n, then the algorithm is finished, else it increments and checks if it is a factor. i is always increasing and so eventually it will reach |n|.

2. Consider the PathExistence algorithm in Lecture 3. Prove that the algorithm is correct by using a loop invariant. Clearly state what invariant you use.

Loop invariant:

• The number of vertices still to be marked is greater than or equal to zero.

Proof:

• This algorithm starts at a node s and moves along an edge to another node v. This node is then marked and it can be said that there is a path from s to v. As such, the number of visited nodes decreases. As the algorithm moves from v to the next node x, it can be said that a path must exist from s to x. The number of nodes still to be reached will always be decreasing but will never go below 0, thus the algorithm must stop.

3. Give a proof that the algorithm PatternMatching(string p, string t) terminates for any given input strings p and t.

For any given input strings p and t, the PatternMatching algorithm terminates. This is because the algorithm increments through each character in the text t checking at most t-p+1 characters and for each of those characters checking a further at most p characters.

4. Prove that the following four statements are equivalent to each other:

• (a) Every nonempty subset of natural numbers contains a smallest number.
• (b) Every decreasing sequence x1 > x2 > x3 > . . . of natural numbers is a finite sequence.
• (c) The first principle of mathematical induction.
• (d) The second principle of mathematical induction.

All decreasing sequences of natural numbers, will have a smallest number as the last element is always the smallest. (a) if (b). All decreasing sets are finite because the sets are constrained to have a smallest value of 0. (b) if (a). If it is true that the first element is the largest, and the next element is always smaller than the previous, then it must be true that for any element, all the preceding elements are smaller. if (c) then (b). If all elements before the current element are of decreasing order and it is always true that the next element is smaller or non-existant then it must be the case that there is a decreasing sequence. if (d) then (b).

5. Prove by induction that the number of strings of length n over a binary alphabet equals to 2n. (See Exercise 2c in Lecture 2).

For a string of length 1, there are 2 possible string combinations. Every time an extra digit is added to the string the last digit can take two different values (1 or 0). As such adding each consecutive digit adds a factor of two. Therefore, for any string of size n, there are 2n possible combinations.

6. Prove by induction that the number of strings of length at most n over binary alphabet equals to 2n+1 − 1. (See Exercise 2d in Lecture 2).

For a string of length 1, there are 2 possible string combinations. Every time an extra digit is added to the string the last digit can take two different values (1 or 0). As such adding each consecutive digit adds a factor of two. Therefore, for any string of size n, there are 2n possible combinations.

7. Prove by induction that for all n natural positive numbers the following equality is true: 1^2 + 2^2 + 3^2 + . . . + n^2 = (n · (n + 1) · (2n + 1))/6 .

1^2 = (1 · (1 + 1) · (2 + 1))/6, 1 = 1 1^2+2^2 = (2 · (2 + 1) · (4 + 1))/6, 5 = 5 For each consecutive squared term, the formula compensates to be the same for any positive natural number.

8. Prove that for all n positive natural numbers the value 11n − 4n is divisible by 7.

11n - 4n is the same as (11-4)n which is 7n. As such any number with a factor of 4 subtracted from a number of 11 leaves a number which can be written in the form 7n. This number therefore has a factor of 7 and is divisible by 7.

9. Prove n^2 > n + 1 for all natural numbers n >= 2.

Where n = 2,

• n^2 = 4
• n + 1 = 2

4>2 and there is a difference of two.

Where n = 3,

• n^2 = 9
• n + 1 = 4

9>4 and there is a difference of five.

This difference continues to increase at a rate of n + (n+1)^2 {In other words n^2} and therefor for all natural numbers > 1, n^2 > n + 1.

10. Write down the loop invariant theorem that corresponds to the second principle of mathematical induction.

S(n) is true for all values of n >= t

11. Prove the fundamental theorem of arithmetic (see Lecture 2) using the second principle of mathematical induction.

• Inductive hypothesis

All the number less than a number k are products of prime numbers.

If k is a prime number then the product of k is k itself. Assume that k is not prime. Then it is a product of smaller numbers s and t, that is k = s · t. By inductive assumption s and t are products of prime numbers. Hence, k must be a product of prime numbers as well.

12. Prove that for every natural number n there are integers a, b such that n = 2 · a + 3 · b.

Basis For the natural number 0, there is an a and b of 0 and 0 respectively. For the natural number 1, there is an a and b of -1 and 1 respectively. For the natural number 2, there is an a and b of -2 and 2 respectively. For the natural number 3, there is an a and b of -3 and 3 respectively.

For any n, there is an a of -n and b of n such that n = 2 · a + 3 · b. This mean that

n = 2 · (-n) + 3 · n
n = -2 · n + 3 · n
n = (3-2) · n
n = n

Which makes it clear that for any n, there are two integers with corresponding factors of 3 and 2 which can be used to make that number.

13. Using the second principle of mathematical induction prove that preorder(T) and postorder(T) algorithms in Lecture 5 print out all the nodes of T without repetition.

Both algorithms work on a basis of when there is a node with no unvisited children, that node is printed and the algorithm attempts to move to a parent. The inductive case is, if there are any unvisited children, move to an unvisited child until a child with no unvisited children are reached. The number of unvisited edges will always be decreasing and will be greater than or equal to 0.

14. This exercise defines the concept of ground term and term-trees in a more general setting. Suppose we are given a finite number of constants c0, c1, . . . , cm, and constructors fn1 0 , . . ., fns s . The number ni is called the arity of the constructor fni i . The arities of the constructors are non-zero natural numbers. Now we define ground terms as follows.

• (a) Basis: Every constant is a ground term.
• (b) Induction: : If t1, . . ., tni are ground terms then the expression fni i (t1, . . . , tni ) is also a ground term, where i � s.

Do the following:

• (a) Give inductive definition of term trees.
• (b) Prove by induction that the leaves of every term tree are labeled by constants, and the interior nodes by constructors.

15. Prove by induction that the factorial function (in Section 3) is correctly defined.

The base case is that the factorial of 1 is 1. The iterative process works by taking the previous smaller case and multiplying the current number to the product.

This loop invariant is that n >= 1. The n starts as the size of the number to find the factorial of. With each inductive step, this decreases until n is <=1. The stack of recursive operations then multiplies out the values of n until the factorial of the number is given.

16. Prove by induction that the algorithm Merge(A,B) (in Section 3) is correct.

17. Discuss the efficiency of the SelectionSort(A[], n) algorithm. Here it is assumed that it takes one unit of time to compare items A[i] and A[j] of the array A. Your discussion should be based on analysis of how much time it takes for the algorithm to stop when the size of an input array is n.

18. Discuss the efficiency of the MergeSort(X) algorithm. In your discussion compare it with the efficiency of the SelectionSort(A[], n) algorithm.