We assume that the standard input contains a sequence of non-zero integers between - 121 and 121, which ends with 0. This sequence will be given by the user

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!