Problem #1

Overview: For problem 1(a) of this assignment, you will need a C++ compiler. In order to receive credit, your program must compile and run; and you must provide the actual source code file so that I can compile and I can your program (e.g. the file you modified ending in .cpp). Examples on how to import existing source code files into your compiler are provided in the file called Importing Source Code.pdf The remaining problems for the assignment must be written up within a single Microsoft Word document. You must include your name and course number within all files that you submit, including source code files as a comment at the top of each file that you create or modify.

1. Recursion. Read the assigned chapter and notes for Week I located in the Learning Activities area in Blackboard. Then provide solutions for the following:

(a) Download the g.cpp file, then using the definition below, implement the details of a recursive function called g (n) This function can be directly translated into C/C++ from the following mathematical definition:

           0                     if n ≤ 0

g (n) = n + g (n - 1)   n ≤ 1 or n ≥ 4

            n + g (n - 3)    otherwise

The function must be implemented based on the mathematical definition provided above,

Note: For this program, you only need to modify the provided file by adding the necessary code to implement the TODD areas as noted in the comments, Everything else can remain the same.

Output: The output for this program once it is implemented will be as follows:

g(-21) is 0

g(-4) is 0

g(0) is 0

g(77) is 3000 g(300) is 45147

** Press any key to continue **

(b) Perform an Internet search and provide a brief description (at least a paragraph with four to five sentences) of an example of a practical use for recursion. For example, the practical use you mention should be something other than simple function implementations such as factorial, the power of a number, Fibonacci, etc. The description must be summary in your own words and not a cut and paste from a website. Include the reference to your source or sources in APA format at the end of your description.

Problem #2

2. Complexity Analysis. Begin by reading the assigned chapter and notes for Week 2 located in the Learning Activities area in Blackboard. Then answer the following questions:

(a) Briefly explain the difference between Θ (Theta) notation and big-O notation. Also provide the mathematical definitions of each.

(b) What is the a.symptotic.: complexity ( big-O) of the ibllowing code block? Briefly explain why.

Note: No programming is necessary for this problem. Just tell me what the big-O of the function, and provide a couple of sentences explaining how you arrived at the solution.

void myFunction(int n, int *a)

for (int i=0; i< n; i++) a[i] = 0;
}
for (int i=0; i< n; i++) {
for (int j=0; j < n; j++}
a[i] += a[j] + i + j;
for (int k=0; j < n; j++} a[j] += a[k] + 1 + j +
}
return;