1 00:00:01,180 --> 00:00:09,670 OK, so we're making our way towards the end of the course now we have a couple more sections to go. 2 00:00:09,700 --> 00:00:16,720 A few more lectures, of course, but now we're kind of getting into more algorithm things. 3 00:00:16,720 --> 00:00:22,120 So we talked a little bit about algorithm analysis, and now we're just going to talk more about design 4 00:00:22,120 --> 00:00:23,740 strategies for algorithms. 5 00:00:23,740 --> 00:00:28,800 And in particular, we're going to start out with a topic called optimization. 6 00:00:28,810 --> 00:00:31,810 So this just means we're looking at optimization problems. 7 00:00:32,440 --> 00:00:37,420 So this is just going to be your introduction lecture on this to explain what that really is, and we 8 00:00:37,420 --> 00:00:42,130 will talk about a couple methods to solve this optimization problems. 9 00:00:43,210 --> 00:00:45,520 So what is an optimization problem? 10 00:00:45,550 --> 00:00:46,600 Well, it's basically one. 11 00:00:46,600 --> 00:00:50,770 We need to find a specific minimum or maximum result for a particular problem. 12 00:00:50,770 --> 00:00:57,490 So this is something like maximizing profit based on input, finding the shortest path distances, stuff 13 00:00:57,490 --> 00:00:58,060 like that. 14 00:00:58,320 --> 00:01:00,550 So more concrete example. 15 00:01:00,550 --> 00:01:08,440 If you're maximizing maximizing profit, it might be like you have some clients for a piece of property 16 00:01:08,440 --> 00:01:16,450 you're trying to rent like, let's say, b b or something like that and you just want to know, Okay, 17 00:01:16,810 --> 00:01:24,610 I have, you know, four months of availability and I want to schedule these clients. 18 00:01:24,610 --> 00:01:26,470 They have requested specific dates. 19 00:01:26,470 --> 00:01:35,410 I want to schedule them in a way where I can actually maximize my profit based on the dates not really 20 00:01:35,410 --> 00:01:36,340 overlapping. 21 00:01:36,340 --> 00:01:42,340 So I need to look at the dates and also how much they're willing to pay or how much I'm charging for 22 00:01:42,340 --> 00:01:45,400 a specific date and make the most money out of that. 23 00:01:45,430 --> 00:01:50,200 So that would be like a concrete example of optimization problem. 24 00:01:51,160 --> 00:01:56,110 So in general, these methods can also help with time complexity. 25 00:01:56,410 --> 00:02:02,380 So they're not always going to be really great time complexity. 26 00:02:02,800 --> 00:02:09,340 And some of the dynamic programming samples will see that maybe not all that impressive, but definitely 27 00:02:09,340 --> 00:02:15,490 better than brute force methods to solve the same problem would be so it's kind of an additive benefit 28 00:02:15,490 --> 00:02:16,060 sometimes. 29 00:02:17,380 --> 00:02:21,190 So the first method we're going to talk about something called the greedy method. 30 00:02:21,710 --> 00:02:24,550 The principle the greedy method is very simple. 31 00:02:25,000 --> 00:02:31,360 A greedy algorithm is just choosing the best option as you go through a particular process, so choosing 32 00:02:31,360 --> 00:02:33,130 the best option at any point in time. 33 00:02:33,850 --> 00:02:38,860 So an example is if you're trying to do that, maximizing profit, let's say with like the clients for 34 00:02:38,860 --> 00:02:45,160 your rental property, maybe you said, OK, I've scheduled this client right now at at this specific 35 00:02:45,160 --> 00:02:51,460 date, and now I can schedule another client and you have some options laid out in front of you. 36 00:02:51,460 --> 00:02:53,680 I can pick Client A, B, C or D. 37 00:02:53,980 --> 00:02:58,750 You basically are just going to look through a, b, c and D see which one is going to offer the most 38 00:02:58,750 --> 00:03:03,400 money as long as it doesn't over laugh with your current client or something like that. 39 00:03:03,910 --> 00:03:08,230 And then you're going to just choose that client, basically. 40 00:03:08,500 --> 00:03:14,800 So it would just be like always looking for just what the biggest value is in that case. 41 00:03:14,800 --> 00:03:21,610 So maximizing the profit, choosing the best thing that's in front of you and keep repeating that until 42 00:03:21,610 --> 00:03:22,450 you've reached an end. 43 00:03:23,350 --> 00:03:28,420 So the key here for the goodI method is that we're attempting to optimize this in real time as we go, 44 00:03:28,750 --> 00:03:30,040 hence the name greedy. 45 00:03:30,040 --> 00:03:35,080 We're just grabbing whatever looks the best to us at a certain point in time. 46 00:03:37,330 --> 00:03:42,970 The other method I'm going to talk about is dynamic programming, so in dynamic programming, we're 47 00:03:43,060 --> 00:03:44,620 also trying to find optimal solution. 48 00:03:44,620 --> 00:03:49,540 But the difference is that rather than just choosing the best option in front of us at a given time, 49 00:03:50,200 --> 00:03:56,980 we instead try and kind of explore all the options, lay them out in front of us and then find an optimal 50 00:03:56,980 --> 00:03:58,900 path through those options. 51 00:03:59,380 --> 00:04:06,010 So this also involves breaking our problem down into some problems quite often and then just realizing 52 00:04:06,010 --> 00:04:12,910 our solution as being a combination of those sub problems, basically more so the solutions to those 53 00:04:13,120 --> 00:04:13,720 problems. 54 00:04:15,190 --> 00:04:21,040 So the key for dynamic programming is that we break our main problem down into some problems, then 55 00:04:21,040 --> 00:04:23,860 choose optimal results from those sub problems. 56 00:04:23,860 --> 00:04:27,550 So that should be the main takeaway when you think about what this really means. 57 00:04:28,840 --> 00:04:35,050 So this might be a little confusing, but don't worry, we're definitely going to go over some examples. 58 00:04:35,650 --> 00:04:40,960 We will compare and contrast greedy method and dynamic programming. 59 00:04:42,540 --> 00:04:45,420 And we will also sometimes, but not every time. 60 00:04:45,900 --> 00:04:51,120 Look at their time complexity, we may even do kind of a formal analysis to try and practice the things 61 00:04:51,120 --> 00:04:52,590 that we learned in the previous section. 62 00:04:53,430 --> 00:04:56,280 So with that, I will see you in the next lecture.