联系方式

  • QQ:99515681
  • 邮箱:99515681@qq.com
  • 工作时间:8:00-21:00
  • 微信:codinghelp

您当前位置:首页 >> Python编程Python编程

日期:2019-03-30 10:58

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
免责声明:本站部分内容从网络整理而来,只供参考!如有版权问题可联系本站删除。 站长地图

python代写
微信客服:codinghelp