CS61B: Data Structures

Final Exam, Spring 2017.

Tips:

•   There may be partial credit for incomplete answers. Write as much of the solution as you can, but we may deduct points if your answers are more complicated than necessary.

•   There are a lot of problems on this exam. Work through the ones with which you are comfortable first. Do not get overly captivated by interesting design issues or complex corner cases you’re not sure about.

•   Not all information provided in a problem may be useful.

• See the coding reference sheet on the last page for potentially useful data structures.

•   Unless otherwise stated, all given code on this exam should compile. All code has been compiled and executed before printing, but in the unlikely event that we do happen to catch any bugs in the exam, we’ll announce a fix. Unless we specifically give you the option, the correct answer is not ‘does not compile. ’

•   ○ indicates that only one circle should be filled in.

•    □ indicates that more than one box may be filled in.

•   For answers which involve filling in a ○ or □, please fill in the shape completely.

0. So it begins (0.5 points). Write your name and ID on the front page. Write the exam room. Check the IDs of your neighbors. Write the given statement. Sign. Write your login in the corner of every page. Enjoy your free 0.5 points ☺ .

1. Mystery Spanning Tree 3000 (12 points).

a)   (4 pts) For the graph below, list the edges in the order they’re added to the MST by Kruskal’s and Prim’s algorithm. Assume Prim’s algorithm starts from vertex A. Assume ties are broken in alphabetical order (i.e. the edge AB would be considered before AC). Denote each edge with alphabetical overbar notation AB , which represents the edge from A to B. You may not need all blanks. For your convenience, the graph is printed twice (to make running algorithms easier).

Prim’s algorithm order:     AB BC BE EF BG CD

Kruskal’s algorithm order:   EF BC BE BG AB CD

b)  (2 pts) Is there any vertex for which the shortest paths tree (SPT) is the same as your Prim MST above?

● Yes, and it’s ____B_____  (or A or the ‘hipster vertex’ G) ○ No

c)   (6 pts) For the following propositions, fill in true or false completely and provide a brief explanation. For a proposition that is false, a counter-example suffices. Assume all edge weights are unique.

● True / ○ False: Adding 1 to the smallest edge across any cut of a graph G must change the total weight of its minimum spanning tree.

Since all edge weights are unique, either this smallest edge (now with weight +1) is included, or this smallest edge is not included, and some larger edge takes its place. Either way, total weight increases.

○ True / ● False: The shortest path from vertex A to vertex B in a graph G is the same as the shortest path from A to B using only edges in T, where T is the MST of G.

No, consider vertices C and E in the graph above.

● True / ○ False: Given any cut, the maximum-weight crossing edge is in the maximum spanning tree. Yes. We can simply use the proof of the cut-property from class, but replacing “larger” with “smaller” .

That is: Suppose it were not. In that case, we could add it to the max spanning tree and a cycle would result. To get rid of the cycle in the MaxST, we could remove the smallest edge in the cycle (which is by definition not the maximum-weight crossing edge) and end up with a larger spanning tree.

2. Sorting (28 points).

a)   (2 pts) How many inversions are in the list [A, D, B, W, K] assuming we want the list sorted alphabetically?

2 (D and B, W and K)

b)  (3 pts) Suppose we want to sort the array [5, 6, 10, 17, 14, 12, 13] using in-place heapsort. Give the array after heapification and a single remove-max operation.

[14, 10, 13, 6, 5, 12, 17]

c)   (14 pts) Suppose we have N items we want to sort. For each scenario below, pick the “best” sort to get them into sorted order. Assume for all scenarios that N is very large. There may be multiple correct answers, and the correct answer may even be ambiguous. Give the running time for the absolute worst case in the right-most column as a function of N. Running time may not be the only consideration for “best” . In all cases, assume we’re using Java.

Choose from among  1: Insertion sort, 2: Merge sort, 3: Quicksort (with Hoare partitioning), and 4: LSD radix sort. You may not need to use all four answers. Assume that we want stability when potentially useful.

Give your answer to “Best Sort” as a number.

Below are listed our answers. We may give other answers credit than those listed below. People looking at these solutions in future semesters: Argue with each other about why we picked our answers. Try to decide if you can find other reasonable answers than the ones we listed and under what assumptions (the array of 10 strings is particularly interesting). Also, hello from May 2017! It feels so … now, right now, but I bet for you it feels like the past, possibly a long time ago.

d)  (9 pts) We call a sort monotically improving if the number of inversions never increases as the sort is executed. Which sorts from the list below are monotically improving? Assume that all sorts are as presented during lecture on arrays. Assume insertion sort and selection sort are in-place. Assume heapsort is in-place and that the array acts as a max heap. Assume that Quicksort is non-randomized, uses the leftmost item as pivot, and uses the Hoare partitioning strategy (i.e. using “smaller than” and “bigger than” pointers) from lecture.

