COMP2011 Tutorial Exercises 3, Week 4

Algorithms

  1. Any questions about Assignment 1.

  2. Give a tight "Big-Oh" characterization, in terms of n, of the running time of each method in the following class:
    public int Ex1( int A[] ) {
        // compute sum of elements of A
        int s = 0;
    
        for( int i=0; i < A.length; i++ ) {
            s += A[i];
        }
        return( s );
    }
    
    public void Ex2( int A[], int B[] ) {
        // store the prefix sums of A into B
        int i,j,s;
    
        for( i=0; i < A.length; i++ ) {
            s = 0;
            for( j=0; j <= i; j++ ) {
                s += A[j];
            }
            B[i] = s;
        }
    }
    
    public void Ex3( int A[], int B[] ) {
        // store the prefix sums of A into B
        int i,s;
    
        s = 0;
        for( i=0; i < A.length; i++ ) {
            s += A[i];
            B[i] = s;
        }
    }
    
    public void Ex4( int A[], int B[] ) {
        // store the prefix sums of prefix sums of A into B
        int i,j,k,s;
    
        for( i=0; i < A.length; i++ ) {
            s = 0;
            for( j=0; j <= i; j++ ) {
                for( k=0; k <= j; k++ ) {
                    s += A[k];
                }
            }
            B[i] = s;
        }
    }
    
    Can Ex4() be re-written so that it runs faster? How much faster?

  3. R-3.2: The number of operations executed by algorithms A and B is 8nlogn and 2n2, respectively. Determine n0 such that A is better than B for n >= n0.

  4. What is the definition of f(n) being O(g(n))?
    R-3.12: Show that if d(n) is O(f(n)) and e(n) is O(g(n)), then d(n)+e(n) is O(f(n)+g(n))
    R-3.16: Show that O(max{f(n),g(n)}) = O(f(n)+g(n))

  5. C-3.4: Describe a method for finding both the minimum and maximum of n numbers using fewer than 3n/2 comparisons.

  6. Any items remaining from previous weeks.