Need help with this C project Overview For problems 1a of th

Need help with this C++ project. Overview: For problems 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 run your program (e.g. the file you modified or created 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. [6 points] Recursion. Read the assigned chapter and notes for Week 1 located in the Learning Modules area in Blackboard. Then provide solutions for the following: (a) [3 points] Download the h.zip file, then implement a recursive function called h(), which can be directly translated into C/C++ from the following mathematical definition:

/** * h.cpp - This progam implements the h() function * as described in the handout. * * */

#include

#include

#include

using namespace std;

int h(int x);

int main(int argc, char **argv)

{ cout << \"h(0) is \" << h(0) << endl;

cout << \"h(1) is \" << h(1) << endl;

cout << \"h(2) is \" << h(2) << endl;

cout << \"h(3) is \" << h(3) << endl;

cout << \"h(4) is \" << h(4) << endl;

cout << \"h(5) is \" << h(5) << endl;

cout << \"\ ** Press any key to continue **\ \ \";

getchar();

return 0; }

int h(int x)

{ // TODO: implement the function h() based on the // mathematical definition provided in the handout. }

(b) [1.5 points] What type of recursion does the h() function in part (a) use? Briefly explain your answer.

(c) [1.5 points] Explain the recursive function design rule that Excessive Recursive functions typically violate. Also, specifically describe why violating this rule is a problem.

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

(a) [2 points] What is the asymptotic complexity (big-O) of the following function? 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.

int pow(int n, int exponent)

{ int result = 1;

for (int i=0; i < exponent; i++)

{ result *= n;

}

return result; }

Solution

Solution:

1. a)

/**
* f.cpp - This progam implements the f() function
* as described in the handout.
*
* TODO: Include your name and course number here.
*/

#include <cstdio>
#include <cstdlib>
#include <iostream>

using namespace std;

int h(int x);

int main(int argc, char **argv)
{
cout << \"h(-44) is \" << h(-44) << endl;
cout << \"h(-20) is \" << h(-20) << endl;
cout << \"h(-1) is \" << h(-1) << endl;
cout << \"h(0) is \" << h(0) << endl;
cout << \"h(1) is \" << h(1) << endl;
cout << \"h(13) is \" << h(13) << endl;
cout << \"h(20) is \" << h(20) << endl;
cout << \"h(50) is \" << h(50) << endl;
cout << \"h(44) is \" << h(44) << endl;

cout << \"\ ** Press any key to continue **\ \ \";
getchar();

return 0;
}

int h(int x)
{
if(x==0)
return 0;
if(x>0)
return (h(x-1)+2*x-1);
if(x<0)
return (h(-x-1)-2*x-1);
}

Q 2)

a) –notation provides an asymptotic lower bound whereas O-notation provides the asymptotic Upper bound of a function.

O -notation : For a given function g(x) , we donates by O(g(x)) (pronounced “big-oh of g of x”) the

set of function

O(g(x)) = { h(x) : there exist positive constants c and n0 such that 0 h(x ) cg(x) for all x >

We use O-notation to give an upper bound on a function, to within a constant factor.

-notation : For a given function g(x) , we donates by (g(x)) (pronounced “big-omega of g of x”) the set of function

(g(x)) = { h(x) : there exist positive constants c and n0 such that 0 cg(x ) h(x) for all x >

We use -notation to give an lower bound on a function, to within a constant factor.

b) The asymptotic complexity of a the given block of code is O(x^3) . The given block of code consist of three for loop every statement inside outermost loop will be executed n-1 time it means the loop statement inside it will also execute x-1 time and this loop itself execute n-1 time which contains one more loop inside it hence the innermost loop will be executed (x-1)(x-1)(x-1) time. So upper bound of function will be x^3.