__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
_{2}N) - None of the above

- The average number of comparisons in sequential search is
- n
^{2} - n(n-1)/2
- n(n+1)/2
- (n+1)/2
- None of the above

- n
- 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__**: **

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

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

- 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:__

- Suppose a machine performs a million floating-point operations per second (10
^{6 }FLOPS), how long an algorithm will run for an input of size n=50?- If the algorithm requires n
^{2}such operations. - If the algorithm requires 2
^{n}such operations.

- If the algorithm requires n

- Briefly explain what the results of the calculations in i) and ii) mean.

- 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:__

- 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);**

**}}}**

- 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