Complete the code

/**

* Question 1a - what's my order?

*

* @param n

*/

public static void bigOh1(int n) {

long time = System.nanoTime();

int total = 0;

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

total += i;

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

total += j;

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

total += k;

System.out.println(String.format("BigOh1 calculated %d in %d uS",

n, System.nanoTime()-time));

}

/**

* Question 1b - what's my order

*

* @param n

*/

public static void bigOh2(int n) {

long time = System.nanoTime();

int total = 0;

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

total += i;

System.out.println(String.format("BigOh2 calculated %d in %d uS",

n, System.nanoTime()-time));

}

/**

* Question 1c - what's my order

*

* @param n

*/

public static void bigOh3(int n) {

long time = System.nanoTime();

int total = 0;

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

total += i;

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

total += j;

}

System.out.println(String.format("BigOh3 calculated %d in %d uS",

n, System.nanoTime()-time));

}

/**

* Question 1d - what's my order

*

* @param n

*/

public static void bigOh4(int n) {

long time = System.nanoTime();

int total = 0;

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

total += i;

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

total += j;

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

total += k;

}

}

System.out.println(String.format("BigOh4 calculated %d in %d uS",

n, System.nanoTime()-time));

}

/**

* Question 2 - simple recursion

* Sum the first n number 1..n

* sumOf(1) = 1

* sumOf(2) = 1+2

* sumOf(3) = 1+2+3

* ...

* sumOf(9) = 1+2+3+4+5+6+7+8+9 = 45

*

* @param n

*/

public static int sumOf(int n) {

// TODO - write the code

return 0;

}

/**

* Question 3 - Recursive Backtracking

* Same as Ex 12.8 except you can take 1,2,or 3 stairs at a time

*

* waysToClimb(1) == [1]

* waysToClimb(2) == [1, 1][2]

* waysToClimb(3) == [1, 1, 1][1, 2][2, 1][3]

* waysToClimb(4) == [1, 1, 1, 1][1, 1, 2][1, 2, 1][1, 3][2, 1, 1][2,

2][3, 1]

*

* @param stairs

*/

public static void waysToClimb(int stairs) {

ArrayList list = new ArrayList();

System.out.println("waysToClimb("+stairs+")");

if (stairs != 0)

explore(stairs, list, 0);

System.out.println();

}

/**

* Question 3a - Helper routine for waysToClimb

* There are many ways to solve this, but it can be done similar to

factorsOf using this helper

* Don't forget that unlike the strings of factorsOf, you must

"reset" the List between trying different size steps

*

* @param stairs - total # of stairs

* @param list - list of steps taken to be printed

* @param listLength - # of stairs climbed so far

*/

public static void explore(int stairs, ArrayList list, int

listLength) {

// TODO - write the code

}

/**

* Question 4 - binary search - predict the mid values & return for

the following:

*

* array = {-10, -5, -2, 1, 3, 4, 35, 72, 95};

* 0 1 2 3 4 5 6 7 8

*

* What are the mid values & return for these values: -2,-1

*

*/

public static void binarySearchTest() {

int[] test = {-10, -5, -2, 1, 3, 4, 35, 72, 95};

System.out.println("test array = " + Arrays.toString(test));

System.out.println("search(-2) : " + binarySearch(test,-2));

System.out.println("search(-1) : " + binarySearch(test,-1));

}

/**

* Question 4 - binary search - predict the indexes visited for

binary search and complete the code to verify

*

* @param nums

* @param target

* @return

*/

public static int binarySearch(int[] nums, int target) {

int start = 0;

int end = nums.length-1;

int mid = 0;

/*

while (false) { // TODO - replace test

mid = (end + start) / 2;

System.out.printf("Start: %d , Mid: %d, End: %d ", start,

mid, end);

if ( false ) { // TODO - replace test

return mid;

} else if (target > nums[mid]) {

// TODO - fill in code

} else {// target <= mid

// TODO - fill in code

}

}

*/

return -start-1;

}

/**

* Question 5 - Mergesort - predict the splits and merges of the

following array to be sorted

*

* Array = {-30,15,-3,0,10,-11,29,7,-5,9}

* 1st split

* 2nd split

* 3rd split

* 1st merge

* 2nd merge

* 3rd merge

*

* Note it's quite challenging to print all the splits/merges on the

same line so the code prints

* the split/merge level next to each fragment

*/

public static void mergeTest() {

int[] test = {-30,15,-3,0,10,-11,29,7,-5,9};

System.out.println("Before sorting: " + Arrays.toString(test));

System.out.println("After sorting: " +

Arrays.toString(mergesort(test)));

}

/**

* 5) Performs a mergesort on two arrays

*

* @param input

* @return

*/

public static int[] mergesort(int[] input) {

return mergesort(input, 0);

}

/**

* 5) Helper for mergesort that includes the level

*

* @param input

* @param level

* @return

*/

public static int[] mergesort(int[] input, int level) {

int N = input.length;

if (N <= 1) return input;

int[] a = new int[N/2];

int[] b = new int[N - N/2];

for (int i = 0; i < a.length; i++)

a[i] = input[i];

for (int i = 0; i < b.length; i++)

b[i] = input[i + N/2];

System.out.println(level + ": split " + Arrays.toString(a) +

Arrays.toString(b));

return merge(mergesort(a, level+1), mergesort(b, level+1), level);

}

/**

* 5) Merges two arrays with a level number

*

* @param a

* @param b

* @return

*/

private static int[] merge(int[] a, int[] b, int level) {

int[] c = new int[a.length + b.length];

int i = 0, j = 0;

for (int k = 0; k < c.length; k++) {

if (i >= a.length) c[k] = b[j++];

else if (j >= b.length) c[k] = a[i++];

else if (a[i] <= b[j]) c[k] = a[i++];

else c[k] = b[j++];

}

System.out.println(level + ": merged: " + Arrays.toString(c));

return c;

}

/**

* Question 6 - reverse a stack

*/

public static void reverseStackTest() {

Stack test = new Stack();

test.push(1);

test.push(2);

test.push(3);

System.out.println("Original stack: " + test);

reverseStack(test);

System.out.println("Reversed stack: " + test);

}

/**

* 6) reverse stack - reverse a stack without creating a second

stack. You may create a single queue

*

* @param input

* @return

*/

public static void reverseStack(Stack input) {

// TODO - write the code with only an additional queue

Queue q = new LinkedList();

}

/**

* Question 7 - reverse a linked list - write it in the last method

of the file

*

*/

public static void reverseLinkedListTest() {

LinkedIntList l = new LinkedIntList();

l.add(0);

l.add(1);

l.add(2);

System.out.println("Original LinkedList: " + l);

l.reverse();

System.out.println("after reversing: " + l);

}

/**

* Q7 helper

*/

static class ListNode {

public int data;

public ListNode next;

public ListNode(int value) {

this.data = value;

this.next = null;

}

}

/**

* Q7 helper

*/

static class LinkedIntList {

private ListNode front; // null for an empty list

public LinkedIntList() {

front = null;

}

public void add(int value) {

if (front == null) {

front = new ListNode(value);

} else {

ListNode current = front;

while (current.next != null) {

current = current.next;

}

current.next = new ListNode(value);

}

}

/**

* Q7 helper

*/

@Override

public String toString() {

if (front == null) {

return "[]";

}

String result = "[" + front.data;

ListNode current = front.next;

while (current != null) {

result += ", " + current.data;

current = current.next;

}

result += "]";

return result;

}

/**

* Q7 write reverse for a linked list

*/

public void reverse() {

// TODO - write the code.

ListNode current = this.front;

}

}

}