Q1Arrays20 Points

Given the following code segment (line number for reference):

1. for (int i = 0; i

2. {

3. for (int j = n-1; j > i; j--)

4. {

5. if ( a[j]

6. {

7. int t = a[j];

8. a[j] = a[j -1];

10 }

11 }

12 }

a) (5 points) What is the number of times the if conditional on line 5 is executed? Give your answer in terms of n? Explain why.

b) (5 points) What is the maximum number of array accesses (reads and writes) for the entire code segment in terms of n? Explain why.

c) (5 points) What is the tilde notation for the answer from part (b)?

d) (5 points) What is the Big-O notation to represent the order of growth from part (b) in terms of n?

Q2Union-find25 Points

A client program is using the union-find API to solve a dynamic connectivity problem in networking. Assume that there are 10 sites identifies as: 0, 1, 2, 3, 4, 5, 6, 7, 8, and 9 in the network. Answer the following questions.

a) (5 points) If the union-find API is implemented with the quick-find discussed in class, show the content of the id[ ] array after adding the following edges in sequence: 0-9, 1-8, 2-7, 9-1

Please select file(s)Select file(s)

b) (10 points) If the API is implemented with quick-union discussed in class, show the content of the parent[ ] array after adding the following edges in sequence: 1-2, 4-5, 6-7, 0-1, 2-4

Please select file(s)Select file(s)

c) (10 points) If the API is implemented with weighted quick-union discussed (union by size) in class, show the content of the parent[ ] and size[ ] array after adding the same edges from part (b).

Please select file(s)Select file(s)

Q3Stacks20 Points

Given the following code segment:

Stack stack = new Stack();

int count = 1;

while (count

{

if (count % 2 == 0)

Stdout.print(count);

else

stack.push(count);

count++;

}

while (!stack.isEmpty())

StdOut.print(stack.pop());

a) (5 points) Describe, in a sentence, what the code segment does.

b) (5 points) What is the output of the code segment?

c) If we replace the if(count % 2 == 0) statement with if(foo()), where foo() returns either true or false, answer the following questions.

i) (5 points) Is the following output possible? 9 8 7 6 5 4 3 2 1. Explain.

ii) (5 points) Is the following output possible? 1 7 3 10 9 8 6 5 4 2. Explain.

Q4Queues20 Points

Assume that a Queue is implemented using a fixed-size circular array of capacity 6. Show the array after each operation in the sequence, label head (h) and tail (t) indices after each operation.

Queue q = new Queue();

q.enqueue(4);

q.enqueue(1);

q.enqueue(3);

q.enqueue();

q.enqueue(8);

q.enqueue();

q.enqueue(5);

q.enqueue(2);

q.enqueue(7);

answer =

Please select file(s)Select file(s)

Q5Linked Lists, findLastDup20 Points

Write the linear time method findLastDup that finds and returns the Node containing the last duplicate item in a sorted linked list of integers. Assume the following Node class:

public class Node {

public int item;

public Node next;

}

public static Node findLastDup (Node front) {...}

For example:

front -> 2 -> 3 -> 3 -> 4 -> 5 -> 6 -> 7 -> 7 -> 7 -> 8 -> 9 returns the last node containing 7

front -> 5 -> 5 -> 15 -> 15 -> 30 -> 30 -> 40 -> 40 -> 45 -> 45 returns the last node containing 45

front -> 13 -> 54 -> 78 -> 79 -> 80 returns null

answer =

Please select file(s)Select file(s)

Q6Linked Lists, removeDup 25 Points

Write the linear time method removeDup that removes all occurrences of duplicate items from a sorted linked list of integers, retain only one copy of each item. Assume the following Node class:

For example:

front -> 2 -> 3 -> 3 -> 4 -> 5 -> 6 -> 7 -> 7 -> 7 -> 8 -> 9 is updated to

front -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9

front -> 5 -> 5 -> 15 -> 15 -> 30 -> 30 -> 40 -> 40 -> 45 -> 45 is updated to

front -> 5 -> 15 -> 30 -> 40 -> 45

front -> 13 -> 54 -> 78 -> 79 -> 80 remains the same

answer =

Please select file(s)Select file(s)