OK, so today we will do recursion. But before we get started, some students asked about function called signatures for native arrays. So let me just deal with that a little bit. This is not part of recursion. We'll start recursion once we are done with this. So if you're declaring a two dimensional native matrix, you can do it as follows. Now, suppose you're doing that inside main. Of course, at this point, m and n need to be defined and known. The values have to be known. So suppose you have declarations like int mn, and then you read them from c in, then the values will be known at this point, and the compiler can do the necessary memory allocation or generate code for the necessary memory allocation to create that 2D array.  Suppose you want to turn the function into upper triangular or whatever it is. So here's the issue. So how should you define fun? Do properly accept a as input. So technically, you cannot even do this in pure c or c plus plus. So I declare fun here. What do I do? If I write something like a mn, this is the most natural instinct of anyone who is learning c or c plus plus for the first time. The problem is, of course, m and n are not in scope. The scope has closed here. So at this point, no one knows what m and n are. Now, if you want to move this declaration outside, if you say int mn, but you read m and n here, even that is a problem because although m and n as variables are known, their values are not known. And remember when we showed the way in which 2D arrays are allocated in memory in row major order, unless you know the value of n, you don't really know how to address cell number ij. So just to find out what the memory offset is for cell number ij, you need to know the actual value of n, if not the first one. So that means that during compilation time, this will again fail, it will claim that n is not a constant. Your only way of succeeding at this is to define this as a constant, but then you can't do that. So it's really painful to pass around multidimensional arrays or matrices in native form. That's why we move to vector and matrices very quickly. Now, in case your n is actually fixed, you don't need to actually declare m. You can keep that empty because whenever you're accessing aij, remember the cell value, the cell number, is something like i times n plus j. So as long as it knows n, that's fine. You don't really need to know the first one. If you go beyond it, C++ is happy letting you access garbage memory anyway. So for all these reasons, it's really bad to try to use multidimensional arrays and these kinds of things. One thing you could do is inside, once you declare a, in the symbol table, a actually points to some beginning of a buffer of ints. So a is what is technically called an int pointer. When you discuss pointers, you will see that you can always pass a as int star a. That tells fun that a is a one-dimensional array of ints, basically. But then you need to send in the row and column information. So you have to say m, n, a. And that's a reasonable compromise. You know the number of rows. You know the number of columns. And you get a handle to the beginning of the buffer. So now you can do your own addressing inside. So now you have to write your own explicit code doing that transformation from row and column to cell number. So everywhere where you wanted to say aij, you have to change that into a i times n plus j. You have to write that arithmetic yourself. The system will not do it for you. That's number one. Number two is in terms of return values or types. Whatever you've studied so far is fair game to return in the sense that if you wanted to write vector int fun with some parameter, that's fine. If you wanted to say a matrix double return from a fun, that's fine. All of these are OK. There's one possibly dangerous thing you can start doing at this point, which is pass out a reference.  Suppose you do that. So see where this is going. Suppose I say int y equals x plus 1, return y. That means you return an integer reference. You don't return an integer. You return an address to an integer. So this might be a little dangerous because you're allocating a y. You're implicitly taking its address and sending it out of the function. And then you're destroying the storage for y. So you're really asking for trouble here. So be careful about this pattern in your code. This is the simplest way of generating an illegal reference to memory which can be messed up as soon as you return. So that's the preliminary stuff. So today we'll start with recursion. And there's nothing much to it. Most of this segment will be solving interesting problems using recursion. The main point is that the function can call itself, which in turn can call itself and so on. And why can you do that? Because we have figured out in detail how collars and collies manage the space for communication between them, how the caller records in advance where the callee must return. So if the caller and the callee are actually the same function, it doesn't matter. You can always nest. Earlier, fun1 called fun2 called fun3, but nothing prevents you from having fun1 call fun1 call fun1. Once you take that leap of faith, you can write many programs much more easily than we have done so far. So look at, for example, that factorial. So I declared a function which takes an int and returns an int. The input is integer n. I want to find the factorial of n. So I say if n is equal to 0, then return 1. Otherwise, return n into factorial n minus 1. Very simple piece of code. The first condition ensures that you don't keep on nesting calls indefinitely. Because every call reduces n by 1. If n is positive, you're bound to hit 0 sooner or later. In fact, if the input is 13, then fact will call itself exactly 13 times and then start returning. So let's look at a quick piece of code to see how that goes. In fact, you can make it look even more nifty, by using the conditional expressions in C or C++. So if n is equal to 0, return 1. Otherwise, n times factorial n minus 1. That's a recursive definition of fact. And there's no point running it. I read the n from every one. And then I output fact n. This will run fine. The important thing is let's trace it to see what exactly happens. So I'm going to declare some additional tracing functions, which are not important. So indent will merely insert depth number of spaces in the output stream, twice depth. So it indents the thing proportionately. And now I'm going to indent n. And then I'm going to print with what input my program was called. In fact, so now let's compile this. So what will happen is at the outermost level, suppose I enter 5 as input. Fact is called with 5. So n is 5. I indent 5 levels and print 5. Then I check against 0. It's not 0. So I call 5 times fact 4. The current fact isn't finished. So its activation record remains on stack. And now the activation for fact 4 goes on top of the stack. I come back here. This time I find n to be equal to 4. And so on. So 5, factorial 5 calls factorial 4, calls factorial 3, calls factorial 2, et cetera. Now we could trace it further by breaking up this nifty one-liner by saying if n equal to 0, there's no indent anywhere. So for 0, it's the base case. Otherwise, I indent. And then I print input equal to n. Then I compute the final output. Int output equals n into fact that. Then I finish off. I say let's put that n-del anywhere. For the new line, I'll indent again. And I'll say input equal to, I'll print the input again. Output equal to then print the new line. So what have I done? I have a method for indenting so many times. In factorial, if it is 0, then that's the base case. Input is 0, I'm returning 1. Otherwise, I indent the line. I say input was n. Then I do the recursive work by calling fact of n-1, multiplying it by n. Then I put out another line saying input was this. And the output I'm going to return is the output. And then finally, I have to return. And in this case, I have to return 1. So once again, be careful that every arm returns something. Otherwise, your code will be silently wrong, potentially. So everyone clear with what the code is? It's just a trace code to see how the function is being entered and exited. In the case of 0, it's entered and exited immediately. So I'm printing only one line. In the other case, I print one line on entry, one line on exit from the function with the input parameter in both cases. So here's the entry point, here's the exit point. So input 5, it didn't finish anything. It called the routine again with input 4. That called with input 3 until it hit input 0, in which case it turned 1. So now the input 1 guy can finish its work and output 1. After that finishes, the input 2 guy can finish an output 2. Then the input 3 guy finishes with 6, input 4 guy finishes with output 4, and 5 finishes with output 120. It's clear what's happening. So in pictures, the activation stack business. So here's my stack. I called fact of 5. So this said that after you return, I'm just putting it pictorially, you have to multiply whatever you get by 5 and then return. Now, and before doing that, it called fact of 4. So that went to another record, where it says whatever you get from above, you have to multiply it by 4 before returning. Then a third entry went there. And finally, the 0 guy did not call anyone else. So when the 0 guy's activation was running, it didn't make any other recursive call. It directly returned a 1 from here. That was multiplied under 1 passed effectively there, 2 passed from here, 6, and so on. So who does all the memory management? The stack segment is managed by your runtime system, which is attached with the executable code. So the mechanism is the same as managing stacks. Between any pair of functions, calling each other. So that's factorial. The second example I wanted to show is GCD. Again, exceedingly simple. The code becomes much, much shorter and simpler to read. So here is GCD. So what is GCD of mn? Return n is equal to 0 than m. Otherwise, GCD of n and m%n. So this assumes that the first argument is larger, or at least as large as the second argument. So you're taking the smaller argument, and then m%n is less than n. So the invariant is satisfied. So whatever you're doing earlier becomes even more readable, because I'm making a recursive call to GCD here. So I could do the tracing just like before. You could say print out. So I just trace what I'm doing here. Return n. So the two branches, in one case I exit with m. In the other case, it's the recursive call. So I could indent as well to keep things a little clear. But indenting now has two variables, so let's forget it. So suppose I find the GCD of, say, 3 and 5 should be 1. So entering GCD should be 5, 3. So that has happened automatically. Then you divide and find the remainder. So 3, 2, 2, 1, 1, 0. This is entering. All the recursive calls. Finally, because n is 0, exiting GCD 1, 0 will answer 1. And then the final return is very simple. Whatever is returned as GCD from a recursive call, the same thing is returned. There is no pending work of multiplying with n, as in factorial. So this is actually even easier to manage. So it just returns the, whenever the innermost return returns, that's the same value which is percolated entirely outside. For example, if I say 8, 12, then 12, 8, 8, 4, 4, 0, and then 4 percolates up to the top. So it's diving in, solving the problem, and going out. Yes? A2i is alphabetical to integer.  If you want to convert one such string numeral into an int, then you use A2i. A2i takes a string as input and passes an int as output. So this is how GCD works. And the last example I had for the moment is Fibonacci. So you call Fibonacci with int n. If n is less than 2, then return 1. Otherwise return fiv n minus 1 plus fiv n minus 2. That's a formal definition of Fibonacci recursively. And of course it will run fine. So here is Fibonacci implemented. Return n less than 2, 1. Otherwise that. So again this will work fine. But again let me start tracing what happens. So I'll do this indent code. And now I'll just separate out those things if n is less than 2 else. So now I will do one thing, which is just print out the argument with which it's called. So don't bother about indent. So I'll say input n. So I'll do that in any case, let's say. So I don't need to case it. And I'll end all this thing. So just to record with what argument it was called, and then we'll just do the same thing. And then finally I'll output the Fibonacci value. So let's run this. So it's a Fibonacci of 0, input 0, 1. Fibonacci of 1, input 1. Those are the base cases. Now I said 2. Input is 2. Then it recursively calls inputs 1 and 0. Each of them returns a 1. The answer is 2. Now what if I say 3? 3 calls 2. 2 calls 1 and 0 and 1. 3 calls 2 and 1. So let me print the following. So one way to understand recursion is also to attach a level which you can use to indent. So I am trying to compute Fibonacci at a particular level called level. And I'm making recursive calls at level plus 1. This is a very easy way to test what recursion is actually doing for you. So I just added an argument which is the nesting level of the call on the stack. And I initialize it to 0. So I'm starting the call at base level of the stack. Any time I'm trying to push something onto the stack, I'm counting how many activation records have gone on the stack. So is the trick of the level clear to you? So I'm just trying to track how many things are there on the stack on my own without any help from the system. And now I'm going to indent to level so that things are shifted properly. With this modification, if I decompile the code, the printout is much more understandable. So if I do say 5, so see what happens here. I called Fibonacci with input 5. That resulted in two recursive calls, input 4 and input 3 at the same level. Input 3 resulted in recursive calls at input 2 and input 1. Input 2 resulted in recursive calls at numbers 1 and 0, which turned immediately without further recursion. So you see the pattern here. If I took another one, so 6 does 5 and 4 at the basic level. So it's a tree structure because each Fibonacci calls two Fibonacci's. So it's a binary tree. But the leaves are always ones and zeros. Ones and zeros don't go any further. So it's not a balanced tree, but it is a binary tree. So now let me switch off the indent, just so that we can just get a listing of how often Fibonacci was called with each number. So if I compile this again with 6 and I less it, I just get this without the indent. So it's not clear what's happening. But I can always sort it, the lines. And then I get this. So you note the 13. In fact, I should switch off the 13. You can even grab for input. So only the input lines come in. Grip is something that matches for a pattern. So now you see that there are all these. All the calls to Fibonacci with various inputs sorted by the input value. Now, how many do we have of each call? So as you can see, input 0 was called many times. Input 1 was called many times. How many times was input called? You can do that by a comment called unique-c. So take unique lines and count them up. And now you see that input 0 was called five times. Input 1 was called eight times. Input 2 was called five times, and so on. So I'll switch to a different screen next with input 5, I think. So let me show that one. So if the input is 5, then remember this. 5 is called 1s. 5 is called 1s. 4 is called 1s. But 3 is called 2is. 2 is called 3 times. 1 is called 5 times. 0 is called 3s. Why is that? So let's look at this chart to figure out why. This is actually with 7, even better. So let me actually do 7 so we can match the counts. So with 7, Fibonacci is called with input 7 once, with input 6 once, with input 5 twice, with input 1 13 times, with input 0 8 times. Why does that happen? Because of this picture. So let me materialize the whole thing. You call Fibonacci with 7. That results in recursive calls with inputs 6 and 5. 6 results in 5 and 4. So if you count up the number of leaves with value 0, that will match the count given by the program. If you count up the number of leaves with value 1, that will match the number of calls with value 1 as printed by the program. Now you see why this is happening. Because there's too much repeated work going on here.  This entire tree of computation returns the same thing over and over again. And still it is actually called thrice. I pay the cost of calling it thrice. Each time it does the recursion. Each time the leaves 1 and 0 return with value 1, Fibonacci 2 will add them up to get 2 and pass it up to the top. Not only that, even the call with 3 is replicated twice in this subtree already. And now when 6 is expanded, that entire 5 subtree is again copied here. And the entire 4 subtree is now copied thrice over. So the moral of the story is just because you can write Fibonacci recursively, you shouldn't. Because the number of subproblems we are solving here grows exponentially. Whereas as we well know, by using just three memory cells, you can compute Fibonacci in linear time. So recursion is a very good hammer, but that doesn't mean that all problems are nails. So recursion may result in unnecessary complication in your code. Every call has an overhead. And so this is an ideal situation where I'm solving the same subproblem over and over again an exponential number of times, which was entirely unnecessary. Why could I save time and effort in Fibonacci? Because as you move up in a web front from the bottom levels of the tree to the upper levels, you can entirely forget the bottom levels for one thing. And the second is that you could really store the value of Fib4 in one place and read it here, there, and here. Why did I have to recompute the whole tree again and again? I could have cashed the answer. So these two observations, that values older than n minus 2 are not required. And that any time I need this in the recursive situation, I can read it from one place. That makes it easier to write Fibonacci in linear time instead of exponential time, as would happen if you ran the recursive code. So offline, what you should do is that you should compile the standard Fibonacci recursive code. And you should run it with increasing input arguments so that it actually does this exponential business and measure the time. And do a quick plot of, as you increase n, how much time does Fibonacci recursive take to return? You'll find it grows exponential. Whereas quite obviously from the iterative scheme, Fibonacci of n will take order n take. So that's an important lesson that recursion should be used quite sparingly, when you think the setting is quite right. But recursion can often be a very good thinking tool. And sometimes even a very good implementation tool. For example, the last time we implemented mod sort. OK, so it was early on in the semester, and we are not too conversant with 1D vectors and indexing yet. So we had to assume that the array was of length, which is a power of 2. And we had to carefully chunk it up into blocks, each of which was a power of 2 size. Then we had to build this merging tree, binary tree. And we had to do the index arithmetic quite correct so that the correct segments were being merged and so on. All that becomes hugely easy to represent if we start writing mod sort recursively. And in this particular case, no efficiency is lost. So this is a good application of writing recursive code. So suppose I have to write a recursive sort function, which is mod sort, where the input vector is a vector of ints, vec. And to generalize it, I say that I have to sort it from low to high. This is the index counterpart of what standard C++ wants you to do, sort from begin to end. So the first call will happen between 0 and vec.size minus 1. What do I do inside? If high minus low is less than equal to 1, then the array is the segment I'm told to sort is either empty or it's one element. So I return immediately. There's nothing to do. If I'm told to sort low to high in the vector, and high minus low is less than equal to 1. Otherwise, I pick a midpoint, which is low plus high divided by 2. Now observe that here I do not need to assume that vector has a size which is a power of 2 or anything. If mid is slightly to the left or right of the exact midpoint, it's fine. It doesn't matter to me. Why? Because in the first recursive call, I'm going to sort vector between low and mid. The convention is that low is included and high is excluded, just like most indexing schemes of C++. So I find mid. I sort between low and mid minus 1, both inclusive, or low inclusive, mid-exclusive. Then I again call sort. This is similar to the Fibonacci recursive call. I again sort the vector from mid-inclusive to high-exclusive. Finally, I create a temporary vector, which is initially empty, and then I merge two segments of vex. See, once sort vex returns, you can assume that low to mid minus 1 is sorted, and mid to high minus 1 is sorted. So I call a merge routine, which takes vex and two segments, low to mid minus 1, and then vex mid to high minus 1. And so think of the first three arguments as providing a range in one vector, and the second three arguments providing a range in another vector. They just happen to be the same vector. I'll merge those using the standard merge routine I have defined, and write them in temp. See, once I do this, it's clear that I can now copy back temp, which is entirely sorted, into vex between low and high, and that finishes my contract. The contract of sort is given any vector and low and high when I output low to high minus 1 has to be sorted in the vector. I do that by invoking the contract recursively. I make the same routine, sort low to mid minus 1, and mid to high minus 1. Then I merge them, and write them out to low to high minus 1. So the complicated index arithmetic is entirely gone. This starts looking almost like binary search, with the exception that there are two recursive calls. To sort the left half, sort the right half. Approximate half is fine. Mid going off by one, either way, is fine. That doesn't bother us anymore. So let's look at the code in action, including tracing code, which I have already written. So here is recursive mod sort. So indent is again, prints out indents to clarify what level the recursion is happening at. Print is just a print routine. So the first thing to look at is copy. So copy takes an input vector and an output vector and a low index. The low applies to the out vector only. So I copy the entire in vector from 0 to in dot size to out low through low plus in dot size minus 1. So to keep a picture on screen, if this is in and that is out, if I say start copying here, then this is replaced by the content here. That's what copy does. Now what does merge do? Merge we've already seen. In fact, because both my arrays are the same, I'm not passing in twice. And by the way, you can always declare this to be const because you're not changing in. Merge, we can also declare as const. From low 1 to high 1, from the same in array, take the ranges low 1 to high 1 and low 2 to high 2. Those are effectively two different arrays now. Merge them and write them out to out. Out is set to empty to start with. And then the cursors are set to low 1 and low 2. Rx1 and Rx2 width will walk through the two segments. And while Rx is less than high 1 and Rx2 is less than high 2, I do the comparison. And to out, I push back whichever is smaller. Very simple code. This is just merging, as we have always seen. And then while one of the arrays survives, you keep exhausting it and pushing it back to the output. So how many people are comfortable with the merge routine? It's a standard merge. It's just that I'm reading the same array in two ranges. It's only the index here we change. Rx1 plus plus Rx2 plus plus. So pictorially, the merge routine looks like this. So here is in the first argument. And then what are the parameters? Low 1 and high 1. So here is low 1. And let's say here is high 1. And let's say here is low 2. There is high 2. And my goal is to take low 1 inclusive to high 1 exclusive, low 2 inclusive to high 2 exclusive, and take these two things, two ranges, and merge them, and write the output vector. Output is initialized to empty. And finally, its size is the sum of these two sizes. That's what merge does. So finally, merge sort, the recursive routine, is extremely easy to write. If phi minus low is less than or equal to 1, indent depth and write that it's already sorted. And I print that sorted vector between low and high. And return. There's nothing to do. Otherwise, I indent depth. I print that I have to sort the segment from low to high. Then I pick the mid. I call merge sort itself recursively between low and mid, and between mid and high, as I did in the slide. Then I create the temporary vector. I do the merge of vec from low to mid and mid to high, and write into temp. Finally, I copy temp back to vector at low. And I indent depth, and I say what I merge to. So the result of the merging, I print the vector now between low and high again. So in main, I just create a vector of names as before, and then I call merge sort between 0 and names dot size. That's the first level call. So everyone comfortable with this? So basically, apart from the tracing code, all I had to write is a merge code and a copy code. And then the definition of merge sort itself was really short. I put in tracing code, which made it longer, but it's actually very, very simple. The code is really as simple as this. So if I run this now, to sort the original array, zebra alligator, giraffe, wolf, lynx, jackalope. That results in two recursive calls, this one and that one. The first one goes from zebra to giraffe, half the array. The second one wants to sort wolf to jackalope. Wolf to jackalope. Let's focus on the first subtree here. So I split it down the middle, but because there is an odd number of elements, the left one contains only zebra. And because it has only one element, it's already sorted. Then I have to sort alligator and giraffe. That recurses into sorting alligator and sorting giraffe in two different segments. Those are already sorted again because they're base cases, only one element. Then I merge alligator and giraffe as two different arrays into alligator and giraffe. Now what do I have? I have zebra already sorted. I have alligator, giraffe already sorted. When I merge those, I have alligator, giraffe, and zebra. On the other top level branch, I wanted to sort wolf, lynx, and jackalope. So again, I do a cut. I find one element on one side and two on the other. Wolf is already sorted, being a single element. Now I have to sort lynx and jackalope, decompose into sorting lynx and sorting jackalope. Already sorted, one element. I merge to jackalope, lynx. And then that merges with wolf to jackalope, lynx, and wolf. So at this point, I have alligator, giraffe, zebra, and jackalope, lynx, wolf. When I merge them, remember each of them is sorted now. I merge to alligator, giraffe, jackalope, to zebra. So it's the same merge sort, except that I don't need to do that messy index arithmetic. I just split it in the middle. It may be off. Doesn't matter. I do recursive calls. I get each of the sub arrays sorted. Then I merge the two and write it back in place. So how many people are comfortable with this stuff? Now once we have the power of recursion, we can actually write another very nice sorting routine called quick sort, which some of you may have heard of. So suppose we have this array to sort 51926. In quick sort, the first step is to pick what's called a pivot element. And a pivot could be any of those elements. So let's arbitrarily pick the first guy as pivot. So choose an arbitrary element as what's called a pivot, mark it yellow, 5. The next job is to what's called shift. So you shake the array and shift it so that all elements less than 5 go to the left of 5. All elements larger than 5 go to the right of 5. But within those, we don't bother to sort yet. In other words, elements less than 5 were 1 and 2. And they happen to be already in sorted order. So that's fine. We don't disturb that. Elements larger than 5 were 9 and 6 in wrong order. We don't bother. We actually keep them in the same order, 9 and 6. All we have done now is, similar to mod sort, we have created a split, one middle element, and the left, which is less, and the right, which is more. So that's the mapping. And note that the other elements are not necessarily sorted among themselves. The only guarantee is that the left, every element on the left is less than 5. Every element on the right is greater than 5. Now the problem naturally decomposes because I can say whatever be the left segment, just sort it. Whatever be the right element, just sort it. The left element is already sorted in this case. The right element is sorted to 6 and 9. And that gives you the sorted overall array. So this is sort of the opposite order of thinking as mod sort. Mod sort first does the recursive calls to make sure that the two sub-arrays are sorted, and then merges them. This guy just splits it up into the lower and the higher, and then does the recursive calls to finish off. So the only issue is, can I do this shifting about as efficiently as merging? If I can do that, then the algorithm will still be as efficient as mod sort. So let's look at quick sort code. That shift routine is slightly tricky, but it's not too bad. So instead of looking at the pieces, let's look at the sort routine. So sort looks exactly the same as before. Vec between low and high, I'm going to sort. If high minus low is less than or equal to 1, that's a trivial array. I've already done a return. Otherwise, I will print out the range just for tracing between low and high, that I'm supposed to sort. I print out the whole vectors. This is older code, but you can plug in the other code to make it print better things. And then I find the pivot. I'm just arbitrarily picking the pivot as the first element, wake of low. You can pick anything you want. And then I find mid. Mid is the result of sifting there on pivot. I will discuss what shift looks like exactly in a moment. Then I sort the left half, then I sort the right half. Note that mid is excluded explicitly here. So compared to mod sort, it's slightly different in that I sort from low to mid minus 1, but not mid to high minus 1, mid plus 1 to high minus 1. Because the pivot is already done. It's in the correct position. So sort itself should be fairly clear, provided we understand what shift really does. So shift returns mid in the sense that I picked some arbitrary value in this thing. I want to find out what the position was. So mid will be, in this case, 2, because 5 moves to position 2. So the job of the shift routine is to place 5 so that all the smaller elements come to the left and all the larger elements go to the right. And report where 5 landed up so that I can do the recursive calls with the correct range indices. So shift tells me where wake of low landed up. And I use that mid to create the recursive calls here. So let's see how this works. In particular, shift is the most complicated thing here. So what does shift do? See, shift is past three arguments. It's past the vector with the range that's involved, low to high minus 1. The third argument is the pivot index. The pivot index in particular is always being called with low. But that just happens since low could choose anything between low and high minus 1 and pass it as the third argument. The algorithm would be correct nevertheless. Instead of low, I could put high minus 1 and the algorithm would be perfectly right. You could put anything between low and high minus 1 as the third argument. So it's returned to low. And now what does shift do? This is a little messy. So see, finding out the correct position of the pivot element is easy. I just have to count how many elements were less than the pivot. But during the move, I have to make sure that I'm not copying things too many times. That I'm moving it in one shot. So the way we do it is as follows. First, I swap the pivot with the highest thing. Let me keep going with that example I have here. 5, 1, 9, 2, 6. It's good to do on the board so that all of them remain in your view at the same time. 5, 1, 9, 2, 6. And this is my pivot element. So px is 0 to start with. So here is the code. So the very first thing you do is swap. Vac px with high minus 1. So what happens here? High minus 1 is 6. The value is 6. So it goes 6, 1, 9, 2, 5. That's the first step that happens. Now I set a right cursor to low, wx. And now for a read cursor, going from low to high minus 1, high minus 2 actually, rx less than high minus 1. So rx less than equal to high minus 2. So the read cursor can only go up to this point. What do I do? If vex of rx is less than vex of high minus 1, remember high minus 1 now has the pivot. So henceforth, this is where the pivot element has landed up. If what I'm reading at rx is less than the pivot, then I swap rx with wx. Initially they're the same. And then I increase the right cursor.  I'm just reading from the first to everything up to and excluding the pivot itself. Anything that's less than pivot, I'm appending to the new buffer in the same order. I'm not bothering to sort. And at the end of it, I'm just swapping the pivot with the read cursor, right cursor. Remember, at the end of it, the right cursor will exactly be the number of items less than the pivot. So I just push the pivot to the end of it. And by magic, everything that's larger have moved to the right. Let's trace this, and you'll see that happen. So in the first step, rx and wx are both 0. And the condition is not satisfied. So nothing happens. Only rx always advances because it's part of the for loop. Wx doesn't advance unless you actually append something here. So after the first step, the array remains the same. rx advances to this position. At this point, rx is less than the pivot. And what happens is that I swap rx with wx. So the array becomes 1, 6, 9, 2, 5. Wx advances because I did do some writing. And rx advances here. In the next step, wx rx is 9. wx i minus 1, which is the pivot, is 5. So I do nothing. rx advances again. So this time, 2 is less than 5. And so I do a swap between wx and rx. So the array becomes 1, 2, 9, 6, 5. And I'm done because rx has bumped into the right limit of high minus 2. And the final step switches. So remember what wx is. wx is advanced 1 to this one. And at this point, I swap high minus 1, which is the pivot with wx. So this becomes 1, 2, 5, 6, 9. So in this case, it turns out to be sorted, but it doesn't need to be in general. So in the sorting order, you're free to change it. You don't need to guarantee that the left and right half are sorted. So the pivot lands up here. This is less than pivot. That is greater than pivot. That's all we guarantee. So the only tricky part here to understand is that by first pushing off the vector to the right and then swapping as I'm doing, that everything higher than the pivot automatically percolates to the right. But after looking at the code for a couple of examples, you'll figure it out easily. So that's the shift routine. Clearly, the shift routine takes linear time. So this is a situation of input dependent complexity in the sense that suppose the time to sort n things, I want to write this as the time to shift plus the time to sort the left plus the time to sort the right. Everything depends on where the pivot landed up. I don't know where the pivot was, so it's value dependent, unlike mod sort where we purposefully chopped it up into halves. So you know exactly what the time was. So analyzing this is a little more complicated. One way to analyze it is, for example, the worst case, time for quick sort is n squared. What if the array given to you is already sorted, and you kept picking the leftmost element as pivot? You're only getting rid of one element at a time. So you can verify that your time will be n squared. But there is a way to ensure that quick sort is quick. That's why it's called quick sort. Which is that you pick a random pivot. You actually choose one of the elements in the current range at random. In that case, it's easy to show or not too difficult to show that the expected time is ordered and logged in, just like mod sort. And the advantage of quick sort is that you don't need an additional buffer like mod sort. We are doing the shifting in place. Any questions about quick sort? So it's the opposite of mod sort in a way of thinking, because in mod sort you first merge the two sub lists, and then you merge it. Here you first split up the original list, shifted it, and then recursively sorted the two remaining parts. The smaller part of the larger part. So the printout is not as friendly as the early on. So here it is. I have to sort the initial add a zebra, alligator, giraffe, wolf, lynx, jackalope. And I'm told to sort it from 0 to 6. 0 inclusive, 6 exclusive. The pivot is zebra, the first one. And now the pivot being zebra, that will go to the end. So one of the halves becomes jackalope through lynx, 0 to 5. So called halves. It's not really half. Now the input is jackalope through lynx, actually. The pivot becomes the first one, jackalope. And now the result is that I have alligator, giraffe, percolating to the left of jackalope. And wolf and lynx to the right of jackalope. Observe that wolf and lynx were unsorted. They remain unsorted on the right side of the pivot. Zebra is already in position. Zebra is the pivot. It's gone to its correct position. So the subreddit I have to focus on is jackalope, alligator, giraffe, wolf, lynx. And jackalope is the first element, which becomes the pivot, moves to the third or second, 2th position. Alligator and giraffe shift to the left. Wolf and lynx remain on the right, unsorted. In the next call, I have to recursively sort alligator and giraffe, 0 to 2 exclusive. The pivot is alligator. It stays where it is. Giraffe is a trivial thing, so all that is sorted. Meanwhile, sorting 3 to 5 exclusive, which is wolf and lynx, makes it lynx and wolf. So the first thing that happens is the first pivot, Zebra, finds its correct position. The second thing that happens is the second pivot, jackalope finds its correct final position. Alligator finds its final position. So it happens in the pivots. The pivots find their correct position, and then the other things are recursively adjusted around them. Now I don't have preparation for the network, but there are very excellent Java applets, which show you comparatively how mod sort and quick sort work on a bunch of keys. They're beautiful graphic applets. I'll see if I can link you to that in Moodle. But you can just do Google search saying sort applet demo or something like that. You can see how these values keep percolating. It's very nice to see those. So that is quick sort for us. Any questions about recursive sorts? So earlier, we looked at selection sort, which was kind of silly. Then we looked at mod sort, where you had to do some index arithmetic. Now all that border is taken away because we can write these things recursively. So the last problem we'll look at today, we'll start, but probably not entirely finished, is string edit distance. Now, so what do I mean by that? You want to find out how similar two strings are. Like you want to find how similar are the two strings kitten and sitting. And you express that as, OK, someone replace the k by an s, and that becomes sit-in, which is a meaningless word. Then the e became an i that was sit-in. And then you appended a g, and that made it sitting. Why is it useful to talk about string edit distances? I'll give you a whole bunch of applications. Nowadays, many envelopes that are addressed with printed addresses on the top, they go through optical character recognition software for automatic routing in big post offices at the metro level. So the OCR can make some mistakes because the label wasn't quite stuck on a right angle or there's a smudge of ink somewhere. What you want to do is to find the nearest matching city name or town name or street name. You want to find an actual address in the post office's address book, which is closest in terms of edit distance. Another example is where you're trying to judge if one web page was a copy of another one so that you don't index it twice in your index. Very often what happens is someone can take a whole site and mirror it. Or you copy someone's page and say, I really like this, and I didn't want to leave it at their site because that can go away. I just made a local copy so I can always see it. And sometimes you're honest. You can write at the bottom that this was last modified by yourself. So your page will have a small difference from the earlier page. So to detect whether these two pages are very similar, you might want to do a string edit distance. Gene research is another important place where string edit distance is very important. So some of you may know that genomes can be expressed as strings of four characters, A, C, G, and T. And then whether an enzyme docks with a gene at the proper site or not really depends on string matching. So large molecules are actually distilled into a few characters. And the pattern of characters decides whether the enzyme in a particular drug, or maybe a virus, can dock onto a particular point in your genome and damage it or fix it. So to do that, you need to find out edit distances between two genomes or a genome's molecule sequence and a drug's molecule sequence to decide if they can dock. So string matching and string edit distance is very important in many areas of computing with other applications. So coming back to this example, if I had to tell someone what to do to edit kitten to sitting, I would give the following instruction. Replace k with s. And in case there are multiple k's in the string, I have to say which one, of course. Then replace e with i and then append a g. So there are three operations. Now in case of, say, optical character recognition for the post office, all edits don't have the same cost. It's fairly easy to confuse reading a 7 for a 1, depending on how you write it, or an 8 for a 3. It's much more rare for a 8 to be mistook for a 1. So when I say replace e with i, the cost of that may be quite different from replacing q with g. So in general, we may have a matrix which gives you the cost of mistaking one character for another one. But in this simple example, I'll assume that the cost of any such operation is exactly one unit. And when I say I'm looking for the minimum cost edit, I give me an edit transforming one string to the other with the minimum number of operations. Just count the number of operations to turn one string into another. So how do I do this? Now clearly, I can't do an exhaustive search because there are too many characters that I can insert at too many positions. So I need to do this a little smartly. So I set up the two input strings as two arrays. And for once, I'll use a one base because that will make life a little easier for us. So the string s, which is kitten, goes from k in position 1 to n in position 1, 2, 3, 4, 5, 6. And similarly, t is sitting. So the source and the target, the two extreme points are s and t. And we define d of ij to be the smallest edit distance or the smallest number of operations in this case that can convert s to t. So d ij returns an integer. d ij is a function which can read s and t. And d ij is defined as the smallest edit distance between not s and t as a whole, but prefixes of s and t. So I'll build up my solution gradually, just like I was building up Fibonacci of n, or I was building up recursive mode sort. So d ij is the smallest edit distance between the prefix of s from 1 to i and t from 1 to j. Now what are the base cases? Suppose I start with the second string being empty. So if d ij is j is equal to 0, it means that my target string is empty. And d i means I have to start from s1 and go up to i. Now suppose I take d of 1, 0. What does it mean? It says take the string k alone and turn it into an empty string. What is the cost? I have to delete k. So here is s. Here is t. So d ij is the number of edits you need to do on this segment to turn it into that segment. Actually in this case, i is included, because I'm not doing a 0 base thing. So naturally, my final answer will be d of mn. That's my eventual answer. So how do I define various things? So suppose I say d of i, 0. Now if j is equal to 0, that means t is actually empty. t is the empty string of length 0. If I want to transform any d of i, 0 to an empty string. So for example, if i is equal to 1, then I just have k here. That's it. To turn k into an empty string, I have to delete k. To turn k i to an empty string, I have to delete two characters. So the cost is 2 and so on. That's the reason why d i, 0 is equal to i. You give me i characters from s. To get rid of all of them, I'll need the cost i. Similarly, d 0, j is equal to j, because I start with an empty string. And I have to turn it into a length j string by appending each of those characters. So those boundary conditions are clear. In particular, d 0, 0 is equal to 0. To turn an empty string into an empty string, you don't need to do anything. The cost is 0. So those are the base cases of the recursion. And then the recursion does one of four things. So I'm trying to transform the string from s1 through si to the string t1 through tj. And j doesn't need to be equal to i. j could be here. But suppose I find that the last two characters are the same. So if I'm trying to transform s1 through i to t1 through j, and si is equal to tj. That's the first case. Then that last place is already matched. There's no cost for it. And I'll have to just recursively match the prefixes. So the call now says that I just have to match this guy with that guy, and I'm done. That's the first line. So dij is equal to just di minus 1, j minus 1 in the fortunate case that the last characters are the same. What's the second situation? You may choose to delete the last character of one of them, which means an insertion for the other one. So for example, the second line says that those two characters are not equal. And I think I should delete i. If I ground out i, then I do a recursive call on the remainder with the same on j. I still have to account for that last character here. I just paid cost 1 by deleting that last character from the first string, from s itself. So I say I'm going to incur a cost of 1 for deleting si. And then the remaining cost is di minus 1, j. Conversely, I may decide to ground this guy paying a cost of 1 plus 1. And then my recursive call will be on the whole of i and the prefix on j minus 1. That's the third line, di and j minus 1. The only remaining possibility is that those two characters are not the same. And I have to transform one to the other, paying a cost of 1, like transform a 3, 2, or 8, or transform a 1, 2, and l, something like that. So currently, that cost is always uniform. That's the plus 1. If I decide that I'm going to edit or replace this character with this character, then the recursion happens on minus 1 and minus 1. So it's di minus 1, j minus 1. So there are only these four cases. Nothing else could happen. If I have to find the edit cost of s1 through i to t1 through j, you depend on what happened in the last position and accordingly you recurse on the previous ones. So how many people are comfortable with this definition? Just the definition. Yes? So there's nothing else that could happen. di, j can be expressed as the minimum of those. And we want it to be minimum. We want to take the best possible option to minimize the overall edit cost. So suppose we write this up. Before writing up, maybe we can look at a couple of examples. So this kitten and sitting example. If you use those rules that we set out in the previous slide, and then because the base cases can be computed right away, so the first thing you do is fill out the 0th row and 0th column. Remember we said that di, 0 is i and d0, j is j. And now we start filling things out from this corner toward the bottom. See, the recursion always refers to either the previous row or the previous column or both. So the right way to fill up would be, say, row, i's or column, i's after you're done with the boundaries. So if I fill up this table, then s and k, you'll see that it's a question of replacement. So you don't want to do a delete followed by an insert because that's a cost of 2. You'd rather do a single replacement of s to k. That'll give you a cost of 1. So at this cell, what you'll compare, you'll choose one of four options. One is substitution or replacement, which will cost you 1. See, the last characters are not the same, s and k. So the first doesn't apply. You have to choose between those three options. So if you say that I'm going to delete one of them and then add the other, that'll be a cost of 2. Whereas if you choose the third option, replacement, then it'll be just 0 plus 1. That's the one you'll take in this case. Now in the second place, i is equal to i. So there is no cost. In the sense that I'm taking now the very first clause. And so this value is just 1 plus 0. I could be a little foolish and say that, well, it happens by first substituting s by k and then appending i and then deleting i, but why do you do that? It's the same thing. So I'll take the minimum cost. So anyway, all you have to do is to just blindly apply these rules which you hopefully trust by now. Compute the cell. And you can also remember which of these four cases led to the minimum. Suppose you also recorded that in the cells, then you could trace back this path. So you would actually remember that this minimum was achieved because of substitution of k with s. That was achieved by doing nothing because i and i matched up, t and t matched up. So you go right down here until i end up with n, which also matches. So up to n, the cost is 2. Why is that? Because of this one substitution of i with e here, that's one of the increases. And the other increase is substitution of k with s here. 0 increase to 1, 1 increase to 2. That's how we end up with a match between kit n and sit in. And to get the g, you have to append it. That's another cost of 1. That's the last cost. So the edit distance in this case is 3, which is exactly the same as the number of operations I specified here. So next time, we'll write a recursive routine for this. And we'll see that this is another of these cases where recursion is a very bad idea. Because these recursive calls are made to a row above under column before, and they keep on proliferating through the lattice. So any particular cell will be touched many, many times. It's much better to create a table and actually store these values in a table form, sort of like if you had an array for Fibonacci. Suppose you don't want to be too smart. You can always to compute Fibonacci of n, you can always retain the whole history of Fibonacci 0 through n minus 1. That will also give you linear time. It just takes a little more space. In this case, the space turns out to be mandatory because you could touch the lower parts of the array at any time. So we will first of all write a recursive routine for this. We'll see that it's very inefficient. Small examples will still terminate. But you'll basically describe all possible parts from this corner into the leftmost corner. You'll traverse all those parts many, many times, touching every cell again and again. So instead, we'll actually cache the results, just like you can cache the results of Fibonacci in a 1D array. So that we'll start populating the array from the upper and left border, and we'll fill this out. We'll remember how each minimum came about so that we can issue the exact edit operations that are required to transform one to the other. So here's another example of transforming Saturday into Sunday. You can again work out the numbers by hand. You'll see that we start with empty, editing to empty with no cost. No cost here, same thing. A and U, you need a replacement. And then you can trace it out.  So this is the insertion of A and T, not editing A to U.  R edits to N, D and D are the same, no increase. A and A are the same, and Y and Y are the same. So again, this is edit distance 3. But the pattern is a little different. So we'll stop here, and next time we'll do the code for edit distances.


