Module 5–6
Answers that describe an algorithm should always include a proof of correctness and running time analysis. Algorithms may be described in English or in clear pseudocode with explanatory comments.
1. You are given an integer r ∈ [1..n] and a sequence σ = s1, s2, . . . , sn of n distinct elements in which elements are presented one at a time. When element si is presented, you can no longer access any of s1,…,si−1 unless your algorithm has stored them. You are asked to output the rth smallest element in σ. Design an algorithm that can accomplish this using O(r) space and O(n) expected time. (25 points)
2. You are given the adjacency-list representation of a directed acyclic graph G = (V, E) with n vertices and m edges. Furthermore, for every vertex v ∈ V with in-degree zero, you are given a number value(v). For every vertex v ∈ V with positive in-degree, we define
value(v) = value(u), (u,v)∈E
the sum of the values of all of v’s predecessors in the graph.
For example, in the graph below, the gray vertices have in-degree zero, so their values deter-
mine the values of all other vertices in the graph.
3 3 3 10 2
3 6 13 5 7
Design a O(n + m)-time algorithm to compute value(v) for all vertices v ∈ V . (25 points)
3. You are given the adjacency list representation of a directed graph G = (V, E) with n vertices
andmedges. WedefinethesetS={v∈V : somecycleinGisreachablefromv}. For example, in the graph below, S = {b, d, f, h, j, k, l}.
Github
Name: NAME HERE Collaborator: COLLABORATOR NAME HERE
Design an O(n + m) time algorithm to find the set S. (25 points)
4. Let G(V, E) be an undirected graph with n vertices and m edges such that G has two vertices s and t where the shortest path from s to t has length strictly more than n/2. Then, prove that there must be a vertex w ∈ V \ {s, t} such that every path from s to t must pass through w. Furthermore, assuming that G is given to you in the adjacency-list representation along with vertices s and t, design an O(n + m) time algorithm to output such a vertex w. (25 points)
程序代写 CS代考 加微信: cstutorcs