4/6/2020 Yijie Lu’s Quiz History: Practice Midterm 2
Practice Midterm 2 Results for Yijie Lu
Submitted Mar 30 at 12:42am
Question 1
Not yet graded / 5 pts
Consider a priority queue implementation that requires O(|V|) time to initialize, O(f(V,E)) time in the worst case for each Extract-Min operation, and O(g(V, E)) time in the worst case for each Decrease-Key operation. Suppose you implement Dijkstra’s algorithm using the priority-queue implementation just described. What is the worst-case running time of Dijkstra’s algorithm on an input graph G = (V, E)? You may assume that G is directed. No justification for your answer is required.
Your Answer:
O(|V|·f(V,E)+|E|·g(V,E))
Question 2
Not yet graded / 5 pts
True or False. A depth-first forest of a directed graph always produces the same number of tree edges, regardless of the order in which the vertices are processed. Justify your answer briefly.
Your Answer:
https://canvas.upenn.edu/courses/1488890/quizzes/2313738/history?version=1 1/7
4/6/2020 Yijie Lu’s Quiz History: Practice Midterm 2
False. A directed graph on two vertices u and v, with only one directed edge (u,v) serves as a counterexample. If the search begins from u then (u, v) is a tree edge, but if the search begins from v then (u, v) is not a tree edge (it is a cross edge).
Question 3
Not yet graded / 12 pts
Consider using Huffman encoding scheme on a set S of n characters. Prove that if some character in S occurs with a frequency more than 0.44, then in the output of the Huffman encoding, there is guaranteed to be a codeword of length 1. For this problem you must state your complete proof below.
Your Answer:
https://canvas.upenn.edu/courses/1488890/quizzes/2313738/history?version=1 2/7
4/6/2020 Yijie Lu’s Quiz History: Practice Midterm 2
Assume for contradiction that none of the characters in S have a codelength of 1. Observe that since no character in S has a code length of 1, it means that all characters in S must have been merged at some point during the course of the algorithm. Among all the characters in S with frequency greater than 0.44 (there can be at most 2), let z ∈ S be the one that was merged the last. Let y be the character that z gets merged with (y may be a result of some merge operations). When z gets merged with y, the size of the alphabet must be greater than 2 (otherwise, the base case of Huffman’s algorithm would have been reached and z would get an encoding of length 1) and thus there must be a symbol, say x, such that fx ≥ fz > 0.44. Since the total frequencies of all symbols equals 1, it must be that fy < 0.12. Note that x cannot be a symbol in S (because we assumed that no symbol in S gets an encoding of length 1) and hence it must be a result of some merge operations. At least one of the two symbols that formed x must have a frequency of greater ′′ than 0.22. Let this symbol be x . Since fy < 0.12, fy < fx′ , which means that x was chosen to form x instead of y (or one of the characters that formed y), which is a contradiction as Huffman’s algorithm always chooses the lowest two frequency characters to be merged
Question 4
Not yet graded / 12 pts
Let n ≥ 100 be an integer. Let A[1 .. n] be the array representation corresponding to a max-heap containing n distinct integers. Prove or disprove the following claim.
There is an O(1) time algorithm that finds the 5th largest element in the heap.
Your Answer:
https://canvas.upenn.edu/courses/1488890/quizzes/2313738/history?version=1 3/7
4/6/2020 Yijie Lu's Quiz History: Practice Midterm 2
Question 5
Not yet graded / 12 pts
In a directed graph G = (V, E), let’s call a set S ⊆ V of vertices well- connected, if every other vertex in the graph is reachable from some vertex in S, i.e., for each v ∈ V \ S, there is a path in G from some vertex in S to v. Give a O(|V | + |E|) time algorithm that will compute a well- connected set S of the smallest size in a directed graph G = (V,E). No justification for correctness is necessary. No justification for running time is necessary.
Your Answer:
We first create the strongly connected component (SCC) graph G′ = (V′,E′) for the given graph G = (V, E), using the algorithm discussed in the class. We now find W ⊆ V ′ in G′ with indegree zero. Then for each node in W choose one vertex in V from the SCC and add to S. Return S.
The claim is true. Note that the fifth largest element has to be in exactly one of the levels 1,2,3,4 of the almost complete binary tree corresponding to the max heap (note that level 0 contains the largest element). Thus the fifth largest element is in the subarray A[1..31]. Thus sorting these 31 elements in decreasing order and returning the fifth largest will solve the problem. Sorting 31 elements takes constant time and hence the claim is true.
Question 6
Not yet graded / 18 pts
Consider the following problem known as MAX-CUT.
https://canvas.upenn.edu/courses/1488890/quizzes/2313738/history?version=1 4/7
4/6/2020 Yijie Lu's Quiz History: Practice Midterm 2
Given an undirected graph G = (V, E), the goal is to partition the vertex set V into two sets A and B such that the total number of edges in E whose one endpoint is in A and the other endpoint in B is maximized.
Prove that if G is a tree then MAX-CUT can be solved optimally in O(|V | + |E|) time. Your algorithm must yield the partition (A, B). Justify the running time of your algorithm and give a short argument to show that your algorithm yields an optimal solution.
Your Answer:
We know that every tree is bipartite. Starting from any vertex, say u, we run breadth-first search on the tree G. This gives us a BFS tree T rooted at u. All vertices in the even layers of T will be in the partition A and the rest of the vertices will belong to B. By the property of breadth-first search we know that for any edge, its endpoints are in the same layer or in adjacent layers. Since G is a tree and hence acyclic, it cannot have any edge that connects to two vertices in the same layer of T . Thus the endpoints of all edges in G belong to adjacent layers in T and hence belong to different partitions. Hence the size of the of the cut is |E|, which is clearly optimal.
Question 7
Not yet graded / 18 pts
Let G = (V,E) be an undirected connected graph with a positive cost
ce associated with each edge e∈E. Let S⊂V. Let T be the set of all spanning trees of G in which each vertex in S is a leaf. Give an O(|E| log |V |) time algorithm that outputs a spanning tree in T of minimum total cost or determines that T is empty. Justify the correctness and the running time of your algorithm.
Your Answer:
https://canvas.upenn.edu/courses/1488890/quizzes/2313738/history?version=1 5/7
4/6/2020 Yijie Lu's Quiz History: Practice Midterm 2
Algo:
Let W = V - S. Then, create a new graph G' induced on W. That is, remove all vertices in S as well as any incident edges from G to create G'. If G' is not connected, then output that T is empty. Then, run Prim's/Kruskal's to get an MST T' of G'. For each vertex s in S, add s and the minimum weight edge from s to a vertex in W back to T'. If any such s does not have an edge to a vertex in W, output that T is empty. Otherwise, return T'.
Runtime:
Creating G' and checking if it is connected both take O(|V| + |E|) time, running Prim's/Kruskal's takes O(|E| log |V|) time, and adding each vertex in S back takes O(|E|) time. Therefore the total runtime is O(|E| log |V|)
Correctness:
Note that in any optimal solution T to the problem, the tree T(W) induced on the set of
vertices W must be connected. This is because if T(W) is not connected then T = T(W S) is also not connected since each vertex in S is a leaf and hence cannot contribute towards connecting disjoint components of T(W). Since we know that T is connected, it must be that T(W) is connected.
Thus the cost of an optimal solution equals the cost of a minimum spanning tree of the graph induced on W plus the minimum cost edges connecting each vertex in S to W. Our algorithm finds both components of the solution optimally and hence yields an optimal solution.
Question 8
Not yet graded / 18 pts
A fellow CIS 121 student wants you to help him review graph algorithms for the midterm exam. While searching for ways to review, he came across the following interesting problem:
https://canvas.upenn.edu/courses/1488890/quizzes/2313738/history?version=1 6/7
4/6/2020 Yijie Lu's Quiz History: Practice Midterm 2
Let G = (V, E) be a directed graph. Give an O(|V | + |E|) algorithm to determine whether or not G is its only strongly connected component. That is, give an algorithm to determine if for every pair of vertices u and v in G, there is a path from u to v and a path from v to u.
There’s just one problem: Your fellow student hasn’t been reviewing for very long, and the only graph algorithm he remembers is breadth-first search. Your goal is to help him solve the problem using only BFS. That is, use BFS to design an O(|V | + |E|) time algorithm to determine if G is strongly connected. Justify the correctness of your algorithm. Justify the running time of your algorithm.
Your Answer:
https://canvas.upenn.edu/courses/1488890/quizzes/2313738/history?version=1 7/7