A3 section 2 (10-17)

[Ahmed Elkatib]

1. Establish how many times statement x = 2* x is executed in the asymptotic sense:

      j = n; x = 1;
      while ( j >= 1 ) {
         for ( i = 1; i <= 2*n; i++ )
            x = 2 * x;
         j = j / 2;
      }
    

    Theta( n^2 / 2 ) 
    Theta( n^2 log( n )^2 ) 
    Theta( n^2 log( n ) ) 
    Theta( n log (n ) ) 
    Theta( n ) 
   

2. Given the following three statements:

   I.     n(n+1)/2 belongs to O(n)

   II.    n(n+1)/2 belongs to Theta(n)

   III.   n(n+1)/2 belongs to Omega(n)

   I, II, and III are respectively

    True, True, False 
    False, False, False 
    False, False, True 
    Ture, False, False 
    False, True, True 
   

3. What is a tree?

    It is a graph that is connected and has no cycles 
    It is a graph the is connected and has cycles 
    It is a graph that is not necessarily connected but has no cycles 
    It is a graph in which each node points to two other nodes 
   

4. Let G=(V,E) be a graph. Let |V|=n and |E|=e. What is the complexity of BFS (breadth first search) as a function of n and e?

    O( n * e ) 
    O( n + e ) 
    O( n log( e ) ) 
    O( n^2 e ) 
   

5. Which of the following is a correct ordering, from best to worst of algorithm speeds?

    Linear, Exponential, Polynomial, Logarithmic 
    Logarithmic, Linear, Polynomial, Exponential 
    Exponential, Polynomial, Linear, Logarithmic 
    Logarithmic, Exponential, Linear, Polynomial 
    Logarithmic, Linear, Exponential, Polynomial 
   

6. Arrange the following in increasing order of growth:

   n!, n³, 2ⁿ, n², n, log n, n log n

7. Establish how many times statement x = 2* x is executed in the asymptotic sense:

      j = n; x = 1;
      while ( j >= 1 ) {
         for ( i = 1; i <= 2*n; i++ )
            x = 2 * x;
         j = j / 2;
      }
    

    Theta( n^2 / 2 ) 
    Theta( n^2 log( n )^2 ) 
    Theta( n^2 log( n ) ) 
    Theta( n log (n ) ) 
    Theta( n ) 
   

8. nlog( n ) + n^2 = Theta( n^2 + sqrt(n) )

    True 
    False