What Is This Course About?
Gain an understanding of the course objectives, structure, and target audience.
We are excited to bring you this course and hope that it will help you build a lasting relationship with graph algorithms. This course covers the mechanics of each algorithm and, more importantly, sheds light on why they work. Reflection on why something works is crucial for understanding it, and we hope this course will do its part in getting you to do that.
Invitation to spend time with graphs
Graphs have a very natural structure for modeling many of the real-world network-like structures we encounter daily, such as the internet, molecules, layout of roads, social networks, flight schedules, transaction maps, and a myriad of structures relied upon in various domains of computing. For many problems involving such network-like structures, it’s often the case that a well-known algorithm for a related problem serves as an inspiration and is adapted appropriately.
Graph-based algorithms are used in versatile ways across various disciplines like computer vision, robotics, computational linguistics, computational biology, chemistry, and operations research, to name just a few.
Many foundational ideas in theoretical computer science are also couched in graph theoretic terms. Many graph theory problems, with fewer applications, have been the subject of immense attention and have been equally important in lending themselves to the development of advanced algorithmic techniques such as approximation algorithms.
Perspective is everything
The algorithms you learn in this course are more than a means to an end. In fact, there is, in some very real sense, optical mileage gained from the process of developing an understanding of each algorithm. The more algorithms you examine under your microscope, the better you get at thinking about related things—understanding them, modeling them, and tailoring the algorithms to fit your needs.
Algorithms are tools to be used, but they are also triggers that inspire you to conceive of new and creative ways to apply them and give you a clarity of perspective.
Coverage
In this course, we cover some important and classical graph algorithms. The content covered here is broadly organized as follows:
- Review of the big-O notation
- Preliminary concepts related to graphs
- Applications of depth-first search
- Shortest-paths problems
- Minimum spanning trees
- Network flows
- Maximum matchings and minimum vertex covers
- Stable matchings
Target audience and expectations
For this course, we assume that the learner is well-versed in basic data structures like arrays, linked lists, stacks, queues, heaps, and priority queues. We also assume a passing familiarity with topics in discrete mathematics.
This course does not contain programming exercises by design. It does contain other interactive elements and exercises that qualify better as mental stretches. In fact, the phrase mental stretches is a pretty good way to describe the overarching theme of this course.
