Final COMP 251, April 2020. Solutions.

1. Lecture on Cartesian trees [treaps, quicksort]
2. Lecture on dags [directed acyclic graphs]
3. Lecture on minimal spanning trees [shortest paths]
4. Lecture on priority queues
5. Lecture on divide and conquer [master theorem]
6. 48
7. 3
8. yes
9. 1 and 2
10. 10
11. 35
12. Digital search tree
13. Prim-Dijkstra algorithm with source 1. O(e log n), O(e + n log n)
14. TSP by dynamic programming: O(n^2 2^n)
15. DFS. Halt when a gray node (back edge) is encountered. O(n+e).
16. Level order (BFS) traversal keeping track of weighted distance to root. O(n). O(n+e) fine too.
17. BFS or level order traversal, computing all largest distances to root. O(n+e).
  [Also: DFS or postorder traversal, reporting all largest distances to a leaf]. O(n+e).
18. MS  and TTS
19. log_2 (n!)  [n log_2 n partially correct; n log n incorrect; all O, Omega answers incorrect.]