Okay, guys this is Mail Bag week number two we have a bunch of things for you
you'll see not only the Mail Bag, but you will see a couple of new lectures that
are, are intended to ease some of the pain when you are moving from assignments
to assignments so essentially we're going to update you on the, on your
progress in aggregate terms, okay? And then we'll go into some of the more
specific topics, some of the questions that you guys ask, and, and give you, you
know, more hints on which video to look next if you have some different kinds of
issues, okay? So this is the number of students active.
We have about 11,000 students active right now, this week.
You know it was 17 last week its a you know a normal decrease at this point not
worry about that, this is also something that is interesting to report this is
essentially the, the prolonging languages that people are reported to know during
one of the survey its very interesting to see how popular Python has become, okay?
And obviously a lot of you are using Python as the implementation language
here. so this is an interesting statistics.
it was kind of surprising to me. Especially the number of people who know
MATLAB compared to other languages. video views 11,000 this week of the
introductory video, okay? So this is pretty good.
The, you see the numbers here? For CP, local search you know
mathematical programming. Very healthy, it's normal.
You know, we are still looking, we are still at the beginning of the class.
We are not expecting people to look at these right now.
you know, the assignments are also prgoressing in each of these topics.
4,000 views of the mail back last week. This is good you know, a little, you
know, people could, you know, actively look at this.
because this is giving also a lot of hints on how to actually approach the
classes. And answering kind of questions globally
as well. this is the students active in the class,
okay? in in assignments.
And once again, you know, you have a drop, okay?
which is roughly the number, the same drop as active students [INAUDIBLE].
Okay what you see here is interesting, So, the number of submission which have
been graded has a very tiny drop, [INAUDIBLE], I mean, it's a drop, but
it's not huge, okay, which is also good. People are, you know, basically, moving
along to the next assignments, which is very nice.
And this is the number of submission by active students you see that actually the
students who are active are actually submitting more which is, which is also
great, okay. So I'll give you some more graph in a
moment, but this is the big picture at this point, okay this is also the
participation we've assignment what you see is two column the, the maximum number
of submission for a [UNKNOWN] plotting a problem and the minimum ones.
you see that knapsack is about you know the, the least you know 2, you know
2.5000 students submitting are submitting the various the, the various solutions
the maximum is 3, 3000 which is good, okay, so very healthy also are the number
for you know colouring its about close to a 1000 if you could raised that a little
bit that would be terrific. And you see that some people have
actually already, you know solved all the assignments and some of the puzzle
challenge as well, okay? But once again, we don't expect that, you
know. This is a week by week class, okay?
We give you all, you know, you can do everything you want but we, we assume
that people are going to progress week by week on every one of these assignments,
okay? no for the grading, once again i want to
set the expectation right,so, so getting all 10's in this class is amazingly
difficult. Ok so, so we are not expecting you know?
a large number of students to actually achieve that This is not their intent.
That would be really really terrific, okay?
But this is, this requires a lot of work. This requires a lot of knowledge.
And even that. That requires a lot of time just getting
these solutions on every one of them. So we don't expect you to do that, in a
sense. So what we want the class to do is focus
on the seven first. You know, solve the assignments.
Get seven on everything. You get a.
Certification at the end and that is really feasible, you know, as far as we
can judge, okay? So the bar is set reasonably for getting
7's on all of the parts.OK? Now what you can do is once you get these
7's, once you have allegories, well several allegories for popular
assignments, and you get 7 on them, you can say oh no I want to proof.
That's good, that's healthy and this is what we want you to do.
But don't focus on 1 particular thing, and say, oh I don't get a 10 on that one.
Okay, so learn more techniques inside during the class.
And you can always go back to these assignments, and correct them.
We lea, we give you some weeks at the end to actually do that.
Okay, so in a sense, guarantee you're doing craft coloring and let's say you
haven't look at the local set lecture, you can go, you know, let's say five
times all of the six party [UNKNOWN] but the last one you can't, you will see
techniques later on, you can go back there and maybe get a 10 on that one.
Okay, that is the essence of the class, right?
So so you don't have to focus on getting every ten, every you know, a ten on every
part of the assignment before moving to the next assignment, don't do that okay.
so there are basically two approaches here that you can always do when you want
to improve right, so you can have the scaleable solution right that I was just
talking about, trying to get seven everywhere Okay, and when you get that,
you basically get, you know, this is basically trying to find an approach
which scales, well on all the parts essentially, on all the instances.
If you can get that, it's not going to be the best algorithm, but you get a good
grade, right. So, you get, you know, essentially 7, on
the 6 part you get 42 for every one assignment.
The other way to do it is to say ooh, I really want some of these 10's, I want to
prove [UNKNOWN] on these problems and it's possible, right.
And when you do that, you may say, oh but that approach doesn't scale as well as
let's say, another approach, okay? But that's fine as well.
You could say, okay, so on four of these [UNKNOWN] I get a ten, on the last two...
I get a 3 because its not scaring you get a still 4 or 6 which is a very nice grade
right, and then later on in the class you can say oh but i have a little bit more
time ,this is the last two weeks, i could see if i can implement something else to
raise that bar, so that's also something you can do,so these two approaches are
what we want you guys to do and we will say how you can get there in some of the
new video that i am going to you know mention in moment.
Once again getting 10 on everything is really hard, okay?
that's why we have a specific distinctions for that particular, for
those people who could actually do that ,so in the sense don't focus on getting
10 in everything. Okay, so its just very very hard and
graphically in particular in very very hard So, this is a curve which is really
interesting. What you see, so this, this is
essentially you know seven of the, the red line that you see there is getting a
seven of average on all the parts that you are assuming to have completed by
now, okay? So, what you see is that there are about
800 students, you know You know, on the right of this curve so
those people are on track. What you see also is a large body of
students that are very, very close and our goal is to take these guys and bring
them over the curve, okay? And so, those people who are there they
just don't have to worry so look at the stuff that we are saying today, look at
the stuff that we present in the lectures, and that should allure you to
go over this bar, okay? Sending expectation right, don't get to,
don't try to get that. Okay, so the goal is to have a seven or
average. Okay, you don't have to be the best in
everything. Okay, so you will have more time later on
to actually refine those assignment and that's the goal here right.
So, we want to bring you over this curve, and you will some of the techniques that,
some of the strategies that we are following to actually do that in
practice, okay? So, we want these people to move, you
know, across this curve and that's the goal, that's the goal of the couple of
lectures that we are going to present. Okay, now there are a lot of questions
that, you know, lot of questions on the board and people are very good at
responding to them.They are three of them that always, you know, come back Okay,
and we want to address them. The first one is why is this class so
hard, then you know, I am completely lost, how do I get started, and we love
the [UNKNOWN] as well. Okay, and what is really the goal of this
class, okay? Okay, and what is really the goal of this
class, okay? And so I think, you know, we basically
specify those things at the beginning but I want to go over again.
Over them again, okay? So, why is this class so hard?
It's the basic principle that we have, this is the way we want to teach.
So there is this beautiful, you know, Beatles song, I want to hold your hand.
That's not what we are about, we don't want to do that.
We don't want to give you the algorithm for graph coloring, and tell you,
implement it, okay? So, because you don't learn as much as
saying this other principle, okay? You can apply them to all these problems,
okay? But now, you have to find the one that's,
that is right for this particular problem.
And you have to actually [INAUDIBLE] it yourself, so that.
you can actually understand, or you put this [UNKNOWN] in practice, okay?
And so, for me, you know the best way to do that, is actually get your hands
dirty. Don't get to many guidelines, because
when you discover things yourself, there are two things that happens.
First you are going to retain them much better.
And the second thing, is it's going to boost your confidence.
And you know that if you see a problem later on Oh, I have done it for graph
coloring. I know I can do it for, let's say, time
tabling. Okay?
So, in a sense, what we want is these two things.
We want you to retain doing formation bets better.
And by doing it yourself, you will retain that better, okay?
And then the second thing that we want, okay?
Is that you are also able to, to. in a sense, apply this much more widely
later on, okay? And to do that, you have to have the
confidence that you know that if, you havn't seen that problem, I have not to
much guidance and I can apply it. Now I want to tell you a story.
So I got educated in Europe. Most of my studies were memorizing
things. And there were 2 or 3 classes that were
not like that, and one of them was just crazy, right?
So we were graded on 20 and that class, all the students had above 16, okay,
well, part of the students had about 16 and part of the students below 4, you can
imagine, right? And it was like, more like 20%, 80%, so
it was crazy, right? So this is the first time the professor
was actually giving that class, okay? he was not able to actually give that
kind of grade later on, he got, you know. Told that, you know, this is not the way
you should grade. But anyway, so with that class, what's
really, really transformally for me, alright?
So it's just the only thing that that class was trying to tell you is that.
You know, use your mind, try to solve the problem, okay?
So we try to do that, but a much weaker extent in a sense, right?
So here we are giving you a lot of guidance.
But not sufficiently so that we give you, you know, an [UNKNOWN] that you have to
quote. So, this is the spirit of this class
Okay. So, the second thing that we want to do
is for you to experience NP-hardness Okay, so we are not cheating any
[UNKNOWN] Okay. So, when we give you graph coloring this
is an amazingly hard problem Okay. So, we did it on purpose right.
So, graph coloring is where you say these problem are really, really, really
difficult, I can't prove up optimality on you know, the largest instance, okay?
And this is on purpose. We want to show you that this is really
really hot, okay? And the only way we can show you that is
by you experiencing it, okay? You try it.
If I tell you why would you believe me, okay?
And in the sense if I only give you instance which are turkey notes, okay,
you can solve them optimally and then it's not even fact, okay?
So, here we want you to really experience you know these are really hard problems,
okay? And problems in practice are, you know,
rough coloring, you know, is very hard but problems in practice are often that
hard. Okay, and You have to be really clever in
how you actually approach them. So, in a sense we want you to really
experience this thing. Okay, there is something called, you
know, NP, NP-hardness. And this is tough okay.
And so that was the goal of the, of the, the graph coloring assignment, okay.
And once again, as I told you, we want you to be able to apply these ideas to
another problem, okay. And so in a sense what we do, we covered,
you know, the paradigms but we don't cover the real implementation.
That's for you to discover, that's the basic principal of this class.
And then we cover modeling techniques, but you will have to creative in choosing
the one you apply for popular [UNKNOWN]. So that's the basic idea.
And that's why its so hard, you have to discover a lot of things yourself.
We don't take your hand, okay, now, so we understand that, you know, you know
sometimes it's really, it's really, you know, it's really hard for different, for
different people in the class or we understand that the diversity here is
very large compared to some of the classrooms in which we have been teaching
similar classes. And so, what we going to do is to, to
actually try to help you or help some of you actually in, in covering a little bit
in more detail some, some of the techniques that you know we basically
assume people would know, okay and so we have three new lectures that I am
going to talk about and please watch them if you are just you know on the, on the
on the left of this curve. On the right of this curve?
Well, whatever. You know, on the wrong side of that curve
and we want to bring you along on the left side of the curve.
Okay, so look at this because they're going to help you, okay?
So we have two, two, two new techniques which are greedy, you know, one and two.
That's basically telling you this is where you should start from, okay?
So start from a greedy algorithm. And that will help you understand the
nature of the problem and will give you some guidance on this okay, and then, you
know what we want to talk a little bit about you know, if you, if you want to
start on this assignment, this is a plan okay this is really you know, if you are
you know not sure on how to approach them, you know, use this strategy okay
and so that's the two you know three lectures I'm going to cover.
in a moment, okay? Now, learning goals of the class is, is
the class you know trying to teach you to use a solver or to learn how to build
one. It's, it's, it's neither of them but it
gives you insight how to, how to do this but the real, the real message from this
class is that if you have an optimization problem, so, these are some of the most
successful methodologies to solve them and we want you to understand that.
And we want you to understand them so that you can actually code these
algorithms yourself, okay? So you have enough information
afterwards, you have enough informtaion to trnaslate that into code.
Of course it's hard, but you have the information to do it, okay?
And you can always use the forum and discuss with other people.
The collaboration policy here is very lenient, okay?
And then but, but that's the essence you could say oh I want to implement
something in constraint programming and I really now how to do it, okay and now you
implemented and then discovery oh, that what it takes and so on, that's one of
the big goals of the, of the, of the class now it also give you the ability to
use solvers you know in, in appropriately so we'll talk about that in, in some of
the when, when we talk about the way to approach the assignments, okay But
essentially a solver is only as good as your understanding of the various
methodologies, okay? So you can put things in a solver and
they can, the solvers can run forever if you're not mothering the problem right.
Okay? And so in a sense, you know, we, we, you
have to understand really how the various techniques are working so that you can
use these solvers in an appropriate fashion.In a sense think about it here,
you know when you look at solver we give the principles you can see through the
layers and decide if that's going to be a good solver for your problem or not, how
you should model your problem and so on Okay, so we'll come back to that because
you know, some of the solvers you can take off the shelf and try to apply to
the problems in this class won't be enough to get you a ten okay, so I'll
come back to that later on okay. But it give you the ability to use a
solver and then you can extend the solver so you can you know tailor them so that
they work for your particular problem, okay.
So, also implementing a solver is a completely different ball games but, once
again you will have the principles and the knowledge to actually go deeper and
look at the right paper see if you want to ever want implement a solver like
this, okay? So, we give you the tools for doing a lot
of different things. But the core here is understanding the
methodologies at a level where you will you know, be able to go deeper in many
different areas of optimization, whether it is application, whether it is solver,
whether it is more, you know, sophisticated algorithm, okay?
yes. Okay, so this is important, okay, I want
to cover this. So if you use a solver, so, so some
people may say, ooh, but the guys who actually know solver have a complete
advantage on this class. Okay?
So first, I don't think it's true. Okay?
Because if you code, you could, you can do two things in this class.
You can code the algorithm yourself. And you can actually get a certificate.
It's going to take you a little bit, you know, longer than somebody who knows the
solver. Okay?
But you will learn a lot, okay? So you learn more than just, you know,
learning a solver and then using it in a naive fashion, okay?
So in a sense, yes, these people will get a, you know, let's say get a certificate
in an easier fashion. You can do it without knowing these
solvers, okay? But the really important point is that if
you look at the way the assignments are chosen, okay, they have been chosen such
that If you taken off the shelf solver use it in a naive fashion, okay or even
in a sophisticated fashion is going to be really difficult for you to get 10 on all
the assignments, okay. If you know one solver try to apply it to
all the assignments its going to be tough, okay?
Okay so in a sense what I am telling you here is that if you want to [UNKNOWN]
many of these assignments You'll have to really creative and go beyond you know
this, you know just a naive or a simple use of the solvers.
You need to combine you use them in a clever fashion or you will need to use
sophisticated technique on top of them or inside them and things like this, okay?
So once again you know, yeah the reason advantage is viewing a solver but its
minimum. Okay, and if you want to get ten on some
of these assignments you have to go beyond what the solver do or use the
solver really creatively Okay? So, so, so this is just to give you that
in perspective. There is not that much of an advantage to
use a solver. It becomes more an advantage on the
final, on the final assignments, but even in those cases, okay?
What you have to understand is that you will have to use this solver in a very
clever fashion. It's just not knowing the solver that's
going to help you, you have to know the material as well, okay?
So, what next. coloring was hard.
It was intended to do that. You have experience in p-hardness.
With with with, with this, okay? So, it's, it's, it's, it's a very
interesting problem because it's very easy to state, and it's incredibly hard,
OK? And this is why this assignment is
positioned there, OK? But it's, it's essentially a shock and
it's, it was intended to be a shock, right?
So the traveling salesman problem is going to be very different.
Finding feasible solution is going to be really easy, but there are many, many
different tools, okay? And here is going to be whole world can
you optimize. Okay, it's the, as, as I said in the
lectures, it's the most, you know, well known optimization problem, okay.
and, once again, you know, I think you should focus on getting it, getting seven
first, and then trying to see if you can turn them into a ten, okay.
It's really tough to get, you know, optimal solution of some of these
benchmarks as well. It's doable, but it's very tough, so, you
know You know, be reasonable in the standards that you have and then try to
compete afterwards when you have more time.
Okay? So, the TSP is discussed in a lot of
details in the local search and in the MIP lectures and you can use some of
these techniques while solving it. Okay.
So, keep up with good work and you know, it's really fun looking at, you know,
what you guys are doing and look at the three lectures if you are interest, you
know, on the left of that curve and we want to bring you on the right.
Okay? Great, thank you.