HW1

CS310 Homework 1

1. NULL (There is no question 1)

2. Give the big O for each of the following:

 a.
sum = 0;
for (int i=0; i < n; i++)
{
for (int j=0; j < i; j++)
{
sum += 1;
}
}

b.
sum = 0;
for (int i=0; i < n*n; i++)
{
for (int j=0; j < n*n; j++)
{
sum += 1;
}
}

c.
sum = 0;
for (int i=0; i < n*n; i++)
{
for (int j=0; j < i; j++)
{
sum += 1;
}
}


3
a. Does O(log n) = O(log_2 n)? Why? (hint: recall the rules of logarithms)
b. Does O(log n) = O(log n^2)? Why?

4
a. Does O(2^n) = O(3^n)? Why?
b. Does O(2^n) = O(2^(n/2))? Why?

5
a. Order the following functions by growth rate:

N, square root of N, N^1.5 , N^2, N log N, N log log N, N log_2 N, N log(N^2), 2^N , 2^(N/2), 37, N^3, and N^2 log N

b. Indicate which functions grow at the same rate.

6
Actual interview question. What is the output? Give a detailed explanation for each println statement.

public class O
{
static int x = 1;

public static void main(String args[]){
O o = new O();
o.call(3);
}

public void call(int x){
O o = new O();
this.x = 5;

System.out.println("Output: " + x);
System.out.println("Output: " + O.x);
System.out.println("Output: " + o.x);
}
}

7
a. What are the implementation differences between abstract classes vs interfaces?
b. Difference between implements and extends? Can you implement multiple interfaces or extend multiple classes?
c. Describe a use case for each.

8.

public static void main(String args[])

a. Why must main be public? Why not private?
b. Why must main be static? Why not a normal method?
c. What’s the void for, and what are the args?

9.
Show the results of the following sequence:

	add(4)
remove()
remove()

for the following data structures:
a. Stack
b. Queue
c. Priority queue (1 is top priority)

10.
What would the output of the following code be if S was a:
a. Stack
b. Queue

S.add("First");
}