CSCI -Problem 1-4 Solution

Consider the third function de ned in EPI, Section 13.1 (Compute the Intersection of Two Sorted Arrays).

1. When we design an algorithm, we design the algorithm to solve a problem or answer a question. What is the problem that this algorithm solves?

2. Prove that the while loop terminates using a decrementing function.

Prove the following statement: Every tree with one or more nodes/vertices has exactly n 1 edges.

Consider the following statement: If a and b are odd numbers, then ab is an odd number.

1. What is the de nition of an odd number?

2. What is the de nition of an even number?

3. What is the contrapositive of this statement?

4. Prove this statement, using the contrapositive.