[JAVA] Study Guide Problems 1. Analyze the running time complexity (in terms of

Question

[JAVA] Study Guide Problems

1. Analyze the running time complexity (in terms of big O notation) of the following code segment:

for (i=0; i<a.length-1; i++)
{
for (j=i+1; j<a.length; j++)
{
if(a[i] > a[j])
{
/* switch a[i] and a[j] */
tmp = a[i];
a[i] = a[j];
a[j] = tmp;
}
}

}

2. Write a method splitStack that takes a stack of integers as a parameter and splits it into negatives and non-negatives. The numbers in the stack should be rearranged so that all the negatives appear on the bottom of the stack and all the non-negatives appear on the top. In other words, if after this method is called you were to pop numbers off the stack, you would first get all the nonnegative numbers and then get all the negative numbers. It does not matter what order the numbers appear in as long as all the negatives appear lower in the stack than all the non-negatives. You may use a single queue as auxiliary storage. For example, if the stack stores [3, -5, 1, 2, -4] , an acceptable result would be [-5, -4 , 3, 1, 2]

3. Recursion Mystery. Consider the following method:

public int mystery3(int n)
{
if (n < 0)
return -mystery3(-n);
  
else if (n < 10)
return n;
  
else
return mystery3(n/10 + n % 10);
}

For each call below, indicate what value is returned:

Method Call Value Returned

mystery3(6) _____________

mystery3(17) _____________

mystery3(259) _____________

mystery3(977) _____________

mystery3(-479) ____________

4. Recursion & Big O:

Write a method called printStar(int n) which will print the following when n=4:

****

***

**

*

*

**

***

****

What is the Big O for this function?

5. What is the asymptotic complexity of the following methods or code segments, in terms of the Big-O notation?

a) void methodA(int n)
{
for (int i=n; i>1; i-=2)
{
System.out.println(i);
}
}

b) void methodB(int n)
{
for (int i=n; i<=n; i++)
{
for (int j=n; j>1; j=j/2)
{
System.out.println(j);
}
}
}

c) Code segment:

int sum = 0;
int X = 100000;
for (int i = 1; i <=4 * N; i++)
{
for (int j = 1; j <= X + 2; j++)
{
sum++
}
for (int j = 1; j <= X * 100; j+= 2)
{
for (int k = 1; k <= X * X; k++)
{
sum++;
}
}
sum++;
}
System.out.println(sum);

d) Code segment:

int sum = 0;
int X = 100000;
for (int j = 0; i < 100 * N; j++)
{
for (int i = N; i > 0; i /= 2)
{
sum++
}
}
System.out.println(sum);

6. Inheritance and Polymorphism

Consider the following classes:

public class Blue extends Green
{
public void one()
{
System.out.println("Blue 1");
super.one();
}
}

public class Red extends Yellow
{
public void one()
{
super.one();
System.out.println("Red 1");
}

public void two()
{
System.out.println("Red 2");
super.two();
}
}

public class Yellow extends Blue
{
public void two()
{
System.out.println("Yellow 2");
}

public void three()
{
two();
System.out.println("Yellow 3");
}
}

public class Green
{
public void one()
{
System.out.println("Green 1");
}

public void three()
{
System.out.println("Green 3");
}
}

The following variables are defined:
Green var1 = new Blue();
Green var2 = new Red();
Blue var3 = new Yellow();
Object var4 = new Green();

In the table below, indicate in the right-hand column the output produced by the statement in the left-hand column. If the statement produces more than one line of output, indicate the line breaks with slashes as in "a / b / c" to indicate three lines of output with "a" followed by "b" followed by "c". If the statement causes an error, fill in the right-hand column with the phrase "error" to indicate this.

Statement Output

var1.one();    ________________________

var1.two();   ________________________

var1.three();   ________________________

var2.one();    ________________________

var2.two();   ________________________

var2.three();   ________________________

var3.two();   ________________________

var3.three();   ________________________

var4.one();   ________________________

((Blue) var1).one();   ________________________

((Yellow) var1).two();   ________________________

((Red) var2).three();   ________________________

((Yellow) var2).two();   ________________________

((Green) var4).three();   ________________________

((Yellow) var4).two();    ________________________

Link to Source PDF:

https://www.dropbox.com/s/1lrjfjs38plzska/Practice_Final_Exam.pdf?dl=0

Explanation / Answer

Hi, I have solved Q1 and Q4,

Please repost other questions in separate post.

Please let me know in case of any issue in Q1,4.

1. Analyze the running time complexity (in terms of big O notation) of the following code segment:
for (i=0; i<a.length-1; i++)
{
for (j=i+1; j<a.length; j++)
{
if(a[i] > a[j])
{
/* switch a[i] and a[j] */
tmp = a[i];
a[i] = a[j];
a[j] = tmp;
}
}

Here we have two for loops they are nested

Outer for loop runs (n-1) times: i=0 to i=n-2

For each vaulue of i, inner for loop runs : (n-i) times

So, T(n) = (n-1) + (n-2) + (n-3) + ...+ 2+ 1

            = n*(n-1)/2

            = O(n^2)

4)

public static void printStar(int n){
      
       for(int i=n; i>=1; i--){
           for(int j=1; j<=i; j++){
               System.out.print("*");
           }
           System.out.println();
       }
      
       for(int i=1; i<=n; i++){
           for(int j=1; j<=i; j++){
               System.out.print("*");
           }
           System.out.println();
       }
   }

First nested for loop: O(n^2)
Second nested for loops : O(n^2)

Total : O(n^2) + O(n^2) = O(n^2)

Related Questions

Navigate

• Browse (All)
• Browse #
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.