Comp 363 Take-home Quiz 2 Due in Sakai at noon Apr 1, 2019. 50 points total. You may use previously
prepared notes on two sides of 8.5 x 11 inch paper. You do not need to do the quiz all at one sitting, but once
you look at it, finish it before discussing algorithms class or looking at an algorithm text or reference or your
notes. I hope it takes around an hour of active work, but if you need more time, you may take up to three
hours. You are encouraged to use a computer as a word processor to print as much as is convenient of your
textual answers, and then add anything else in handwriting. Do not use a computer for algorithms reference or
for running code.
I have read and followed the instructions above, and worked alone, using only the allowed notes:
Signature:______________________________ Name printed ____________________________
Approximate number of minutes working on the quiz _____
[12] 1. Do a depth-first search of the whole digraph below, using our usual order: assuming all vertex lists are
in alphabetical order. As you do the DFS, keep track of the sequence of starting and ending times in the
places shown as (__, __) by each vertex, with starting time on the left, and ending time on the right.
Start counting from 1. Since there will be starting and ending times for 8 vertices, the last ending time
should be 16.
Also, by the middle of each edge, in the spaces [ _ ], label the type of edge from the DFS using:
T for tree edge; F for forward edge; B for back edge: C for cross edge
[10] 2. The figure below shows a DAG with the vertex start and end times for a DFS. While there are many
possible topological orders for the vertices, there is just one directly derived from the timing numbers shown
for this DFS. List the vertices, from left to right, with that topological order. Show a forward, not reverse,
topological order.
[10] 3. Draw the meta-graph associated with the digraph below. Each meta-graph vertex name should include a
subset of the vertex letters in the original graph. Make a new figure, separate from the original diagram.
[10] 4. Given an undirected, connected, unweighted graph G with n vertices 0..n-1 and m edges. Assume for
any vertex v, N[v] is a list of the neighbors of vertex v. Given any specified vertex w, give an O(n+m)
algorithm for finding a vertex at maximal distance from w. The distance between two vertices p and q
is length of the shortest path between them. There may be more than one vertex at the maximal distance
from w. It does not matter which one is returned as the solution.
If you are using or modifying a standard algorithm, you do not need to completely rewrite the code,
but make a clear explanation of how any standard algorithms are used or modified, and a clear
explanation of why your algorithm is O(n+m). You may write Python, Java, or clear pseudocode. (The
order restriction means you cannot use Dijikstra's algorithm, O(m log n). Examples are not a sufficient
answer.)
[8] 5. Explain clearly why the following proposition is true: Given an undirected graph G and a starting vertex
s. If one ordering of edges makes the depth-first search starting from s have a back edge to s, then every
ordering of the edges will make the depth-first search starting from s have a back edge to s. (Just
concluding there is a back edge somewhere in the graph is not enough: The back edge must have s as an
endpoint. Examples are not a sufficient answer.)
Remember to enter the total time spent working on these problems back at the top of the quiz.
版权所有:编程辅导网 2021 All Rights Reserved 联系方式:QQ:99515681 微信:codinghelp 电子信箱:99515681@qq.com
免责声明:本站部分内容从网络整理而来,只供参考!如有版权问题可联系本站删除。