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.