1 00:00:03,400 --> 00:00:07,938 Today, we're going to talk about recurrence relations, which is a first 2 00:00:07,938 --> 00:00:13,085 step towards developing mathematical models for the performance of computer 3 00:00:13,085 --> 00:00:18,097 programs s we saw when we covered the analysis of Quicksort in the last 4 00:00:18,097 --> 00:00:21,213 lecture. To begin, we're going to look at the idea 5 00:00:21,213 --> 00:00:25,548 of using the computer to compute values of recurrence relations. 6 00:00:25,548 --> 00:00:31,318 This is very important for us as unlike many other mathematical disciplines. 7 00:00:31,318 --> 00:00:36,625 we have the ability to be able to quickly check our answers and maybe develop 8 00:00:36,625 --> 00:00:40,032 hypotheses about the answers that we're looking for. 9 00:00:40,032 --> 00:00:42,718 So, but first of all, what is a recurrence? 10 00:00:42,718 --> 00:00:47,108 Well, it's a simply define. It's an equation that defines a sequence 11 00:00:47,108 --> 00:00:50,712 recursively. that's easily understood by computer 12 00:00:50,712 --> 00:00:54,447 scientists. and just as a simple example here's the 13 00:00:54,447 --> 00:00:59,820 Fibonacci numbers recurrence which is familiar to mathematicians as well. 14 00:00:59,820 --> 00:01:03,341 so the recurrence relation is f sub n = f 15 00:01:03,341 --> 00:01:07,012 sub n-1 + f sub n-2. So that's defined recursively. 16 00:01:07,012 --> 00:01:13,005 Each term in the sequence is defined in terms of previous terms in the sequence. 17 00:01:13,005 --> 00:01:18,624 But its very important as every programmer knows, in a recursive program 18 00:01:18,624 --> 00:01:21,846 you need to specify the initial conditions. 19 00:01:21,846 --> 00:01:27,764 Also, in a recurrence relation, you need to carefully specify initial conditions 20 00:01:27,764 --> 00:01:32,110 and make sure that things are defined for all values of n. 21 00:01:32,110 --> 00:01:37,703 In the case of the Fibonacci numbers, we define f0 to be zero and f1 to be one, 22 00:01:37,703 --> 00:01:43,010 and then insist that the equation hold for n greater than or equal to two. 23 00:01:43,010 --> 00:01:50,045 So, f sub two is zero plus one is one, f sub three is one1 plus one is two, and so 24 00:01:50,045 --> 00:01:53,120 forth. We get each term in the sequence by 25 00:01:53,120 --> 00:01:57,514 adding the previous two. So that's example of a recurrence 26 00:01:57,514 --> 00:02:01,394 relation. so now, the question that naturally comes 27 00:02:01,394 --> 00:02:05,128 up is if we're given the recurrence relation 28 00:02:05,128 --> 00:02:10,766 can we come up with a simple formula for describing fn as a function of n, 29 00:02:10,766 --> 00:02:15,106 as a simple function of n? that's the kind of question that we're 30 00:02:15,106 --> 00:02:19,122 going to be addressing. Now as we saw in the last lecture, 31 00:02:19,122 --> 00:02:24,705 recurrences directly model costs and programs for example, we talked about 32 00:02:24,705 --> 00:02:27,612 Quicksort. And it's a much more complicated 33 00:02:27,612 --> 00:02:32,772 recurrence but it still has the same property that every term in the sequence, 34 00:02:32,772 --> 00:02:37,998 in this case the sequence defines the running time of Quicksort or the number 35 00:02:37,998 --> 00:02:42,826 of compares taken by quick sort. Every term in the sequence is defined in 36 00:02:42,826 --> 00:02:48,846 terms of earlier terms in the sequence. in this case the result is not integers 37 00:02:48,846 --> 00:02:54,204 and you can work out that c00 as specified c1 is two and so forth. 38 00:02:54,204 --> 00:02:59,297 That's the number of comparisons used by quick sort to sort n elements. 39 00:02:59,297 --> 00:03:05,041 And we remember, we derive the recurrents from the program, it's a mathematical 40 00:03:05,041 --> 00:03:11,309 model of the running time of the program. specifically the number of compares taken 41 00:03:11,309 --> 00:03:16,120 to sort a randomly order sequence of array of indistinct elements. 42 00:03:16,120 --> 00:03:21,158 Now, a common sense rule, anytime you're addressed faced with a recurrence 43 00:03:21,158 --> 00:03:26,197 nowadays is just to use the computer to compute values to see if you can 44 00:03:26,197 --> 00:03:29,450 understand what the values are and what's going on. 45 00:03:29,450 --> 00:03:35,063 it's, it's even better to do that before doing the math as it might tell you 46 00:03:35,063 --> 00:03:39,018 something that might be difficult to discover with math. 47 00:03:39,018 --> 00:03:43,419 And it's so easy to do. so first thing you might say is why not 48 00:03:43,419 --> 00:03:48,151 use a recursive program? well, we teach now, in every elementary 49 00:03:48,151 --> 00:03:51,624 programming course that you don't want to do this. 50 00:03:51,624 --> 00:03:57,209 it's a very bad idea to try to compute values of a recurrence like this with a 51 00:03:57,209 --> 00:04:01,160 recursive program because it takes exponential time. 52 00:04:01,160 --> 00:04:05,739 That is to compute f of 50, we have to compute 49 and 48. 53 00:04:05,739 --> 00:04:11,794 To compute 49, 48 and 47, and so forth. And if you look at this table, you'll see 54 00:04:11,794 --> 00:04:15,132 that we're recomputing values all the time, 55 00:04:15,132 --> 00:04:20,721 f of 48 twice, f of 47 three times f of 46 five times, and so forth. 56 00:04:20,721 --> 00:04:27,009 Actually it takes exponential time to compute this, so it's not going to 57 00:04:27,009 --> 00:04:31,744 complete even for f of 50. It's, it's much, much too slow. 58 00:04:31,744 --> 00:04:38,646 so it would be nice to think about using a recursive program but we don't do that 59 00:04:38,646 --> 00:04:42,874 in practice. instead what we do is save all the values 60 00:04:42,874 --> 00:04:48,945 in an array and so we'll, we'll need a an array entry for every value that we want 61 00:04:48,945 --> 00:04:52,239 to compute. but nowadays that's no problem. 62 00:04:52,239 --> 00:04:58,279 so, in this case, if you want to compute f of 50, we'll make an array of size 51. 63 00:04:58,279 --> 00:05:02,465 Set the first two values according to the initial conditions. 64 00:05:02,465 --> 00:05:07,270 and then simply [COUGH] go ahead and compute for every 65 00:05:07,270 --> 00:05:12,128 [COUGH] value in the sequence it's value from the previous two values. 66 00:05:12,128 --> 00:05:17,520 So that's a common sense way to deal with any recurrence just use an array. 67 00:05:17,520 --> 00:05:23,296 now [COUGH] what we'll do is maybe a little 68 00:05:23,296 --> 00:05:27,238 more complete. And I, I don't want to make this a course 69 00:05:27,238 --> 00:05:32,518 on modern programming techniques. But, I might as well use modern code so 70 00:05:32,518 --> 00:05:38,642 that we can leverage off of all the code that we've developed for our algorithms 71 00:05:38,642 --> 00:05:41,951 in Introduction to Programming in Java courses. 72 00:05:41,951 --> 00:05:47,864 So if you go to the algorithm's fourth edition book site you'll see to get 73 00:05:47,864 --> 00:05:53,706 started link that you can go ahead and use to download some standard library 74 00:05:53,706 --> 00:06:00,290 packages that are available for average programmers to write these kinds of 75 00:06:00,290 --> 00:06:06,240 programs using a modern model. this is not required but many people will 76 00:06:06,240 --> 00:06:12,261 be familiar with this model so it's the one that I'm going to use for the code 77 00:06:12,261 --> 00:06:17,290 that I cover in this course. and this code is easily translated to 78 00:06:17,290 --> 00:06:22,461 other environments and languages so I'm not going to dwell on that. 79 00:06:22,461 --> 00:06:28,270 so nowadays in a, in a modern approach it's, here's this code that goes ahead 80 00:06:28,270 --> 00:06:36,389 and fills up an array [COUGH] with of size n or size max and with the Fibonacci 81 00:06:36,389 --> 00:06:40,673 numbers. but this is a modern approach where we 82 00:06:40,673 --> 00:06:45,869 use a data type. And the client program will go ahead and 83 00:06:45,869 --> 00:06:52,888 built this array with a constructor and then ask for values out of the array. 84 00:06:52,888 --> 00:06:59,724 Again, this is not the place to talk about details of programming with data 85 00:06:59,724 --> 00:07:04,100 types. But this is a very straightforward way to 86 00:07:04,100 --> 00:07:09,503 approach this problem. And the reason that we use it is that we 87 00:07:09,503 --> 00:07:15,287 can reuse code and, or, or write code that we can use for different sequences. 88 00:07:15,287 --> 00:07:21,565 just by saying that the only way that we're going to evaluate what or deal with 89 00:07:21,565 --> 00:07:27,702 what this sequence is is to use this eval function to get out a particular value. 90 00:07:27,702 --> 00:07:34,333 and then we can write code that will print out values for any sequence so this 91 00:07:34,333 --> 00:07:36,801 code, for example. so again 92 00:07:36,801 --> 00:07:40,470 in this case with this code, it's not that much code. 93 00:07:40,470 --> 00:07:45,022 we, I want to get the first fifteen Fibonacci numbers, it prints it out for 94 00:07:45,022 --> 00:07:47,938 us. and you can in your own programming 95 00:07:47,938 --> 00:07:54,197 environment do whatever you want to to get that result and that's an exercise 96 00:07:54,197 --> 00:07:58,090 worth doing. Now more interesting lets look at the 97 00:07:58,090 --> 00:08:02,967 Quicksort recurrence. now remember we did some algebra to show 98 00:08:02,967 --> 00:08:09,399 that we can make the Quicksort recurrence a very simple linear recurrence rather 99 00:08:09,399 --> 00:08:14,984 than the one involving the sun. and so this is the corresponding code for 100 00:08:14,984 --> 00:08:20,285 the Quicksort recurrence. to using that version of the recurrence 101 00:08:20,285 --> 00:08:24,031 we can [COUGH] in the constructor, create an array. 102 00:08:24,031 --> 00:08:28,980 fill it up with the first n values just using that recurrence. 103 00:08:28,980 --> 00:08:34,474 so it's just dividing by n. and then eval will give us the value of 104 00:08:34,474 --> 00:08:39,102 that recurrence. So the same code will print out the first 105 00:08:39,102 --> 00:08:43,440 fifteen values of the Quicksort sequence in in that way. 106 00:08:43,440 --> 00:08:49,701 so that's a, a good first start so we can get some idea of what these numbers are. 107 00:08:49,701 --> 00:08:55,685 but actually often what we're want to do, and I'll have plenty of examples some 108 00:08:55,685 --> 00:09:00,416 examples in this lecture is, we just want to plot the initial values. 109 00:09:00,416 --> 00:09:03,825 We want to draw the curve to get some idea. 110 00:09:03,825 --> 00:09:11,294 and so this code here uses our standard library for drawing things within a 111 00:09:11,294 --> 00:09:18,494 window on your computer to do the plot. and I'll have some examples later on that 112 00:09:18,494 --> 00:09:24,957 use this kind of code to just draw the value of each recurrence for, and on the 113 00:09:24,957 --> 00:09:30,684 x-axis, and the value of the recurrence on the y-axis scaled to the largest 114 00:09:30,684 --> 00:09:33,695 value, that's what this this code does. 115 00:09:33,695 --> 00:09:40,378 So in the case of quicksort, if we use a call on this show method instead of 116 00:09:40,378 --> 00:09:46,913 printing out the values then you get the curve like that, which is the curve for 117 00:09:46,913 --> 00:09:51,969 for N log N in this case. so, that type of code is a, is a good 118 00:09:51,969 --> 00:09:56,467 starting point. And if you don't want to use my Java code 119 00:09:56,467 --> 00:10:01,894 it's definitely worth while for you to use whatever programming environment 120 00:10:01,894 --> 00:10:07,036 you're comfortable with. to be sure that you can compute values of 121 00:10:07,036 --> 00:10:12,748 any recurrence efficiently, and also to be able to develop plots like this. 122 00:10:12,748 --> 00:10:18,890 and you'll get a good feeling for why we want to do that in just a minute. 123 00:10:18,890 --> 00:10:23,140 So that's computing values of a recurrence.