Question

(1) Give a formula for SUM{i} [i changes from i=a to i=n], where a is an integer between 1 and n.

(2) Suppose Algorithm-1 does f(n) = n**2 + 4n steps in the worst case, and Algorithm-2 does g(n) = 29n + 3 steps in the worst case, for inputs of size n. For what input sizes is Algorithm-1 faster than Algorithm-2 (in the worst case)?

(3) Prove or disprove: SUM{i**2} [where i changes from i=1 to i=n] ϵ tetha(n**2).

(4) Write out the algorithm (pseudocode) to find K in the ordered array by the method that compares K to every fourth entry until K itself or an entry larger than K is found, and then, in the latter case, searches for K among the preceding three. How many comparisons does your algorithm do in the worst case?

(5) Design and implement (meaning write code and execute the code turning in test cases and source code) for the following two algorithms to raise an integer to an integer power assume in both cases that n, the exponent, is a power of 2:

      Again, in case you don’t have any programming language at hand you can use pseudocode to solve the problem.

Algorithm 1

X**N = X* X**(N-1)

X**0 = 1

Algorithm 2

n = 2**m

X**n = ((X**2)**2)**2…, etc. [NOTE: the symbol of power (**) is used m times here, i.e., X**8 = ((X**2)**2)**2, because 8 = 2**3].

Which algorithm is more efficient with respect to the number of multiplications?

(6) Answer questions (a) and (b) below:

(a)    How many times exactly is the code block below executed?

For (i = 1, n)

{

                        For (j = 1, i)

{

For (k = 1, j)

{

code block

}

}

}

Hint: You have to start with n=1, then make assumption what you make expect for any given n = N, and check if the formula you found works for n =N+1.

This is what we call prove by induction.

(b) What is the theta value of this code segment?

Answer 1

1)

Mathematical Expression:

Mathematical Formula:

We know that sum of all natural numbers is given by the formula : n(n+1)/2

Sum of all natural numbers from a to n = Sum of natural numbers upto n - Sum of natural numbers upto (a-1)

Hence,

$Sum_i = \frac{n(n+1)}{2} - \frac{(a-1)a}{2}$

Algorithm:

            INPUT :          Two integers, a and n

            OUTPUT:       An integer, sum

Step 1.            Input a and n

Step 2.            If a < 1 Or a > n Then

                                                  i.            Print "Error in Input”

                                                ii.            Exit

(End of if condition)

Step 3.            Initialize sum := 0

Step 4.            Set i := a

Step 5.            Repeat While i <= n

                                                  i.            sum := sum + i

                                                ii.            i := i + 1

(End of while loop)

Step 6.            Print sum

Code in C

#include<stdio.h>

#include<stdlib.h>

void main()

{

      int a, n, sum, i;

     

      //Input a and n

      printf("Enter any integer, n :");

      scanf("%d", &n );

     

      printf("Enter another integer, a ( 1<=a<=n ) :") ;

      scanf("%d", &a );

     

      //Test if 1 <= a <= n

      if ( a < 1 || a > n )

      {

                  printf ("Invalid value of a.... Exiting program");

                  exit(1);

      }

      else

      {

//Find value of sum of all numbers from a to n and store it in variable sum

                  sum = 0;

                  i = a;

                  while ( i <= n)

                  {

                              sum = sum + i;

                              i++;

                  }

//Output value of sum

                  printf ("\nSum = %d", sum);

      }

}

Output

2)

For small input sizes, Algorithm – 1 will execute faster than Algorithm – 2. However, as the value of n increases, the time required for executing Algorithm – 1 will grow faster. This will happen until a particular value of n, when f(n) = g(n). Beyond this value of n, Algorithm – 2 will execute faster.

Computation of n for which f(n) = g(n):

Hence, Algorithm – 1 will execute faster than Algorithm – 2 for all values of n which are less than or equal to 25. Beyond that, Algorithm – 2 will execute faster.

3)

The sum of squares of first n natural numbers is given by the formula :

$f(n) = Sum_{i^{2}} = \frac{n(n&plus;1)(2n &plus; 1)}{6}$

$f(n) = \frac{n^3}{3} &plus; \frac{n^2}{2} &plus; \frac{n}{6}$

$f(n) < n^3 &plus; n^3 &plus; n^3, f(n) < 3n^3$

Hence,

$f(n) =$ O ( $n^3$)

$f(n) > n^3$

Hence,

$f(n) = \Omega (n^3)$

Hence $f(n) = \Theta (n^3)$

Hence the statement that $f(n) = \Theta (n^2)$ is not true.

5)

CODE IN C

#include<stdio.h>

//This function raises an integer by an integer power using algorithm 1

int algorithm1 ( int x, int n)

{

if ( n == 0 )

return 1;

return (x * algorithm1(x, n-1));

}

//This function raises an integer by an integer power using algorithm 2

int algorithm2 ( int x, int n)

{

int retval = 1, i;

for ( i = 1; i <= n ; i++ )

retval = retval * x;

return retval;

}

int main()

{

int number, exponent;

//Input numbers and exponents

printf("Enter any integer, (base) :");

scanf("%d", &number);

printf("Enter exponent :");

scanf("%d", &exponent);

//Sample run for algorithm 1

printf("Answer using algorithm 1 = %d", algorithm1(number, exponent));

//Sample run for algorithm 1

printf("\nAnswer using algorithm 2 = %d", algorithm2(number, exponent));

return 0;

}

OUTPUT

(Please note that the minimum requirement of answering the first three sub-sections has been fulfilled)