Course Topics:
A course dealing with graphs and algorithms for graphs, with a focus on exploring graphs and finding shortest paths. Graphs can represent many real-world situations, from road to computer to social networks.
Topics in the first 5 weeks include:
- Graphs (both directed & undirected and weighted & unweighted)
- Trees aka directed acyclic graphs
- Both strongly and weakly connected components and algorithms to find them
- Topological order and sorts
- Breadth- and depth-first search
- Shortest paths and shortest-path trees
- Dijkstra's and Bellman-Ford algorithms
- Arbitrage and negative cycles
- Greedy algorithms, the cut property, and Prim's & Kruskal's algorithms
- Proofs of correctness
Final Week
The final week, quiz, and set of projects dealing with advanced shortest path algorithms were optional, but were completed.
Topics include:
- Bidirectional Dijkstra algorithm
- Potential functions, the A* algorithm, and it's bidirectional varient
- Landmarks
- Contraction hierarches algorithm, including subcomponents such as preprocessing, node ordering, and witness search, as well as a proof of correctness
- Implementing a small-scale Traveling Salesman solver
