Design and describe, in precise English and without using code, linear-time algo

Question

Design and describe, in precise English and without using code, linear-time algorithms for the following problems.

You will be designing and describing three different algorithms below. These algorithms must run in linear time (i.e., O(E+V) on an adjacency list and O(V2) on an adjacency matrix. Describe these algorithms in two or three sentences. You are encouraged to make use, as appropriate, of the algorithms for depth-first search, explore, topological sort, strongly connected components, graph reversal, and breadth-first search.

#1

Given an undirected graph G and one of its edges (u,v), determine whether or not G contains a cycle involving (u,v). (Your first step should be to remove (u,v) from G.)

#2

Given a directed, acyclic graph G, determine whether there is a directed path through G that visits each vertex exactly once. There will be no such path if there are multiple sources. But even if there is only one source, there may be no such path.)

#3

Given a directed graph G, one of its vertices u, and an integer n, determine whether there are paths of length n or less from u to every other vertex in G.

Explanation / Answer

#1

________________________________________________________________________

#2

_____________________________________________________________________________

#3

Related Questions

Navigate

• Browse (All)
• Browse D
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.