COS 226 Final: COS 226 Princeton Final Fall 10 Solution
31 Jan 2019
School
Department
Course
Professor
Document Summary
U find a maximum spanning tree in a connected edge-weighted graph. This problem and the mst linear-time reduce to one another (by negating the weights). The existence of a deterministic linear-time algorithm for the mst is an open problem. P find all vertices reachable from a given set of source vertices in a digraph. We used this subroutine in the nfa simulation algorithm for regular expressions. I find a hamilton path in a digraph (if one exists). This problem is np-complete, so unless p = n p , it cannot be solved in polynomial time, let alone in linear time. P find a hamilton path in a dag (if one exists). This can be found by computing the topological order and checking that there is an edge between each consecutive pair of vertices in the order. P find the strong components of a digraph. P insert n comparable keys into a binary heap.
