The primary topics in this part of the specialization are: greedy algorithms (scheduling, minimum spanning trees, clustering, Huffman codes) and dynamic programming (knapsack, sequence alignment, optimal search trees).

Loading...

From the course by Stanford University

Greedy Algorithms, Minimum Spanning Trees, and Dynamic Programming

433 ratings

The primary topics in this part of the specialization are: greedy algorithms (scheduling, minimum spanning trees, clustering, Huffman codes) and dynamic programming (knapsack, sequence alignment, optimal search trees).

From the lesson

Week 1

Two motivating applications; selected review; introduction to greedy algorithms; a scheduling application; Prim's MST algorithm.

- Tim RoughgardenProfessor

Computer Science

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.

Â So notice the different social networks may correspond to undirected or directed

Â graphs. Facebook for example corresponding to an

Â undirected graph, Twitter corresponding to a directed graph.

Â So let's now return to the first interpretation I wanted to focus on,

Â that where the vertices are in-hosts and routers and it does represent direct

Â physical or wireless connections indicating that two machines can talk

Â directly to each other. So going back to that graph, let's go

Â back to the story where I'm sending an email to somebody at Cornell.

Â And this data has to travel from my local machine to some local machine at Cornell.

Â So, in particular, this piece of data has to get from the Stanford gateway router,

Â in effect to the airport for Stanford's network to the Cornell gateway router.

Â So there will be landing airport over on Cornell's side.

Â Now it's not easy to figure out exactly out what the structure of the routes

Â between Stanford and Cornell look like. But one thing I can promise you is that

Â there is not a direct physical link between the Stanford gateway router and

Â the Cornell gateway router. Any route between the two is going to

Â comprise multiple hops. It will have intermediate stops.

Â And there's not going to be a unique such route.

Â So if you have the choice between taking one route which stops in Houston and then

Â Atlanta and then in Washington D.C., how would you compare that to one which

Â stops in Salt Lake City and Chicago. Well hopefully your first instinct and a

Â perfectly good idea is all else being equal, prefer the path that is in some

Â sense the shortest. Now in this context, shortest could mean

Â many things, and it's interesting to think about different definitions.

Â But for simplicity let's just focus on the fewest number of hops, equivalently

Â the fewest number of intermediate stops. Well, if we want to actually execute this

Â idea, we clearly need an algorithm that given a source and destination computes

Â the shortest path between the two. So hopefully you feel well equipped to

Â discuss this problem, because one of the highlights of part one of this class, was

Â the discussion of Dijkstra's shortest pathalum rhythm in a blazing fast of

Â limitation using heaps that run's in almost linear time.

Â We did mention one caveat when we discussed Dijkstra's algorithm mainly

Â that it requires all edge lengths to be non negative but in the context of

Â internet routing almost any edge metric you'd imagine using will satisfy this non

Â negativity assumption. There is, however, a serious issue with

Â trying to apply Dijkstra's shortest path algorithm off the shelf to solve this

Â distributed internet routing problem, and the issue was caused by the just massive,

Â distributed scale of modern day internet. Probably back in the 1960's, when you had

Â the 12-note ARPANET, you could get away with running Dijkstra's shortest path

Â algorithm, but not in the twenty-first century.

Â It's not feasible for the Stanford gateway router to maintain locally a

Â reasonably accurate model of the entire internet graph.

Â So how can we elude this issue? Is it fundamental that because the

Â internet is so massive, it's impossible to run any shortest path algorithm?

Â Well, the ray of hope would be if we could have a shortest path algorithm that

Â admitted a distributed implementation. Whereby, a node could just interact,

Â perhaps iteratively, with its neighbors with the machines to which its directly

Â connected. And yet, somehow converge to having

Â accurate shortest paths to all of the destinations.

Â So perhaps, the first thing you'd try would be to seek out an implementation of

Â Dijkstra's algorithm, where each vertex uses only local computation.

Â That seems hard to do. If you look at the pseudo-code of

Â Dijkstra, it just doesn't seem like a localizable algorithm.

Â So instead, what we're going to do is we're going to learn a different shortest

Â path algorithm. It's also a classic.

Â Definitely on the greatest hits compilation.

Â It's called the Bellman-Ford Algorithm. So the Bellman-Ford algorithm, as you'll

Â see, can be thought of as a dynamic programming algorithm.

Â And indeed, it correctly computes shortest path using only local

Â computation. Each vertex only communicates in rounds

Â with the other vertices to which it's directly connected.

Â As a bonus, we'll see this algorithm also handles negative edge lengths.

Â Which of course, Dijkstra's algorithm was not.

Â But don't think Dijkstra's algorithm is obsolete.

Â It still has faster running time in situations where you can get away with

Â centralized computation. Now, it was really kind of amazing here

Â is that the Bellman-Ford algorithm, it dates back to the 1950's.

Â So, that's not just pre-internet, that pre-ARPANET.

Â So that's before the internet was even a glimmer in anybody's eye.

Â And yet, it really is the foundation for modern internet routing protocol's.

Â Needless to say, there's a lot of really hard engineering work and further ideas

Â required to translate the concept from Bellman-Ford to actually doing routing in

Â the very complex modern day internet. But yet, those protocol's at their

Â foundation, goes all the way back to the Bellman-Ford algorithm.

Â Coursera provides universal access to the worldâ€™s best education,
partnering with top universities and organizations to offer courses online.