1 00:00:01,120 --> 00:00:03,924 Welcome back. This is Discrete Optimization in Coursera 2 00:00:03,924 --> 00:00:07,530 and this is not a lecture. This is about work. 3 00:00:07,530 --> 00:00:10,692 Okay, so what we going to do today is basically look at the course structure 4 00:00:10,692 --> 00:00:15,060 and the philosophy behind the courses, what we are trying to achieve. 5 00:00:15,060 --> 00:00:18,659 And then give you a sense of the assignment design and what you have to do 6 00:00:18,659 --> 00:00:24,007 in this class to get a grade, okay? So basically you have seen this picture 7 00:00:24,007 --> 00:00:26,870 before, right? So what you have over here is problem 8 00:00:26,870 --> 00:00:30,310 size. You have time over there, okay? 9 00:00:30,310 --> 00:00:33,928 And the goal, the goal in this class is to try to get to, to pull this 10 00:00:33,928 --> 00:00:37,959 exponential. Such that you can solve real practical 11 00:00:37,959 --> 00:00:41,428 problems, okay? So you know that the best that you could 12 00:00:41,428 --> 00:00:45,290 do in this problem is typically linear time, right? 13 00:00:45,290 --> 00:00:48,576 It means, because that is the time that it will probably take for checking a 14 00:00:48,576 --> 00:00:51,756 solution for actually outputting a solution. 15 00:00:51,756 --> 00:00:54,107 That is the number of the decision variables. 16 00:00:54,107 --> 00:00:58,259 You have to decide for everyone of these decision variables, what you do okay? 17 00:00:58,259 --> 00:01:01,472 And so what we want, what we want is you to design Algorithm in this class such 18 00:01:01,472 --> 00:01:04,933 that you get close to that, as close as possible. 19 00:01:04,933 --> 00:01:07,520 For problems that are going to be of reasonable size. 20 00:01:07,520 --> 00:01:12,380 So we want to pull this exponential as closely as possible to this linear time. 21 00:01:12,380 --> 00:01:16,960 Of course it's tough, okay? It's going to be really tough, okay? 22 00:01:16,960 --> 00:01:20,992 so, one of the things that you'll see in the class is a bunch of lectures to 23 00:01:20,992 --> 00:01:25,483 actually try to do that, okay? So you'll see different techniques, 24 00:01:25,483 --> 00:01:28,450 constraint programming, local search, and integer programming or mixed integer 25 00:01:28,450 --> 00:01:31,263 programming. And then we'll give you the tools to 26 00:01:31,263 --> 00:01:35,320 actually try to pull these exponential or find high quality solution quickly. 27 00:01:35,320 --> 00:01:38,686 Now, if you look at these assignments and can solve them all very, very quickly, 28 00:01:38,686 --> 00:01:41,599 okay? There is one thing you need to know, you 29 00:01:41,599 --> 00:01:44,680 need to call me as quickly as possible, okay? 30 00:01:44,680 --> 00:01:46,940 And don't tell anyone, just talk to me, okay? 31 00:01:46,940 --> 00:01:52,212 And we'll be in business together. Okay, so, now for the assignment. 32 00:01:52,212 --> 00:01:56,260 Okay, so this is how it's going to work. Okay, so we going to, we going to give 33 00:01:56,260 --> 00:02:01,169 you one NP-Hard problem every week. Okay, and so your goal is going to be to 34 00:02:01,169 --> 00:02:03,952 solve it. And you can solve it in any way you want, 35 00:02:03,952 --> 00:02:06,321 okay. So you will use any of the techniques we 36 00:02:06,321 --> 00:02:10,675 have presented, you can invent your own. But you have to optimize it as best you 37 00:02:10,675 --> 00:02:14,072 can. Pool this exponental, find high-quality 38 00:02:14,072 --> 00:02:17,492 solution quickly, okay? And then what you have to do is you have 39 00:02:17,492 --> 00:02:20,264 to submit this solution to us so that we know how great you are, and how beautiful 40 00:02:20,264 --> 00:02:24,470 your solutions are. Okay, so that's the rule of the game. 41 00:02:24,470 --> 00:02:27,964 Okay, one NP-Hard problem a, a week. Okay, and we'll start easy, and then 42 00:02:27,964 --> 00:02:31,258 we'll move to more and more and more complex problems as the, as the, as the 43 00:02:31,258 --> 00:02:35,670 classes goes on, okay? Now, this is how we're going to grade. 44 00:02:35,670 --> 00:02:39,168 You can always submit junks thing, okay, or infeasible solutions, and if you do 45 00:02:39,168 --> 00:02:43,724 so, you know, essentially your grade is going to be very, very low, okay? 46 00:02:43,724 --> 00:02:47,156 You can submit you know, solutions of low quality, and typically you'll see the 47 00:02:47,156 --> 00:02:50,484 assignments already have some of these solutions, and then you get a very low 48 00:02:50,484 --> 00:02:54,228 grade, okay? And then you start submitting good 49 00:02:54,228 --> 00:02:57,712 quality solution, and we'll have a lower bar, okay so a standard, that you have to 50 00:02:57,712 --> 00:03:02,200 meet to, to, to define what is a good, good quality solution. 51 00:03:02,200 --> 00:03:04,565 And it's got to be a reasonable Algorithm, and your goal is to get at 52 00:03:04,565 --> 00:03:07,956 least to that level, okay? Or you can submit a really, really 53 00:03:07,956 --> 00:03:11,680 beautiful solution And then you get a, the maximum grade. 54 00:03:11,680 --> 00:03:14,790 And so your goal is to be between these two lines. 55 00:03:14,790 --> 00:03:16,664 Okay? So essentially that's what we hope you to 56 00:03:16,664 --> 00:03:19,597 do. now, there is a thing which is really 57 00:03:19,597 --> 00:03:24,880 nice about this class is that you can submit solution over time, all over gain. 58 00:03:24,880 --> 00:03:27,794 Okay, so you can find your best solution, and then two days later, you have a 59 00:03:27,794 --> 00:03:30,436 better idea. You can, you know, run it again and 60 00:03:30,436 --> 00:03:32,852 submit it again. Okay, and you can come back to 61 00:03:32,852 --> 00:03:35,780 assignments and resubmit, we'll talk about that. 62 00:03:35,780 --> 00:03:38,340 You can also use different solutions for different parts of the problems and 63 00:03:38,340 --> 00:03:41,550 submit them at the same time. You'll see how we can do that. 64 00:03:41,550 --> 00:03:44,905 But essentially, we give you a lot of freedom to actually get that grade as 65 00:03:44,905 --> 00:03:50,112 high as possible, okay? So time commitment typically is going to 66 00:03:50,112 --> 00:03:53,610 be 15 hours a week, okay? So, so it's a tough class, okay? 67 00:03:53,610 --> 00:03:57,040 So solving NP complete problems are hard, okay? 68 00:03:57,040 --> 00:04:00,001 So you will have one or three hours to, you know, for the lectures and you will 69 00:04:00,001 --> 00:04:03,040 have essentially 12 to fi, 14 hours of coding. 70 00:04:03,040 --> 00:04:05,540 This is essentially for the later assignments, okay? 71 00:04:05,540 --> 00:04:07,860 There is, the assignments at the beginning are going to be a little bit 72 00:04:07,860 --> 00:04:10,600 easier, okay? So there is a time investment in this 73 00:04:10,600 --> 00:04:13,600 class okay, so, you have to be conscious of that. 74 00:04:13,600 --> 00:04:16,020 An you have to start early, you have to do these assignments. 75 00:04:16,020 --> 00:04:18,911 But of course as I said, you can come back to them an revise them later on, 76 00:04:18,911 --> 00:04:21,333 okay? But there is a significant time 77 00:04:21,333 --> 00:04:25,620 commitment, it's not an easy class. Okay now as I said there, the, the 78 00:04:25,620 --> 00:04:30,866 assignments remain open, all the time. So the dates, there is a due date which 79 00:04:30,866 --> 00:04:35,115 is a recommended completion, okay. So this is when we expect you to actually 80 00:04:35,115 --> 00:04:38,612 submit the assignment. Now take this unit seriously because the 81 00:04:38,612 --> 00:04:41,740 assignments are going to pile up. Okay, so you have one problem a week, 82 00:04:41,740 --> 00:04:44,271 okay. So if you accumulate 5 from them, that's 83 00:04:44,271 --> 00:04:47,770 a problem, okay, especially given these things, okay. 84 00:04:47,770 --> 00:04:50,698 Then you will have hard deadline that's going to be the last chance for you to 85 00:04:50,698 --> 00:04:54,154 submit an assignment, okay. So, you know you have to satisfy that 86 00:04:54,154 --> 00:04:56,391 deadline. But as I said before, you can always 87 00:04:56,391 --> 00:05:00,360 return to an assignment you did, you did before the hard deadline, right? 88 00:05:00,360 --> 00:05:02,754 So you go, you have a better idea, you know, you take a shower, you get a really 89 00:05:02,754 --> 00:05:06,110 good idea, you come back, you code it, you know, and then it's great. 90 00:05:06,110 --> 00:05:08,862 So you can submit it a new solution and see, you know, and, and we'll grade that 91 00:05:08,862 --> 00:05:10,690 one as well. Okay? 92 00:05:10,690 --> 00:05:14,688 So we'll be always extremely fair. In the sense that when we look at the 93 00:05:14,688 --> 00:05:18,842 solutions, we always will take the best of the solutions that you have submitted 94 00:05:18,842 --> 00:05:25,192 for any kinds of, for any subset of the problems that, that you have submitted. 95 00:05:25,192 --> 00:05:28,366 You know, the solution for. So, over time, you know, your solutions, 96 00:05:28,366 --> 00:05:30,962 even if it sometimes you submit the solution which is worse, it doesn't 97 00:05:30,962 --> 00:05:33,654 matter. We'll always take the best one and you 98 00:05:33,654 --> 00:05:37,248 can have different techniques for different part of the assignments. 99 00:05:37,248 --> 00:05:39,742 And you can run them all the different techniques, you know, on, on the 100 00:05:39,742 --> 00:05:42,494 assignments and we'll take the best one that you have submitted at any point, 101 00:05:42,494 --> 00:05:46,410 okay? So, really nice for you, okay? 102 00:05:46,410 --> 00:05:49,440 Now, how to succeed in this class. Okay, so first thing you have to do is 103 00:05:49,440 --> 00:05:51,660 relax, okay. Be creative, okay? 104 00:05:51,660 --> 00:05:54,554 And try to think about how to solve these problems, okay. 105 00:05:54,554 --> 00:05:58,210 It's, it's, it's, you know, it's I'm going to tell you a story in a moment. 106 00:05:58,210 --> 00:06:02,419 But it, it tends to be, it tends to be about learning, and about do, solving 107 00:06:02,419 --> 00:06:07,157 this problems in practice. So one of the things that we want, it's 108 00:06:07,157 --> 00:06:11,380 for you experience exponentially verse. Okay, so we can talk about it for hours, 109 00:06:11,380 --> 00:06:13,705 and hours. And, and then you don't have a fit about 110 00:06:13,705 --> 00:06:16,052 it. So what these assignments are for, it's 111 00:06:16,052 --> 00:06:19,740 for you to get a sense of what an what an NP hard problem is. 112 00:06:19,740 --> 00:06:24,736 What is exponential growth, okay? So once you experience that, you will get 113 00:06:24,736 --> 00:06:28,009 some respects for these problems. And then you're going to start 114 00:06:28,009 --> 00:06:31,130 appreciating some of the techniques that we'll talk about. 115 00:06:31,130 --> 00:06:34,038 And you will see, you know? Oh wow, these techniques are actually 116 00:06:34,038 --> 00:06:36,490 helping us really solve these problems. Okay? 117 00:06:36,490 --> 00:06:40,009 And then you will also build intuition on which one, you know, which techniques are 118 00:06:40,009 --> 00:06:43,770 going to be, you know, good for different kinds of problems. 119 00:06:43,770 --> 00:06:46,138 And which one you have to apply and which are easier to apply, and which one are 120 00:06:46,138 --> 00:06:49,114 more complicated. But they will give you more benefits at 121 00:06:49,114 --> 00:06:51,642 the end, okay? So one of the things that this class will 122 00:06:51,642 --> 00:06:54,980 have is a lot of programming assignments. And you can get frustrated. 123 00:06:54,980 --> 00:06:58,050 And I want to tell you a story. When I was actually young, you know, 124 00:06:58,050 --> 00:07:01,530 student, you know, a young PhD student, I had this great guy. 125 00:07:01,530 --> 00:07:05,149 You know, [UNKNOWN] friend. And I came to him because I disbark for 126 00:07:05,149 --> 00:07:07,830 two weeks. Okay, so two weeks I was trying, building 127 00:07:07,830 --> 00:07:11,820 this optimization system. Having a bug and I couldn't find it. 128 00:07:11,820 --> 00:07:14,734 And so I went to him because he had a reputation of being a good debugger and I 129 00:07:14,734 --> 00:07:17,640 asked him, you know, what do I have to do? 130 00:07:17,640 --> 00:07:21,940 And he said, well, first he told me, you are taking this wrong, okay? 131 00:07:21,940 --> 00:07:25,520 So you are getting frustrated. This is not what you should do. 132 00:07:25,520 --> 00:07:28,920 This is a game, you see. It's a game between man and machine and 133 00:07:28,920 --> 00:07:32,168 man has to win, okay? And so we sat down and we had fun, you 134 00:07:32,168 --> 00:07:36,080 know, we found a bug after about three or four hours. 135 00:07:36,080 --> 00:07:39,564 And it was a really learning experience so all you, you, change your attitude and 136 00:07:39,564 --> 00:07:44,140 then it changes the way you act as you know, view the problems. 137 00:07:44,140 --> 00:07:47,251 So most of the problems that you will see in this class, you can view them as 138 00:07:47,251 --> 00:07:51,718 problem solving tricky puzzle, okay? you, you know, you don't have to get 139 00:07:51,718 --> 00:07:54,701 frustrated about it. You have to say, I want to beat this 140 00:07:54,701 --> 00:07:58,334 machine, I want to get these machines to do what I want, okay? 141 00:07:58,334 --> 00:08:01,534 So you see things like Sudoku, and one of the things you realize is that some of 142 00:08:01,534 --> 00:08:04,884 the techniques that we are actually using in this class will enable you to digest 143 00:08:04,884 --> 00:08:09,872 most of the values here. In a very, very simple, simple manner, 144 00:08:09,872 --> 00:08:12,124 okay? And once you do that these puzzles, you 145 00:08:12,124 --> 00:08:15,975 know, they become much easier to solve. An many of the optimization problems that 146 00:08:15,975 --> 00:08:18,756 we'll see in this class. If you look at them in the right way, 147 00:08:18,756 --> 00:08:22,261 it's going to be really nice. You know, hog, you know, you to find a 148 00:08:22,261 --> 00:08:26,090 really nice technique to actually solve that, okay? 149 00:08:26,090 --> 00:08:29,570 Now there will be other ones that may seem completely messy. 150 00:08:29,570 --> 00:08:32,987 And you start by editing something which is, like, looking like spaghetti code, 151 00:08:32,987 --> 00:08:36,254 and so on. But you know, one of the goal for you is 152 00:08:36,254 --> 00:08:39,740 also to try to make these things a work of art, okay? 153 00:08:39,740 --> 00:08:43,380 So serving optimization problems can lead to optimization problems that are truly 154 00:08:43,380 --> 00:08:46,151 beautiful. You will be really proud of them at the 155 00:08:46,151 --> 00:08:48,960 end, okay? So, spend time finding solutions that are 156 00:08:48,960 --> 00:08:52,288 elegant, because most of the time, the elegant solutions are also going to be 157 00:08:52,288 --> 00:08:56,560 very efficient solutions and very effective solutions, okay? 158 00:08:56,560 --> 00:08:59,305 Now there is a collaboration policy on this class, you have to take it very 159 00:08:59,305 --> 00:09:02,090 seriously. You can refer to the syllabus. 160 00:09:02,090 --> 00:09:05,460 The, the collaboration policy is spelled out in all the details. 161 00:09:05,460 --> 00:09:08,720 There are things you can do and there are things you cannot do, okay? 162 00:09:08,720 --> 00:09:11,120 So we try to give you as much freedom as we can. 163 00:09:11,120 --> 00:09:14,128 There will be forum, discussion, you know, a lot of discussion on how to solve 164 00:09:14,128 --> 00:09:17,190 these problems. You can exchange information about 165 00:09:17,190 --> 00:09:19,980 solution ideas. Okay, we'll let you do that. 166 00:09:19,980 --> 00:09:23,662 But you have to do that at a high level. Its like your personal life, right? 167 00:09:23,662 --> 00:09:26,773 So you can talk about it at a high level, but you don't want to enter into you 168 00:09:26,773 --> 00:09:31,142 know, intimate details, okay? You can share all the objective values, 169 00:09:31,142 --> 00:09:36,217 discuss some of these techniques but you know, stay at a reasonable level, okay? 170 00:09:36,217 --> 00:09:39,336 Now there are things that you, we don't want you to do. 171 00:09:39,336 --> 00:09:42,954 So don't go on the web, find the cutting edge research paper on the assignment and 172 00:09:42,954 --> 00:09:46,464 implement it, okay? So you will learn nothing, okay? 173 00:09:46,464 --> 00:09:49,456 Because essentially, you're going to take some you know someone else's ideas, code 174 00:09:49,456 --> 00:09:52,404 them, and the only thing that you will have done is basically understanding that 175 00:09:52,404 --> 00:09:55,820 techniques. But he will not have understood what this 176 00:09:55,820 --> 00:09:58,947 class is all about. Getting used to experience you know, what 177 00:09:58,947 --> 00:10:02,097 these problems are about, what are exponential growths, and how you have to 178 00:10:02,097 --> 00:10:05,420 be creative to actually solve these problems. 179 00:10:05,420 --> 00:10:09,641 Because most NP hard problems, okay, that you will encounter in practice are not 180 00:10:09,641 --> 00:10:14,495 the ones that you find in papers. Papers simplifies them, there are plenty 181 00:10:14,495 --> 00:10:17,708 of other constraints that you have in real life that typically are not in the 182 00:10:17,708 --> 00:10:22,030 papers that are written by, in academia and for a good reason. 183 00:10:22,030 --> 00:10:24,640 Because you don't want to describe the complexity of this world. 184 00:10:24,640 --> 00:10:26,650 But in practice, you will have to cope with that. 185 00:10:26,650 --> 00:10:29,850 So, you have to experience what it means to solve an actual you know, an actual 186 00:10:29,850 --> 00:10:32,413 problem. And you have to get a feel of what going 187 00:10:32,413 --> 00:10:35,540 to work and what is not going to work. That is why you don't what to do this, 188 00:10:35,540 --> 00:10:39,560 don't go and implement something that somebody else has designed, okay? 189 00:10:39,560 --> 00:10:42,824 The other thing that we don't want is you to copy codes from anyone else or, you 190 00:10:42,824 --> 00:10:46,020 know, to copy the algorithms of anyone else. 191 00:10:46,020 --> 00:10:49,300 Everything, you know, you use in this class should be your own, okay? 192 00:10:49,300 --> 00:10:51,856 As I said you can discuss the various approach, okay? 193 00:10:51,856 --> 00:10:55,600 So we encourage that, okay, because in real life you can do that, okay? 194 00:10:55,600 --> 00:10:58,300 But we, wanted to find a solution, be your own. 195 00:10:58,300 --> 00:11:01,770 It has to be your own algorithm. It has to be your own code, okay? 196 00:11:01,770 --> 00:11:04,302 So, have fun. Optimization is fun, you know the 197 00:11:04,302 --> 00:11:06,898 assignments are going to be fun, you're going to learn tons of things in this 198 00:11:06,898 --> 00:11:09,550 class. It's a lot of work, okay? 199 00:11:09,550 --> 00:11:11,924 [SOUND]. But it's also, it's also rewarding in the 200 00:11:11,924 --> 00:11:16,806 end when you see these things you know, generating very high quality solutions. 201 00:11:16,806 --> 00:11:20,900 Proving optimality to something that seems to be completely out of scope. 202 00:11:20,900 --> 00:11:23,459 Okay? So welcome again, you know, and start 203 00:11:23,459 --> 00:11:25,560 working. Great.