0:00

[MUSIC] Next, let me mention, embarrassingly briefly, linear

programming. So linear programming is a problem that,

on the one hand, is efficiently solvable both in theory and in practice.

And, on the other hand, is very general. It includes as a special case, bipartite

matching, maximum flow, and tons of other stuff.

The general problem solved by linear programming is to optimize a linear

function, maximize or minimize it doesn't matter, optimize a linear function over a

set of linear constraints. Geometrically, that corresponds to

finding the best point, the optimal point, in the feasible region which is

representable as the inner section intersection of half spaces.

So let me just draw a cartoon picture, which is going to be in the plane.

Although let me emphasize, the power of linear programming is that you can

efficiently solve problems that are in a massively higher dimensions.

Not 2 dimensions, but think millions of them.

Dimensions. So in the plane, the intersection of half

planes, assuming it's bounded, is just going to be a polygon and you could think

about optimizing a linear function are just trying to push as far as possible in

some direction subject to being inside the feasible region.

So, for example, maybe you want to push as far to the northeast as possible

Subject to being one of these blue points, somewhere in this polygon.

For example, the maximum flow of problem is easily encoded as a special case of

linear programming. You use one dimension, that is, one

decision variable for each edge. The decision variable describes how much

flow you route on a given edge. The linear objective function would be

the maximized The sum of the flows on the edges going out of the source vertex.

And then you would have linear constraints just insisting that the

amount of flow coming into a vertex is the same as the amount of flow coming out

of a vertex. And, linear programming code is not just

maximum programming flow, but tons and tons of other problems as well.

Despite its generality linear programming problems can be solved efficiently both

in theory and in practice. The systematic formalization and

algorithm solution of linear programs was pioneer by George Dantzig back in the

1940's. In particular, Dantzig invented what's

called the simplex method which remains to date one of the most important.

2:32

Practical methods for solving linear programs.

Have you ever heard that story about the student who walks in late to a class,

sees what he thinks is homework written up on the chalk board and solves them,

not knowing that they are in fact major open research questions?

Well, maybe you thought that story was apocryphal, assuming I did for many

years, But it's not. Turns out it's totally about George

Dantzig. In 1939, he walked into his graduate

statistics class late. The 2 major open questions in the field

were written on the chalkboard, and he solved them within a few days.

That wound up being his PhD dissertation before he got interested in linear

programming. Now, the algorithms used to efficiently

solve one of your programs, they're pretty complicated, both versions of the

simplex method and so called Interior Point algorithms.

So, it may or may not be a good use of your time learning more about how the

guts of these algorithms work. But what I'm most surely is a good use of

your time is how to be an educated clients of these algorithms that is to

get some practice formulating problems as linear programs and solving linear

programs using either op, open source solvers.

Or commercial linear programming solvers. Those solvers are a very powerful black

box tool to have in your algorithm assists toolbox.

In fact there are black box subroutines available to you that are strictly more

powerful than linear programming. One generalization is convex programming,

so linear functions are special case of convex functions and if you want to

minimize the convex function or equivalently maximize a concave function

subject to convex constraints that again is a problem you can solve efficiently

both in theory in terms of polynomial time and in practice.

May be the problem size is you can reach on.

Quite as big with linear programming, but there pretty close.

The different generalization is energer linear programming, so these are like

linear program but where you add the extra constraint that certain decision

variables have to take on and interger variable.

So something like 1/2 as a value for a decsion variable would be disallowed in

an interger program. Now these in general are no longer

solvable efficiently in theory, it's easy to encode empty complete problems, like

lets say vertex cover as a special case of engineer programming.

But there is quite a bit of advance technology out there.

For solving at least in special domains, integer programs.

So again if you have an empty complete problem and you really need to solve it,

integer programming is a technique your going to want to learn more about.

What are some other topics we haven't had time to discuss? Well, first of all, for

many of topics we have discussed, we've only scratched the surface.

There's beautiful and useful stuff beyond what we've discussed in these discussed

in these classes. On topics ranging from data structures,

for example, with hashing in research trees, to graph algorithms. We already

mentioned matchings and flows. To approximation alogrithm like better

heuristics for the travelling salesman problem.

A topic we've barely discussed at all is geometric algorithms, one exception being

a divide and conquer algorithm for the closest pair problem that we discussed in

part one. Roughly speaking, the study of geometric

algorithms has two flavors, low dimensional problems and high dimensional

