- Oy, week 12.
How did it get to be week 12?
Time flies.
Hey there, welcome to week 12 of CS 124 online,
Data Structures and Algorithms.
Let's see, last week,
what did we do?
We introduced relations and equivalence relations
and the dynamic equivalence problem.
And now this week, we're going to work out
a few different implementations
of the dynamic equivalence problem.
And each one, each successive implementation
is gonna be moving closer and closer
to a good solution as we go.
And we'll find in the end that,
while we can't quite achieve linear time performance
for both find and union, we can get pretty darn close.
And that's based on some neat tricks.
So I hope you enjoy that part.
And once we wrap that up,
then we'll get started with graphs and graph algorithms.
We've studied trees.
We'll see that trees are just a special case of graphs.
To be specific,
trees are connected, undirected, acyclic graphs.
And so this week we're going to start our study
of graphs proper where we'll allow things
like cycles, directed edges, disconnected components,
things that aren't allowed in trees.
And we'll also learn our first graph algorithm
called topological sort.
Now topological sort has wide application
in many areas where dependency arise,
all kinds of applications, manufacturing applications.
For example, you can choose topological sorting
to determine the order of classes you need to take,
where the directed edges in your dependency graph
represent prerequisites.
So wherever dependencies arise,
topological sort usually isn't too far away.
And topological sort takes a dependency graph
that is a directed acyclic graph,
and returns an ordering of the nodes
such that for every directed edge, AB in the graph,
A comes before B in the topological ordering.
And we'll see that some directed acyclic graphs
have more than one such ordering,
but that every directed acyclic graph must have
at least one such ordering, no exceptions.
And our introduction to graphs
is going to provide the foundation
for the rest of the course.
The rest of this course is going to be entirely
on graphs and graph algorithms.
So we're going to see Dijkstra's famous
shortest path algorithm.
So famous that we usually just say Dijkstra's
and everybody knows what we're talking about.
Algorithms for network flows.
We're going to see, oh, Dijkstra's algorithm
is going to be an example of a greedy algorithm.
And that's something that we haven't discussed before.
So we'll also see, like I said, algorithms
for network flows and for finding minimum spanning trees.
Minimum spanning trees are minimal substructures
within a graph, which connect all the nodes.
And, you know, you've heard this part before,
at the end of the week, we'll have another quiz
which will cover this week's material
and some additional material that we covered from last week.
And I hope you enjoy it.
I like graphs.
I like graph algorithms.
I think they're pretty cool.
So enjoy that's all for now.
I'll see you on Yellowdig, and have fun.