Graph Problems and Algorithms
Overview
In mathematics, graphs are structures used to model pairwise relationships between objects. These have many applications — they can be used to model many types of relations and processes in physical, biological, social and information systems. Thus graph problems and algorithms are widely studied and used.
The final part of the course includes an introduction to graph algorithms and problems. It leads nicely into a future course that computer science majors will take — CPSC 413 — because it includes another kind of algorithm — a greedy algorithm — that will be studied in that course.
Lecture #20: Introduction to Graphs
Required Reading
Lecture Presentation
Lecture #21: Graph Search
Required Reading
Lecture Presentation
Tutorial #17: Graph Search
Lecture #22: Computation of Minimum-Cost Paths — Dijkstra’s Algorithm
Required Reading
Lecture Presentation
Tutorial #18: Computation of Minimum-Cost Paths
Lecture #23: Computation of Minimum-Cost Spanning Trees — Prim’s Algorithm
Required Reading
Lecture Presentation
Tutorial #19: Computation of Minimum-Cost Spanning Trees
Lecture #24: Network Flow
Required Reading
- Lecture Notes: [ PDF ] [ Video ]
- Supplement: Proofs of Claims in the Lecture Notes
