1. Using the big-Oh notation, what is the worst-case time complexity of each of the following pieces of code? In every case consider n being the growth rate variable. When there is no variable n in the code, consider that the variable responsible for the growth is n in the big-oh notation.

void test1(int n) {

int m = 10 * n;

while (m > 0) {

System.out.println(n + m);

m--; n = n * 2;

}

} . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

void test2(int n) {

int sum = 0;

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

System.out.println(n);

sum += n;

}

System.out.println(sum);

} . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

void test3(int n) {

for (int i = n; i > 1; i--) {

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

System.out.println(i+j); }

}

} . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

void test4(int n) {

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

for (int j = 1; j < n; j *= 2) {

for (int k = 0; k <= 10; k++) {

System.out.println("test");

}

}

}

} . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . void test5(int[] arr) {

if (arr.length%2==1){

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

System.out.println(arr[i]);

}

} else{

for (int i = 1; i < arr.length; i++) {

arr[i] = arr[i-1];

int j=0;

while (j<=arr.length){

System.out.println(arr[j]);

j=j*2;

}

}

}

} . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

2. Write a recursive method that sums up all the odd numbers between 1 and n. As an example, if n == 5 the method must return 9, which is the sum 5 + 3 + 1. If n == 6 the method must return 9, as well, because the odd numbers to sum are still 5, 3, and 1. You must use the following method header. public static int recursiveOddSum(int n){

3. You have the following three methods.

public static void recursivePrint1(int r){

if (r==0)

return;

System.out.println(r);

recursivePrint1(r-1);

}

public static void recursivePrint2(int r){

if (r<=1)

return;

recursivePrint2(r/2);

System.out.println(r);

}

public static int recursivePrint3(int r){

System.out.println(r);

if (r<=1)

return 0;

int a= recursivePrint3(r/2);

int b= recursivePrint3(-r/2);

return a+b;

}

(a) What is the terminal output of the method call recursivePrint1(5)?

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

(b) What is the terminal output of the method call recursivePrint2(5)?

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

(c) What is the terminal output of the method call recursivePrint3(5)?

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

4. Suppose you have a doubly linked list of Node objects with char data elements. The Node class is provided below. class Node {

char data;

Node next; // links to the next node

Node prev; // links to the previous node

}

Consider that head is the reference variable that holds the starting non-null node and tail is the last non-null node of the doubly linked list you have. Obviously, both head and tail are instances of the Node class.

(a) Write a recursive method named isPalindrome that checks whether a sequence of characters in a doubly linked list of Node objects forms a palindrome. The method must return true if the sequence forms a palindrome; otherwise, it should return false. As examples, if the linked list contains {A, C, C, A} or {A, C, A} in a sequence then the isPalindrome method should return true. For a sequence, {A, C, C, B}, the isPalindrome method should return false. You must use the following header.

public static boolean isPalindrome(Node head, Node tail) {

(b) What is the time complexity (big-oh) of the isPalindrome method you have written?

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

5. Write a recursive method that will return the count of vowels in a string. For example, the method should return 5 for an input string application. Assume that string s will not contain uppercase letters.

public static int countVowels(String s){

6. Compute the big-oh time complexity of the following function. You must show the derivation for full credit.

T(n) = T(n/ 3) + c

You might need the following list of formulas to solve this problem.

1+2+3...+(n-1)+n = n(n+1)/2

a^0 + a^1+ a^2 + a^3+....+ a^(n-1)+a^n = a^(n+1)-1/a-1

2^0 + 2^1 + 2^2 + 2^3 + .....+ 2^(n-1) + 2^n = 2^(n+1)-1/2-1

7. Two algorithms, A and B, have the time functions f and g, where f(n) = 10n^2 + 16n + 11 and g(n) = 9n^2 + 22n + 6. Determine which algorithm runs faster. You must show the derivations for full credit. You will need to compute a maximum common point after which one algorithm is faster than the other but before that point the conclusion might not be true.

8. Show divide-and-conquer steps of merge sort on the following array: 15, 8, 13, 11, 7. You must show each step of the algorithm.