Write an algorithm, called Decomposition_Powers_Three, which produces the decomposition of each integer using powers of 3, namely 1, 3, 9, 27, and 81, and the + and – operators. Each power of 3 should appear at most once in the decomposition. Examples: 1 = 1 2 = 3 – 1 3 = 3 4 = 3 + 1 7 = 9 – 3 + 1 14 = 27 – 9 – 3 – 1 43 = 81 – 27 – 9 – 3 + 1 121 = 81 + 27 + 9 + 3 + 1 2. Show that the algorithm Decomposition_Powers_Three is correct using an informal proof (i.e., discussion). 3. Give a program corresponding to Decomposition_Powers_Three, using any of your favorite programming languages. Observation: The intervals [-121,-41], [-40,-14], [-13,-5], [-4,-2], [-1,-1], [1,1], [2,4], [5,13], [14,40], and [41,121] play a particular role.

1

Department of Electrical Engineering and Computer Science

Texas A&M University-Kingsville

CSEN 5303 Foundations of Computer Science

Fall 2021

Instructor: Habib M. Ammari, Ph.D. (CSE), Ph.D. (CS)

Homework 4

Due Date: Sep. 10, 2021

Note: Feel free to solve any two problems of your choice to be graded.

Problem 1: Put comments on the following functions to identify the base and general cases. Also,

explain what each function does.

a. int Power(int base, int exponent)

{

if (exponent == 0)

return 1;

else

return base*Power(base,exponent-1);

}

b. int Factorial(int num)

{

if (num > 0)

return num*Factorial(num-1);

else

if (num == 0)

return 1;

}

Problem 2: The Fibonacci sequence is the series of integers 0, 1, 1, 2, 3, 5, 8, 21, 34, 55, 89 …

See the pattern? Each element in the series is the sum of the preceding two items. There is a

recursive formula for calculating the nth number of the sequence (the 0th number is Fib(0) = 0):

a. Write a recursive version of the function Fibonacci.

b. Write a non-recursive version of the function Fibonacci.

c. Compare the recursive and iterative versions for efficiency.

d. Can you think of a way to make the recursive version more efficient?

Problem 3: Given the following recursive function:

2

int Ulam(int num)

{

if (num <2)

return 1;

else

if (num %2 ==0)

return Ulam(num/2);

else

return Ulam(3* num +1);

}

1. What problems come up in verifying this function?

2. How many recursive calls are made by the following initial calls?

a. cout << Ulam(7) <<endl;

b. cout << Ulam(8) <<endl;

c. cout << Ulam(15) << endl;

Problem 4: Assume a correct input date given in the form of a string and three integers: day of

the week, number of the month, number of the day, number of the year. We want to compute the

date of the next day.

3. Show your fine analysis of the problem.

4. Give an algorithm that computes the date of the next day.

Submission

You should submit your work through Blackboard following the link associated with this

Homework 4.

Good Luck!