CSE 101 Exam 1
Winter 2021
1
Question 1 (Topological Sort, 30 points). Give a topological ordering of the graph below:
2
Question 2 (Coming Together, 35 points). Rose and Greg are stranded on opposite sides of Graphania.
The map of Graphania is given by a directed graph where each edge in the graph takes 1 minute to traverse.
Each minute each of the two travellers can either traverse an edge or stay where they are. Give an algorithm
that given the map of Graphania along with the initial locations of Rose and Greg computes the minimum
amount of time required for them to meet at the same location. For full credit, your algorithm should run in
linear time or better.
3
Question 3 (Cycle Finding, 35 points). Provide an algorithm that given a directed graph G finds a cycle in
G if one exists, and prove the correctness of your algorithm. For full credit, your algorithm should run in
linear time or better.
4