■ Insertion sort    ■ Selection sort    □ Heapsort    ■ Quicksort    □ LSD Sort     ■ MSD Sort

3. Traversals (14 points). Suppose we have an NAryIntTree, defined as shown below. Any node may have any number of children. If a node is a leaf, children is null. Assume that children[i] is never null for any i.

a)   (6 pts) Fill in the printTreePostOrder method below, which prints the values of the tree in postorder, with one val per line. Your solution must be recursive and take linear time in the number of nodes.

public class NAryIntTree {

private Node root;

public class Node {

public Node[] children;

public int val;

}

public void printTreePostOrder() {

printTreePostOrderHelper(root)

}

public void printTreePostOrderHelper(Node x) {

if (x.children != null) {

for (int i = 0; i < x.children.length; i += 1) {

printTreePostOrderHelper(x.children[i]);

}

}

System.out.println(val);

}

/* ... */

}

b) (8 pts) Fill in the code below which prints out the values of the tree in level order with one val per line. Your solution must be iterative and take linear time in the number of nodes for any tree.

private void printTreeLevelOrder() { // is a method of NAryIntTree

Queue fringe = new Queue<>();

fringe.enqueue(root);

while (fringe.size() > 0) {

Node x = fringe.dequeue();

System.out.println(x.val);

if (x.children != null) {

for (int i = 0; i < x.children.length; i += 1) {

fringe.enqueue(x.children[i]);

}

}

}

}

4. Algorithms and Data Structures (12 points).

a)   (4 pts) In class we primarily considered two graph representations: the adjacency list and the adjacency matrix. Antares suggests that we can improve the performance of Dijkstra’s algorithm with a third graph representation  he  calls  an “adjacency heap” .  For  each  vertex  v,  v’s  adjacency heap  stores  all  of v’s neighbors in a heap ordered by edge weight, so that the smallest edge adjacent to v is at the root of its heap. Naturally, Antares  stores these heaps  as  arrays. Antares reasons that by considering  small  edges  first, Dijkstra’s will be able to complete faster.

Will using an adjacency heap result in better, equivalent, or worse asymptotic runtime performance for Dijkstra’s  algorithm  than using  a regular  adjacency list?  Assume that we  only  care  about worst  case asymptotic performance. Briefly justify your answer.

○Adjacency heap is better ● Performance is the same ○ Adjacency heap is worse

Justification: Vertices get dequeued in the same order, so only difference is the time to iterate through       adjacency heap vs. list. Iteration takes the same amount of time for both assuming Antares just iterates      through the array. Or even if he deletes from the PQ, the overall runtime is still the same (see partial credit answer below).

Or for partial credit:

○Adjacency heap is better ○ Performance is the same ● Adjacency heap is worse

Justification: Vertices get dequeued in the same order, so only difference is the time to iterate through         adjacency heap vs. list. Since Antares wants to go through “small edges first”, perhaps this means that he    iterates through in decreasing order, which must takes D log D time, where D is the degree of the vertex. In the worst case, the totality of these iterations costs E log V. This does not change the runtime of Dijkstra’s  algorithm asymptotically, so is not correct, but we gave partial credit for recognizing (as long as your         answer was very clear) that Antares’s idea was simply going to slow things down with no benefit                whatsoever.

b)  (4 pts) Suppose Antares has conjured up the Gulgate Priority Queue (GPQ). Given a GPQ containing N elements, the worst-case running time for insertion, deletion, and change-priority are given as follows: Insertion: (N), Deletion: (N), Change-Priority: (1).

Suppose we run the implementation of Dijkstra's algorithm provided in class (where every vertex is initially inserted into the PQ with infinite priority) using a GPQ on a graph with V vertices and E edges. What is the worst case runtime of Dijkstra’s? Give your answer in big O notation in terms of V and E. Assume that E >> V (this means E is much greater than V).

Runtime:   O(E+V2), but since E is bounded above by V2, it’s fine to also say O(V2). Simplifications which      remove V2 log V are not correct, e.g. O(E log V) and O(E log E): Suppose we build graphs where E = V1.5 . In  this case, E is certainly much larger than V as both grow very large, but the function E log V would grow more slowly than V2 log V.

c)   (4 pts)  Suppose Antares has  also  created  a Xelha Quick Union (XQU) to  check  if two vertices  are connected while running Kruskal’s. Given that there are N items in an XQU, the running time for XQU operations is as follows: Constructor: (N), Union: (N log N), Is-Connected: (log N)

Suppose we run the implementation of Kruskal’s algorithm as presented in class using a XQU and a heap- based priority queue. Recall that in our version of Kruskal’s from class, all edges are initially inserted into a regular heap-based priority queue and removed one by one, and added to the MST so long as there are no cycles. What is the worst case runtime of Kruskal’s algorithm? Give your answer in big O notation in terms of V and E. Assume that E >> V.