Chat with us, powered by LiveChat Write an algorithm, called Decomposition_P - Study Help
  

 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!

error: Content is protected !!