HW1

Goal: To understand how to analyze code at the per operation level. To understand the terminology to discuss and communicate the runtime of algorithms. To exercise understanding of the Java language. To exercise understanding of Stacks and Queues. To be able to implement a java method given high level instructions.

#1

Give the exact number, tilde, and Big O values of assignment to the sum variable (= and +=) and and compare operations for each of the following:

// a.
sum = 0;
for (int i=0; i < n*n; i++){
    for (int j=0; j < n*n; j++){
        sum += 1;
    }
}
//Assignment: Exact: ________, tilde: ________, Big O: ________  
//Compare   : Exact: ________, tilde: ________, Big O: ________  

//b
sum = 0;
for (int i=0; i < n; i++){
    for (int j=0; j < i; j++){
        sum += 1;
    }
}
//Assignment: Exact: ________, tilde: ________, Big O: ________  
//Compare   : Exact: ________, tilde: ________, Big O: ________ 

// c
sum = 0;
for (int i=0; i < n*n; i++){
    for (int j=0; j < i; j++){
        sum += 1;
    }
}
//Assignment: Exact: ________, tilde: ________, Big O: ________  
//Compare   : Exact: ________, tilde: ________, Big O: ________  
 

#2

a. Give the exact number of array accesses and compare operations with respect to the length of num (call this n) in the best and worst case. Describe the best and worst case and explain why they have the runtime you specify.

void BubbleSort(int[] num) {
    int j;
    boolean flag = true; // set flag to true to begin first pass
    int temp; // holding variable
    while (flag) {
        flag = false; // set flag to false awaiting a possible swap
        for (j = 0; j < num.length - 1; j++) {
            if (num[j] < num[j + 1]) {
                temp = num[j]; // swap elements
                num[j] = num[j + 1];
                num[j + 1] = temp;
                flag = true; // shows a swap occurred
            }
        }
    }
} // code credit: mathbits.com

//Best Case Description: __________________________________
//Array Access: Exact: ______________
//Compare     : Exact: ______________

//Worst Case Description: __________________________________
//Array Access: Exact: ______________
//Compare     : Exact: ______________

b. What are the Big O and ~ runtimes of the above code?

#3

a. Does $O(\log_{10} n) = O(\log_2 n)$? Why? (hint: recall the rules of logarithms)
b. Does $O(\log_{10} n) = O(\log n^2)$? Why?
c. Plot the above functions using R, Python, or Java and submit the code and a png file of the plot

#4

d. Order the following functions by growth rate:
$n$
$\sqrt{n}$
$n^{1.5}$
$n^2$
$n \log n$
$n \log \log n$
$n \log_2 n$
$n \log(n^2)$
$2^n$
$2^{\frac{n}{2}}$
$37$
$n^3$
$n^2 \log n$

b. Indicate which functions grow at the same rate.

#5

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);
    }
}

#6

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.

#7

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?

#8

What is the result of the following sequence of method calls? Show the contents of the data structure after every operation.

add(4)
add(8)
add(1)
add(6)
remove()
remove()

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

#9

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

collection.add("First");
collection.add("Second");
collection.add("Third");
for (String i : collection) {
   System.out.println(i);
}

#10

Given two arrays, write a function to compute their intersection.

Example:
Given nums1 = [1, 2, 2, 1], nums2 = [2, 2], return [2].

Note:
Each element in the result must be unique.
The result can be in any order.
Name your source file Intersection.java

// here is some code to get started with
void main(String[] args) {
    {
    int[] x = {1, 2, 2, 1};
    System.out.println("x = " + Arrays.toString(x));
    int[] y = {2, 2};
    System.out.println("y = " + Arrays.toString(y));
    int[] z = intersection(x, y);
    System.out.println("intersection(x, y) = " + Arrays.toString(z));

    System.out.println(Arrays.equals(z, new int[]{2}));
    }

    {
    int[] x = {2, 5, 3, 7};
    System.out.println("x = " + Arrays.toString(x));
    int[] y = {5, 2, 9, 0, 1};
    System.out.println("y = " + Arrays.toString(y));
    int[] z = intersection(x, y);
    System.out.println("intersection(x, y) = " + Arrays.toString(z));
    
    Arrays.sort(z);
    int [] correct = new int[]{2,5};
    Arrays.sort(correct);
    System.out.println(Arrays.equals(z, correct));
    }
}

int[] intersection(int[] nums1, int[] nums2) {
...
}

Due: 6/9 @5pm
Turn in answers digitally to the hw1 folder with the filename “memo.txt”

Grading:
9 points: All questions correct.
1 point: How easy was the assignment to grade.