OK, so we're making our way towards the end of the course now we have a couple more sections to go.
A few more lectures, of course, but now we're kind of getting into more algorithm things.
So we talked a little bit about algorithm analysis, and now we're just going to talk more about design
strategies for algorithms.
And in particular, we're going to start out with a topic called optimization.
So this just means we're looking at optimization problems.
So this is just going to be your introduction lecture on this to explain what that really is, and we
will talk about a couple methods to solve this optimization problems.
So what is an optimization problem?
Well, it's basically one.
We need to find a specific minimum or maximum result for a particular problem.
So this is something like maximizing profit based on input, finding the shortest path distances, stuff
like that.
So more concrete example.
If you're maximizing maximizing profit, it might be like you have some clients for a piece of property
you're trying to rent like, let's say, b b or something like that and you just want to know, Okay,
I have, you know, four months of availability and I want to schedule these clients.
They have requested specific dates.
I want to schedule them in a way where I can actually maximize my profit based on the dates not really
overlapping.
So I need to look at the dates and also how much they're willing to pay or how much I'm charging for
a specific date and make the most money out of that.
So that would be like a concrete example of optimization problem.
So in general, these methods can also help with time complexity.
So they're not always going to be really great time complexity.
And some of the dynamic programming samples will see that maybe not all that impressive, but definitely
better than brute force methods to solve the same problem would be so it's kind of an additive benefit
sometimes.
So the first method we're going to talk about something called the greedy method.
The principle the greedy method is very simple.
A greedy algorithm is just choosing the best option as you go through a particular process, so choosing
the best option at any point in time.
So an example is if you're trying to do that, maximizing profit, let's say with like the clients for
your rental property, maybe you said, OK, I've scheduled this client right now at at this specific
date, and now I can schedule another client and you have some options laid out in front of you.
I can pick Client A, B, C or D.
You basically are just going to look through a, b, c and D see which one is going to offer the most
money as long as it doesn't over laugh with your current client or something like that.
And then you're going to just choose that client, basically.
So it would just be like always looking for just what the biggest value is in that case.
So maximizing the profit, choosing the best thing that's in front of you and keep repeating that until
you've reached an end.
So the key here for the goodI method is that we're attempting to optimize this in real time as we go,
hence the name greedy.
We're just grabbing whatever looks the best to us at a certain point in time.
The other method I'm going to talk about is dynamic programming, so in dynamic programming, we're
also trying to find optimal solution.
But the difference is that rather than just choosing the best option in front of us at a given time,
we instead try and kind of explore all the options, lay them out in front of us and then find an optimal
path through those options.
So this also involves breaking our problem down into some problems quite often and then just realizing
our solution as being a combination of those sub problems, basically more so the solutions to those
problems.
So the key for dynamic programming is that we break our main problem down into some problems, then
choose optimal results from those sub problems.
So that should be the main takeaway when you think about what this really means.
So this might be a little confusing, but don't worry, we're definitely going to go over some examples.
We will compare and contrast greedy method and dynamic programming.
And we will also sometimes, but not every time.
Look at their time complexity, we may even do kind of a formal analysis to try and practice the things
that we learned in the previous section.
So with that, I will see you in the next lecture.