Dimensional problems. So when I say low dimensional, I mean

probably 2 or 3 dimension. So problems in the plane or problems in free space.

A conical computational problem here would be the convex hull problem.

Which means I give you a bunch of points and then you want to know which points

are on the convex hull of the point set. So, here's a way to think about the

convex hull problem in the plane. So, take a wooden board, a flat wooden

board, that represents the plane. Now, pound a bunch of nails into the

wooden board. Those are representing the points in the

plane. Now, to compute the convex hull, what you

can do is you can take a rubber band, stretch it out really far so that it

bounds. All of the nails you pounded into the

wooden board and now let the wo, rubber band go, and it's going to snap around

the boundry nails. That's a way to computer the convex hull

in 2 dimensions. And so the question is, how do you do that efficiently given just

a bunch of coordinates of points? The state-of-the-art here are divide and

conquer algorythm, very much in the spirit of the closest pair problem back

in Part 1. So why would you care about computing

convex hulls? Well, there's lots of reasons.

But, you know, as one example, suppose you were doing some 3D graphics, and you

had moving objects in your scene, and you wanted to know whether, when two objects

collide. Because then you have to respond

appropriately in rendering the scene. Well, to know where the two objects

collide, you don't have to remember all of the details of the objects.

You just have to keep track of their convex hulls.

They collide exactly when their convex hulls intersect, and so that's one reason

you might want to do that computation. A very different flavor of geometric

algorithms is the high-dimensional case. And here, I'm thinking of the number of

dimensions as being a thou, in the thousands say, or perhaps even quite a

bit more than that. Now, why would you ever have points in

the thousands of dimensions? Well, imagine you were doing say, information

retrieval, imagine you had a bunch of documents.

Now, documents don't really have geometry intrinsically, but it can be useful to

imbue them with geometry. How do you do that? Well, imagine you

make a list of all of the words in the world.

That you care about. So maybe say, 10,000 words that you think

are interesting. And for a given document, you just count

the number of occurrences of each of these 10,000 interesting words in the

document. So maybe lots of them are zero, the words

don't occur at all. You know, but maybe there's some word

that occurs seven times in the document. The document.

So then you'd give it a seven in that coordinate and boom, you've now

represented each document as a point in 10,000 dimensional space.

One coordinate for each of the interesting words, the value of the

coordinate being the frequency of that word in that document.

Now you can start asking questions like, given a new document is it similar to any

of the documents you've already been storing? And geometrically, that just

corresponds to asking something called a nearest neighbor query.

Given a bunch of points and possibly high dimensional space, and given a new point,

which of the previous points is closest, say a new distance, to the new point you

where just given? That would be a canonical question you would ask, in high

dimensional computational geometry. In these Design and Analysis of

Algorithms courses, we've been focusing on the most classical style of

computation, where you're given upfront an input.

You do a computation and you produce some output.

And you take a bow, and you leave the stage.

But if you think about computation in the real world, there's plenty of algorithms

whose work Is never finished, algorithms that in effect run forever.

Two applications that we've mentioned in passing in this class are the caching

problems, so for example if you're writing an algorithm to manage a cache or

an algorithm system, that algorithms work is never really done.

It's going to have to manage the cache Indefinitely.

Similarly, you can think about routing in a network, say in Internet routing.

Again, that algorithm's work is never done.

There's always going to be link failures. There's always going to be new nodes.

There's always going to be new data to route.

So, it has to keep making routing decisions indefinitely, as long as the

Internet exists. As you would hope, both the theory and

the practice of understanding algorithms that run indefinitely, making decisions

in real time, is based quite squarely on the lessons that we've learned in the

classical computational paradigm here. But it is an interesting.

Topic worthy of study in its own right. A major concern of algorithms research in

the 21st century is massive data sets, meaning data sets that are way too big to

fit in the main memory of a single machine.

One hot topic has been so-called streaming algorithms, that is algorithms

which have to in effect take a firehose of data being generated at a torrential

pace and boil it down using small space into just a few accurate statistics.

So you might think, for example, about an algorithm running locally at a network

router with data packets flying through the router at a ridiculous pace or an

algorithm which is responsible for summarizing the data generated by a bunch

of telescopic observations. A final, important topic by which the

current theory is actually quite immature is understanding how to exploit

parallelism in tackling massive data sets.

For example, using the distributive system's approach exported by the map

produced Hadoop Systems.