Week 10 - Graphs
Learning objectives
- Use BFS and DFS to identify bipartite graphs and cycles, and to do topological sorts
- Execute Dijkstra's and Prim's algorithms
Class Schedule
Monday
- Search Trees & Search Implementation
Tuesday
- Search related Algorithms
Wednesday
- Weighted Graph Algorithms
Thursday
- On your own - Final Review
No class session today. Available for virtual format office hours.
Topics
Search Trees & Search Implementation
Read Ch 26.4
Watch this video:
Experiment with the BFS simulator and DFS simulator (recursive)
Do the SearchTree WS
Search related Algorithms
Read Ch 26.6-26.7
Watch this video:
Try out the Topological sort simulator. Note that it marks each vertex with a timestamp on enter and exit. (And that time gets updated every time we enter or leave a node). The part we really care about is the exit time for each node.
Do the SortRelatedAlgorithms WS
Weighted Graphs
Read Ch 27.4-27.5
Watch this video:
Try out simulators of Dijkstra's shortest path algorithm and Prim's minimum spanning tree algorithm
Do Weighted Graph WS