During the preparation for the CS 577 Midterm, I find that it may be helpful if I list the complexity of some algorithms.

- Dijkstra – \(O((n+m)\log n)\) (using adjacency lists and priority queues)
- Topological Sort – \(O(n)\)

Also, solution to Question 7 in the practice problems (see also this file, and this better one, also a better problem statement by Jeff Erickson).

Solution in part (a) of Question 9 turns out to be essentially finding median of an array in linear time. See this amazing blog post (and this, too).