Question

Question 1: Complexity

Take a look at the following algorithm written in pseudocode:

procedure mystery(a1, a2, …, an: integer)

i := 1

while (i < n and ai ≤ ai+1)

i := i + 1

if i == n then print “Yes!”

else print “No!”

1. What property of the input sequence {an} does this algorithm test?

2. What is the computational complexity of this algorithm, i.e., the number of comparisons being computed as a function of the input size n?

3. Provide a reasonable upper bound for the growth of the complexity function by using the big-O notation (no proof necessary).

Question 2: The Boston Powerflower

Botanists at UMass Boston recently discovered a new local flower species that they named the Boston powerflower. It has a beautiful, blue blossoms, and each plant lives for only one summer. During that time, each plant produces ten seeds. Two of these seeds will turn into plants in the following year, and the remaining eight seeds will turn into flowers the year after. As the name powerflower suggests, these seeds always turn into flower plants; there is no failure ever.

During the year of this discovery (let us call it year one), the scientists found two powerflowers on the UMass campus, and in the following year, there were already four of them.

1. Devise a recurrence relation for the number of flower plants fn in year n, and specify the initial conditions.

2. Use the above recurrence relation to predict the number of plants on the UMass campus in years 3, 4, 5, and 6.

3. Find an explicit formula for computing the number of plants in any given year without requiring iteration, i.e., repeated application of a formula. You should (but do not have to) check the correctness of your formulas using some of the results you obtained in (b). Remember that our initial conditions are for a1 and a2.

Question 3: Induction

a. Use mathematical induction to show that the following equation is true for all natural numbers n:

20 + 21 + 22 + … + 2n = 2n+1 – 1

b. Show by induction that every power of 6 ends in 6.

Question 4: Prime Factor Examples

Write down the prime factorization (in ascending order) of each of the following integers
(Example: 720 = 24⋅32⋅5).

1. 16777216

2. 103

3. 255

4. 10000

Question 5: Euclidean Algorithm

Use the Euclidean algorithm to determine the following greatest common divisors. Write down every step in your calculation.

1. Gcd(12211, 10422)

2. gcd(1755, 855)

3. gcd(62525, 625)

Answer 1

Answer 1)

It tests the property that whether the elements of the input sequence are in non-decreasing order.

Number of computations: In worst case there might be n comparisons of i < n and n comparisons of ai < ai+1 . Also, theres a single comparison  i == n. So, there are a total of (2n + 1) comparisons.

Complexity : O(n) [Since, O(2n+1) = O(n)]

Answer 2)

Devise a recurrence relation for the number of flower plants fn in year n, and specify the initial conditions.

Recurrence relation: fn= 2fn-1+8fn-2

Initial conditions: f1= 2, f2= 4

Use the above recurrence relation to predict the number of plants on the UMass campus in years 3, 4, 5, and 6.

f3= 2f2+8f1= 8 + 16 = 24

f4= 2f3+8f2= 48 + 32 = 80

f5= 2f4+8f3= 160 + 192 = 352

f6= 2f5+8f4= 704 + 640 = 1344

Find an explicit formula for computing the number of plants in any given year without requiring iteration, i.e., repeated application of a formula. You should (but do not have to) check the correctness of your formulas using some of the results you obtained in (b). Remember that our initial conditions are for a1 and a2.

Answer 3)

Let P(n) be 20+21+22+.....+2n = 2n+1 - 1

We will show P(n) is true for all n ∈ ℕ.

For our base case, we need to show P(0) is true, meaning the sum of the first zero powers of two is 20 – 1. Since the sum of the first zero powers of two is 0 = 20 – 1, we see P(0) is true.

For the inductive step, assume that for some k ∈ ℕ that P(k) holds, meaning that 20+21+22+.....+2k = 2k+1 - 1. We need to show that P(k + 1) holds, meaning that the sum of the first k + 2 powers of two is 2k+2 – 1.

Consider the sum of the first k + 2 powers of two. This is the sum of the first k+1 powers of two, plus 2k+1 . Using the inductive hypothesis, we see that

20+21+22+.....+2k+1 = (20+21+22+.....+2k) + 2k+1 = 2k+1 – 1 + 2k+1 = 2(2k+1) – 1 = 2k+2 – 1

Thus P(n + 1) is true, completing the induction.

Answer 4)

16777216 = 224

103 = 103

255 = 3*5*17

10000 = 24*54