JAVA. Must finish code below.

Please write your answers to problems 1 through 4 in electronic format (Word, etc.), or write them on paper and scan the pages. In either case, please upload your solutions into the D2L dropbox when you have completed the assignment.

1. (2 points) Demonstrate the -complexity of the functions below. In order to demonstrate that f(n) = (g(n)) you must find 4 positive constants C1, C2, x1, and x2 such that

C1*g(n) f(n) for all n x1 C2*g(n) f(n) for all n x2

In each of your answers, you should list values for these 4 constants for the given function f.

f(n) = 5

f(n) = n3 - 3*n2 + 5

f(n) = 2*log2(n) - 4

f(n) = n + log2(n) + 2

2. (2 points) Give a complexity, in terms of n, of the worst-case running time of each of the code fragments below. Assume that n has been declared appropriately and has been set to a value.

(a) int sum = 0; for ( int i = 0; i < n; i++) 

 for ( int j = i; j < n; j += 2) sum++; 

(b) int sum = 0; for ( int i = 0; i < n * n; i++) 

 for ( int j = 0; j < i; j++ ) sum++; 

(c) int sum = 0; 

for ( int i = n; i<0; i/=2) for ( int j = 0; j < n; j++ ) 

sum++;

(d) int sum = 0; for ( int i = n; i<0; i/=2) 

 for ( int j = 0; j < i; j++ ) sum++; 

3. (2 points) Consider the following priority queue. Notice that higher numbers have higher priority.

Draw the state of the queue after each insertion: 6. 7, 4, 10

4. (2 points) Consider the following priority queue. Again, notice that higher numbers have higher priority.

Show the state of the queue after each of 4 calls to the poll method (i.e., the method which dequeues the highest priority item in the queue).

5. (2 points) Given the code for the PQ class discussed during lecture on Monday, July 10, implement a method called changePriority. It is passed 2 parameters: an item (of type T) and an integer representing the items new priority. The priority queue should be modified to reflect the new priority, with the item moving either up or down the queue as specified by the new priority.

package hw5;

/* * CSC 300 Sections 201, 210 Summer I 2017 * An implementation of a priority queue */

public class PQ { private T items[]; private int priorities[];

/****** YOU MUST IMPLEMENT THIS METHOD *******/ public void changePriority(T item, int newPriority) { } private static final int INIT_CAPACITY = 5; private int size;

public PQ() { items = (T[]) new Object[INIT_CAPACITY]; priorities = new int[INIT_CAPACITY]; size = 0; } public void expand() { T newItems[] = (T[]) new Object[items.length*2 + 1]; int newPriorities[] = new int[priorities.length*2 + 1]; for (int i=0; i

public void enqueue(T item, int priority) { if (size == items.length) expand(); items[size] = item; priorities[size] = priority; up(size++); }

public T dequeue() { T answer = items[0]; items[0] = items[size-1]; priorities[0] = priorities[size-1]; size--; down(0); return answer; } private void up(int index) { if (index == 0) return; int pIndex = parentIndex(index); if (priorities[pIndex] >= priorities[index]) return; int temp = priorities[pIndex]; priorities[pIndex] = priorities[index]; priorities[index] = temp; T temp2 = items[pIndex]; items[pIndex] = items[index]; items[index] = temp2; up(pIndex); } private void down(int index) { int left = leftChildIndex(index); int right = rightChildIndex(index); if (left == -1 && right == -1) return; int child = left; if (right != -1 && priorities[right] > priorities[left]) child = right; if (priorities[child] > priorities[index]) { int temp = priorities[child]; priorities[child] = priorities[index]; priorities[index] = temp; T temp2 = items[child]; items[child] = items[index]; items[index] = temp2; down(child); } } private int parentIndex(int cIndex) { int idx = (cIndex-1); if (idx < 0) return -1; return idx/2; } private int leftChildIndex(int pIndex) { int idx = pIndex*2 + 1; if (idx >= size) return -1; else return idx; } private int rightChildIndex(int pIndex) { int idx = pIndex*2 + 2; if (idx >= size) return -1; else return idx; } public static void main(String[] args) { PQ q = new PQ(); String letters = "abcdefghij"; int p[] = {1, 3, 5, 2, 4, 8, 7, 9, 6, 0}; for (int i=0; i<10; i++) q.enqueue(letters.charAt(i), p[i]); for (int i=0; i<10; i++) System.out.println(q.dequeue()); } }