CS 61B MSTs, Dijkstra’s, and Tries Spring 2021 Exam Prep Discussion 11: April 5, 2021
1 Oracle Dijkstra’s
In some graph G, we are given a sorted list of nodes, sorted by their distances from some start vertex A. Design an efficient algorithm to find the shortest paths tree starting from A.
Hint: Your algorithm should be more efficient than Dijkstra’s.
2 MSTs, Dijkstra’s, and Tries 2 Multiple MSTs
Recall a graph can have multiple MSTs if there are multiple spanning trees of minimum weight.
(a) For each subpart below, select the correct option and justify your answer. If you select “never” or “always,” provide a short explanation. If you select “sometimes”, provide two graphs that fulfill the given properties — one with multiple MSTs and one without. Assume G is an undirected, connected graph.
1. If none the edge weights are identical, there will ⃝ never be multiple MSTs in G.
⃝ sometimes be multiple MSTs in G.
⃝ always be multiple MSTs in G.
Justification:
2. If some of the edge weights are identical, there will ⃝ never be multiple MSTs in G.
⃝ sometimes be multiple MSTs in G.
⃝ always be multiple MSTs in G.
Justification:
3. If all of the edge weights are identical, there will ⃝ never be multiple MSTs in G.
⃝ sometimes be multiple MSTs in G.
⃝ always be multiple MSTs in G.
Justification:
(b) Suppose we have a connected, undirected graph G with N vertices and N edges, where all the edge weights are identical. Find the maximum and minimum number of MSTs in G and explain your reasoning.
Minimum: _________ Maximum: _________
Justification:
(c) It is possible that Prim’s and Kruskal’s find different MSTs on the same graph G (as an added exercise, construct a graph where this is the case!). Given any graph G with integer edge weights, modify G to ensure that Prim’s and Kruskal’s will always find the same MST. You may not modify Prim’s or Kruskal’s.
Hint: Look at subpart 1 of part a.
MSTs, Dijkstra’s, and Tries 3
4 MSTs, Dijkstra’s, and Tries
3 Graph Algorithm Design
For each of the following scenarios, write a brief description for an algorithm for finding the MST in an undirected, connected graph G.
(a) If all edges have edge weight 1. Hint: Runtime is O(V+E)
(b) If all edges have edge weight 1 or 2. Hint: Use your algorithm from part (a)
4 A Wordsearch
Given an N by N wordsearch and N words, devise an algorithm to solve the word- search in O(N3). For simplicity, assume no word is contained within another, i.e. if the word ”bear” is given, ”be” wouldn’t also be given.
If you are unfamiliar with wordsearches or want to gain some wordsearch solving intuition, see below for an example wordsearch. Note that the below wordsearch doesn’t follow the precise specification of an N by N wordsearch with N words, but your algorithm should work on this wordsearch regardless.
Example Wordsearch:
Hint: Add the words to a Trie, and you may find the longestPrefixOf operation helpful. Recall that longestPrefixOf accepts a String key and returns the longest prefix of key that exists in the Trie, or null if no prefix exists.
MSTs, Dijkstra’s, and Tries 5