0:01

Welcome back. This is Discrete Optimization in Coursera

and this is not a lecture. This is about work.

Okay, so what we going to do today is basically look at the course structure

and the philosophy behind the courses, what we are trying to achieve.

And then give you a sense of the assignment design and what you have to do

in this class to get a grade, okay? So basically you have seen this picture

before, right? So what you have over here is problem

size. You have time over there, okay?

And the goal, the goal in this class is to try to get to, to pull this

exponential. Such that you can solve real practical

problems, okay? So you know that the best that you could

do in this problem is typically linear time, right?

It means, because that is the time that it will probably take for checking a

solution for actually outputting a solution.

That is the number of the decision variables.

You have to decide for everyone of these decision variables, what you do okay?

And so what we want, what we want is you to design Algorithm in this class such

that you get close to that, as close as possible.

For problems that are going to be of reasonable size.

So we want to pull this exponential as closely as possible to this linear time.

Of course it's tough, okay? It's going to be really tough, okay?

so, one of the things that you'll see in the class is a bunch of lectures to

actually try to do that, okay? So you'll see different techniques,

constraint programming, local search, and integer programming or mixed integer

programming. And then we'll give you the tools to

actually try to pull these exponential or find high quality solution quickly.

Now, if you look at these assignments and can solve them all very, very quickly,

okay? There is one thing you need to know, you

need to call me as quickly as possible, okay?

And don't tell anyone, just talk to me, okay?

And we'll be in business together. Okay, so, now for the assignment.

Okay, so this is how it's going to work. Okay, so we going to, we going to give

you one NP-Hard problem every week. Okay, and so your goal is going to be to

solve it. And you can solve it in any way you want,

okay. So you will use any of the techniques we

have presented, you can invent your own. But you have to optimize it as best you

can. Pool this exponental, find high-quality

solution quickly, okay? And then what you have to do is you have

to submit this solution to us so that we know how great you are, and how beautiful

your solutions are. Okay, so that's the rule of the game.

Okay, one NP-Hard problem a, a week. Okay, and we'll start easy, and then

we'll move to more and more and more complex problems as the, as the, as the

classes goes on, okay? Now, this is how we're going to grade.

You can always submit junks thing, okay, or infeasible solutions, and if you do

so, you know, essentially your grade is going to be very, very low, okay?

You can submit you know, solutions of low quality, and typically you'll see the

assignments already have some of these solutions, and then you get a very low

grade, okay? And then you start submitting good

quality solution, and we'll have a lower bar, okay so a standard, that you have to

meet to, to, to define what is a good, good quality solution.

And it's got to be a reasonable Algorithm, and your goal is to get at

least to that level, okay? Or you can submit a really, really

beautiful solution And then you get a, the maximum grade.

And so your goal is to be between these two lines.

Okay? So essentially that's what we hope you to

do. now, there is a thing which is really

nice about this class is that you can submit solution over time, all over gain.

Okay, so you can find your best solution, and then two days later, you have a

better idea. You can, you know, run it again and

submit it again. Okay, and you can come back to

assignments and resubmit, we'll talk about that.

You can also use different solutions for different parts of the problems and

submit them at the same time. You'll see how we can do that.

But essentially, we give you a lot of freedom to actually get that grade as

high as possible, okay? So time commitment typically is going to

be 15 hours a week, okay? So, so it's a tough class, okay?

So solving NP complete problems are hard, okay?

So you will have one or three hours to, you know, for the lectures and you will

have essentially 12 to fi, 14 hours of coding.

This is essentially for the later assignments, okay?

There is, the assignments at the beginning are going to be a little bit

easier, okay? So there is a time investment in this

class okay, so, you have to be conscious of that.

An you have to start early, you have to do these assignments.

But of course as I said, you can come back to them an revise them later on,

okay? But there is a significant time

commitment, it's not an easy class. Okay now as I said there, the, the

assignments remain open, all the time. So the dates, there is a due date which

is a recommended completion, okay. So this is when we expect you to actually

submit the assignment. Now take this unit seriously because the

assignments are going to pile up. Okay, so you have one problem a week,

okay. So if you accumulate 5 from them, that's

a problem, okay, especially given these things, okay.

Then you will have hard deadline that's going to be the last chance for you to

submit an assignment, okay. So, you know you have to satisfy that

deadline. But as I said before, you can always

return to an assignment you did, you did before the hard deadline, right?

So you go, you have a better idea, you know, you take a shower, you get a really

good idea, you come back, you code it, you know, and then it's great.

So you can submit it a new solution and see, you know, and, and we'll grade that

one as well. Okay?

So we'll be always extremely fair. In the sense that when we look at the

solutions, we always will take the best of the solutions that you have submitted

for any kinds of, for any subset of the problems that, that you have submitted.

You know, the solution for. So, over time, you know, your solutions,

even if it sometimes you submit the solution which is worse, it doesn't

matter. We'll always take the best one and you

can have different techniques for different part of the assignments.

And you can run them all the different techniques, you know, on, on the

assignments and we'll take the best one that you have submitted at any point,

okay? So, really nice for you, okay?

