1.(20 pts) For each of the following program fragments(expressions), give an analysis of the running time in terms of the big-O notation.
a. cin >> n;
total = 0;
while (total < n/2)
cout << total;
total++;
b. cin >> n
count=0;
do
count = count + 2;
for(i=0; i< count; i++)
cout << "Just a test"
while(count <= n)
c. cin >> n;
sum = 0;
for (int i = 0; i < n; i++)
for (int j = 10; j < n * n; j++)
sum++;
d. cin >> n;
k = n;
sum = 0;
while (k > 1)
{
sum++;
k = k/2;
test(n);
}
void test(int x)
{
for(int i =0; i < x; i++)
cout << endl;
}
e. cin >> n;
k = 1;
m = n;
do
{
j = 1;
m = m * 2;
do
{
.
.
j++;
}while (j <= m);
k++;
}while(k <= n);
2.(5 points) To prove the following statement:
3n3 + 2n = O(n3)
Using the method discussed in class
3. (10 pts) Given an x, show that X62 can be computed with only eight multiplications (A general algorithm can not accomplish it).
4. (10 points) Assume that the input is a sequence of n real numbers. Design an algorithm that prints a number that is not in the sequence. Submit the program along with its output and the big-O notation (My algorithm runs O(n).
5. (10 points) Given an input set S containing n real numbers and a real number x. Design an algorithm that determines whether there are two numbers in S whose sum is exactly x. Submit your program and its time complexity analysis in terms of the big O.
6.(10 pts) Show the output of the following statement:
cout << func(5);
Int func(int n)
{
if (n == 0 or n == 1)
return 1;
else
return 2*func(n-2) + 3*func(n-1);
}
7.(10 pts) Consider the test function below:
Void test(int p1, int p2)
{
if (p1 != p2)
{
p1 = p1 + 2;
p2 = p2 - 1;
test(p1,p2);
cout << p1;
cout << p2;
}
}
a) Show the output resulting from the following function call: test(2,8).
b) Is it possible that the execution may result in infinite recursion. If so, give an example.
7.(5 pts) Given a recurrence relation shown below, show the first 8 numbers of the sequence.
T(n) = 2(T(n-1) - 3* T(n-2))
T(1) = 1; T(2) = 4
8. (20 pts) Execute two java programs with O(n) and O(2n) time complexity respectively and submit the actual execution time and your programs.
The input to the O(n) program:
10,100,1000,10000,100000
The input to the O(2n) program:
1,10,20,30,40,50 .. until you give up
(more than 2 hours)
Type your answers and execute the programs. Submit their executions.