The designer analysis of algorithms is the interplay between on the one hand

general principles and on the other hand its stantiations of those principles to

solve specific problems. While there's no silver bullet in

algorithm design, no one technique which solves every computational problem that's

ever going to come up. There are general design principles which have proven

useful over and over again over the decades for solving problems that arise

in different application domains. Those, of course, are the principles that

we focus on in this class. For example, in part one we studied the

divide and conquer algorithm design paradigm, principles of graph search

amongst others. On the other hand, we study specific

substantiations of these techniques. So in part one, we studied divide and

conquer and how it applies to say, Strassen matrix multiplication, merge

short and quicksort. In graph search, we culminated with the

rightfully famous Dijkstra's algorithm for computing shortest paths.

This, of course, is useful not just, because as any card-carrying computer

scientist or programmer, you want to know about what these algorithms are and what

they do, but it also gives us a toolbox, a suite of four free primitives, which we

can apply to our own computational problems as a building block in some

larger program. Part two of the course will continue this

narrative. We'll learn very general algorithm

paradigms. Like greedy algorithms, dynamic

programming algorithms and many applications, including a number of

algorithms for the greatest hits compilation.

And in this video and the next, I want to whet your appetite for what's to come, by

plucking out two of the applications that we'll study in detail later in the

course. Specifically, in the dynamic programming

section of the course. First of all, for both of these problems,

I think their importance is self evident. I don't think I'll have to really discuss

why these are interesting problems. Why, in some sense, we really need to

solve these two problems. Secondly, these are quite tricky

computational problems. And I would expect that most of you do

not currently know good algorithms for these problems and it would be

challenging to design one. Third, by the end of this class you will

know efficient algorithms for both of these problems.

In fact, you'll know something much better.

You'll know general algorithm design techniques which solve as a special case

these two problems and have the potential to solve problems coming up in your own

projects as well. And one comment before we get started on

these two videos. They're both at a higher level than most

of the class, by which I mean there won't be any equations or math.

There won't be any concrete pseudo-code, and I'll be glossing over lots of

details. The point is just to convey the spirit of

what we're going to be studying, and to illustrate the range of applications of

the techniques that we're going to learn. So what I want to talk about first is

distributed shortest path routing and why it is fundamental to how the internet

works. So let me begin with a kind of non very

mathematical claim. I claim that we can usefully think of the

internet as a graph, as a collection of verticies and a collection of edges.

So this is clearly an, clearly an ambiguous statement.

There's many things I might mean as we'll discuss.

But here's the primary interpretation I want you to have for this particular

video. So to specify this, the vertices I intend

to be the end-hosts and the routers of the internet.

So machines that generate traffic, machines that consume traffic, and

machines that help traffic get from one place to another.

So the edges are going to be directed and they are meant to represent physical or

wireless connections indicating that one machine can talk directly to another one

by either a physical link between the two or a direct wireless connection.

So it's common that you'll have edges in both directions, so that if machine A can

talk to machine B directly, then also machine B can talk directly to machine A,

but you definitely want to allow the possibility of asymmetric communication.

So, for example, imagine I send an email from my Stanford account to one of my old

mentors at Cornell, where I did my graduate studies.

So this piece of data, this email, has to somehow migrate from my machine local at

Stanford to my mentor's machine over at Cornell.

So how does that actually happen? Well, initially there's a phase of, sort

of local transportation, so, this piece of data has to get from my local machine

to a place within the Stanford network that can talk to the rest of the world.

Just like if I was trying to travel to Cornell, I would have to first use local

transportation to get to San Francisco airport and only from there could I take

an airplane. So this machine from which data can

escape from the Stanford network to the outside world is called the gateway

router. The Stanford gateway router passes it on

to a networks, whose job is to cross the country.

So last I checked, the commercial internet service provider of Stanford was

Cogent so they, of course, have their own gateway router which can talk to the

Stanford one and vice versa. And of course, these two nodes and the

edges between them are just this tiny, tiny, tiny piece embedded in this massive

graph, comprising all the end hosts and routers of the internet.

So that's the main version of a graph that we're going to talk about in this

video, but let me just pause to mention a couple of other graphs that are related

to the internet, and quite interesting in their own right.

So one graph that is generated an enormous amount of an interest in study

is the graph induces by the web. So here, the vertices are going to

represent web pages and the edges which is certainly directed represent

hyperlinks. Not one web page points to another one.

So for example, my homepage is one node in this massive, massive graph.

And as you might expect, there is a link from my home page to the course page for

this class. It is of course essential to use directed

edges to faithfully model the web. There is for example, no directed edge

from this courses homepage to my own homepage at Stanford.

So the web really exploded around, you know, mid 90's, late 90's, So for the

past 15 plus years, there's been lots of research, about the web graph.

I'm sure you won't be surprised to hear that, you know, around the middle of the

last decade, people got extremely excited about properties of social networks.

Those, of course, can also be fruitfully thought of as graphs.

Here, the vertices are going to be people, and the lengths are going to

denote relationships. So, for example, friend relationships and

Facebook or the following relationship on Twitter.