Now, how to succeed in this class. Okay, so first thing you have to do is

relax, okay. Be creative, okay?

And try to think about how to solve these problems, okay.

It's, it's, it's, you know, it's I'm going to tell you a story in a moment.

But it, it tends to be, it tends to be about learning, and about do, solving

this problems in practice. So one of the things that we want, it's

for you experience exponentially verse. Okay, so we can talk about it for hours,

and hours. And, and then you don't have a fit about

it. So what these assignments are for, it's

for you to get a sense of what an what an NP hard problem is.

What is exponential growth, okay? So once you experience that, you will get

some respects for these problems. And then you're going to start

appreciating some of the techniques that we'll talk about.

And you will see, you know? Oh wow, these techniques are actually

helping us really solve these problems. Okay?

And then you will also build intuition on which one, you know, which techniques are

going to be, you know, good for different kinds of problems.

And which one you have to apply and which are easier to apply, and which one are

more complicated. But they will give you more benefits at

the end, okay? So one of the things that this class will

have is a lot of programming assignments. And you can get frustrated.

And I want to tell you a story. When I was actually young, you know,

student, you know, a young PhD student, I had this great guy.

You know, [UNKNOWN] friend. And I came to him because I disbark for

two weeks. Okay, so two weeks I was trying, building

this optimization system. Having a bug and I couldn't find it.

And so I went to him because he had a reputation of being a good debugger and I

asked him, you know, what do I have to do?

And he said, well, first he told me, you are taking this wrong, okay?

So you are getting frustrated. This is not what you should do.

This is a game, you see. It's a game between man and machine and

man has to win, okay? And so we sat down and we had fun, you

know, we found a bug after about three or four hours.

And it was a really learning experience so all you, you, change your attitude and

then it changes the way you act as you know, view the problems.

So most of the problems that you will see in this class, you can view them as

problem solving tricky puzzle, okay? you, you know, you don't have to get

frustrated about it. You have to say, I want to beat this

machine, I want to get these machines to do what I want, okay?

So you see things like Sudoku, and one of the things you realize is that some of

the techniques that we are actually using in this class will enable you to digest

most of the values here. In a very, very simple, simple manner,

okay? And once you do that these puzzles, you

know, they become much easier to solve. An many of the optimization problems that

we'll see in this class. If you look at them in the right way,

it's going to be really nice. You know, hog, you know, you to find a

really nice technique to actually solve that, okay?

Now there will be other ones that may seem completely messy.

And you start by editing something which is, like, looking like spaghetti code,

and so on. But you know, one of the goal for you is

also to try to make these things a work of art, okay?

So serving optimization problems can lead to optimization problems that are truly

beautiful. You will be really proud of them at the

end, okay? So, spend time finding solutions that are

elegant, because most of the time, the elegant solutions are also going to be

very efficient solutions and very effective solutions, okay?

Now there is a collaboration policy on this class, you have to take it very

seriously. You can refer to the syllabus.

The, the collaboration policy is spelled out in all the details.

There are things you can do and there are things you cannot do, okay?

So we try to give you as much freedom as we can.

There will be forum, discussion, you know, a lot of discussion on how to solve

these problems. You can exchange information about

solution ideas. Okay, we'll let you do that.

But you have to do that at a high level. Its like your personal life, right?

So you can talk about it at a high level, but you don't want to enter into you

know, intimate details, okay? You can share all the objective values,

discuss some of these techniques but you know, stay at a reasonable level, okay?

Now there are things that you, we don't want you to do.

So don't go on the web, find the cutting edge research paper on the assignment and

implement it, okay? So you will learn nothing, okay?

Because essentially, you're going to take some you know someone else's ideas, code

them, and the only thing that you will have done is basically understanding that

techniques. But he will not have understood what this

class is all about. Getting used to experience you know, what

these problems are about, what are exponential growths, and how you have to

be creative to actually solve these problems.

Because most NP hard problems, okay, that you will encounter in practice are not

the ones that you find in papers. Papers simplifies them, there are plenty

of other constraints that you have in real life that typically are not in the

papers that are written by, in academia and for a good reason.

Because you don't want to describe the complexity of this world.

But in practice, you will have to cope with that.

So, you have to experience what it means to solve an actual you know, an actual

problem. And you have to get a feel of what going

to work and what is not going to work. That is why you don't what to do this,

don't go and implement something that somebody else has designed, okay?

The other thing that we don't want is you to copy codes from anyone else or, you

know, to copy the algorithms of anyone else.

Everything, you know, you use in this class should be your own, okay?

As I said you can discuss the various approach, okay?

So we encourage that, okay, because in real life you can do that, okay?

But we, wanted to find a solution, be your own.

It has to be your own algorithm. It has to be your own code, okay?

So, have fun. Optimization is fun, you know the

assignments are going to be fun, you're going to learn tons of things in this

class. It's a lot of work, okay?

[SOUND]. But it's also, it's also rewarding in the

end when you see these things you know, generating very high quality solutions.

Proving optimality to something that seems to be completely out of scope.

Okay? So welcome again, you know, and start

working. Great.