Theory of Algorithms - Sample exam

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 (log₂N)
  • None of the above
• The average number of comparisons in sequential search is
  • n²
  • n(n-1)/2
  • n(n+1)/2
  • (n+1)/2
  • None of the above
• Find the solution to T(n) = (T(n- 1))², 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 (10⁶ FLOPS), how long an algorithm will run for an input of size n=50?
   1. If the algorithm requires n² such operations.
   2. If the algorithm requires 2ⁿ 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