1
00:00:02,470 --> 00:00:04,400
- Oy, week 12.

2
00:00:04,400 --> 00:00:06,123
How did it get to be week 12?

3
00:00:07,680 --> 00:00:08,840
Time flies.

4
00:00:08,840 --> 00:00:13,840
Hey there, welcome to
week 12 of CS 124 online,

5
00:00:14,900 --> 00:00:16,823
Data Structures and Algorithms.

6
00:00:18,950 --> 00:00:20,260
Let's see, last week,

7
00:00:20,260 --> 00:00:21,093
what did we do?

8
00:00:21,093 --> 00:00:25,120
We introduced relations
and equivalence relations

9
00:00:25,120 --> 00:00:27,293
and the dynamic equivalence problem.

10
00:00:28,210 --> 00:00:29,830
And now this week, we're going to work out

11
00:00:29,830 --> 00:00:31,640
a few different implementations

12
00:00:31,640 --> 00:00:33,673
of the dynamic equivalence problem.

13
00:00:34,540 --> 00:00:37,540
And each one, each
successive implementation

14
00:00:37,540 --> 00:00:39,580
is gonna be moving closer and closer

15
00:00:39,580 --> 00:00:41,720
to a good solution as we go.

16
00:00:41,720 --> 00:00:43,720
And we'll find in the end that,

17
00:00:43,720 --> 00:00:46,990
while we can't quite achieve
linear time performance

18
00:00:46,990 --> 00:00:51,860
for both find and union, we
can get pretty darn close.

19
00:00:51,860 --> 00:00:54,400
And that's based on some neat tricks.

20
00:00:54,400 --> 00:00:57,050
So I hope you enjoy that part.

21
00:00:57,050 --> 00:00:58,740
And once we wrap that up,

22
00:00:58,740 --> 00:01:01,873
then we'll get started with
graphs and graph algorithms.

23
00:01:02,720 --> 00:01:04,123
We've studied trees.

24
00:01:05,140 --> 00:01:08,540
We'll see that trees are just
a special case of graphs.

25
00:01:08,540 --> 00:01:09,610
To be specific,

26
00:01:09,610 --> 00:01:13,723
trees are connected,
undirected, acyclic graphs.

27
00:01:14,820 --> 00:01:18,120
And so this week we're
going to start our study

28
00:01:18,120 --> 00:01:20,700
of graphs proper where we'll allow things

29
00:01:20,700 --> 00:01:24,020
like cycles, directed edges,
disconnected components,

30
00:01:24,020 --> 00:01:26,290
things that aren't allowed in trees.

31
00:01:26,290 --> 00:01:29,070
And we'll also learn our
first graph algorithm

32
00:01:29,070 --> 00:01:30,563
called topological sort.

33
00:01:31,580 --> 00:01:34,200
Now topological sort has wide application

34
00:01:34,200 --> 00:01:36,653
in many areas where dependency arise,

35
00:01:38,570 --> 00:01:43,080
all kinds of applications,
manufacturing applications.

36
00:01:43,080 --> 00:01:46,590
For example, you can
choose topological sorting

37
00:01:46,590 --> 00:01:49,620
to determine the order of
classes you need to take,

38
00:01:49,620 --> 00:01:52,460
where the directed edges
in your dependency graph

39
00:01:52,460 --> 00:01:54,183
represent prerequisites.

40
00:01:55,160 --> 00:01:57,650
So wherever dependencies arise,

41
00:01:57,650 --> 00:02:00,293
topological sort usually
isn't too far away.

42
00:02:01,350 --> 00:02:04,200
And topological sort
takes a dependency graph

43
00:02:04,200 --> 00:02:07,080
that is a directed acyclic graph,

44
00:02:07,080 --> 00:02:09,110
and returns an ordering of the nodes

45
00:02:09,110 --> 00:02:13,100
such that for every directed
edge, AB in the graph,

46
00:02:13,100 --> 00:02:16,263
A comes before B in the
topological ordering.

47
00:02:17,300 --> 00:02:20,850
And we'll see that some
directed acyclic graphs

48
00:02:20,850 --> 00:02:23,100
have more than one such ordering,

49
00:02:23,100 --> 00:02:26,170
but that every directed
acyclic graph must have

50
00:02:26,170 --> 00:02:30,163
at least one such ordering, no exceptions.

51
00:02:32,440 --> 00:02:34,800
And our introduction to graphs

52
00:02:34,800 --> 00:02:36,500
is going to provide the foundation

53
00:02:36,500 --> 00:02:37,840
for the rest of the course.

54
00:02:37,840 --> 00:02:40,730
The rest of this course
is going to be entirely

55
00:02:40,730 --> 00:02:43,810
on graphs and graph algorithms.

56
00:02:43,810 --> 00:02:45,760
So we're going to see Dijkstra's famous

57
00:02:45,760 --> 00:02:47,413
shortest path algorithm.

58
00:02:48,640 --> 00:02:51,100
So famous that we usually
just say Dijkstra's

59
00:02:51,100 --> 00:02:53,350
and everybody knows what
we're talking about.

60
00:02:54,870 --> 00:02:57,760
Algorithms for network flows.

61
00:02:57,760 --> 00:03:00,950
We're going to see, oh,
Dijkstra's algorithm

62
00:03:00,950 --> 00:03:03,260
is going to be an example
of a greedy algorithm.

63
00:03:03,260 --> 00:03:05,893
And that's something that
we haven't discussed before.

64
00:03:06,790 --> 00:03:09,482
So we'll also see, like I said, algorithms

65
00:03:09,482 --> 00:03:13,670
for network flows and for
finding minimum spanning trees.

66
00:03:13,670 --> 00:03:16,360
Minimum spanning trees
are minimal substructures

67
00:03:16,360 --> 00:03:18,560
within a graph, which
connect all the nodes.

68
00:03:20,070 --> 00:03:22,520
And, you know, you've
heard this part before,

69
00:03:22,520 --> 00:03:24,380
at the end of the week,
we'll have another quiz

70
00:03:24,380 --> 00:03:25,940
which will cover this week's material

71
00:03:25,940 --> 00:03:29,163
and some additional material
that we covered from last week.

72
00:03:30,190 --> 00:03:31,850
And I hope you enjoy it.

73
00:03:31,850 --> 00:03:32,800
I like graphs.

74
00:03:32,800 --> 00:03:34,030
I like graph algorithms.

75
00:03:34,030 --> 00:03:35,290
I think they're pretty cool.

76
00:03:35,290 --> 00:03:37,570
So enjoy that's all for now.

77
00:03:37,570 --> 00:03:40,793
I'll see you on Yellowdig, and have fun.