Attempt ALL of the following questions. Each question carries equal marks.

• Example(s) of O (1) algorithms is(are)
• Printing a character to the screen
• Incrementing a variable
• All of the above
• None of the above
• Which of the following algorithm should execute the slowest for large values of N?
• O ( )
• O (N)
• O (log2N)
• None of the above
• The average number of comparisons in sequential search is
• n2
• n(n-1)/2
• n(n+1)/2
• (n+1)/2
• None of the above
• Find the solution to T(n) = (T(n- 1))2, T(1) = 2. Give the smallest correct answer.
• O( )
• O(
• O( )
• O(
• O(
• Tail recursion
• Is a path that includes a recursive call to the routine to solve a smaller version of the original problem
• Occurs when the recursive call is the last statement executed in a recursive procedure or function
• Is a structure that keeps track of the activation records at run time, in order to preserve the values the parameters, return addresses, registers & so on
• Refers to the point in the compile/execution cycle when variable names are associated with addresses in memory
• None of the above

Question-2:

1. Consider the following growth functions. Each one has a different asymptotic complexity.

Write them out in complexity order, slowest growth rate first.

1. Given an array of n positive integers, write an algorithm to find out the number of odd and even numbers, as well as the number of zeros in that array.

Question-3:

1. Suppose a machine performs a million floating-point operations per second (106 FLOPS), how long an algorithm will run for an input of size n=50?
1. If the algorithm requires n2 such operations.
2. If the algorithm requires 2n such operations.
• Briefly explain what the results of the calculations in i) and ii) mean.
1. Write two functions that call each other to determine whether a nonnegative number N is odd or even (assume that the integer 0 is even).

Question-4:

1. What is the time complexity of the following piece of code in Big-O notation?

for( int i = n; i > 0; i = i/2){

for( int j = 1; j < n; j = j*2){

for( int k = 0; k < n; k = k+2){

cout<< (i+j+k);

}}}

1. Design an algorithm that is given a positive integer N and determines whether N is a prime number, that is, not evenly divisible by any value other than 1 and itself. The output of your algorithm is either the message “not prime”, along with a factor of N, or the message “prime”.

Best wishes…