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.