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.

Â