CS 61B Heaps and Graphs Spring 2021 Exam Prep Discussion 9: March 15, 2021
1 Fill in the Blanks
Fill in the following blanks related to min-heaps. Let N is the number of elements in the min-heap. For the entirety of this question, assume the elements in the min-heap are distinct.
1. removeMin has a best case runtime of runtime of .
2. insert has a best case runtime of time of .
3. A or
output the elements in sorted order. Assume there are at least 3 elements in the min-heap.
4. The fourth smallest element in a min-heap with 1000 elements can appear in places in the heap.
5. Given a min-heap with 2n − 1 elements, for an element
• to be on the second level it must be less than ele-
ment(s) and greater than element(s).
• to be on the bottommost level it must be less than element(s) and greater than element(s).
Solution:
1. removeMin has a best case runtime of Θ(1) and a worst case runtime of Θ(logN ).
2. insert has a best case runtime of Θ(1) and a worst case runtime of Θ(logN).
3. A pre order or level order traversal on a min-heap can output the elements in
sorted order.
4. The fourth smallest element in a min-heap with 1000 distinct elements can appear in 14 places in the heap. (it can be on the second, third, or fourth levels)
5. Given a min-heap with 2N − 1 distinct elements, for an element –
• to be on the second level it must be less than 2(N−1) −2 element(s) and greater than 1 element(s). (must be greater than the topmost and less than the elements in its subtree)
• to be on the bottommost level it must be less than 0 element(s) and greater than N – 1 element(s). (must be greater than the elements on its branch)
and a worst case and a worst case run-
traversal on a min-heap may
2 Heaps and Graphs
2 Heap Mystery
We are given the following array representing a min-heap where each letter repre- sents a unique number. Assume the root of the min-heap is at index zero, i.e. A is the root. Note that there is no significance of the alphabetical ordering, i.e. just because B precedes C in the alphabet, we do not know if B is less than or greater than C.
Array: [A, B, C, D, E, F, G]
Four unknown operations are then executed on the min-heap. An operation is either a removeMin or an insert. The resulting state of the min-heap is shown below.
Array: [A, E, B, D, X, F, G]
(a) Determine the operations executed and their appropriate order. The first op- eration has already been filled in for you!
1. removeMin() 2.
3.
4.
Solution:
1. removeMin() 2. insert(X) 3. removeMin() 4. insert(A)
Explanation: We know immediately that A was removed. Then, after looking at the final state of the min-heap, we see that C was removed. Then, for A to remain in the min-heap, we see that A must have been inserted afterwards. And, after seeing a new value X in the min-heap, we see that X must have been inserted as well. We just need to determine the relative ordering of the insert(X) in between the operations removeMin() and insert(A), and we see that the insert(X) must go before both.
(b) Fill in the following comparisons with either >, <, or ? if unknown. Note that this question does not assume a specific ordering of operations from the previous part, i.e. we don’t know which of the two possible
1.X D 2.X C 3.B C 4.G X
Solution:
1. X ? D 2. X > C 3. B > C 4. G < X
Reasoning:
1. X is never compared to D
2. X must be greater than C since C is removed after X’s insertion.
3. B must also be greater than C otherwise the second call to removeMin would have removed B
4. X must be greater than G so that it can be ”promoted” to the top after the removal of C. It needs to be promoted to the top to land in its new position.
Heaps and Graphs 3
4 Heaps and Graphs
3 Graph Conceptuals
Answer the following questions as either True or False and provide a brief expla- nation:
1. If a graph with n vertices has n − 1 edges, it must be a tree. False. The graph must be connected.
2. The adjacency matrix representation is typically better than the adjacency list representation when the graph is very connected.
True. The adjacency matrix representation is usually worse than the adja- cency list representation with regards to space, scanning a vertex’s neighbors, and full graph scans. However, when the graph is very connected, the ad- jacency matrix representation has roughly same asymptotic runtime in these operations, while “winning” in operations like hasEdge.
3. Every edge is looked at exactly twice in every iteration of DFS on a connected, undirected graph.
True. The two vertices the edge is connecting will look at that edge when it’s their turn.
4. In BFS, let d(v) be the minimum number of edges between a vertex v and the start vertex. For any two vertices u, v in the fringe, |d(u) − d(v)| is always less than 2.
True. Suppose this was not the case. Then, we could have a vertex 2 edges away and a vertex 4 edges away in the fringe at the same time. But, the only way to have a vertex 4 edges away is if a vertex 3 edges away was removed from the fringe. We see this could never occur because the vertex 2 edges away would be removed before the vertex 3 edges away!
4 Cycle Detection
Given an undirected graph, provide an algorithm that returns true if a cycle exists in the graph, and false otherwise. Also, provide a Θ bound for the worst case runtime of your algorithm. You may use either an adjacency list or an adjacency matrix to represent your graph. (We are looking for an answer in plain English, not code).
We do a depth first search traversal through the graph. While we recurse, if we visit a node that we visited already, then we’ve found a cycle. Assuming integer labels, we can use something like a visited boolean array to keep track of the elements that we’ve seen, and while looking through a node’s neighbors, if visited gives true, then that indicates a cycle.
However, since the graph is undirected, if an edge connects vertices u and v, then u is a neighbor of v, and v is a neighbor of u. As such, if we visit v after u, our algorithm will claim that there is a cycle since u is a visited neighbor of v. To address this case, when we visit the neighbors of v, we should ignore u. To implement this in code, one idea is using a Map to map each node to the node we took to get there, e.g. we would map v to u in the example described above.
In the worst case, we have to explore at most V edges before finding a cycle (number of edges doesn’t matter). So, this runs in Θ(V ).
Heaps and Graphs 5