Scribd
Upload
122 views

CST 370 - Spring A 2020 Homework 3: Answer: 1

The document contains a student's homework assignment that includes: 1) Solutions to recursive algorithms computing values for input numbers. 2) Solutions to recurrence relations modeling recursive algorithms using backward substitution. 3) An algorithm to find the minimum element in an array modeled with a recurrence relation. 4) An algorithm to compute the sum of cubes of numbers from 1 to n modeled with a recurrence relation. 5) An English description of an efficient algorithm to find all common elements between two sorted lists.

Uploaded by

api-427618266
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
122 views

CST 370 - Spring A 2020 Homework 3: Answer: 1

The document contains a student's homework assignment that includes: 1) Solutions to recursive algorithms computing values for input numbers. 2) Solutions to recurrence relations modeling recursive algorithms using backward substitution. 3) An algorithm to find the minimum element in an array modeled with a recurrence relation. 4) An algorithm to compute the sum of cubes of numbers from 1 to n modeled with a recurrence relation. 5) An English description of an efficient algorithm to find all common elements between two sorted lists.

Uploaded by

api-427618266
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 4

CST 370 – Spring A 2020

Homework 3

Name: _______________Yauheniya Nikulyak__________________

Class ID: _________2606______________________

1. (5 points) Consider the following recursive algorithm.


Algorithm Q(n)
// Input: A positive integer n
if n = 1 return 1
else return Q(n - 1) + 2 * n - 1

(a) Present the return value for Q(1).


Answer: 1

(b) Present the return value for Q(2).

Answer: 4

(c) Present the return value for Q(3).

Answer: 9

(d) Determine what the algorithm computes for a general number n: Q(n).

Answer: Algorithm computes a square of a number n.

2. (10 points) In the class, you learned the recurrence relation and backward substitution to get the time
complexity of a recursive algorithm. To remind the topic, read the Google document again at
https://goo.gl/HmoUNQ

Solve the following recurrence relations using the backward substitution. You have to present
intermediate steps as described.

(a)
M(n) = 2*M(n – 1) for n > 1 // recurrence relation
M(1) = 3 // initial condition

Answer:
M(n) = 2*M(n – 1)
= 2*[2*M(n-2)]
= 4*M(n-2)
= 4*[2*M(n-3)]
= 8*M(n-3)
= 8*[2*M(n-4)]
=16*M(n-4)
…..
= 2^i * M(n-i)
Page 1 of 4
….
= 2^(n-1)*M(n-(n-1))
= 2^(n-1) *M(1)
= 2^(n-1) * 3
= 2^(n-1) ∈ O(2^n)

(b)
M(n) = 3*M(n – 1) for n > 1 // recurrence relation
M(1) = 4 // initial condition

Answer:
M(n) = 3*M(n-1)
= 3*[3*M(n-2)]
= 9*M(n-2)
= 9*[3*M(n-3)]
= 27*M(n-3)
= 27*[3*M(n-4)]
= 81*M(n-4)
…..
= 3^i * M(n-i)
….
= 3^(n-1)*M(n-(n-1))
= 3^(n-1) *M(1)
= 3^(n-1) * 4
= 3^(n-1) ∈ O(3^n)

3. (15 points) Consider the following recursive algorithm.

(a) What does this algorithm compute?

Answer: The algorithm computes the minimal element in the array.

(b) Set up a recurrence relation for the comparison operation at the “if n = 1” in the line number
3.

Answer: M(n) = M(n-1) + 1

(c) Provide an initial condition for the recurrence relation you develop at the question (b)

Answer: M(1) = 1

(d) Solve the recurrence relation using backward substitution method. Present the intermediate
steps and the time complexity of the result

Page 2 of 4
Answer:
M(n) = M(n-1) + 1
= [M(n-2) + 1] + 1
= [M(n-3) +1] + 1 + 1
…
= M(n-i) + i
…
= M(n-(n-1)) + (n-1)
= M(1) + n-1
=1+n–1
= n ∈O(n)

4. (15 points) Consider the following recursive algorithm for positive integer n
ALGORITHM S(n)
//Input: A positive integer n
if n = 1 return 1
else return S(n − 1) + n ∗ n ∗ n

(a) What does this algorithm compute?

Answer: The algorithm computes the sum of cubes of numbers from 1 till n: 1^3+2^3+3^3+...+n^3

(b) Set up a recurrence relation for the multiplication as the basic operation
Answer: M(n) = M(n-1) + 2

(c) Provide an initial condition for the recurrence relation

Answer: M(1) = 0

(d) Solve the recurrence relation using backward substitution method. Present the intermediate
steps and the time complexity of the results

Answer:
M(n) = M(n-1) + 2
= [M(n-2) + 2] + 2
= M(n-2) + 4
= [M(n-3) + 2] + 4
= M(n-3) + 6
…..
= M(n – i) + 2*i
….
= M(n-(n-1)) + 2*(n-1)
=M(1) + 2*(n-1)
= 0 + 2*(n-1)
= 2*(n-1) ∈ O(n)

Page 3 of 4
5. (15 points) Describe an efficient algorithm (in English) for finding all common elements in two
sorted lists of numbers. For example, for the lists 2, 5, 5, 5 and 2, 2, 3, 5, 5, 7, the output should be 2,
5, 5. As another example, for the lists 20, 30, 50, 70, 90, 100 and 10, 20, 30, 50, 80, the output should
be 20, 30, 50.

Answer:

1. Assign two running indexes to 0;


2. Create a new list that would hold common element of both lists
3. Iterate through both arrays at the same time till either of the arrays reach the end
4. During each iteration compare the element from the first array with the element from the second
array.
5. If the element from the first array is greater than the element from the second array, increment the
index of the second array by 1.
6. If the element from the first array is less than the element from the second array, increment the
index of the first array by 1.
7. If the elements are equal, increment both indexes by 1 and add element into a list for common
elements.
8. When either of the array reaches its end, stop iteration and print all the element from list with
common elements.

Page 4 of 4

You might also like