Data Structures and Algorithms with Object-Oriented Design Patterns in C#

Exercises

1. Consider the function . Using Definition  show that .
2. Consider the function . Using Definition  show that .
3. Consider the functions and . Using Theorem  show that .
4. Consider the functions and . Using Theorem  show that .
5. For each pair of functions, f(n) and g(n), in the following table, indicate if f(n)=O(g(n)) and if g(n)=O(f(n)).

   f(n)	g(n)
   10n

6.   Show that the Fibonacci numbers (see Equation ) satisfy the identities

   

   for .

7. Prove each of the following formulas:
   1. 
   2. 
   3. 
8. Show that , where and .
9. Show that .
10. Solve each of the following recurrences:
    1. 
    2. 
    3. 
    4. 
11. Derive tight, big oh expressions for the running times of Example-a,Example-b,Example-c,Example-d,Example-f,Example-g,Example-h,Example-i.
12. Consider the C# program fragments given below. Assume that n, m, and k are non-negative ints and that the methods E, F, G, and H have the following characteristics:
    • The worst case running time for E(n,m,k) is O(1) and it returns a value between 1 and (n+m+k).
    • The worst case running time for F(n,m,k) is O(n+m).
    • The worst case running time for G(n,m,k) is O(m+k).
    • The worst case running time for H(n,m,k) is O(n+k).
    Determine a tight, big oh expression for the worst-case running time of each of the following program fragments:

    1. F(n, 10, 0);
       G(n, m, k);
       H(n, m, 1000000);

    2. for (int i = 0; i < n; ++i)
           F(n, m, k);

    3. for (int i = 0; i < E(n, 10, 100); ++i)
           F(n, 10, 0);

    4. for (int i = 0; i < E(n, m, k); ++i)
           F(n, 10, 0);

    5. for (int i = 0; i < n; ++i)
           for (int j = i; j < n; ++j)
               F(n, m, k);

13.   Consider the following C# program fragment. What value does F compute? (Express your answer as a function of n). Give a tight, big oh expression for the worst-case running time of the method F.

    public class Example
    {
        public static int F(int n)
        {
    	int sum = 0;
    	for (int i = 1; i <= n; ++i)
    	    sum = sum + i;
    	return sum;
        }
        // ...
    }

14.   Consider the following C# program fragment. (The method F is given in Exercise ). What value does G compute? (Express your answer as a function of n). Give a tight, big oh expression for the worst-case running time of the method G.

    public class Example
    {
        // ...
        public static int G(int n)
        {
    	int sum = 0;
    	for (int i = 1; i <= n; ++i)
    	    sum = sum + i + F(i);
    	return sum;
        }
    }

15. Consider the following C# program fragment. (The method F is given in Exercise  and the method G is given in Exercise ). What value does H compute? (Express your answer as a function of n). Give a tight, big oh expression for the worst-case running time of the method H.

    public class Example
    {
        // ...
        public int H(int n)
    	{ return F(n) + G(n); }
    }

Copyright © 2001 by Bruno R. Preiss, P.Eng. All rights reserved.