CSE 214 Computer Science II (Spring 2015)

RECITATION 2 – OOP and Algorithm Analysis

Objective:

1. To work with generic class in Java.
2. Analyze the complexity of expressions and given procedures

1.  [15] We have Generic class and method,

1. use the generic method printValues to print data values for integer, float and character datatypes

[Note: The code sniipet can be found at http://www3.cs.stonybrook.edu/~sael/teaching/cse214/rec/GenericMethodDemo.java ]

public class GenericMethodDemo

   {

   // generic method printValues                        

   public static < E > void printValues( E inputValue )

                 {

              // Display Value             

                    }

    public static void main( String args[] )

    {

        // Create values of integer, float and Character

        System.out.println( "\n Integer value is:" );

                  // call the printValues function

        System.out.println( "\n Float value is:" );

                  // call the printValues function

        System.out.println( " \n Character value is " );

                  // call the printValues function

    }

}

2. use the generic class to insert 10 integer values and display them. Using the same class and methods repeat the procedure for String values.

[Note: The code snippet can be found at http://www3.cs.stonybrook.edu/~sael/teaching/cse214/rec/ Main.java ]

class GenericClassDemo<T> {

            private T t;

            public void insert(T t) {

                           this.t = t;

            }

            public T get() {

                           return t;

            }

}

public class Main {

            public static void main(String[] args) {

            GenericClassDemo <Integer> Obj = new GenericClassDemo <Integer>();

            //Insertion of value

            Obj.insert(12);

            //Display value

            Integer i = Obj.get();

            System.out.println(i);

            }

}

2. [5 minutes] Write the order of complexity for the following programs using Big O notation if the programs execute the following number of operations for n inputs:

  a) 678912                                  b) 3n + 9n⁴+ 2n⁵                           c) n(log₂ n)² + 2n

   d) (log₂ n)² + n!                         e)   20n+6                                      f) 2ⁿ + n¹⁰        

3. [10 minutes]  Given the following procedures, find the order of complexity:

1. int d = 0;

for(int i = 1; i <= n; i++)

{   d=d+d*5;

}

for(int i=0;i<n;i++){

for(int j = 0; j < i; j++)

{   d = d – 5;

}

}

2.  int d = 0;

for(int i = 1; i <= n; i++)

{   for(int j = 1; j <= i; j++)

        d = d + i + j;

    d = d + 2;

}

for(int k = 1; k < n; k = k*2)

{   d = d – 5;

}

4. [10] Carry out the empirical analysis to find the timing experiment on the methods repeat1 and repeat 2.

long startTime=System.currentTimeMillis();

long endTime=System.currentTimeMillis();

long elapsed=endTime-startTime

1. Uses repeated concatenation to compose a String with n copies of character c

public static String repeat1(char c, int n)

{

String answer=””;

for(int j=0;j<n;j++)

answer+=c;

return answer;

}

2. Uses StringBuilder to compose a String with n copies of the character c

public static String repeat2(char c, int n)

{

StringBuilder sb= new StringBuilder();

for(int j=0;j<n;j++)

sb.append(c);

return sb.toString();

}