Welcome to The Spiritual Masters, a podcast from Tan Books and Tan Direction in which we look at the greatest and holiest writers from Catholic history. Join us as we explore the life and times in which they lived, an overview and study of their greatest works, and how we as Catholics can look to these masters as models for our own holiness on our journey to heaven. All right, welcome back for another episode on The Spiritual Masters with our focus on the great Doctor of the Church, the Doctor of Grace, Saint Augustine of Hippo. And we continue with my dear friend, Dr. Paul Thigpen. Thank you again for being here with us, Dr. Thigpen. It's a delight, Connor. Thank you for having me. Let's begin this time with a short prayer seeking Augustine's intercession into this conversation in our lives. Would you lead us, please? Sure. In the name of the Father, and of the Son, and of the Holy Spirit. Saint Augustine, Doctor of Grace, pray with us now and for us that God's grace will be abundant in this conversation, that we'll have the grace to discern and also the grace to act on what we learn. We thank you for your life of holiness, your pursuit of the truth. We ask that we could imitate you. Father, we ask all these things in the name of your Son, Jesus Christ. Amen. Amen. Thank you. All right, Paul, why does the book Confessions matter to you so much? This matters to a lot of people, but just give us your own personal experience. What's the big deal about this book? When I read this book, I read my own story in so many ways. I mean, not to compare myself in any way to Saint Augustine, but he was really the only ancient writer like this to look so closely at the movements of the soul, interior things, whether it's memory or imagination or sense of guilt or moral behavior. I like to call him a doctor of the soul, a teacher of the soul. He really understood the soul. To this day, you have psychologists who study these passages in here because they officer so much abundant material to talk about. Augustine was the first psychologist. I think in certain ways you could say that. And he did it by looking at himself. I mean, he doesn't have some psychology of Monica in there too and Ambrose, maybe, but he did it by looking at himself.  He laid it out for people to read and for people to talk about because he thought it would help them to understand that. And here we are all these centuries later reading it and seeing ourselves. It's like a mirror sometimes. Seeing ourselves is his confession. So what about the kind of the historical context of this? You know, where was he in his life when he wrote this? He was not an old man yet. So talk to us about that. I read he was 43, which is my age. That's right. That's not an old man. I don't know. It's not yet. No, not in my book, that's for sure. Well, again, he was bishop at the time. A fairly new bishop a couple of years maybe. I don't know. A few years up. Let's look at the timeline here. He at least started writing about the about 400 and it was what 396, I guess, became bishop. Just a handful of years, just a few years. But already of great reputation. He's already kind of a celebrity. I mean, a reputation before he even became Christian when he was because of his rhetoric. He was such a preacher. So amazing thing that he would open up his life and be transparent and vulnerable. It made him so vulnerable to use the modern terms for the sake of his flock that some way maybe you can be encouraged by my struggles and be encouraged that I'm making it. It seems to be, but I still have struggles and I understand your struggles. So what a beautiful thing to do and it came at a price. I mean, there would have been people who would have made all kinds of, hey, out of this, did you hear what the bishop said about himself or especially his enemies, the Pallagians and others? Just touch on that because the Pallagians were really stuck up and they would have been scandalized about him confessing these things out loud. So just kind of touch on why would that be so scandalous today?  Well, they had a political, theological, political axe to grind. And so anything they said that, and he was their most formidable opponent, anything that he said that would give them ammunition was a good thing. And also, the Pallagians, the Pallagians that the, the core of their belief though, or actually more the Donatists. Well, I was going to say the Donatists probably more because they were the ones that the Puritans of their day. They're Puritans. They basically believed that if you were, if you had committed certain kinds of sins, then your sacraments weren't valid and that a priest could not confer the sacraments. And then there's certain people that, for instance, if you committed a apostasy, you could not even be forgiven. A lot of them believed it and brought back into the church. Yeah. So for him being a prominent bishop and confessing these things, these Puritans, for lack of a better word, they were scandalized. And, but to get back to the Pallagians, they, they claimed that they looked in the confessions and saw indications that he was really still Manichaean in certain ways. We talked in the last episode about the Manichae, Manichae's and because he, he talks so much about brokenness.  And it was a way to try to explain how evil's in the world. And so anyway, his enemies would do take different tax with it. But, oh, he's not, not to be respected at all because he has this past or he still struggles with things or to say, oh, yeah, you've listened to him. He's, he's still Manichaean. Wow. Yeah. And they probably knew that he'd be open to all those things, but still he wrote it. And still we have this gift today centuries later where we can read this book and say, oh my goodness, that's my story. The books had many additions, many translations through the years, probably in every language imaginable. And I have to note that if we're, we're recording this in February of 2023, I mean, in a few more months, we're going to have our own translation at 10 books, we're going to have our own translation of the Augustine's Confessions by Dr. Anthony Esslin, who you know, know of. And, and, and he's just a masterful translator. He did all of Dante, the Divine Comedy. So I wish we had that now to read some passages, but it's still in manuscript form. But I'm hoping that that will be a tremendous addition to add to the, the long lineage of many good additions. If someone had asked me, you know, before I knew about that he's doing it, if you could grab one living person to do a new translation of the Confessions, well, who would it be? It would have been Tony. That's awesome. Thanks. Yeah. Thanks for saying that because I'm so excited. I called him or we called him as a team and said, so I would know you like to translate, you know, how would you like to do the Confessions? And he said, he said, this sounds awesome. Let me think about it. And very quickly, he's like, yep, I'll do it. So we're very, very excited. I just can't, can't wait to, to read it. It's going to be beautiful. I mean, you have Augustine who just wrote beautifully, but if your translation's not right, you can butcher it. So Tony will nail it. He certainly will. All right. So here at 10, we're trying to add to that, you know, to that great history of great translations. Okay. So, you know, this book really gives a very good overview of his early life, a couple key points that I thought we'd kind of touch on. I sent some interesting things. And I'm trying not to be too redundant about the timeline that we covered in the last episode, because we don't want to repeat everything. But let's, let's zoom in on a few key points that reveal what Augustine's really trying to discover about himself and about his human nature. It was just always the struggle for him to understand what is this human nature that we have. And it begins, well, actually, let's begin by saying how the book actually begins, which is the, the great famous quote that we finished last episode with. So just go through that, because I think that's the very beginning of the work. Mm-hmm. I did, this is not a commercial because this is out of print, but I did a book before Restless, So We Rest in You. It was Reflections from St. Augustine. And I chose that title because on the very first page of the Confessions, he says, you know, you have made us for yourself, O Lord. Almost choked up. And our hearts are restless until they find the rest in you. And he returns to that theme again and again, seeking rest. He, and again, other books too, City of God and All, How the Great Sabbath, the consummation of all things that we read about in the Book of Revelation, it will be the great rest, the great rest. And so I think it tells us so much about the book. It tells us so much about the man that his whole life was spent seeking the truth and doing so seeking God. And he was restless. And in the way he did it, he would, you get it in the Confessions, he'll, he'll see a lizard basking in the sun. And immediately his mind will turn to, okay, what's the spiritual illustration that comes out of that? Or he'll hear the women in the harvest who are harvesting a great crop there in North Africa. And they have this kind of uvulik trail that they do that it goes beyond words. And it's, but it's just this great celebratory thing. And he sees that as almost like some people have been said, like speaking in tongues or something, but a praise that just goes beyond earth because we're so exalted up to heaven with it. And for every term, he was restless to find God in that moment, God in that situation. What lesson can I learn about God? He's looking for traces of God in the creation. Yeah, absolutely. And early in the Confessions, he finds it, he asks questions and finds these difficult celestial questions, even in infant nursing on his mother. I've had plenty of kids. So he has a, I'm just gonna, well, explain why would he even bring that up? What was the point of that? Well, he said, you know, even when we're babies, we're selfish. Real selfish. It's basically, you know, original sin or concupiscence already.  Yeah. Oh, yeah. I can't remember exactly how I said it. But he says, basically, yeah, they're, people say, well, they're harmless. He says, well, they're only harmless because they're not as strong as adults are. But with their attitude and their desires and their passions, if they were strong as we are, they'd really be troubled. They've been beating us all up because they are selfish in that way. Right. And then he says, you know, in particular, that if you have two children at the breast and one sees the other one is drinking, it doesn't matter whether the other one's hungry or not. This is my place. You know, we had twins five years ago. I saw it firsthand. These little guys, well before the age of reason, they were getting very territorial in lots of ways. But it's just, again, that shows the spirit of Augustine. He is seeing the moral dilemma, the human nature, the presence of God, the lack of God and sin and vice. And he sees it everywhere, everywhere. And so it's just a stroke of brilliance to kind of begin the book by talking about infants. He's confessing I was an infant and a selfish infant. Who would have thought to do that? But to use it as a point and we're all this way. We're all this way. So that kind of leads into his adolescence, about 12 years old, and there's a famous scene that gets, you know, again, it's kind of, it looks like a little harmless incident in every boy's little life. But he's able to extrapolate tremendous theological insight from it. So tell us that story. So he's out playing with some buddies and he makes the comment, we're probably out much too late. And being that late than the adults weren't watching. And so somebody gets the idea, hey, this neighbor over here has a pear tree and it's full of fruit. And he makes the point of saying, the fruit wasn't that good. It wouldn't even taste it very good.  And they all went and they shook the thing to get all the pears down and started pulling all the pears off the tree. And he used to have a pear tree. And I remember one time for myself, I was shaking it and they just all started falling because they get so heavy. But anyway, they do this.  In fact, we took the pears and fed them to the beast. I don't know, pigs or something. We threw it to them. We didn't want it for ourselves. The pleasure was in doing the wrong thing. And if any starts thinking about, you know, take that to the next level, how often is that the case for us? We're not even doing it because we're hungry knowing that it's wrong because it's not ours. But we're doing it just because we take pleasure, not in the pear, but in the stealing of the pear. It's a staggering thought.  I mean, when is that present? But is it fair to say, Paul, that Augustine, he struggled with the problem of evil his entire life? I mean, he just continually came back to it in one way or another, dealing with the heresies, dealing with his own sermons, his different works. I mean, what is this thing in us or outside of us or both that is drawing us away from God? And it was just, you can just tell, I can just see the guy sitting in his room, just shaking his head, saying, what is going on? Well, I mean, his experience with the mannequins, that's what one of the things that would have attracted them. They promised this explanation for that. And seeing that there is a dualistic presence in the universe and there was just this God of evil, at least he could stick his finger out. Exactly. That's what it is. Yeah, that's because we are trapped here in this world and have been trapped because there was an elaborate mythology that they had, but we are trapped in this world. So that's, that's where it comes from. That's the problem. So I mean, that's the thing is like it just shows that his intellectual and his own spiritual struggle began very young. He must have been aware of it. But even as a 43-year-old man, a bishop, he's looking back at 12 years old, he's looking back at infancy and saying, this struggle, this struggle. And that's, again, that's the other side of that restlessness. So it's kind of beautiful. So what else about the confession? What are the themes or do you think or some passages that you might want to read? I mean, what we've talked about, it takes tremendous humility. It's about this internal struggle. We're not really going through the biography, but what other parts of the confessions would you want to talk about? I think it's important to recognize why he called it the Confessions. Oh yeah, of course.  And that was certainly one of the, as we're seeing, one of the important themes there. But confession also meant, it could mean a confession of faith. So even later on the middle ages, you would, like the Lutherans had the Augsburg Confession, and it was a creed, basically. But then also confession could have the sense of praise, saying to God, how wonderful you are. So you're kind of, you're speaking, you're stating something with God. You're agreeing with God about your sin, you're agreeing with God. Even like the word con was with, of course. And the word for fessio or whatever is something having to do with speak or deliver or something. So you're speaking with God. We're speaking with God. God says, it's wrong. You say, yes, sir.  And it was an interest. I had never really thought about it. Oh, we're in agreement. Okay, that's good. You know, that's a start. But that's a confession, and it's kind of an interest. Yeah. And we'll often say profession of faith, because you're speaking forth, that means declaring. But in the other sense of confession, of staying faith, you also think about how you're agreeing with God about the truth, but you're also agreeing with the others, especially when you make a corporate confession of faith, that you're saying together, you're saying with each other, these things are true.  And you think this is why he wrote the Confessions to God? It's everything that that was your unique device.  He's not just writing first person, I do this, I do that.  But the whole thing is, it's a book length prayer, because it's all said to God, second, and he's consistent about it. And so it makes very vivid, you know, his sense of the reality that God is right there with him, watching everything, observing, talking. It did that for me to help me think about how God is right there.  I did, you know, it enables you to put it into your own mind and your own words. It helps you connect with it. But I can't think of many other saints or scholars who have used this device. And it might be because we're all scared to try it, because he did such a good job. We don't want to look like a third-rate Augustan if we try it, you know. I was going to find this book that I had done. So this book that you wrote? This is the one that I wrote. It was basically daily meditations. Yeah, but drawn from his. Yeah, that's just some beautiful places where but he has one place where he just goes on and on, and he just does what I was doing a while ago, just creates this mountain of praise where he just keeps, it's like he keeps piling on, piling on. Oh, you're great. You're so good. You're merciful to us. You forgive us. And it all has an interior aspect to it where he's talking about, this is what you've done for me and this is what you've done in me. But it's a very powerful expression of praise. It reminds you of the Psalms, which he loved dearly. And he wrote about all the Psalms. He had commentaries on all the Psalms. And, you know, speaking about that mounting of praises, he just keeps building and building it and building it. You know, he said somewhere, and I have the quote buried in here somewhere, but he makes the comment that he's always, he feels the truth and beauty in his heart so, so strongly. And he's always disappointed when it comes out of his mouth. He says, why cannot my lips do justice to my heart, you know? And it's amazing to think that because, you know, he was so articulate and so beautiful in his speech, but he always feels let down when he speaks and writes. And as somewhat of a writer myself, I can relate that, you know, one of the reasons I like writing more than speaking is you can polish and edit. That's right. That's right. Because you have as a melancholic, I have the sense that I never quite said it right. And I second guess, speaking of melancholic, I'm reading his biography the other night. And my wife, who's an extremely caloric temperament, and I'm very melancholic, and I read a part in here where a quote from Augustine that says, I was just looking for sad things to read. I love reading sad things. And I read this to my wife and she went, oh, he's such a melancholic. So, but he was, but that enabled him to feel deeply. He was a, and I think the confessions, particularly that amongst all his works, Paul, it shows that he felt even more deeply than he thought. Oh, passionate about God. I love how he's passionate about his friendships. You read some of his descriptions. He says, you know, close friend, we were like one soul and two bodies. And when he has a friend die, and he just, he grieves so deeply. He says, I don't even want to be in the places where we used to be together. I can't stand that. And I keep thinking that I just want to die myself. But then he says, but no, because we really were kind of like one soul and two bodies. I didn't want to die because then it would mean the rest of who he was would be gone too. And all these just beautiful things. He just like that. But let me, yeah, let me give an example here. Please, please do. I did find one of the ones. And a lot of folks will recognize the words. He says to God in the confessions. I'm going to read it without you. Too late have I come to love you. Beauty so ancient, so new. Yes, too late have I come to love you. You were within. Sorry, I can't read it for you. My own conversion.  I and my ugliness rushed headlong into the things of beauty you had made. She's loving the things, the beautiful things more than the one who made them. You were with me, Lord, what a great line. You were with me, but I was not with you. The things you had created kept me far from you, yet if they had not been in you, they would not have been at all.  You flashed and shone and chased away my blindness. You breathed upon me frequently. I drew in my breath, and now I pant for you. I tasted, and now I hunger and thirst for you. You touched me, and I burned to enjoy your peace.  It's my story. That's your story? It's my story. Thank you. Yeah. I should have had it closer by if we were going into the confessions. I should have known. That language is packed so full with meaning. It's such beauty. It's analogies, it's imagery, it's all. But if you recognize it as your own, you just can't read it without tears. That's amazing. That's a perfect passage to show this passion of this man, and the doctor of grace. It could be the doctor of passion. It could be the doctor of many things. But thank you for sharing that and sharing the emotion. It's very powerful. Let's move now to the last three books of the Confession. It was interesting to me that we go from this extraordinarily passionate appeal and description of his life and the pair and his conversion. Of course, which we talked about in the last episode, but his baptism, the moments of conversion when he hears about the life of St. Anthony and then he hears the child calling to him to pick up, take it up and read and he finds the passage from St. Paul and the death of his mother and just all this incredible stuff. But at the last three chapters or books of this work, he turns to Genesis and he starts doing some biblical commentary. It seems out of place, but it's probably not. So why do you think he finishes his autobiography at the age of 43 as a fairly new bishop? The last three parts of the work are on the book of Genesis. Why? I think it's at least once since it's his confession of praise. Because what he does with it is to draw out from these first chapters of Genesis the creation and that means talking about who the Creator is and how he's all-powerful and does it out of nothing. Not just it's powerful to make these things, but as he said in the passage I read, you're the beauty so ancient and so new. You look at creation and what he's made. It's so beautiful because he's beautiful. The one who made it is beautiful. It's reflecting his own beauty. So it shows his power, his beauty, but also shows his wisdom. And so by looking at the early chapters of Genesis, it's kind of a almost like a confession of faith, finally saying, first of all, this is God. This is all about God. But then, because it's those early chapters, you also get to the fall and that allows him to start talking about this theme that we're talking about, sin, grace, and how our story begins there. And as a human race it begins there, but for each of us it kind of begins there too, because of original sin. And so it gives him the opportunity, I think, to lay out kind of so many principal truths of the Christian faith. But it also reflects just how important the scripture was to him. He had written off to Saint Jerome, please give me your translations of scripture and studying them. And you look at this, not just these books, but his homilies. He's just tossing scripture references off all the time. And certainly would have agreed with the famous statement of Saint Jerome, ignorance of the scripture is ignorance of Christ. So he sees Christ the Word in these words. And so even though some folks have complained that it seems to lack unity, the book does, because you've got this last part like that, I think it just shows us Augusta. It shows where his heart is. It shows us where his mind is. These are important things, and they touch on all the kinds of themes that we've been discussing. You know what I think it is? Whether it was intentional or not intentional but providential. It was a foreshadowing of his new life, you know, the new Augusta. And most of that book was kind of the old Augusta. But now it's saying, I sought wisdom. I sought even pleasure in all ways, in all manicheism and neoplatonism and all these different places in Cicero and Virgil and wherever. Now I'm going to seek it in holy scripture. And for an academic to admit that is quite something. And so for him to say, yep, my autobiography at the age of 43, it finished it up with showing that I'm dedicating my life to understanding scripture. And that's ultimately what he did. I mean, he was just one of the greatest biblical scholars. But again, I just want to really drive the point home for a philosopher to admit it's just in understanding what God is saying through scripture. That's where true wisdom is found. That's a great act of humility. And I think he's showing us that this is what he's going to do for the rest of his life. I think it's a foreshadowing. It illustrates what, since she's later, St. Thomas will say, you know, is that even though the faith is reasonable, there's a lot that we can't get to by reason. It had to come by revelation. And he gives the reasons. It's in the beginning of his summa gives various reasons for why God had to also reveal truths that, you know, for starters, he says, you know, it could take a play to figure out some of these things and we're not all Plato. But also things that like the inner life of God, the inner nature of God, the Trinity, you can't get there by reason. But that doesn't mean it's not true or it's unreasonable. It has to be revealed. And it's revealed in, first of all, in Christ's coming, but then in the scripture that points to Christ. It's a beautiful work. Closing comments, I'll give you the last word on what makes the Augustans Confessions so powerful. The next episode, we're going to talk about the city of God, which is a very different kind of work. But closing comments on the confessions. I would just call them a doctor of the soul, not just a doctor of grace, but a doctor of the soul, doctor in the old sense of the word that means teacher from the land. And people have recognized that, even people who don't agree with them on so much, even it's amazing. Calvin and Luther just were great Augustinians in certain ways. They didn't take it all the way. But modern psychologists, modern philosophers, it's such a rich garden to go digging in and find all different kinds of fruits and other things. And I would just encourage our listeners to read the book, even if you get to a place where he starts talking about time and eternity and he's a little above me, my pay grade, just jump over it, but keep reading. And you'll almost certainly see at least some part of your story there. And it will stretch your mind in all kinds of ways. That's wonderful. I'm actually going to change course now. I'm actually going to do something that might sound weird, but I'd like you to read that passage again, read the passage again. And that's just the perfect way to let us go out. And so wherever our audience is listening to this, it's worthy of hearing it again. They're not going to be able to go and jump right into the book and find it. So I think it's worth you reading it one more time. Should have had you earmarked last time. All right, let it rip, Paul. Here we go. This will take us out.  Yes, too late have I come to love you.  I, my ugliness, rushed headlong into the things of beauty you had made. You were with me, but I was not with you. The things you had created kept me far from you, yet if they had not been in you, they would not have been at all. You called to me and cried aloud and you broke through my deafness. You flashed and shone and chased away my blindness. You breathed upon me frequently. I drew in my breath and now I pant for you. I tasted and now I hunger and thirst for you. You touched me and I burned to enjoy your peace. This has been an episode of The Spiritual Masters, a podcast from Tan Books and Tan Direction. To follow the show, learn about more inspiring holy men and women, and to get special offers exclusive to Spiritual Masters listeners, sign up at SpiritualMastersPodcast.com and thanks for listening.


