ĐĎॹá>ţ˙ Z\ţ˙˙˙Y˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙ěĽÁ7 đżü?bjbjUU b7|7|ü;˙˙˙˙˙˙l¨¨¨¨¨¨¨źĆĆĆĆ Ňlź**J J J J J J J J ”)–)–)–)–)–)–)$?+ _-Xş)¨J J J J J ş)l&¨¨J J Ď)l&l&l&J "¨J ¨J ”)l&J ”)l&l&€)¨¨€)J >  ‚vaĹź Ćl&€)€)ĺ)0*€)ˇ-l&ˇ-€)l&źź¨¨¨¨ŮRecursion Mathematically, a recursive function is one that is defined in terms of other values of that same function. A couple (overused) examples are as follows: Fibonacci numbers: F(0)=0, F(1)=1, F(n) = F(n-1)+F(n-2), for all n>1. (F is defined for all non-negative integers here.) Factorials: Fact(0) = 1, Fact(n)=n*Fact(n-1), for all n>0. (Fact is also defined for all non-negative integers.) Analogously, a recursive method is one where the method body contains a call to the method itself. (Remember, each instance a method is called, the computer allocates some memory for THAT instance to run. There is no reason why two DIFFERENT instances of the same method can not be in the middle of running at the same time.) You have seen recursion in CS1. Probably most of the recursion you saw in that class was straightforward, such as implementing the two functions listed above. In this class we will look at more complicated recursive algorithms. Incidentally, here are Java methods that compute the two recursive functions listed above: public static int Fib(int n) { if (n<2) return n; else return Fib(n-1)+Fib(n-2); } public static int Fact(int n) { if (n ==0) return 1; else return n*Fact(n-1); { What would make both of these methods more robust? What problem becomes more probable with recursion? When dealing with recursion, there are essentially two issues to tackle: 1) How to trace through recursive code. 2) How to write recursive code. Tracing through recursion Clearly, the first is easier than the second, and you can't do the second if you can't do the first. So, let's talk about tracing through recursion first. Really, there are no NEW rules to use when tracing through recursion, as compared to tracing through code that has method calls. Anytime a new method is called, you checkpoint and STOP running the calling method, and start executing the callee method. When the callee has terminated, it returns a value to the caller, and then the caller continues execution EXACTLY where it left off. The stack trace illustration your CS1 book uses is a fairly good model to use when tracing recursion. I often explain a trace using a physical stack of papers, where each paper is allowed to keep track of one method call. Let's trace through a couple simple examples of the two functions above. Writing recursion The toughest part with writing a recusive method ISN'T coding the method. Rather, the most difficult part is coming up with the recursive algorithm to solve the problem. Once you come up with the idea for the algorithm, the actual code is not so difficult to write. (As you can see, the mathematical definition of both fibonacci and factorial look amazingly similar to the code. Once you can get this mathematical definition, the code is not far off.) The most difficult part of creating a recursive algorithm is finding a way to solve the given problem that involves a solution to a problem of the exact same nature. In both the Fibonacci and Factorial examples, the functions themeselves are defined recursively, so we don't have that problem. Here is a problem you were probably shown in CS1 that is not typically defined recursively: Find the sum 1+2+3+...+n. You probably did a for loop in a function to find this sum in CS1. Then, in order to come up with a recursive solution, you first had to think of a mathematical way to express the function above, recursively. The big key is that 1+2+3+... = n + (1+2+3...+n-1) Thus, if we let s(n)=1+2+3+...+n, then we can derive that s(n) = n + s(n-1), for all n>1, s(1)=1. Now using the information above, the recursive method that computes the function s above is apparent. Once you have found a recursive algorithm to solve a problem, there is one other main issue to consider before coding a recursive method: For what values should the recursive algorithm be executed, and for what values should it NOT be executed, because the value to return can be easily computed? This is known as the terminating condition. All recursive methods have to have a terminating condition in some shape or form. If they didn't, you would get infinite recursion. (This is very similar to an infinite loop.) There are two basic constructs that most recursive methods take. Here they are: if (terminating condition) finish task else solve problem recursively if (not terminating condition) solve problem recursively One other way to view coding a recursive problem is the following: Imagine that you have been asked to write a method, but that someone else has already written the method and you are allowed to make as many calls to THAT method that you want to, as long as you don't pass it the same parameters that have been passed to you. Thus, when computing Fact(n), for example, instead of doing all that multiplying yourself, you call the function your friend has written to calculate Fact(n-1). When he/she returns that answer to you, all you have to do to finish your job is multiply that answer by n and you are done!!! Recursive Binary Search Here the key is that we have two terminating conditions: having no search space, and if the middle element is the target. After that, based on our comparison with the middle element, we can make one of two recursive calls for a search in either the lower or upper half of the array. public static boolean search(int [] vals, int low, int high, int t) { if (low > high) return false; int mid = (low+high)/2; if (vals[mid] == t) return true; else if (vals[mid] < t) return search(vals, mid+1, high, t); else return search(vals, low, mid-1, t); } Minesweeper - Recursive Clear Minesweeper is the popular game included with windows where the player has to determine the location of hidden bombs in a rectangular grid. Initially, each square on the grid is uncovered. When you uncover a square, one of three things can happen: 1) A bomb is at that square and you blow up and lose. 2) A number appears, signifying the number of bombs in adjacent squares. 3) The square is empty, signifying that there are no adjacent bombs. In the real minesweeper, when step 3 occurs, all of the adjacent squares are automatically cleared for you, since it's obviously safe to do so. And then, if any of those are clear, all of those adjacent squares are cleared, etc. Step 3 is recursive, since you apply the same set of steps to clear each adjacent square to a square with a "0" in it. I am going to simplify the code for this a bit so that we can focus on the recursive part of it. (I will replace some code with comments that simply signify what should be done in that portion of code.) The key here is ONLY if we clear a square and find 0 bombs adjacent to it do we make a recursive call. Furthermore, we make SEVERAL recursive calls, potentially up to 8 of them. public boolean domove(int row, int col) { // Take care of losing move if (realboard[row][col] == "*") { ... } // Take care of case where you've already uncovered that sq. else if (board[row][col] != '_') { ... } // Normal case else { // Finds # of adjacent bombs. int num = numberbombs(row,col); totalmoves--; //keeps track of total moves left to win. board[row][col] = (char)(num+48); //Changes board // to indicate move // Handles recursive case if (num == 0) { for (int i=-1; i < 2; i++) { for (int j=-1; j < 2; j++) { if (valid(row+i,col+j) && board[row+i][col+j]=='_') domove(row+i,col+j); } } } return false; } } Introduction to Towers of Hanoi The story goes as follows: Some guy has this daunting task of moving this set of golden disks from one pole to another pole. There are three poles total and he can only move a single disk at a time. Furthermore, he can not place a larger disk on top of a smaller disk. Our guy, (some monk or something), has 64 disks to transfer. After playing this game for a while, you realize that he's got quite a task. In fact, he will have to make 264 - 1 moves total, at least. (I have no idea what this number is, but it's pretty big...) Although this won't directly help you code, it is instructive to determine the smallest number of moves possible to move these disks. First we notice the following: It takes one move to move a tower of one disk. For larger towers, one way we can solve the problem is as follows: 1) Move the subtower of n-1 disks from pole 1 to pole 3. 2) Move the bottom disk to pole 2. 3) Move the subtower of n-1 disks from pole 3 to pole 2. We can now use this method of solution to write a method that will print out all the moves necessary to transfer the contents of one pole to another. Here is the prototype for our method: public static void towers(int n, int start, int end); n is the number of disks being moved, start is the number of the pole the disks start on, and end is the number of the pole that the disks will get moved to. The poles are numbered 1 to 3. Here is the method: public static void towers(int n, int start, int end) { if (n > 0) { int mid = 6 - start - end; towers(n-1, start, mid); System.out.print("Move disk "+n+" from tower "); System.out.println(start+" to tower "+end+"."); towers(n-1,mid,end); } } Recursive Method to Print Out a Number in Any Base Given a decimal number, consider printing it out in another base. For the ease implementation, let's assume the base is 10 or less. (In the text they show a small work around that works for bases up to 16, that could be extended to even larger bases.) The basic idea is as follows: Given a decimal number D in base B, we can determine the following: 1) The least significant digit 2) The value of the leftover number 1) This is simply D%B. 2) What is leftover can be represented as D/B, using integer division. Thus, if we are given a number with more than one digit in base B, we solve the problem recursively as follows: 1) Print out the whole number, except for the last digit. 2) Print out the last digit. Note that #1 is the recursive part of the algorithm. In code, we have: public static void printInt(int n, int base) { if (n >= base) printInt(n/base, base); System.out.print(n%base); } Modular Exponentiation The modular exponentiating problem is calculating xn mod p. Note that the answer will always be in between 0 and p-1, inclusive. Here is the standard iterative solution: public static int modexp(int x, int n, int p) { int ans = 1; for (int i=0; i 0. public static int numOnes(int n);  É ä . A Á é ĹßBbŽ"Ď"…$‡$ˆ)ź)Ń,L-d-—-˜-..{/0‹1Ž1#2&2š2…3ó3ř388€88ť<ź<Ď<ˆ>í>??:?ű?ü?ű÷đ÷đ÷ę÷ű÷äŢű÷ÔĚÄĚşś÷°÷ş÷ş÷°÷°÷ş÷đ÷°÷°÷ĚÄĚş÷ĚÄĚ 5CJ H*5CJ$5CJ OJQJ^J5CJ$OJQJ5CJ OJQJ5CJ H*OJQJ 5CJ \ 5CJ(\ 5>*CJ 56CJ ]5CJ 5CJ(0  ¤Ľ¸š ,-’“˝ž:DPVrtu•Ą­łÉúúőőőőőőőőőóőóőőőőőőőőőőőőőő$a$$a$ü?ţÉËĚ˙2 3 | } Ľ Ĺ Ć Ç Č É ä ĺ €    * + , - . @ A úúúúúúúúúřřřřúúúúúúúúúúúúúúú$a$‰Š¤ĽvwŞäĺ tužŸ{|ĚÍčřý<Z[\úúúúúúúúúúúúúúúúúúúúúúúúúúúúú$a$\Ÿ Ł¤ÄĹŢßúűAVn‹¤ťŘ?ABabZ[‘Úúúúúúúőőúóóóóóóóóóóóóóőőúúúú$a$$a$Ú ~JKýţ˙,-Ms~„Ĺě÷ýţ  D n úúúúúřúúúřřřřřřřřřřřřřřřřřřř$a$n ° ě !!4!N!y!¨!ż!đ!%"&"V"k"{"‰"˘"Ź"Ž"Î"Ď"ŕ$á$†%‡%ś%ˇ%ú%ýýýýýýýýýýýýýýýýýýýřřóóóóóóó$a$$a$ú%ű%4&W&&’&N'O'…'†'C(W(X(((˘(Ç(ę(%)_)~)…)‡)ť)ź)¸*š*×*Ř*+úúúúúúúúúúúúúúúúúúúúúúúúúúúúú$a$++<+`+a+x+ż+Ŕ+0,1,k,ˆ,‰,Đ,Ń,----I-K-L-c-d-..?.@.O.i.úúúúúúúúúúúúúúúúúúúúőúúúúúúú$a$$a$i.~.Œ.Ž..I/J/z/{/Ť/Ź/ş/Č/Ű/ë/ň/000N0O0P091:1[1\1ˇ1¸1č1é1úúúúúúúúúúúúúúúúúúúúúúúúúúúúú$a$é122‡2ˆ2™2š2Ę2Ë2Ů2ç2ú2 3!3A3Y3]3d3ƒ3…3†3ť3ź3q4r4+5,5e5f5š5úúúúúúúúúúúúúúúúúúúúúúúúúúúúú$a$š5›5ą5˛5'7(7]7^7‰7Š7Ÿ7ż7ć7ó78c8¨8Š899é9ę9::7:N:e:i:ƒ:´:úúúúúúúúúúúúúúúúúúúúúúúúúúúúú$a$´:ľ:Ö:;;€;;°;ą;Ĺ;Ć;Ź<­<ş<ť<ź<Ď<j=k={=|=š=ş=Í=Î=Ü=Ý=4>5>úúúúúúúúúúúúúúúőóóóóóóóóóóóó$a$$a$5>‡>ˆ>Ž>Ż>˝>Ë>Ň>ę>ě>í>??:?;?ż?Ŕ?Ř?ú?ű?ü?ýýýýýýýýýýýřóřřřřřřř$a$$a$°Đ/ °ŕ=!°"°# $ %° i8@ń˙8 NormalCJ_HaJmH sH tH <A@ň˙Ą< Default Paragraph Fontü;b ˙˙˙˙ ¤Ľ¸š ,-’“˝ž:DPVrtu•Ą­łÉËĚ˙23|}ĽĹĆÇČÉä倁* + , - . @ A    ‰ Š ¤ Ľ v w Ş ä ĺ tužŸ{|ĚÍčřý<Z[\Ÿ Ł¤ÄĹŢßúűAVn‹¤ťŘ?ABabZ[‘Ú ~JKýţ˙,-Ms~„Ĺě÷ýţDn°ě4Ny¨żđ%&Vk{‰˘ŹŽÎĎŕ á †!‡!ś!ˇ!ú!ű!4"W""’"N#O#…#†#C$W$X$$$˘$Ç$ę$%%_%~%…%‡%ť%ź%¸&š&×&Ř&''<'`'a'x'ż'Ŕ'0(1(k(ˆ(‰(Đ(Ń())-)I)K)L)c)d)**?*@*O*i*~*Œ*Ž**I+J+z+{+Ť+Ź+ş+Č+Ű+ë+ň+,,,N,O,P,9-:-[-\-ˇ-¸-č-é-..‡.ˆ.™.š.Ę.Ë.Ů.ç.ú. /!/A/Y/]/d/ƒ/…/†/ť/ź/q0r0+1,1e1f1š1›1ą1˛1'3(3]3^3‰3Š3Ÿ3ż3ć3ó34c4¨4Š455é5ę56676N6e6i6ƒ6´6ľ6Ö677€77°7ą7Ĺ7Ć7Ź8­8ş8ť8ź8Ď8j9k9{9|9š9ş9Í9Î9Ü9Ý94:5:‡:ˆ:Ž:Ż:˝:Ë:Ň:ę:ě:í:;;:;;;ż;Ŕ;Ř;ú;ű;ţ;˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜@0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜@0€€˜@0€€˜@0€€˜@0€€˜@0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜@0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€š0€€˜0€€š0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€ü?"É\Ún ú%+i.é1š5´:5>ü?#%&'()*+,-./0ü?$ĽŽô÷),14ƒ†Œnt†Œ%(b j € ‰ š  é ô Z ] ă ć #%(.18;sv~†”˜ÉÍđôöű)- !$%(U^dgÝŕNQXcdkx‚ĹČÓŮadefklrs“ßęAGHS""c"k"i#l#p#s#{#~#r$u$y$|$„$‡$Ź$Ż$ô$%/%A%r%{%s'v'ä(ě(í(đ(ô(÷())/)?)@)F)p)~)–)˜)* *!*'*(*+*/*2*6*9*B*E*F*I*V*Y*Z*[*_*`*d*e*m*p*t*w*‡*Š*ő*ů*++‰+Œ++“+”+—+›+ž+˘+Ľ+ć+é+,,, ,Š-Œ-".$.¨.Ť.Ź.˛.ł.ś.ş.˝.Á.Ä.//%/(/0/6/7/:/Q/W/q/w/x/{/n4p4ž5Ă5ľ6¸6ů6ű67‘788D9G9::':*:V:Y:–:™:š::ž:Ą:Ľ:¨:Ý:ŕ:ä:ç:ć;é;ę;ń;ň;ő;ţ;˙˙dmarino1C:\arup\COP3503\Spring03\Lectures\Recursion01.docdmarinofC:\Documents and Settings\dmarino\Application Data\Microsoft\Word\AutoRecovery save of Recursion01.asddmarinofC:\Documents and Settings\dmarino\Application Data\Microsoft\Word\AutoRecovery save of Recursion01.asddmarinofC:\Documents and Settings\dmarino\Application Data\Microsoft\Word\AutoRecovery save of Recursion01.asdű;ţ;Ý˙@€K)K)Č}K)K)ü;€@˙˙Unknown˙˙˙˙˙˙˙˙˙˙˙˙G‡z €˙Times New Roman5€Symbol3& ‡z €˙Arial3‡z €˙Times?5 ‡z €˙Courier New"qˆđĐhƒŠr&‡Ě•fj­v1i!đ ´´0˝<b)2ƒQđ˙˙ Recursiondmarinodmarinoţ˙ŕ…ŸňůOhŤ‘+'łŮ0p˜Ź¸ČÔŕô  , 8 DPX`hä Recursion ecudmarinomarmar Normal.dotdmarino6arMicrosoft Word 9.0@üÚÎ@GÖÂ@ZÖvaĹ­v1ţ˙ŐÍ՜.“—+,ůŽ0  hp˜ ¨° ¸ŔČĐ Ř îäUniversity of Central Floridaai˝<   Recursion Title  !"#$%&'()*+,-./01ţ˙˙˙3456789:;<=>?@ABCDEFGHţ˙˙˙JKLMNOPţ˙˙˙RSTUVWXţ˙˙˙ý˙˙˙[ţ˙˙˙ţ˙˙˙ţ˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙Root Entry˙˙˙˙˙˙˙˙ ŔF0.#vaĹ]€1Table˙˙˙˙˙˙˙˙˙˙˙˙2ˇ-WordDocument˙˙˙˙˙˙˙˙bSummaryInformation(˙˙˙˙IDocumentSummaryInformation8˙˙˙˙˙˙˙˙˙˙˙˙QCompObj˙˙˙˙jObjectPool˙˙˙˙˙˙˙˙˙˙˙˙0.#vaĹ0.#vaĹ˙˙˙˙˙˙˙˙˙˙˙˙ţ˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙˙ţ˙ ˙˙˙˙ ŔFMicrosoft Word Document MSWordDocWord.Document.8ô9˛q