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

Question-1:  Choose the most correct answer from the answers offered.

  • Example(s) of O (1) algorithms is(are)
    • Printing a character to the screen
    • Incrementing a variable
    • Adding two numbers together
    • 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…

Dr.-Ing. Samy Sadek