Yes, welcome back to entrepreneurship Tuesday special. Thanks to Alex for that informative interview and doing something for the environment remember we have a question on Facebook and The question is are you preparing for your retirement as we learned earlier? You can retire 31 you can retire 35 you can retire 40 you can retire 20 It depends on what you do to secure your retirement So that is a question that we're looking for to your feedback so we can sample them towards the end of this But right about now it's time For another interview and I have the pleasure to introduce to you the Miss United Nations Kenya And she's going to be representing Kenya in India for the global Competition Karibu San All right, your camera is number four Jill Just a give them a brief intro of Jill Good morning everyone who is watching just look them straight into the eyes. Okay. My name is Kanel Jill Otago I'm 23 years old, but 9 is at 24 December so I'm old. I'm from Migori County, Coabado and Currently I'm Miss United Nations Kenya. I'll be Glad to represent or rather to fly our country's flag out there In India, I'll be I should be flying out on Friday.  Yes I'm done with the 8th or 4th. I'm awaiting graduation. I Was doing a bachelor in education arts. So a lithography at Jaramogi University in Boundo. So this notion about People from your area not knowing Swahili is a misconception. I did When did your passion for modeling begin? Mine isn't wasn't really in one. It's not something I really aspired to do But after completing my phone for I found Why if you know what that means make a corner So being seen and told my friends my friends are going to teach you.  Mm-hmm. It was just a push from close friends And I tried and then it became a part of a part of me It's something I live to do each and every day. It's like a career to me now All right, I tell modeling to a lot of self-confidence self-awareness Physical beauty.  I Won't really say I was born shy But then again these industries built me because along the way there are challenges There are difficult times.  Mm-hmm. Yeah. All right, wonderful In my life, I've never seen me like this You know the song We are living in a world where more and more women are bleaching. Yeah, that's a fact and we have been trained to think Light is beautiful The lighter the skin the more beautiful the woman.   What to do is give them a cold shoulder Because the moment you show them that you really care what their words heart you get hurt in the process So I learned to live with it. They could I could also joke about it with them as they joke We laugh together. All right.  I Followed that more often they gave you more spirit and more energy. Yeah, all right. Do you feel like? No other skin would have worked Do you feel like this was the right skin that you were supposed to play around with these phone apps? And I look at myself brown and I'm like Are you doing anything to put that confidence? In other girls who are ducks. Yeah, I I actually have a modeling agency Gea model. I hope you have a branch in me gory. Yeah, of course Because I believe that the people in me gory look up to me more modeling in me gory is not really strong So unless you go out there, you can't make it So I'm trying to bring it to their doorstep and especially encouraging the dark women I use the term black women because I need people to embrace the Black nature of it. Yes. And the different shades of that is the shades of black.  So that's why wherever I go, too I make sure I'm very I look very beautiful in that In the dress and from the minimalistic bag of I see and the jewelry I see that you're rocking some African inspired jewelry as well. Yeah, is this something that you do on the regular? And is this something you're going to do in India? Yeah being an African woman that I am It's something I I live up to each and every day that I wake up Minimal makeup, of course I wouldn't want that should disappear because it is my confidence Where that's my learning that it's the first clothes I put on each day I wake up for any other clothes. All right Every time I move around people ask me, are you just in Bieber? Do they compare you to Lupita? Several times. Several times. I actually look up to getting to where she is if not meeting her, but at least Get to where she is. Get to where she is. For sure. We have seen the likes of a Juma Doing a thing. We've seen Aduta Akesh now doing a thing Do you think they're setting the right precedence for young black girls from Africa like like you and the rest of them? Yeah, I'd say they inspire me. In fact Aduta is I guess younger than me, but she's she inspires me a lot Yeah, I look at her strut those runways meet those big people and I say just like So you know, Juma is limited All right, so for Juma, it's a literal runway for you. It's a figurative runway Yeah, but it's also a race because walking on hills each time is not easy. And who's in that confidence over time? With that big crowd, it's not easy. I'm about to ask you a very controversial question Yeah, and I'm sorry for putting you on the spot like this. No problem One day at a car All right, so Before do you think Africans are embracing this black beauty of the likes of a Juma and Aduta and Lupita because the white person embraced it in Hollywood row in a runway somewhere in Paris or in Europe Do you think the black people are starting to embrace it because white people embraced it first, you know According to my Opinion, it's still a challenge in these African countries in as much as somebody will see a black girl and tell her I love your skin.  Yeah, people are embracing it But it's still a challenge. It's still a challenge. All right. How did you get to be the person who's going to be representing Kenya in? in India for Miss United Nation There was an online registration registration But then it's Africa models that own the franchise. Yeah, it's called Africa models So I should sign too. Yeah. Yeah, so we were picked online Photos were sent through that agency. We were not dealing with them directly So through the agency we were selected a few models then we went for bootcamp in the race alarm So in the rest alarm only one winner was picked. All right. Yeah, because The front franchise is for the entire Africa for entire figure. Yeah So when we went to the rest alarm, we met as African countries. So we were finding It's representative from each country had to be so it was stiff there Yeah, it was stiff in Kenya and still stiff over there Yeah, but you met the winner and you're going to be representing us. So you're representing Africa, okay? I'm representing Kenya. You're representing Kenya. Yeah in India and you're flying on Friday on Friday All right. So what were some of the requirements apart from the pictures? What else was required for you to enter this competition so that somebody can enter next year at least? After submitting, of course, they are professional pictures. You are selling yourself with the Using through the photos.  What's attached to that when you become the Miss United Nations? What would you want to give back to the people? So through the project that was submitted, they were able to know Who is who and then of course the agency came in handy when we went for the bootcamp At least they had to spend time with us. They could know people watch your behavior What was your project about I'm interested in your project because it's very dear to to to both sexes Yeah, I'll give up for the first time at least I'll give a brief about it. But majorly I was I'm normally moved when I look at the boy child because nowadays in as much as I'm a girl child But most of the projects gear towards the girl child, you know, the boy child has been sidelined They go through they suffer from things that they don't talk about because boy child My face is lightening when you speak They go through depressions that no one Is able to help them through at the long run they fall into drug Addictions So, you know when there's no need coming to the news and telling us that somebody committed suicide yet There is a real solution to this problem So how about if we indulge the boy child towards coming these problems that we claim the girl child goes through How about we include the boy child, you know, while organizing those Projects or for the girls for the girl child We include the boy child and let them know that these and these and these are what Supposed to be done and we would like you to help, you know, they'll also do it from their heart And understand what the girl child is going through what the girl child is really going through and why in the process Yeah, all right and why is much attention Given to the girl child, you know, they want to feel left out. All right. Wonderful. Is this what you Preparing to to push and present when you get to India as well Yeah, okay Considering my country is suffering from that um It's not something I'll go with globally because the same problem probably is not affecting the other Also, it needs to be a problem that the world understands Kind of affects the world but still affects Kenya as well. So my global project is majorly on the environment the global warming Yeah, I'm trying to come up with some of the Possible ways in which we can help cap this global warming because currently it affects People globally. Yes, and we are facing the effects as we speak. There's flooding in the country as we speak We just had a firm in in the country. It's affecting everyone There's a lot of pollution in the river just next to us right here Not so far from where we are And this is a problem for sure all the best in India. Just remind them your social media handle So they can interact with you and support you whenever you need it Yeah, so About that. I love to say come in it or so There is a Amani sasa foundation. I'm not sure that you've heard about it. But there is Amani sasa foundation Kenya Uh, I'm the secretary there and uh, I must be a header on that So there is an event coming up for Mr and Ms face of Amani sasa foundation Kenya We need a face that will be representing Amani sasa foundation. There is Ms face of devolution Kenya coming up Then there is gia models recruiting new faces. So feel free to contact us our social media handles at instagram There is gia models africa Gia models underscore africa. There is canal gel canal underscore gel There is miss face of devolution Kenya You can find us on instagram and then don't forget to use the hashtag Amani sasa foundation Kenya. All right. Thank you Uh, thank you very much for that. Thank you for sharing that. There's a question from one of our viewers And always, uh, where do you teach geography and swahili? So I will let him to talk Uh, currently I'm a teacher by profession. Yes, but I'm currently a teacher on a different field They don't teach in a traditional school. I teach using heels in those chalk All right. It's not a traditional school, but you still teach and they can find you on social media Uh, just give them that handle again your personal canal gel Canal underscore gel canal underscore gel canal k-e-r-n-e-l underscore gel j-i-w-l Yes, from y in the morning all the best in india. Thank you so much and fly the canon flag. Thank you All right, we've come to the end of this particular show Of the day and to everyone who has sent their answers our way We appreciate you so much even though we are not going to sample them right now We are going to be replying to them for sure on our facebook That is at white 54 on facebook white 54 underscore channel on instagram and white 54 channel on twitter Keep interacting with us even after the end after the end of the show because tomorrow We are still on with queens. Wednesday. You don't go nowhere. Don't take that down. My name is by mosses. It's by bone social media


So, right now we can only select answer must be text or can it be multiple choices also and I mean like for example, it is not a multiple choice answer, it is only the text answer, but we can have the multiple answers for the particular question user can if we are provided with the one answer as a default and user come again and if user feels like that this answer could be improved more then he can or she can provide more inputs or they can submit the answer. Other user can do one thing they can create this particular answer if the particular answer has a higher rating than any other answer it will come up on the top of the list that is the default first answer. This is like in a pipeline we can create this particular end for the person who it will come up in the like a leadership board. So, that particular user get the ranking over there if the user like someone like a someone give the answer for the five different question and get the rating like a plus one for the each one in total rating is a five and someone is a come up with only two answer, but they get the rating like three plus three total six. So, here will be on the leadership board here will be on the top as compared to Samarth. This is the idea behind this particular end. So, that anyone can enhance his or her interval and improve the technical knowledge.