Past exam of the year 1 of the computer science course of the University of Oxford / 2016 / Functional programming, design and analysis of algorithms / 6 / e / Solution

Compute any topological sort

(w_{1}, \dots, w_{n})

using a standard algorithm, then check its consecutive entries in the adjacency matrix:

DAGHamiltonianPath(A):
    order = TopologicalSort(A)
    for j = 1,...,n-1:
        if not A[order[j],order[j+1]]:
            return "no Hamiltonian path"
    return order

If all checks pass, the returned ordering is a Hamiltonian path. If a check fails but a Hamiltonian path existed, part (d) would force the computed topological sort to equal the unique path order, whose consecutive edges all exist. This contradiction proves the negative answer correct.

A standard topological sort scans all matrix rows and therefore takes

O (n^{2})

time with this input representation; the subsequent

n - 1

edge checks take

O (n)

. The answer is consequently $O (n^{2})$ time, with

O (n)

auxiliary storage beyond the input matrix. An

O (∣ V ∣ + ∣ E ∣)

bound for an adjacency list must not be substituted for the stipulated adjacency matrix bound.

 Ancestors (12)

 View article source

 Discussion (0) New discussion

There are no discussions about this article yet.

 Articles by others on the same topic (0)

There are currently no matching articles.

  See all articles in the same topic Create my own version