(************** Content-type: application/mathematica ************** CreatedBy='Mathematica 5.0' Mathematica-Compatible Notebook This notebook can be used with any Mathematica-compatible application, such as Mathematica, MathReader or Publicon. The data for the notebook starts with the line containing stars above. To get the notebook into a Mathematica-compatible application, do one of the following: * Save the data starting with the line of stars above into a file with a name ending in .nb, then open the file inside the application; * Copy the data starting with the line of stars above to the clipboard, then use the Paste menu command inside the application. Data for notebooks contains only printable 7-bit ASCII and can be sent directly in email or through ftp in text mode. Newlines can be CR, LF or CRLF (Unix, Macintosh or MS-DOS style). NOTE: If you modify the data for this notebook not in a Mathematica- compatible application, you must delete the line below containing the word CacheID, otherwise Mathematica-compatible applications may try to use invalid cache data. For more information on notebooks and Mathematica-compatible applications, contact Wolfram Research: web: http://www.wolfram.com email: info@wolfram.com phone: +1-217-398-0700 (U.S.) Notebook reader applications are available free of charge from Wolfram Research. *******************************************************************) (*CacheID: 232*) (*NotebookFileLineBreakTest NotebookFileLineBreakTest*) (*NotebookOptionsPosition[ 134621, 4397]*) (*NotebookOutlinePosition[ 141978, 4663]*) (* CellTagsIndexPosition[ 140693, 4610]*) (*WindowFrame->Normal*) Notebook[{ Cell["\[Copyright] 20042 K. Sutner ", "SmallText"], Cell[CellGroupData[{ Cell["Recursion", "Title", Evaluatable->False, AspectRatioFixed->True, CellTags->"c:1"], Cell[CellGroupData[{ Cell["Recursive Programs", "Section", Evaluatable->False, AspectRatioFixed->True, CellTags->"c:2"], Cell["\<\ Recursion is another general principle that can be used in many \ cases to attack computational problems. Recursion is very closely related to \ iteration, but there are differences. In iteration, we apply the same \ function over and over, until the desired output emerges, often in the form \ of a fixed point. In recursion, functions are calling themselves. Of \ course, the recursive calls must be on different input, and there must be \ some condition that terminates the recursion. In practice, whenever you construct a recursive function, the very first \ thing you should think about is the exit condition: when does the recursion \ stop? Then worry about the recursive call(s). \ \>", "Text", Evaluatable->False, AspectRatioFixed->True], Cell[CellGroupData[{ Cell[TextData[{ " The Standard Example: ", Cell[BoxData[ \(TraditionalForm\`n\)]], " factorial. " }], "Subsection", Evaluatable->False, AspectRatioFixed->True, CellTags->"c:3"], Cell[TextData[{ StyleBox["Here is the mandatory standard example: the factorial function. \ The basic equations for the factorial function are\n (1) ", FontFamily->"Times"], Cell[BoxData[ \(TraditionalForm\`f(0)\ = \ 1\)]], ", ", StyleBox["\n (2) ", FontFamily->"Times"], Cell[BoxData[ \(TraditionalForm\`f(n)\ = \ n\ \[CenterDot]\ \(f(n - 1)\)\)]], StyleBox[" for all ", FontFamily->"Times"], Cell[BoxData[ \(TraditionalForm\`n\ > \ 0\)]], StyleBox[". \nThe first equation is our exit condition, the second \ describes the recursive call. \n\nWe can easily translate this into \ Mathematica code. ", FontFamily->"Times"] }], "Text", Evaluatable->False, AspectRatioFixed->True], Cell["\<\ Clear[fac] fac[0] := 1; fac[n_] := n fac[n-1];\ \>", "Input", AspectRatioFixed->True], Cell[BoxData[ \(fac[10]\)], "Input", AspectRatioFixed->True], Cell[TextData[{ "We can get an idea of the internal activity by using the ", StyleBox["Trace", "SmallText"], " function. \n\n", StyleBox["WARNING", FontWeight->"Bold", FontColor->RGBColor[1, 0, 0]], "\n", StyleBox["Trace", "SmallText"], " can produce huge amounts of output, look up help and use it additional \ constraints like the one below to limit the output. " }], "Text", Evaluatable->False, AspectRatioFixed->True], Cell[BoxData[ \(Trace[\ fac[10], fac[_]\ ]\)], "Input", AspectRatioFixed->True], Cell[TextData[{ "Note that ", StyleBox["Trace", "SmallText"], " returns a deeply nested expression, the nesting structure represent the \ nested recursive calls. Unfortunately, this output is somewhat difficult to \ read for humans. You may be better off ", StyleBox["Flatten", "SmallText"], "'ing it. " }], "Text", Evaluatable->False, AspectRatioFixed->True], Cell[BoxData[ \(Flatten[Trace[fac[10], fac[_]]]\)], "Input", AspectRatioFixed->True], Cell[TextData[StyleBox["Again, in order for a recursively defined function to \ work properly, two conditions must be met:\n\t(1) There has to be an exit \ condition: for some inputs the computation must terminate rather than to \ produce more recursive calls. \n\t(2) Every input must ultimately lead to \ the exit condition: we cannot have an infinite sequence of calls that always \ misses the exit condition. Most notably, this happens when you type by \ accident something like ", FontFamily->"Times"]], "Text", Evaluatable->False, AspectRatioFixed->True], Cell[TextData[StyleBox["\tf[n_] := .... f[n] .....", "SmallText"]], "Text", Evaluatable->False, AspectRatioFixed->True], Cell[TextData[StyleBox["In general, these conditions are actually very hard \ to check, but in simple cases there is no problem.", FontFamily->"Times"]], "Text", Evaluatable->False, AspectRatioFixed->True], Cell[TextData[{ "For the factorial function, e.g., we have\n\n\tExit condition: ", Cell[BoxData[ \(TraditionalForm\`\(\(\ \)\(n\ = \ 0\)\)\)]], "\n\tRecursive call: ", Cell[BoxData[ \(TraditionalForm\`n\ \[DoubleLongRightArrow]\ n - 1\)]], "\n\nClearly, any chain of calls starting at a non-negative integer will \ ultimately hit the exit condition and terminate. " }], "Text", Evaluatable->False, AspectRatioFixed->True] }, Closed]], Cell[CellGroupData[{ Cell[TextData[{ " The Strange Example: ", Cell[BoxData[ \(TraditionalForm\`n\^2\)]], " . " }], "Subsection", Evaluatable->False, AspectRatioFixed->True, CellTags->"c:4"], Cell[TextData[{ StyleBox["Squaring can obviously done without recursion, but we can \ rephrase it as a recursive process:\n (1) ", FontFamily->"Times"], Cell[BoxData[ \(TraditionalForm\`sq(0)\ = \ 0\)]], ", ", StyleBox["\n (2) ", FontFamily->"Times"], Cell[BoxData[ \(TraditionalForm\`sq(n)\ = \ \ sq(n - 1)\ + \ 2 \((n - 1)\)\ + \ 1\)]], StyleBox[" for all ", FontFamily->"Times"], Cell[BoxData[ \(TraditionalForm\`n\ > \ 0\)]], StyleBox[". \nRight? ", FontFamily->"Times"] }], "Text", Evaluatable->False, AspectRatioFixed->True], Cell[BoxData[{ \(Clear[sq]\), "\n", \(\(sq[0] = 0;\)\), "\n", \(\(sq[n_] := sq[n - 1]\ + \ 2 \((n - 1)\)\ + \ 1;\)\)}], "Input", AspectRatioFixed->True], Cell["sq[5]", "Input"], Cell["The trace is essentially the same as in the last example. ", "Text"], Cell[BoxData[ \(Trace[sq[10], sq[_]]\ // \ Flatten\)], "Input", AspectRatioFixed->True] }, Closed]], Cell[CellGroupData[{ Cell[" Nest and nest", "Subsection", Evaluatable->False, AspectRatioFixed->True, CellTags->"c:5"], Cell[TextData[{ "Recall the axioms for ", StyleBox["Nest", "SmallText"], " from the last notebook.\n(1) \t", StyleBox["Nest[ f, a, 0 ] = a", "SmallText"], ",\n(2) \t", StyleBox["Nest[ f, a, t+1 ] = f[ Nest[ f, a, t ] ]", "SmallText"], "." }], "Text", Evaluatable->False, AspectRatioFixed->True], Cell[TextData[{ "If we think of these equations not as assertions, but as a recursive \ definition, we can easily build our own mock-up of Nest. The exit condition \ fires when the third parameter is 0, and the recursive call is again of the \ type ", Cell[BoxData[ \(TraditionalForm\`t + 1\ \[DoubleLongRightArrow]\ t\)]], ". Note that we have to change this to ", Cell[BoxData[ \(TraditionalForm\`t\ \[DoubleLongRightArrow]\ t - 1\)]], ", since Mathematica cannot cope with a term such t+1 on the formal \ paramter list in a function definition. (It is not a syntax error, but given \ a numerical value such as ", Cell[BoxData[ \(TraditionalForm\`\(\(\ \)\(t\ = \ 10\)\)\)]], " , Mathematica will not rewrite it in the form 9 + 1, and the function \ will not evaluate). " }], "Text", Evaluatable->False, AspectRatioFixed->True], Cell[BoxData[{ \(Clear[nest, f, a]\), "\n", \(\(nest[f_, a_, 0] := a;\)\), "\n", \(\(nest[f_, a_, t_] := f[nest[f, a, t - 1]];\)\)}], "Input", AspectRatioFixed->True], Cell[BoxData[{ \(nest[f, a, 0]\), "\n", \(nest[f, a, 10]\), "\n", \(% == Nest[f, a, 10]\)}], "Input", AspectRatioFixed->True], Cell[TextData[{ "We can also implement our own version of ", StyleBox["NestList", "SmallText"], " in this way. To avoid horrible inefficiency, we use a With-construct \ rather than retyping the second axiom verbatim. " }], "Text", Evaluatable->False, AspectRatioFixed->True], Cell[BoxData[{ \(Clear[nestList]\), "\n", \(\(nestList[f_, a_, 0] := {a};\)\), "\n", \(\(nestList[f_, a_, t_] := With[{L = nestList[f, a, t - 1]}, Append[L, f[Last[L]]]];\)\)}], "Input", AspectRatioFixed->True], Cell[BoxData[ \(nestList[f, a, 5]\)], "Input", AspectRatioFixed->True] }, Closed]], Cell[CellGroupData[{ Cell[" Radix Representation", "Subsection", Evaluatable->False, AspectRatioFixed->True, CellTags->"c:6"], Cell[TextData[{ StyleBox["We already have two methods to calculate the digits in the radix \ representation of an integer, one using a traditional while-loop and the \ other using iteration and fixed points. However, the perhaps most natural \ approach uses recursion. \nThe idea is that for ", FontFamily->"Times"], Cell[BoxData[ \(TraditionalForm\`0\ \[LessEqual] \ n\ < \ b\)]], StyleBox[", where", FontFamily->"Times"], StyleBox[" ", FontFamily->"Times", FontWeight->"Bold"], Cell[BoxData[ \(TraditionalForm\`b\)]], StyleBox[" is the base, there is nothing to do: the expansion is simply ", FontFamily->"Times"], Cell[BoxData[ \(TraditionalForm\`{n}\)]], StyleBox[" in this case. Otherwise, we determine the last digit, and use a \ recursive call to get the remaining digits.", FontFamily->"Times"] }], "Text", Evaluatable->False, AspectRatioFixed->True], Cell["\<\ Clear[integerDigits] integerDigits[n_,b_] := {n} /; n", "Input", AspectRatioFixed->True], Cell[TextData[{ StyleBox["Note the condition in the first part of the function definition: \ it can be applied only when ", FontFamily->"Times"], Cell[BoxData[ \(TraditionalForm\`n\)]], StyleBox[" is less than ", FontFamily->"Times"], Cell[BoxData[ \(TraditionalForm\`b\)]], StyleBox[". ", FontFamily->"Times"] }], "Text", Evaluatable->False, AspectRatioFixed->True], Cell[BoxData[{ \(integerDigits[10025, 2]\), "\n", \(integerDigits[10025, 10]\), "\n", \(integerDigits[10025, 17]\)}], "Input", AspectRatioFixed->True], Cell[BoxData[ \(TableForm[ Flatten[Trace[integerDigits[10025, 17], integerDigits[__]]]]\)], "Input",\ AspectRatioFixed->True], Cell["\<\ Compare this solution to our previous iterative method, it is very \ similar but perhaps slightly more natural. The point here is that the \ recursion hides the list of digits, we don't have to bother to implement it \ quite as explicitely as in the iterative method. Of course, there is a price \ one has to pay for this convenience: recursion is slightly harder to \ implement than iteration.\ \>", "Text", Evaluatable->False, AspectRatioFixed->True] }, Closed]], Cell[CellGroupData[{ Cell[" Foos and Bags", "Subsection", Evaluatable->False, AspectRatioFixed->True, CellTags->"c:7"], Cell[CellGroupData[{ Cell[" foo", "Subsubsection", Evaluatable->False, AspectRatioFixed->True, CellTags->"c:8"], Cell[TextData[{ StyleBox["Here is an example of a recursive function where the recursive \ call is not to ", FontFamily->"Times"], Cell[BoxData[ \(TraditionalForm\`n - 1\)]], StyleBox[", but to ", FontFamily->"Times"], Cell[BoxData[ \(TraditionalForm\`n/2\)]], StyleBox[". We have to take floors in case ", FontFamily->"Times"], Cell[BoxData[ \(TraditionalForm\`n\)]], StyleBox[" is odd.", FontFamily->"Times"] }], "Text", Evaluatable->False, AspectRatioFixed->True], Cell["\<\ Clear[foo] foo[1] = 0; foo[n_] := foo[Floor[n/2]] + 1;\ \>", "Input", AspectRatioFixed->True], Cell[BoxData[ \(foo[1000]\)], "Input", AspectRatioFixed->True], Cell[TextData[{ StyleBox["What does ", FontFamily->"Times"], StyleBox["foo", FontFamily->"Times", FontWeight->"Bold"], StyleBox[" do? Let's look at a few more values. ", FontFamily->"Times"] }], "Text", Evaluatable->False, AspectRatioFixed->True], Cell[BoxData[ \(val = Map[\ foo, Range[100]]\)], "Input", AspectRatioFixed->True], Cell[TextData[{ StyleBox["It seems that ", FontFamily->"Times"], StyleBox["foo", FontFamily->"Times", FontWeight->"Bold"], StyleBox[" is some kind of step function. A picture might help. ", FontFamily->"Times"] }], "Text", Evaluatable->False, AspectRatioFixed->True], Cell[BoxData[ \(\(ListPlot[val, PlotStyle \[Rule] Blue];\)\)], "Input", AspectRatioFixed->True], Cell[TextData[{ StyleBox["Now things should become fairly clear: the function jumps at \ certain places, namely powers of ", FontFamily->"Times"], Cell[BoxData[ \(TraditionalForm\`2\)]], StyleBox[". A little more thought reveals that \n\n ", FontFamily->"Times"], Cell[BoxData[ \(TraditionalForm\`\(\(\ \)\(foo(n) = \ k\)\)\)]], StyleBox[" ", FontFamily->"Times", FontWeight->"Bold"], StyleBox[" iff ", FontFamily->"Times"], StyleBox[" ", FontFamily->"Times", FontWeight->"Bold"], Cell[BoxData[ \(TraditionalForm\`2\^k \[LessEqual] \ n\ < \ 2\^\(k + 1\)\)]], StyleBox[". \n \nFor example", FontFamily->"Times"] }], "Text", Evaluatable->False, AspectRatioFixed->True], Cell[BoxData[ \(Select[Range[100], foo[#1] == 5 &]\)], "Input", AspectRatioFixed->True], Cell[TextData[{ "In other words, foo is really a discrete verision of the logarithm \ function: \n\n ", Cell[BoxData[ \(TraditionalForm\`foo( n)\ = \ \[LeftFloor]\ \(log\_2\) n\ \[RightFloor]\)]], ".\n\nOf course, it remains to prove that foo actually has this property. \ We'll postpone the proof. For the moment, a computational test will do. " }], "Text", Evaluatable->False, AspectRatioFixed->True], Cell[BoxData[ \(Map[\ foo[#] == Floor[N[Log[2, #]]] &, Range[100]]\)], "Input", AspectRatioFixed->True] }, Closed]], Cell[CellGroupData[{ Cell[" bag", "Subsubsection", Evaluatable->False, AspectRatioFixed->True, CellTags->"c:9"], Cell[TextData[{ StyleBox["Here is another strange function. Again, the recursive call is to \ ", FontFamily->"Times"], Cell[BoxData[ \(TraditionalForm\`n/2\)]], StyleBox[". Note that this is almost exactly the same function as foo. ", FontFamily->"Times"] }], "Text", Evaluatable->False, AspectRatioFixed->True], Cell["\<\ Clear[bag] bag[0] = 0; bag[n_] := bag[n/2] /; EvenQ[n]; bag[n_] := bag[(n - 1)/2] + 1;\ \>", "Input", AspectRatioFixed->True], Cell[BoxData[ \(bag[1000]\)], "Input", AspectRatioFixed->True], Cell[BoxData[ \(val = Map[\ bag, Range[200]]\)], "Input", AspectRatioFixed->True], Cell["However, the picture looks much more complicated than foo. ", "Text", Evaluatable->False, AspectRatioFixed->True], Cell[BoxData[ \(\(ListPlot[val];\)\)], "Input", AspectRatioFixed->True], Cell["\<\ Actually, this may look vaguely familiar. We've seen a similar \ picture before, when we computed digit sums, i.e., when we counted the number \ of 1's in the binary expansion of a number. \ \>", "Text", Evaluatable->False, AspectRatioFixed->True], Cell[BoxData[ \(\(DigitSum[n_] := Plus @@ IntegerDigits[n, 2];\)\)], "Input", AspectRatioFixed->True], Cell[BoxData[ \(DigitSum /@ Range[200]\)], "Input", AspectRatioFixed->True], Cell[BoxData[ \(val === %\)], "Input", AspectRatioFixed->True], Cell["\<\ Again, it remains to prove that bag actually has this property, and \ again we'll postpone the proof. Can you see what's going on, though?\ \>", \ "Text", Evaluatable->False, AspectRatioFixed->True] }, Closed]] }, Closed]], Cell[CellGroupData[{ Cell[" Multiple Recursive Calls", "Subsection", Evaluatable->False, AspectRatioFixed->True, CellTags->"c:10"], Cell[CellGroupData[{ Cell[" Fibonacci Numbers", "Subsubsection", Evaluatable->False, AspectRatioFixed->True, CellTags->"c:11"], Cell[TextData[{ "Our examples so far all had only one recursive call inside the function \ body. There is no reason, however, why one should not be able to have two or \ more calls. The case of two recursive calls is particularly frequent in \ practice. \n\nHere is a standard example: the Fibonacci numbers ", Cell[BoxData[ \(TraditionalForm\`F\_n\)]], ", ", Cell[BoxData[ \(TraditionalForm\`n\ \[GreaterEqual] \ 0\)]], ". These numbers are the sequence 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, and \ so on. In other words, ", Cell[BoxData[ \(TraditionalForm\`F\_0\ = \ 0\)]], ", ", Cell[BoxData[ \(TraditionalForm\`F\_1\ = \ 1\)]], ", and all other terms are obtained by adding the two previous ones. \n\nIt \ is straightforward to implement this sequence by recursion. " }], "Text", Evaluatable->False, AspectRatioFixed->True], Cell[BoxData[{ \(Clear[F]\), "\n", \(\(F[0] = 0;\)\), "\n", \(\(F[1] = 1;\)\), "\n", \(\(F[n_Integer] := F[n - 1] + F[n - 2];\)\)}], "Input", AspectRatioFixed->True], Cell[BoxData[ \(F /@ Range[0, 10]\)], "Input", AspectRatioFixed->True], Cell["\<\ Actually, this implementation is quite useless. The problem lies in \ the fact each recursive call tends to trigger 2 more, which trigger 4 more, 8 \ more, and so on. Moreover, many of these calls are made on the same value. \ Consider the following trace:\ \>", "Text", Evaluatable->False, AspectRatioFixed->True], Cell[BoxData[ \(tr\ = \ Flatten[Trace[F[11], F[_]]]\)], "Input", AspectRatioFixed->True], Cell[BoxData[ RowBox[{"Count", "[", RowBox[{"%", ",", TagBox[\(F[2]\), HoldForm]}], "]"}]], "Input", AspectRatioFixed->True], Cell[TextData[{ "There are 34 calls to ", StyleBox["F[2]", "SmallText"], " alone. Here is a table of all the call frequencies:" }], "Text", Evaluatable->False, AspectRatioFixed->True], Cell["tr // Frequencies // TableForm", "Input"], Cell["\<\ Last /@ Frequencies[tr] Plus@@%\ \>", "Input"], Cell["\<\ In order to avoid such re-computation, Mathematica has a mechanism \ to keep track of already computed values. It stores all known values of F \ internally in a so-called hash table, and when some value F[m] is requested, \ it first checks the table to see if it is already known. Otherwise, it makes \ recursive calls. \ \>", "Text", Evaluatable->False, AspectRatioFixed->True], Cell["\<\ Clear[F] F[0] = 0; F[1] = 1; F[n_Integer] := F[n] = F[n-1] + F[n-2];\ \>", "Input", AspectRatioFixed->True], Cell[BoxData[ \(Flatten[Trace[F[10], F[_]]]\)], "Input", AspectRatioFixed->True], Cell["\<\ Much better. All the known values of F are now stored, together \ with the general rule on how to compute more values if needed. \ \>", "Text", Evaluatable->False, AspectRatioFixed->True], Cell[BoxData[ \(Information["\", LongForm \[Rule] False]\)], "Input", AspectRatioFixed->True], Cell["\<\ If you want to compute large Fibonacci numbers, you will also have \ to change the recursion limit. By default, Mathematica only allows 256 nested \ calls. \ \>", "Text", Evaluatable->False, AspectRatioFixed->True], Cell[BoxData[{ \($RecursionLimit\), "\n", \($RecursionLimit = 1024\)}], "Input", AspectRatioFixed->True], Cell[BoxData[ \(Timing[F[500]]\)], "Input", AspectRatioFixed->True], Cell[TextData[{ StyleBox["WARNING", FontFamily->"Times", FontWeight->"Bold", FontColor->RGBColor[1, 0, 0]], "\nDo not use ", StyleBox["$RecursionLimit = Infinite ", "SmallText"], " unless you are absolutely certain you know what you are doing. The system \ may crash. " }], "Text", Evaluatable->False, AspectRatioFixed->True], Cell[TextData[{ StyleBox["Fibonacci numbers are and endless source of curious little facts. \ For example, we will show in the HW exercises that \n\n\t\t", FontFamily->"Times"], Cell[BoxData[ \(TraditionalForm\`F\_\(n + 1\)\%\(\(\ \)\(2\)\)\ - \ \(F\_n\) F\_\(n + 2\) = \ \((\(-1\))\)\^n\)]], ". \n", StyleBox["Here is a computational test. ", FontFamily->"Times"] }], "Text", Evaluatable->False, AspectRatioFixed->True], Cell[BoxData[ \(\((F[#1 + 1]\^2 - F[#1]\ F[#1 + 2] &)\) /@ Range[200]\)], "Input", AspectRatioFixed->True] }, Closed]], Cell[CellGroupData[{ Cell[" An Iterative Solution", "Subsubsection", Evaluatable->False, AspectRatioFixed->True, CellTags->"c:12"], Cell["\<\ Just for the record, there several other useful solutions to the \ problem of computing the Fibonacci numbers. One is by iteration.\ \>", "Text",\ Evaluatable->False, AspectRatioFixed->True], Cell[BoxData[{ \(Clear[F, fib]\), "\n", \(\(fib[{x_, y_}] := {y, x + y};\)\), "\n", \(F[n_Integer] := First[Nest[fib, {0, 1}, n]]\)}], "Input", AspectRatioFixed->True], Cell[BoxData[ \(F /@ Range[0, 10]\)], "Input", AspectRatioFixed->True], Cell[BoxData[ \(Timing[F[500]]\)], "Input", AspectRatioFixed->True], Cell["\<\ Note that this is very similar to our iterative approach to \ converting numbers to digits. The real work is done by iterating fib, but we \ need a little wrapper function to obtain a useable main function. As far as speed is concerned, the iterative method is faster than recursive \ one for the first call; after that the recursive method is superior because \ the valued remains stored in a table. However, you have to pay the price of \ storing a potentially very large table. So, there is a time/space trade-off. \ \>", "Text", Evaluatable->False, AspectRatioFixed->True] }, Closed]], Cell[CellGroupData[{ Cell[" Binomial Coefficients", "Subsubsection", Evaluatable->False, AspectRatioFixed->True, CellTags->"c:13"], Cell[TextData[{ "One more example of a double recursion that is very important. There is a \ built-in function ", StyleBox["Binomial[n,m]", "SmallText"], " that computes the so-called binomial coefficients. We will give a more \ detailed analysis of these numbers later, for the time being suffice it to \ say that you can think of ", StyleBox["Binomial[n,m]", "SmallText"], " as the coefficient of ", Cell[BoxData[ \(TraditionalForm\`a\^\(\(\ \)\(m\)\)\)]], " in the expansion of ", Cell[BoxData[ \(TraditionalForm\`\(\(\ \)\(\(\((a\ + \ b)\)\(\ \)\)\^n\)\)\)]], ", where ", Cell[BoxData[ \(TraditionalForm\`0\ \[LessEqual] \ m\ \[LessEqual] \ n\)]], ". " }], "Text", Evaluatable->False, AspectRatioFixed->True], Cell["\<\ Expand[(a + b)^5] Binomial[5, Range[0, 5] ]\ \>", "Input", AspectRatioFixed->True], Cell[TextData[{ "For our purposes, the important property of the binomials is that they \ have a recursive definition. Again we use the hashing trick to eliminate an \ exponential number of calls. The justification for the recursive definition \ is \n\t\t", Cell[BoxData[ \(TraditionalForm\`\(\(\ \)\(\(\((a\ + \ b)\)\(\ \)\)\^n\ = \ \ \ \(\(\(\((a\ + \ b)\)\(\ \)\)\^\(n - 1\)\) \((a + b)\)\ = \ \ \(\(\((a\ + \ b)\)\(\ \)\)\^\(n - 1\)\) a\ + \ \ \(\(\((a\ + \ b)\)\(\ \)\)\^\(n - 1\)\) b\)\)\)\)]], ".\n" }], "Text", Evaluatable->False, AspectRatioFixed->True], Cell[BoxData[{ \(\(Clear[bin];\)\), "\n", \(\(bin[0, 0] := 1;\)\), "\n", \(\(bin[0, _] := 0;\)\), "\n", \(\(bin[_, 0] := 1;\)\), "\n", \(\(bin[n_, m_] := \(bin[n, m] = bin[n - 1, m] + bin[n - 1, m - 1]\);\)\)}], "Input", AspectRatioFixed->True], Cell["\<\ Here is a table of the first few values of bin. Note the geometric \ interpretation of the recursion in the table. The leftmost column and the \ diagonal are all 1's. Above the diagonal there are only 0's, and any other \ entry is computed by adding the entry above and to the left one row up. \ \ \>", "Text", Evaluatable->False, AspectRatioFixed->True], Cell[BoxData[{ \(\(tab = Table[bin[m, n], {m, 0, 9}, {n, 0, 9}];\)\), "\n", \(TableForm[tab]\)}], "Input", AspectRatioFixed->True] }, Closed]], Cell[CellGroupData[{ Cell[" Differentiation of Polynomials. ", "Subsubsection", Evaluatable->False, AspectRatioFixed->True, CellTags->"c:14"], Cell[TextData[{ StyleBox["Here is an example from calculus: differentiation of polynomials. \ Suppose we only consider polynomials in a fixed variable ", FontFamily->"Times"], Cell[BoxData[ \(TraditionalForm\`x\)]], ". The rules for differentiation are ", StyleBox["\n (1) ", FontFamily->"Times"], Cell[BoxData[ \(TraditionalForm\`d(c)\ = \ 0\)]], ", for any constant ", Cell[BoxData[ \(TraditionalForm\`c\)]], ", ", StyleBox["\n (2) ", FontFamily->"Times"], Cell[BoxData[ \(TraditionalForm\`d(x)\ = \ 1\)]], ", ", StyleBox[" \n (3)\t", FontFamily->"Times"], Cell[BoxData[ \(TraditionalForm\`d(\ p\ + \ q\ )\ = \ d(p)\ + \ d(q)\)]], ", and \n", StyleBox[" (4)\t", FontFamily->"Times"], Cell[BoxData[ \(TraditionalForm\`d(\ p\ \[CenterDot]\ q\ )\ = \ \(d(p)\)\ \[CenterDot]\ q\ + \ p\[CenterDot]\ \(d(q)\)\)]], ". \n \nNote that this type of recursion is much more complicted than \ the previous ones: it is no longer clear what the next step should be since \ there are different ways one can decompose a polynomial into sums or products \ of other polynomials. In fact, it is not at all clear that different \ decompositions would ultimately lead to the same final result. \nHowever, we \ simply use the standard decomposition as a sum of products (sum of monomials) \ and apply these rules correspondingly. \nTo keep hacking under control, we \ have to realize that ", StyleBox["Mathematica", FontSlant->"Italic"], " represents products such a ", Cell[BoxData[ \(TraditionalForm\`\(\(\ \)\(5\ x\ x\)\)\)]], " in exponential form (as is only reasonable):" }], "Text", Evaluatable->False, AspectRatioFixed->True], Cell["5 x x // FullForm", "Input"], Cell[TextData[{ "So, we will cheat a bit and use a special rule to deal with ", Cell[BoxData[ \(TraditionalForm\`x\^n\)]], " (which could be derived from rule number 4 above). Also, we will \ restrict ourselves to integer coefficients. " }], "Text"], Cell[BoxData[{ \(Clear[dd, x]\), "\n", \(\(dd[x] = 1;\)\), "\n", \(\(dd[_Integer]\ := \ 0;\)\), "\n", \(dd[pp_\ + \ qq_]\ := \ \ dd[pp]\ + \ dd[qq]\), "\n", \(\(dd[\ pp_\ qq_]\ := \ dd[pp]\ Times[qq]\ + \ pp\ dd[qq];\)\), "\n", \(\(dd[\ x^n_]\ := \ n\ Power[x, n - 1];\)\)}], "Input", AspectRatioFixed->True], Cell["dd[ 8 + 5x + 15 x^3 + x^12 ]", "Input"], Cell["Trace[ dd[ 8 + 5x + 15 x^3 + x^12 ], dd[__] ] // Flatten", "Input"] }, Closed]] }, Closed]], Cell[CellGroupData[{ Cell[" Pairs", "Subsection", Evaluatable->False, AspectRatioFixed->True, CellTags->"c:15"], Cell["\<\ We can also solve the old HW problem of defining a pairing function \ recursively. The recursion here depends on the length of the list. First, a solution that is a little more complicated than necessary. Let us \ accumulate the pairs in a separate list, and append to it as we go along. \ \ \>", "Text", Evaluatable->False, AspectRatioFixed->True], Cell["\<\ Clear[pairs] pairs[{},{},res_List] := res; pairs[A_List,B_List,res_List] := \tpairs[ Rest[A], Rest[B], \t\t\tAppend[res,{First[A],First[B]}]];\ \>", "Input", AspectRatioFixed->True], Cell[BoxData[ \(pairs[{a, b, c}, {1, 2, 3}, {}]\)], "Input", AspectRatioFixed->True], Cell[TextData[{ "A trace shows how the output is generated from the pieces. Note how we \ filter out information in the trace (see what happens if you just do a ", StyleBox["Trace[ ..., pairs[__] ]", "SmallText"], " )." }], "Text", Evaluatable->False, AspectRatioFixed->True], Cell["\<\ Trace[ pairs[{a,b,c},{1,2,3},{}], pairs[_List,__] ] // Flatten // \ TableForm\ \>", "Input"], Cell["\<\ The additional list makes it easy to think about the recursive \ function, but it is really not necessary. Here is version without the extra \ result list. \ \>", "Text", Evaluatable->False, AspectRatioFixed->True], Cell["\<\ Clear[pairs] pairs[{},{}]:={}; pairs[A_,B_] := \tPrepend[ pairs[Rest[A],Rest[B]], {First[A],First[B]} ];\ \>", "Input", AspectRatioFixed->True], Cell[BoxData[ \(pairs[{a, b, c}, {1, 2, 3}]\)], "Input", AspectRatioFixed->True], Cell[TextData[{ "Make sure you understand why we use ", StyleBox["Append", "SmallText"], " in the first version, and ", StyleBox["Prepend", "SmallText"], " in the second. Here is a trace. The result list is now invisible." }], "Text", Evaluatable->False, AspectRatioFixed->True], Cell["\<\ Trace[ pairs[{a,b,c},{1,2,3}], pairs[__] ] // Flatten // \ TableForm\ \>", "Input"], Cell["\<\ We can make the result list visible by modifying the trace. \ \>", \ "Text", Evaluatable->False, AspectRatioFixed->True], Cell["\<\ Trace[ pairs[{a,b,c},{1,2,3}], Prepend[_List,_] ] // Flatten // \ TableForm\ \>", "Input"], Cell[TextData[{ "We don't have to use ", StyleBox["First", "SmallText"], "/", StyleBox["Rest", "SmallText"], ", since we can use pattern matching in the definition of pairs. " }], "Text", Evaluatable->False, AspectRatioFixed->True], Cell["\<\ Clear[pairs] pairs[{},{}] := {}; pairs[{x_,xx___},{y_,yy___}] := Prepend[pairs[{xx},{yy}],{x,y}];\ \>", "Input",\ AspectRatioFixed->True], Cell[BoxData[ \(pairs[{a, b, c}, {1, 2, 3}]\)], "Input", AspectRatioFixed->True], Cell[BoxData[ \(Trace[pairs[{a, b, c}, {1, 2, 3}], pairs[__]]\)], "Input", AspectRatioFixed->True], Cell[BoxData[ \(Trace[pairs[{a, b, c}, {1, 2, 3}], Prepend[__]]\)], "Input", AspectRatioFixed->True], Cell[TextData[{ "We will have more to say about this type of recursive definition on lists \ in a moment. \nThe recursive function is not as efficient as the hack based \ on ", StyleBox["Thread", "SmallText"], ", but it's still quite useable. " }], "Text", Evaluatable->False, AspectRatioFixed->True], Cell[BoxData[{ \(\(R200 = Range[200];\)\), "\n", \(Timing[\(pairs[R200, R200];\)]\), "\n", \(Timing[\(Thread[{R200, R200}];\)]\)}], "Input", AspectRatioFixed->True] }, Closed]], Cell[CellGroupData[{ Cell[" Towers of Hanoi", "Subsection", Evaluatable->False, AspectRatioFixed->True, CellTags->"c:16"], Cell[TextData[{ "You all know the game Towers of Hanoi. You have three pegs, and a \ collection of disks ", Cell[BoxData[ \(TraditionalForm\`D\_1, D\_2, \[Ellipsis], D\_n\)]], " of different sizes. Initially, all disks are stacked up at peg 1, the \ largest disk ", Cell[BoxData[ \(TraditionalForm\`D\_1\)]], " at the bottom, then the next largest ", Cell[BoxData[ \(TraditionalForm\`D\_2\)]], ", and so on, up to the smallest disk ", Cell[BoxData[ \(TraditionalForm\`D\_n\)]], "which sits on top. A move in this game consists of moving the top disk \ from one peg to another, subject to the condition that a larger disk may \ never come to rest on a smaller one. The objective is to find a sequence of \ admissible moves that will bring all the disks to peg number 2. \nThere are \ profound metaphysical aspects to this game, in particular when the disks are \ made from solid gold, there are 64 of them, the pegs are made from diamond, \ and the game is played by monks. However, we won't go into the details here. \ \nSeveral questions come to mind. First of all, there is the obvious problem \ of whether the game has a solution for all values of ", Cell[BoxData[ \(TraditionalForm\`n\)]], ". As we will see, there is in fact a solution regardless of the number of \ disks. Next there is the problem of how many moves are required to move the \ disks from peg 1 to peg 2. More generally, are all admissible placements of \ disks (", Cell[BoxData[ \(TraditionalForm\`D\_i\)]], " rests on top of ", Cell[BoxData[ \(TraditionalForm\`D\_j\)]], " implies ", Cell[BoxData[ \(TraditionalForm\`i > j\)]], ") reachable from the initial placement? In how many moves? What can one \ say about the best strategy? " }], "Text", Evaluatable->False, AspectRatioFixed->True], Cell[CellGroupData[{ Cell["Vector Configurations", "Subsubsection", CellTags->"c:17"], Cell["\<\ Rather than just answering these questions, we will try to present \ some general ideas that are helpful not just for the Towers of Hanoi, but \ more generally for combinatorial problems. Finding the appropriate model is \ often the key step towards a solution, just as finding the appropriate data \ structure is often the key towards implementing an efficient algorithm. \ \ \>", "Text", Evaluatable->False, AspectRatioFixed->True], Cell[TextData[{ "The first problem is to find a concise description of the possible \ configurations of disks that one has to deal with. The obvious answer is to \ represent a configuration by a list of three lists of disks, each \ representing the stack on one of the three pegs. Let us agree that the last \ list element corresponds to the top disk on that peg. For the sake of \ simplicity, we replace disk ", Cell[BoxData[ \(TraditionalForm\`D\_i\)]], " by the integer ", Cell[BoxData[ \(TraditionalForm\`i\)]], ", so that the initial configuration is given by \n\t\t", Cell[BoxData[ \(TraditionalForm\`{\ {1, 2, \[Ellipsis], n}, \ {}, \ {}\ }\)]], ".\nAn admissible move takes us from configuration ", Cell[BoxData[ \(TraditionalForm\`\(\({\ L\_1, L\_2, L\_3}\)\(\ \ \)\)\)]], " to ", Cell[BoxData[ \(TraditionalForm\`\(\({\ K\_1, K\_2, K\_3}\)\(\ \ \)\)\)]], " where \n\t", Cell[BoxData[ \(TraditionalForm\`K\_\(\(r\)\(\ \)\) = \ L\_r\)]], " and \n\t", Cell[BoxData[ \(TraditionalForm\`K\_s = \ drop(L\_s, \(-1\))\)]], " and \n\t", Cell[BoxData[ \(TraditionalForm\`K\_t\ = \ app(\ L\_\(\(\[VeryThinSpace]\[VeryThinSpace]\)\(t\)\), last(L\_s))\)]], ",\nwhere ", Cell[BoxData[ \(TraditionalForm\`{r, s, t}\ = \ {1, 2, 3}\)]], " and ", Cell[BoxData[ \(TraditionalForm\`last(L\_s)\ > \ last(L\_\(\(\[VeryThinSpace]\[VeryThinSpace]\)\(t\)\))\)]], ". \nThus, there are usually 3 next possible configurations, but sometimes \ there are only 2 (when?). Since only the top disk from peg ", Cell[BoxData[ \(TraditionalForm\`j\)]], " moves to peg ", Cell[BoxData[ \(TraditionalForm\`k\)]], ", and everything else remains the same, we can express a single move \ economically as a pair ", Cell[BoxData[ \(TraditionalForm\`{s, t}\)]], " (source to target). A solution to the problem can be expressed as a \ sequence of moves:\n\t", Cell[BoxData[ \(TraditionalForm\`{s\_1, t\_1}, {s\_2, t\_2}, \ \[Ellipsis], \ {s\_m, t\_m}\)]], ". " }], "Text"], Cell[TextData[{ StyleBox["In order to experiment, we need a function \n\t", FontFamily->"Times"], Cell[BoxData[ \(TraditionalForm\`act\ : \ configurations\ \[Cross]\ moves\ \[LongRightArrow]\ configurations\)]], "\nthat computes the next configuration, given the current configuration \ and a move. We will tacitly assume that the move is admissible, the ", Cell[BoxData[ \(TraditionalForm\`act\)]], " function will not actually check. Implementing act is quite \ straightforward:" }], "Text", Evaluatable->False, AspectRatioFixed->True], Cell["\<\ Clear[act] act[ L_List,{i_,j_}]:= Module[{x,LL}, \t\tLL=L; \t\tx=Last[LL\[LeftDoubleBracket]i\[RightDoubleBracket]]; \t\tLL\[LeftDoubleBracket]i\[RightDoubleBracket]=Drop[LL\[LeftDoubleBracket]i\ \[RightDoubleBracket],-1]; \t\tLL\[LeftDoubleBracket]j\[RightDoubleBracket]=Append[LL\[LeftDoubleBracket]\ j\[RightDoubleBracket],x]; \t\tLL ];\ \>", "InputOnly", AspectRatioFixed->True], Cell[BoxData[{ \(act[{{1, 2, 3}, {}, {}}, {1, 2}]\), "\n", \(act[\ %, {1, 3}]\), "\n", \(act[%, {2, 3}]\)}], "Input", AspectRatioFixed->True], Cell[TextData[{ "A bit more interesting is the question how to deal with a whole sequence \ of moves. As in the last computation, we need to feed back the previous \ configuration and the next move to the act function. As it turns out, this \ type of operation occurs so frequently that ", StyleBox["Mathematica", FontSlant->"Italic"], " provides a special function for this purpose: the commands ", StyleBox["Fold", "SmallText"], " and ", StyleBox["FoldList", "SmallText"], ". " }], "Text"], Cell[BoxData[{ \(\(Clear[f, x, a, b, c, d, e];\)\), "\n", \(Fold[\ f, \ x, \ {a, b, c, d, e}\ ]\)}], "Input"], Cell[TextData[{ "Using ", StyleBox["Fold", "SmallText"], " and ", StyleBox["act", "SmallText"], ", we can cope with sequences of moves:" }], "Text"], Cell[BoxData[ \(Fold[\ act, {{1, 2, 3}, {}, {}}, {{1, 2}, {1, 3}, {2, 3}}]\)], "Input"], Cell[TextData[{ "Here is a solution for ", Cell[BoxData[ \(TraditionalForm\`n = 3\)]], ". " }], "Text"], Cell["\<\ tt = FoldList[ act,{{1,2,3},{},{}}, \t{{1,2},{1,3},{2,3},{1,2},{3,1},{3,2},{1,2}}]; TableForm[tt,TableDepth\[Rule]2]\ \>", "Input"], Cell[TextData[{ StyleBox["But how do we actually compute a sequence of moves that solves \ the problem? The easiest way to attack this problem is by recursion. We will \ recursively define a function ", FontFamily->"Times"], Cell[BoxData[ \(TraditionalForm\`play[n, i, j]\)]], StyleBox[" that outputs a proper sequence of moves that will transport the \ top", FontFamily->"Times"], Cell[BoxData[ \(TraditionalForm\`\(\(\ \)\(n\)\)\)]], StyleBox[" disks from peg", FontFamily->"Times"], Cell[BoxData[ \(TraditionalForm\`\(\(\ \)\(i\)\)\)]], StyleBox[" to peg ", FontFamily->"Times"], Cell[BoxData[ \(TraditionalForm\`j\)]], StyleBox[". If ", FontFamily->"Times"], Cell[BoxData[ \(TraditionalForm\`n\)]], StyleBox[" is ", FontFamily->"Times"], Cell[BoxData[ \(TraditionalForm\`1\)]], StyleBox[", this is straightforward. For larger values of ", FontFamily->"Times"], Cell[BoxData[ \(TraditionalForm\`n\)]], StyleBox[" we use recursion:", FontFamily->"Times"] }], "Text", Evaluatable->False, AspectRatioFixed->True], Cell["\<\ Clear[play] play[1,i_,j_]:={{i,j}}; play[n_,i_,j_]:= With[{k=6-i-j}, \t\tJoin[play[n-1,i,k],play[1,i,j],play[n-1,k,j]]];\ \>", "Input", AspectRatioFixed->True], Cell["\<\ Note the beautiful hack to determine the number of the other peg. \ Make sure you understand the method here. Also note that this is another \ example of a function using multiple recursive calls. \ \>", "Text", Evaluatable->False, AspectRatioFixed->True], Cell[BoxData[{ \(play[2, 1, 2]\), "\n", \(play[3, 1, 2]\)}], "Input", AspectRatioFixed->True], Cell["Here is a test.", "Text", Evaluatable->False, AspectRatioFixed->True], Cell[BoxData[{ \(\(nn\ = \ 6;\)\), "\n", \(tt\ = \ FoldList[\ act, {Range[nn], {}, {}}, play[nn, 1, 2]]; \ TableForm[tt, TableDepth \[Rule] 2]\)}], "Input"], Cell[TextData[{ "Incidentally, using a list of three vectors to represent a configuration \ is actually not such a particularly good idea. For example, it is hard to \ determine how many possible configurations there are for ", Cell[BoxData[ \(TraditionalForm\`n\)]], " disks. In the next section we introduce a better representation" }], "Text", Evaluatable->False, AspectRatioFixed->True] }, Closed]], Cell[CellGroupData[{ Cell["Digression: State Transitions", "Subsubsection", CellTags->"c:18"], Cell[TextData[{ "The act function from the last section warrants further discussion. Its \ basic form is the following. We have a system that has possible ", StyleBox["internal states", FontColor->RGBColor[0, 0, 1]], " and that responds to external stimuli or ", StyleBox["input signals", FontColor->RGBColor[0, 0, 1]], ". Suppose ", Cell[BoxData[ \(TraditionalForm\`Q\)]], " is the collection of all possible states, and ", Cell[BoxData[ \(TraditionalForm\`A\)]], " is the collection of all signals. Then we can describe the behavior of \ the system by a function \n\t", Cell[BoxData[ \(TraditionalForm\`f\ : \ Q\ \[Cross]\ A\ \[LongRightArrow]\ Q\)]], ",\nthe ", StyleBox["transition function", FontColor->RGBColor[0, 0, 1]], " of the system: ", Cell[BoxData[ \(TraditionalForm\`f(p, a)\)]], " is the next state if the system is currently in state ", Cell[BoxData[ \(TraditionalForm\`p\ \[Element] \ Q\)]], ", and the current input signal is ", Cell[BoxData[ \(TraditionalForm\`a\ \[Element] \ A\)]], ". \n\nSingle inputs are usually not very interesting, one needs to know \ the behavior of the system under whole sequences of inputs. Hence, we need to \ extend the transition function to a map\n\t", Cell[BoxData[ \(TraditionalForm\`\(f\^*\)\ : \ Q\ \[Cross]\ \(A\^*\)\ \[LongRightArrow]\ Q\)]], ",\nwhere we have written ", Cell[BoxData[ \(TraditionalForm\`\(A\^*\)\)]], " for the collection of all sequences of inputs from ", Cell[BoxData[ \(TraditionalForm\`A\)]], ". This can always be done in exactly the same way via recursion:\n\t", Cell[BoxData[ \(TraditionalForm\`\(f\^*\)(\ p, \ \[Epsilon]\ )\ = \ p\)]], " and \n\t", Cell[BoxData[ \(TraditionalForm\`\(f\^*\)(\ p, \ x\[VeryThinSpace]a\ )\ = \ f(\(f\^*\)(\ p, \ x\ ), \ a\ )\)]], ".\nHere ", Cell[BoxData[ \(TraditionalForm\`x\[VeryThinSpace]a\)]], " is a sequence ending in ", Cell[BoxData[ \(TraditionalForm\`a\ \[Element] \ A\)]], ". " }], "Text", Evaluatable->False, AspectRatioFixed->True], Cell[TextData[{ "A particularly important special case is when the state set is finite, and \ the input signals are symbols from an alphabet. In this case these transition \ systems are called ", StyleBox["finite state machines", FontColor->RGBColor[0, 0, 1]], ", and are used in countless places in CS. For example, popular text search \ programs such as ", StyleBox["grep", "SmallText"], " are based on finite state machines. They are also indispensible in the \ design of compilers. " }], "Text"] }, Closed]], Cell[CellGroupData[{ Cell["Function Configurations", "Subsubsection", CellTags->"c:19"], Cell[TextData[{ "The representation of configurations from the last section starts at the \ pegs, and describes the state of each peg. Alternatively, we could think \ about the disks, and describe the state of each disk. Since each disk is \ attached to one out of three possible pegs, we can describe a configuration \ as a function \n\t\t", Cell[BoxData[ \(TraditionalForm\`f\ : \ \([n]\)\ \[LongRightArrow]\ \([3]\)\)]], "\nwhere the obvious interpretation is that disk ", Cell[BoxData[ \(TraditionalForm\`D\_i\)]], " rests on peg ", Cell[BoxData[ \(TraditionalForm\`f(i)\)]], ". Note that each function corresponds to an admissible configuration, so \ there clearly are ", Cell[BoxData[ \(TraditionalForm\`3\^\(\(\ \)\(n\)\)\)]], " configurations. These functions can be represented by a value vector ", Cell[BoxData[ \(TraditionalForm\`\((a\_1, a\_2, \[Ellipsis], a\_n)\)\)]], ", ", Cell[BoxData[ \(TraditionalForm\`1\ \[LessEqual] \ a\_i\ \[LessEqual] \ 3\)]], ". In other words, the set of all configurations now simply takes the form \ ", Cell[BoxData[ \(TraditionalForm\`\([3]\)\^\(\(\ \)\(n\)\)\)]], ", a plain Cartesian product. In particular, it is now clear that there are \ precisely ", Cell[BoxData[ \(TraditionalForm\`3\^\(\(\ \)\(n\)\)\)]], " admissible configurations, a fact that is absolutely not clear from our \ previous representation." }], "Text", Evaluatable->False, AspectRatioFixed->True], Cell["\<\ If our two representations are really equivalent, there ought to be \ a way to convert back and forth. How exactly does one convert these function \ configurations to and from the old vector configurations? \ \>", "Text"], Cell["\<\ toVector[L_List] := { Flatten@Position[L,1], Flatten@Position[L,2], \tFlatten@Position[L,3]}; fromVector[{L1_List,L2_List,L3_List}] := \tLast /@ \ Sort[Join[CartesianProduct[L1,{1}],CartesianProduct[L2,{2}],CartesianProduct[\ L3,{3}] ] ];\ \>", "Input"], Cell[BoxData[{ \(toVector[\ {1, 2, 3, 1, 2, 2, 1}]\), "\n", \(fromVector[%]\)}], "Input"], Cell[TextData[{ "It is an excellent exercise to implement an ", StyleBox["act", "SmallText"], " operation for these new configurations, without invoking ", StyleBox["toVector", "SmallText"], " and ", StyleBox["fromVector", "SmallText"], ". \n\nOne of the reasons the new configurations are better than the old \ is that they allow us to draw a nice picture of the space of configurations. \ In order to express the possible moves between configurations, we would like \ to draw a picture where \n\[Bullet] each configuration corresponds to a \ node,\n\[Bullet] each admissible move is indicated by a line connecting the \ appropriate nodes. \nFor ", Cell[BoxData[ \(TraditionalForm\`n = 1\)]], " there are only three nodes, and the picture should be an equilateral \ triangle. " }], "Text"] }, Closed]], Cell[CellGroupData[{ Cell["A Picture of Hanoi Configurations", "Subsubsection", CellTags->"c:20"], Cell["\<\ Ignore the code in this section (or look at the GraphicsCode \ notebook for more information). It exploits complex numbers to get a simple \ representation for points in the plain (the real component is the \ x-coordinate, and the imaginary part is the y-coordinate). Just execute, and enjoy the picture. \ \>", "Text"], Cell["\<\ Clear[triangle,next,toPoints,toLines]; RegularNGon[nn_Integer] := (E^(2 \[Pi] \[ImaginaryI]/nn))^Range[0,nn-1]; triangle = RegularNGon[3]* E^(\[Pi] \[ImaginaryI]/2); next[pl_List] := With[ {pp = pl/2}, \tChop@N@Flatten[{pp,pp,pp} + triangle] ]; makeNodes[n_Integer?NonNegative] := \t\t{Re[#],Im[#]}& /@ Nest[next,{0},n]; toPoints[LL_List] := Point /@ LL; top[L_List] := L\[LeftDoubleBracket] (Length[L]+1)/2\[RightDoubleBracket]; left[L_List] := First[L]; right[L_List] := Last[L]; threeLines[{L1_List,L2_List,L3_List}] := { Line[ {top[L1],left[L2]}], Line[{right[L2],top[L3]}], Line[{left[L3],right[L1]}] }; toLines[L_List] := Module[ {pp,trs={}}, \t\tDo[ \t\t\tpp =Partition[Partition[L,{3^i}],3]; \t\t\ttrs = Join[ trs, threeLines /@ pp ], \t\t\t{i,0,Log[3,Length[L]-1]} \t\t]; \t\ttrs ];\ \>", "Input"], Cell["\<\ n = 3; With[ {pts = makeNodes[n]}, Graphics[ {GrayLevel[.8], \ toLines[pts],PointSize[0.015],Blue,toPoints[pts] }, \tBackground->LightYellow,Frame->True,FrameTicks->None,AspectRatio->Automatic]\ ] // Show;\ \>", "Input"], Cell["\<\ The claim is that this picture faithfully represents the possible \ configurations in a Hanoi game with 5 disks, as well as the possible moves \ between them. The corner vertices correspond to the configurations where two \ pegs are empty. Note that with a bit of work one can read off optimal move sequences from the \ corners to any point in the space, not just the other corners. How? \ \>", \ "Text"] }, Closed]], Cell[CellGroupData[{ Cell["But is it true?", "Subsubsection", CellTags->"c:21"], Cell[TextData[{ "How do we know that the last picture accurately reflects the game? We \ already know that there are ", Cell[BoxData[ \(TraditionalForm\`3\^\(\(\ \)\(n\)\)\)]], " configurations, precisely the number of nodes in the graph. But how do \ we knwo that the links are properly drawn? One way to make sure nothing bad \ is going on is to label the nodes with configurations they represent. Then we \ can check that the links are in fact legitimate. \nHere is another piece of \ code that does exactly that. More precisely, for every configuration it \ determines a point in the plane where the label should be, and prints it at \ that point. Below we define a function\n\t", Cell[BoxData[ \(TraditionalForm\`pos\ : \ \([3]\)\^\(\(\ \)\(n\)\)\[LongRightArrow]\ \ \[DoubleStruckCapitalC]\)]], " \nthe determines the right position for each configuration, expressed in \ the function notation from above.\nTry to do this without looking at the \ code, and you will see that it is annoyingly difficult to get all the details \ right. " }], "Text"], Cell["\<\ Clear[pos,up,do,ri,totext,phi,s,g] phi = 2Pi/3; s = .5; g[i_] := g[i] = N[Cos[i phi] + I Sin[i phi]]; up[x_] := s g[2] x + g[1]; do[x_] := s g[1] x + g[2]; ri[x_] := s x + g[0]; pos[a_] := g[a-1]; pos[1,x__] := ri@pos[x]; pos[2,x__] := do@pos[x] /; OddQ[Length[{x}]]; pos[2,x__] := up@pos[x]; pos[3,x__] := up@pos[x] /; OddQ[Length[{x}]]; pos[3,x__] := do@pos[x]; totext[x__] := Module[ {xx = I pos[x]}, \tText[ StringJoin@@Map[ToString,{x}], {Re[xx],Im[xx]}, \t TextStyle->{FontWeight->\"Bold\",FontSize->12}] ];\ \>", "Input"], Cell["\<\ n = 3; Show[ Graphics[ Apply[ totext, CartesianProduct@@Table[3,{n}],{1}] ], \tAspectRatio->1, PlotRange->All ];\ \>", "Input"], Cell["\<\ Make sure to check that the moves suggested by this picture are in \ fact all legitimate.\ \>", "Text"] }, Closed]], Cell[CellGroupData[{ Cell["A Non-Recursive Approach", "Subsubsection", CellTags->"c:22"], Cell[TextData[{ "Just for the record: recursion is very convenient to tackly the Towers of \ Hanoi problem, but we can also find a direct solution. Frist, let us develop \ a more compact notion for the moves. The coding we have used so far is the \ most obvious one: \n\tpair ", Cell[BoxData[ \(TraditionalForm\`\((i, j)\)\)]], " expresses the move where the topmost disk of peg ", Cell[BoxData[ \(TraditionalForm\`i\)]], " is moved to peg ", Cell[BoxData[ \(TraditionalForm\`\(\(\ \)\(j\)\)\)]], ". \nHence, a priori, there are 9 moves, though not all of them will be \ admissible at any particular point. As a matter of fact, at any time during \ the game there are only two of the topmost disks that could potentially be \ moved: the smallest one, and the second smallest one. If we arrange the pegs \ in a circular pattern, we can express all possible moves as follows:\n\t", Cell[BoxData[ \(TraditionalForm\`\(\[PlusMinus]s\)\)]], "\tmove the smallest disk clockwise/counterclockwise,\n\t", Cell[BoxData[ \(TraditionalForm\`\(\[PlusMinus]b\)\)]], "\tmove the second smallest disk clockwise/counterclockwise.\nAgain not all \ moves will be admissible all the time, but now there are only 4 possible \ moves, so in general only one of them violates the rules (which?). \nNow \ consider the optimal strategy. Since the optimal strategy will not move the \ same disk twice in a row, we must alternate between ", Cell[BoxData[ \(TraditionalForm\`s\)]], " and ", Cell[BoxData[ \(TraditionalForm\`b\)]], " moves, starting with an ", Cell[BoxData[ \(TraditionalForm\`s\)]], "-move. It follows that the optimal strategy can in fact be represented by \ a simple binary sequence. To keep the new representation close to the \ previous one, we will use a sequence of '+' and '-' signs rather than a \ binary sequence. \nWhat does the optimal strategy look like? We can use the \ play function from above in conjunction with a simple substitution rule. " }], "Text"], Cell["\<\ rule = { {i_,j_} /; (i+1==j || i==3 && j==1 )->\"+\", \ {i_,j_}->\"-\" }; \ \>", "Input"], Cell["\<\ play[5, 1, 2 ] Partition[% //. rule,2] // TableForm \ \>", "Input"], Cell["\<\ Lo and behold, the small disks moves on ahead at all odd steps, but \ the second smallest disk alternates direction in a more complicated fashion. \ Clearly, there is a lot of symmetry. In particular, the whole sequence is \ symmetric around the middle, so one might expect powers of 2 to come into \ play somehow. Let us write the step numbers in binary right next to the \ moves.\ \>", "Text"], Cell["\<\ pp = play[5, 1, 2 ] //. rule; Thread[ Append[ Thread@Partition[pp,2], IntegerDigits[#,2,4]& /@ \ Range[Length[pp]/2] ] ] // TableForm[#,TableDepth->2]& \ \>", "Input"], Cell["\<\ pp = play[6, 1, 2 ] //. rule; Thread[ Append[ Thread@Partition[pp,2], IntegerDigits[#,2,5]& /@ \ Range[Length[pp]/2] ] ] // TableForm[#,TableDepth->2]& \ \>", "Input"], Cell["\<\ This is still a bit complicated, but we can check that the sequence \ obeys the following recursion:\ \>", "Text"], Cell["\<\ Clear[mv] mv[1] = {0}; mv[n_] := With[ {x=mv[n-1]}, Join[ x, {1}, x ] ] /; EvenQ[n]; mv[n_] := With[ {x=mv[n-1]}, Join[ x, {0}, x ] ];\ \>", "Input"], Cell["\<\ mv[3] mv[4] mv[5]\ \>", "Input"], Cell[TextData[{ "The recursion can be translated into a simple algorithm for the Towers of \ Hanoi problem:\n\[FilledCircle] At any odd step ", Cell[BoxData[ \(TraditionalForm\`n\)]], ", move the smallest disk clockwise.\n\[FilledCircle] At any even step ", Cell[BoxData[ \(TraditionalForm\`n\ = \ 2\^\(\(\ \)\(k\)\)\[CenterDot]\ p\)]], ", where ", Cell[BoxData[ \(TraditionalForm\`p\)]], " is odd, ", Cell[BoxData[ \(TraditionalForm\`k > 0\)]], ", move the second smallest disk counterclockwise if ", Cell[BoxData[ \(TraditionalForm\`k\)]], " is odd, and clockwise if ", Cell[BoxData[ \(TraditionalForm\`k\)]], " is even. \nLet's check." }], "Text"], Cell["\<\ powerTwo[n_] := Module[ {nn=n,e=0}, While[EvenQ[nn],e++;nn/=2]; e ]\ \>", "Input"], Cell["\<\ powerTwo /@ Range[16] Mod[%,2] mv[4]\ \>", "Input"], Cell["\<\ Seems to work. Here is code that applies the optimal strategy to as \ determined by this non-recursive approach. We use vector configurations to \ express the stages of the game. \ \>", "Text"], Cell["\<\ ClearAll[next,inc,dec] inc[1]=2; inc[2]=3; inc[3]=1; dec[1]=3; dec[2]=1; dec[3]=2; next[t_][L_List] := Join[ {inc@First[L]}, Rest[L] ] /; OddQ[t]; next[t_][L_List] := Module[ {p=2,tt=t/2}, \t\tWhile[ L[[p]]==L[[1]], p++ ]; \t\tIf[ OddQ@powerTwo[tt], \t\t\tReplacePart[ L, inc[L[[p]]], p ], \t\t\tReplacePart[ L, dec[L[[p]]], p ] \t\t] ];\ \>", "Input"], Cell["\<\ tt = 0; NestList[ (tt++;next[tt][#])&, {1,1,1,1}, 15 ] // TableForm\ \>", "Input"] }, Closed]] }, Closed]] }, Closed]], Cell[CellGroupData[{ Cell["Recursive Data Structures", "Section", Evaluatable->False, AspectRatioFixed->True, CellTags->"c:23"], Cell[CellGroupData[{ Cell[" Sequences and Lists", "Subsection", Evaluatable->False, AspectRatioFixed->True, CellTags->"c:24"], Cell[TextData[{ "Some of the previous examples already indicate that recursion applies not \ just to natural numbers, but also to more complicated data structures. In \ practice, recursion on lists and trees is particularly important. \n\nIn \ mathematics, as ", StyleBox["sequence", FontColor->RGBColor[0, 0, 1]], " or ", StyleBox["list", FontColor->RGBColor[0, 0, 1]], " over some ground set ", Cell[BoxData[ \(TraditionalForm\`A\)]], " is defined to be a function ", Cell[BoxData[ \(TraditionalForm\`s\ : \ \([n]\)\ \[LongRightArrow]\ A\)]], ", where ", Cell[BoxData[ \(TraditionalForm\`n\ \[Element] \ \[DoubleStruckCapitalN]\)]], ". To keep notation bearable, this is ususally written as \n\t", Cell[BoxData[ FormBox[ RowBox[{" ", FormBox[\(s = \((s\_1, s\_2, ... , s\_n)\)\), "TraditionalForm"]}], TraditionalForm]]], " or perhaps ", Cell[BoxData[ FormBox[ RowBox[{" ", FormBox[\(s = s\_1, s\_2, ... , s\_n\), "TraditionalForm"]}], TraditionalForm]]], "\nThe collection of all sequences is \n\t", Cell[BoxData[ \(TraditionalForm\`Seq( A)\ = \ \ {\ \ s\ : \ \([n]\)\ \[LongRightArrow]\ A\ \ | \ \ \ n\ \[Element] \ \[DoubleStruckCapitalN]\ \ \ }\)]], ". \nThe natural number ", Cell[BoxData[ \(TraditionalForm\`n\)]], " in the definition is the length of the sequence, written ", Cell[BoxData[ \(TraditionalForm\`n\ = \ \(\(|\)\(\ \)\(\(s\)\(|\)\)\)\)]], ". It is straighforward to check that this supports all the operations on \ sequences that one might be interested in. For example, we can define a join \ (or catenation) operation\n\t", Cell[BoxData[ \(TraditionalForm\`\(\[CirclePlus]\ \(\(:\)\(\ \ \)\(\(Seq( A)\)\ \[Cross]\ \(Seq(A)\)\ \[LongRightArrow]\ \(Seq( A)\)\)\)\)\)]], " \nMore precisely, given ", Cell[BoxData[ \(TraditionalForm\`r\ : \ \([n]\)\ \[LongRightArrow]\ A\)]], " and ", Cell[BoxData[ \(TraditionalForm\`s\ : \ \([m]\)\ \[LongRightArrow]\ A\)]], " define \n\t", Cell[BoxData[ \(TraditionalForm\`r\[CirclePlus]\(s\ : \ \([n + m]\)\ \[LongRightArrow]\ A\)\)]], " by \n\t", Cell[BoxData[ \(TraditionalForm\`\(\(\((r\[CirclePlus]s)\) \((i)\)\)\(\ \)\(=\)\(\ \)\ \(r(i)\)\(\ \)\)\)]], " for ", Cell[BoxData[ \(TraditionalForm\`1\ \[LessEqual] \ i\ \[LessEqual] \ n\)]], " and \n\t", Cell[BoxData[ \(TraditionalForm\`\(\(\((r\[CirclePlus]s)\) \((n + i)\)\)\(\ \)\(=\)\(s(i)\)\(\ \)\)\)]], " for ", Cell[BoxData[ \(TraditionalForm\`1\ \[LessEqual] \ i\ \[LessEqual] \ m\)]], ".\n\nOr we could define the reversal operation ", Cell[BoxData[ \(TraditionalForm\`rev\ : \ \ \(Seq(A)\)\ \ \[LongRightArrow]\ \(Seq( A)\)\)]], " on sequences by \n\t", Cell[BoxData[ \(TraditionalForm\`rev(r)\ : \ \([n]\)\ \[LongRightArrow]\ A\)]], " by \n\t", Cell[BoxData[ \(TraditionalForm\`\(\(\(rev(r)\) \((i)\)\)\(\ \)\(=\)\(\ \)\(r( n - i + 1)\)\(\ \)\)\)]], " for ", Cell[BoxData[ \(TraditionalForm\`1\ \[LessEqual] \ i\ \[LessEqual] \ n\)]], ".\nAnd so on and so forth." }], "Text", Evaluatable->False, AspectRatioFixed->True], Cell[TextData[{ "This description of sequences is somewhat static: a sequence is \ constructed once and for all (this corresponds nicely to the notion of an \ array in many programming languages). Alternatively, we can think of lists \ as being generated dynamically, starting with the empty list and adding one \ element at a time. \n\n", StyleBox["List Axioms", FontFamily->"Times", FontWeight->"Bold"], StyleBox[" (using append)\n\t(1) ", FontFamily->"Times"], Cell[BoxData[ \(TraditionalForm\`{}\)]], StyleBox[" is a list (the empty list ),\n\t(2) for any list ", FontFamily->"Times"], Cell[BoxData[ \(TraditionalForm\`L\)]], StyleBox[", and any ", FontFamily->"Times"], Cell[BoxData[ \(TraditionalForm\`a\)]], StyleBox[", ", FontFamily->"Times"], Cell[BoxData[ \(TraditionalForm\`app(L, a)\)]], StyleBox[" is a list.\n", FontFamily->"Times"], "\n", StyleBox["In other words, each and every list can be constructed from the \ empty list by a sequence of append operations. There is another tacit \ assumption here: nothing else is a list. Unless you can prove that \ something is a list using just these two principles, it is not. Furthermore, \ one assumes that there is only one way to compose a list using ", FontFamily->"Times"], Cell[BoxData[ \(TraditionalForm\`append\)]], StyleBox[": \n\n\t", FontFamily->"Times"], Cell[BoxData[ \(TraditionalForm\`app(X, x) = \ app(Y, y)\)]], " ", StyleBox[" implies ", FontFamily->"Times"], Cell[BoxData[ \(TraditionalForm\`X\ = \ Y\)]], StyleBox[" and ", FontFamily->"Times"], Cell[BoxData[ \(TraditionalForm\`x\ = \ y\)]], StyleBox[". \n\nThis approach is a bit more vague (we have never really \ explained what precisely append is supposed to be), but it actually can be \ expressed nicely in many programming languages (linked lists). Making sense \ out of recursive definitions like the ones for lists can be quite difficult, \ but the corresponding programs are often quite straightforward. ", FontFamily->"Times"] }], "Text", Evaluatable->False, AspectRatioFixed->True], Cell[TextData[{ StyleBox["Furthermore, our axioms immediately yield a whole class of \ recursive operations on lists. In order to define a function ", FontFamily->"Times"], Cell[BoxData[ \(TraditionalForm\`f\)]], StyleBox[" on all lists, you only have to \n\n\t(1) specify ", FontFamily->"Times"], Cell[BoxData[ \(TraditionalForm\`f({})\)]], StyleBox["\n\t(2) specify ", FontFamily->"Times"], Cell[BoxData[ \(TraditionalForm\`f(\ app(X, x)\ )\)]], StyleBox[", assuming that a value for ", FontFamily->"Times"], Cell[BoxData[ \(TraditionalForm\`f(X)\)]], StyleBox[" is already defined. \n", FontFamily->"Times"] }], "Text", Evaluatable->False, AspectRatioFixed->True] }, Closed]], Cell[CellGroupData[{ Cell[" The Length of a List", "Subsection", Evaluatable->False, AspectRatioFixed->True, CellTags->"c:25"], Cell[TextData[{ StyleBox["Here is an example. The length of a list is clearly the length of \ the truncated list (last element dropped) plus 1. That observation produces a \ recursive algorithm to compute the length of a list. Here is the abstract \ form of the algorithm:\n\t", FontFamily->"Times"], Cell[BoxData[ \(TraditionalForm\`length({})\ = \ 0\)]], ",\n\t", Cell[BoxData[ \(TraditionalForm\`length(\ app(X, x))\ = \ length(X)\ + \ 1\)]], "." }], "Text", Evaluatable->False, AspectRatioFixed->True], Cell[BoxData[{ \(Clear[length]\), "\n", \(\(length[{}] = 0;\)\), "\n", \(\(length[L_List] := length[Drop[L, \(-1\)]] + 1;\)\)}], "Input", AspectRatioFixed->True], Cell[BoxData[ \(length[Range[10]]\)], "Input", AspectRatioFixed->True], Cell[TextData[{ StyleBox["The Drop operation is necessary here because we are given the \ whole list ", FontFamily->"Times"], Cell[BoxData[ \(TraditionalForm\`L\)]], StyleBox[" on the left as input, it is not presented in append form.\n\ Actually, we can avoid an explicit drop operation by using pattern matching. \ This definition is almost a verbatim application of the list axioms. ", FontFamily->"Times"] }], "Text", Evaluatable->False, AspectRatioFixed->True], Cell["\<\ Clear[length] length[{}] = 0; length[{xx___,a_}] := length[{xx}] + 1;\ \>", "Input", AspectRatioFixed->True], Cell[BoxData[ \(length[Range[10]]\)], "Input", AspectRatioFixed->True], Cell[TextData[{ StyleBox["\nWARNING", FontFamily->"Times", FontWeight->"Bold", FontColor->RGBColor[1, 0, 0]], "\nYou cannot use a construct like \n\t", StyleBox["length[ Append[L_,a_] ] := ...", "SmallText"], "\n", StyleBox["FullForm", "SmallText"], " shows why. " }], "Text", Evaluatable->False, AspectRatioFixed->True], Cell[BoxData[{ \(Append[L_, a_]\), "\n", \(FullForm[L_]\), "\n", \(FullForm[Append[L_, a_]]\)}], "Input", AspectRatioFixed->True], Cell["\<\ A trace shows the sequence of calls triggered by the last input.\ \>", "Text",\ Evaluatable->False, AspectRatioFixed->True], Cell[BoxData[ \(Trace[length[Range[10]], length[_]]\)], "Input", AspectRatioFixed->True], Cell[TextData[{ StyleBox["Another function that fits into this pattern is the built-in \ command ", FontFamily->"Times"], StyleBox["Max", FontFamily->"Times", FontWeight->"Bold"], StyleBox[" which determines the maximum element in a list. The value for \ the emtpy list here is a little tricky. ", FontFamily->"Times"] }], "Text", Evaluatable->False, AspectRatioFixed->True], Cell[BoxData[{ \(Clear[max]\), "\n", \(\(max[{}] = \(-\[Infinity]\);\)\), "\n", \(\(max[{xx___, a_}] := If[a > max[{xx}], a, max[{xx}]];\)\)}], "Input", AspectRatioFixed->True], Cell[BoxData[ \(max[{1, 2, 3, 123, \(-5\)}]\)], "Input", AspectRatioFixed->True], Cell[TextData[{ StyleBox["Needless to say, we could have chosen ", FontFamily->"Times"], StyleBox["Prepend", FontFamily->"Times", FontWeight->"Bold"], StyleBox[" as the fundamental operation to construct lists, rather than ", FontFamily->"Times"], StyleBox["Append", FontFamily->"Times", FontWeight->"Bold"], StyleBox[". It is always a most amusing exercise to show that on operation \ defined using, say, ", FontFamily->"Times"], StyleBox["Prepend", FontFamily->"Times", FontWeight->"Bold"], StyleBox[", produces the same output as its counterpart using ", FontFamily->"Times"], StyleBox["Append", FontFamily->"Times", FontWeight->"Bold"], StyleBox[". We'll return to this topic. ", FontFamily->"Times"] }], "Text", Evaluatable->False, AspectRatioFixed->True] }, Closed]], Cell[CellGroupData[{ Cell[" Reversing a List", "Subsection", Evaluatable->False, AspectRatioFixed->True, CellTags->"c:26"], Cell[TextData[{ StyleBox["The ", FontFamily->"Times"], StyleBox["Reverse", FontFamily->"Times", FontWeight->"Bold"], StyleBox[" operation in Mathematica flips a list around. Here is a mock-up. \ If the list is empty, return it unchanged. Otherwise, remove the last \ element, and prepend it to the result of recursively reversing the truncated \ list. \n\n", FontFamily->"Times"], StyleBox["Reversal Axioms", FontFamily->"Times", FontWeight->"Bold"], StyleBox[" (right)\n\t(1) ", FontFamily->"Times"], Cell[BoxData[ \(TraditionalForm\`rev(\ {}\ )\ = \ {}\)]], StyleBox["\n\t(2) ", FontFamily->"Times"], Cell[BoxData[ \(TraditionalForm\`rev(\ app(\ X, \ x\ ))\ = \ pre(\ rev(X), \ x\ )\)]], StyleBox["\nIn sloppy notation, writing the prepend/append operations as if \ they were multiplications, this would read\n\t", FontFamily->"Times"], Cell[BoxData[ \(TraditionalForm\`rev(\ X\ x\ )\ = \ x\ \ \(rev(X)\)\)]], StyleBox[".\nWe will stick with the more formal notation (which provides \ more detailed information, there is no distinction made between prepend and \ append in the sloppy form), but it may be very helpful to rewrite some of the \ arguments, to get a better feel for what is going on. \n\nThe operation \ described by the axioms is called right reversal since the rightmost element \ is moved to the left. Similar one can do left reversal. Here is a direct \ Mathematica implementation of these ideas. First, the clumsy version with \ if-then-else.", FontFamily->"Times"] }], "Text", Evaluatable->False, AspectRatioFixed->True], Cell["\<\ Clear[rev] rev[L_List] := \tIf[ L==={}, {}, Prepend[rev[Drop[L,-1]],Last[L]] ]\ \>", "Input", AspectRatioFixed->True], Cell["Then a definition by cases using pattern matching. ", "Text", Evaluatable->False, AspectRatioFixed->True], Cell[BoxData[{ \(Clear[rev]\), "\n", \(\(rev[{}] = {};\)\), "\n", \(rev[{x___, a_}] := Prepend[rev[{x}], a]\)}], "Input", AspectRatioFixed->True], Cell["Check that this really works:", "Text", Evaluatable->False, AspectRatioFixed->True], Cell[BoxData[{ \(rev[{}]\), "\n", \(rev[Range[5]]\), "\n", \(rev[Array[a\_# &, {10}]]\)}], "Input", AspectRatioFixed->True], Cell[BoxData[ \(\(Trace[rev[Range[5]], rev[___]]\ // \ Flatten\)\ // \ TableForm\)], "Input", AspectRatioFixed->True], Cell["\<\ Works. But how about left reversal where we peel off the first \ element, and attach it in front. This would be the natural thing to do if we \ consider lists to be built from the empty list by a sequence of Prepend \ operations. \ \>", "Text", Evaluatable->False, AspectRatioFixed->True], Cell[BoxData[{ \(Clear[ver]\), "\n", \(\(ver[{}] = {};\)\), "\n", \(ver[{b_, xx___}] := Append[ver[{xx}], b]\)}], "Input", AspectRatioFixed->True], Cell[BoxData[ \(ver[Range[5]]\)], "Input", AspectRatioFixed->True], Cell[TextData[{ StyleBox["Of course, if both implementations of reversal are correct, we \ should have for any list ", FontFamily->"Times"], Cell[BoxData[ \(TraditionalForm\`L\)]], "\n", StyleBox["\n\t ", FontFamily->"Times"], Cell[BoxData[ \(TraditionalForm\`ver(\ L\ )\ = \ rev(\ L\ )\)]], StyleBox[".", FontFamily->"Times", FontWeight->"Bold"], StyleBox["\n\nBut that requires proof. If you campare the traces, it is not \ so clear that the final result is the same (the intermediate results \ definitely are not). ", FontFamily->"Times"] }], "Text", Evaluatable->False, AspectRatioFixed->True], Cell[BoxData[ \(\(Trace[rev[Range[5]], rev[___]]\ // \ Flatten\)\ // \ TableForm\)], "Input", AspectRatioFixed->True], Cell[BoxData[ \(\(Trace[ver[Range[5]], ver[___]]\ // \ Flatten\)\ // \ TableForm\)], "Input", AspectRatioFixed->True], Cell["\<\ By the way, the system function is not a simple recursive \ implementation like the ones we have given.\ \>", "Text", Evaluatable->False, AspectRatioFixed->True], Cell[BoxData[ \(Trace[Reverse[Range[5]], Reverse[_]]\)], "Input", AspectRatioFixed->True] }, Closed]], Cell[CellGroupData[{ Cell[" Joining Lists", "Subsection", Evaluatable->False, AspectRatioFixed->True, CellTags->"c:27"], Cell[CellGroupData[{ Cell[" Definitions", "Subsubsection", Evaluatable->False, AspectRatioFixed->True, CellTags->"c:28"], Cell[TextData[{ "The list operations considered so far all have a single input. Needless to \ say, the recursion machinery also works for more arguments. Typically, only \ one argument is changed in the recursive calls, the others remain fixed (so \ called dummy parameters). A typical examples is the ", StyleBox["Join", "SmallText"], " operation in Mathematica. It can be defined recursively in terms of the \ ", StyleBox["Append", "SmallText"], " operation as follows.\nLet ", Cell[BoxData[ \(TraditionalForm\`A = {a\_1, a\_2, ... , a\_k}\)]], " and ", Cell[BoxData[ \(TraditionalForm\`B = {b\_1, b\_2, ... , b\_s}\)]], " be two lists and define an operation ", Cell[BoxData[ \(TraditionalForm\`join[A, B]\)]], StyleBox[" as follows:\n\n\t", FontFamily->"Times"], Cell[BoxData[ \(TraditionalForm\`join(A, B)\ = \ {a\_1, a\_2, ... , a\_k, b\_1, b\_2, ... , b\_s}\)]], "\n\t", StyleBox["\nOf course, this is a definition only in the eye of the human \ beholder, for a machine we need a more precise definition.\n", FontFamily->"Times"], StyleBox["Join Axioms:", FontFamily->"Times", FontWeight->"Bold"], StyleBox["\n\t(1) ", FontFamily->"Times"], Cell[BoxData[ \(TraditionalForm\`\(\(\ \)\(join(\ A, \ {}\ )\ = \ A\)\)\)]], StyleBox[",", FontFamily->"Times", FontWeight->"Bold"], StyleBox["\n\t(2) ", FontFamily->"Times"], Cell[BoxData[ \(TraditionalForm\`\(\(\ \)\(join(\ A, \ app(\ B, \ b\ ))\ = \ app(\ join(A, B), \ b\ )\)\)\)]], StyleBox[".\n\t\n", FontFamily->"Times", FontWeight->"Bold"], StyleBox["From these axioms it follows for example that ", FontFamily->"Times"], Cell[BoxData[ \(TraditionalForm\`join(\ A, \ {b}\ )\ = \ app(\ A, \ b\ )\)]], StyleBox[". The argument is:\n", FontFamily->"Times"], Cell[BoxData[ \(TraditionalForm\`join(\ A, \ {b}\ )\ = \ \(join(\ A, \ app({}, b)\ )\ = \ \(app(\ join(A, {}), \ b\ )\ = \ app(\ A, \ b\ )\)\)\)]], ".", StyleBox["\nThis type of reasoning will be typical in what follows. The \ argument consists of a sequence of rather simple steps. Each step \ individually is rather obvious, the problem in general is to find the right \ sequence of steps to establish the claim in question. \n\nHere is a almost \ verbatim implementation of this method:", FontFamily->"Times"] }], "Text", Evaluatable->False, AspectRatioFixed->True], Cell["\<\ Clear[join] join[A_List,{}] := A; join[A_List,B_List] := \tAppend[ join[A,Drop[B,-1]], Last[B] ];\ \>", "Input", AspectRatioFixed->True], Cell[BoxData[ \(join[{a, b, c}, {2, 7}\ ]\)], "Input", AspectRatioFixed->True], Cell[TextData[{ "Works fine, but is a little clumsy. Again, we can use the pattern matching \ machinery in Mathematica to simplify this algorithm a bit. In particular, we \ can get rid of the ", StyleBox["Drop", "SmallText"], " and ", StyleBox["Last", "SmallText"], " operations. " }], "Text", Evaluatable->False, AspectRatioFixed->True], Cell["\<\ Clear[join] join[{xx___},{}] := {xx}; join[{xx___},{yy___,y_}] := Append[join[{xx},{yy}],y];\ \>", "Input", AspectRatioFixed->True], Cell[BoxData[ \(join[{a, b, c}, Range[3]]\)], "Input", AspectRatioFixed->True], Cell["\<\ The pattern matching takes care of distinguishing the two cases, \ and of splitting the second list in the proper way. In many ways, this is a \ cleaner solution than the first. The first argument is never changed, as the trace shows. \ \>", "Text", Evaluatable->False, AspectRatioFixed->True], Cell[BoxData[ \(Trace[join[{a, b, c}, Range[3]], join[__]]\)], "Input", AspectRatioFixed->True] }, Closed]], Cell[CellGroupData[{ Cell[" Crucial Properties", "Subsubsection", Evaluatable->False, AspectRatioFixed->True, CellTags->"c:29"], Cell[TextData[{ StyleBox["The basic properties of the recursive join operation are \ summarized in the next claim. We will formally prove the claim in the \ section on induction. \n\n", FontFamily->"Times"], StyleBox["Lemma", FontFamily->"Times", FontWeight->"Bold"], StyleBox[": For all lists ", FontFamily->"Times"], Cell[BoxData[ \(TraditionalForm\`A\)]], StyleBox[" and ", FontFamily->"Times"], Cell[BoxData[ \(TraditionalForm\`B\)]], StyleBox[" we have\n(1) ", FontFamily->"Times"], Cell[BoxData[ \(TraditionalForm\`\(\(\ \)\(join(\ A, \ {}\ )\ = \ A\)\)\)]], StyleBox[",\n(2) ", FontFamily->"Times"], Cell[BoxData[ \(TraditionalForm\`join(\ {}, \ A)\ = \ A\)]], StyleBox[",\n(3) Associativity: ", FontFamily->"Times"], Cell[BoxData[ \(TraditionalForm\`join(\ A, \ join(\ B, \ C\ ))\ = \ join(\ join(\ A, \ B\ ), \ C\ )\)]], StyleBox[".\n\nOne important consequence of associativity is that it makes \ sense to allow more than two inputs. For an associative function ", FontFamily->"Times"], Cell[BoxData[ \(TraditionalForm\`f\)]], " w", StyleBox["e can define ", FontFamily->"Times"], Cell[BoxData[ \(TraditionalForm\`f(x, y, z)\ = \ f(f(x, y), z)\)]], ", ", StyleBox[" ", FontFamily->"Times"], Cell[BoxData[ \(TraditionalForm\`f(x, y, z, u)\ = \ f(f(f(x, y), z), u)\)]], ", and so forth.\nWe have chosen to group the elements in the inputs to the \ left, but since ", Cell[BoxData[ \(TraditionalForm\`f\)]], " is associative we would get the same result if we grouped to the right, \ or in any random fashion. \nThis is used in Mathematica for example in the ", StyleBox["Plus", "SmallText"], " function. " }], "Text", Evaluatable->False, AspectRatioFixed->True], Cell[BoxData[ \(a + b + c + d\)], "Input", AspectRatioFixed->True], Cell[TextData[{ "In order to be incompatible with standard mathematical notation, WRI has \ chosen to use the attribute ", StyleBox["Flat", "SmallText"], " to represent associative functions. Never mind the other ones for the \ time being. " }], "Text", Evaluatable->False, AspectRatioFixed->True], Cell[BoxData[ \(Attributes[Plus]\)], "Input", AspectRatioFixed->True] }, Closed]] }, Closed]], Cell[CellGroupData[{ Cell[" IntList: nested lists of integers", "Subsection", Evaluatable->False, AspectRatioFixed->True, CellTags->"c:30"], Cell[CellGroupData[{ Cell[" The Axioms", "Subsubsection", Evaluatable->False, AspectRatioFixed->True, CellTags->"c:31"], Cell[TextData[{ StyleBox["Recursion is particularly useful to describe nested data \ structures such as lists. Suppose we want to make precise the notion of lists \ of lists of lists ... of integers. \nI.e., we are interested in lists whose \ elements are either lists of the same type, or simply integers. As we will \ see later when we implement data structures in C++, it is always a good idea \ to be very careful in one's basic definitions. We can define a data type ", FontFamily->"Times"], StyleBox["IntList", FontFamily->"Times", FontWeight->"Bold"], StyleBox[" by the following conditions. \n\nNote that this approach is \ slightly different from the one taken in the last section. There are usually \ several natural definitions for any interesting data structure. Which is \ better depends on context.\n \n", FontFamily->"Times"], StyleBox[" IntList Axioms", FontFamily->"Times", FontWeight->"Bold"], StyleBox["\n (1) every list ", FontFamily->"Times"], Cell[BoxData[ \(TraditionalForm\`{x\_1, \ ... , \ x\_k}\)]], StyleBox[" is an ", FontFamily->"Times"], StyleBox["IntList", FontFamily->"Times", FontWeight->"Bold"], StyleBox[", \n where each ", FontFamily->"Times"], Cell[BoxData[ \(TraditionalForm\`x\_i\)]], " is an ", StyleBox["integer, ", FontFamily->"Times"], Cell[BoxData[ \(TraditionalForm\`k\ \[GreaterEqual] \ 0\)]], ",", StyleBox["\n (2) for any sequence ", FontFamily->"Times"], Cell[BoxData[ \(TraditionalForm\`L\_1, \[Ellipsis], L\_n\)]], " ", StyleBox["where each ", FontFamily->"Times"], Cell[BoxData[ \(TraditionalForm\`L\_i\)]], StyleBox[" is an of integer or an ", FontFamily->"Times"], StyleBox["IntList", FontFamily->"Times", FontWeight->"Bold"], StyleBox[", \n ", FontFamily->"Times"], Cell[BoxData[ \(TraditionalForm\`\(\(\ \)\({L\_1, \[Ellipsis], \ L\_n}\)\)\)]], StyleBox[" is again an ", FontFamily->"Times"], StyleBox["IntList", FontFamily->"Times", FontWeight->"Bold"], StyleBox[". \n \nAgain, there is another tacit condition here: nothing \ else is an ", FontFamily->"Times"], StyleBox["IntList", FontFamily->"Times", FontWeight->"Bold"], StyleBox[". Also, the decomposition is again unique: ", FontFamily->"Times"], Cell[BoxData[ \(TraditionalForm\`\(\(\ \)\({L\_1, \[Ellipsis], \ L\_n}\)\)\)]], StyleBox["= ", FontFamily->"Times"], Cell[BoxData[ \(TraditionalForm\`\(\(\ \)\({K\_1, \[Ellipsis], \ K\_m}\)\)\)]], StyleBox[" implies ", FontFamily->"Times"], Cell[BoxData[ \(TraditionalForm\`n\ = \ m\)]], StyleBox[" and ", FontFamily->"Times"], Cell[BoxData[ \(TraditionalForm\`L\_i = K\_i\)]], StyleBox[" for all ", FontFamily->"Times"], Cell[BoxData[ \(TraditionalForm\`i\ = \ 1, ... , n\)]], StyleBox[". \n\nFor example, ", FontFamily->"Times"], Cell[BoxData[ \(TraditionalForm\`\(\(\ \)\({\ 1, \ 2, \ {3, \ 4}\ }\)\(\ \)\)\)]], StyleBox[" is an ", FontFamily->"Times"], StyleBox["IntList", FontFamily->"Times", FontWeight->"Bold"], StyleBox[" since\n1) 3 and 4 are IntLists\n2) from 1), {3,4} is an \ IntList\n3) 1 and 2 are IntLists\n4) from 2) and 3), {1,2,{3,4}} is an \ IntList.\n", FontFamily->"Times"] }], "Text", Evaluatable->False, AspectRatioFixed->True], Cell[TextData[{ StyleBox["Again, this formal description of a type of list facilitates a \ whole class of recursive function definitions on lists. This time, in order \ to define a function ", FontFamily->"Times"], Cell[BoxData[ \(TraditionalForm\`f\)]], StyleBox[" on all lists, you have to \n\n(1) specify ", FontFamily->"Times"], Cell[BoxData[ \(TraditionalForm\`\(\(\ \)\(f({x\_1, \[Ellipsis], x\_n})\)\(\ \)\)\)]], StyleBox[" for integers ", FontFamily->"Times"], Cell[BoxData[ \(TraditionalForm\`x\_i\)]], StyleBox[", \n(2) specify ", FontFamily->"Times"], Cell[BoxData[ \(TraditionalForm\`f({L\_1, \[Ellipsis], L\_n})\)]], StyleBox[" where all the ", FontFamily->"Times"], Cell[BoxData[ \(TraditionalForm\`L\_i\)]], StyleBox[" are either ", FontFamily->"Times"], StyleBox["IntLists", FontFamily->"Times", FontWeight->"Bold"], StyleBox[" or integers,\n assuming that a value for ", FontFamily->"Times"], Cell[BoxData[ \(TraditionalForm\`f(L\_i)\)]], StyleBox[" has already been defined.\n ", FontFamily->"Times"] }], "Text", Evaluatable->False, AspectRatioFixed->True] }, Closed]], Cell[CellGroupData[{ Cell[" Example: Depth", "Subsubsection", Evaluatable->False, AspectRatioFixed->True, CellTags->"c:32"], Cell[TextData[{ "The built-in ", StyleBox["Depth", "SmallText"], " function is a typical example. It determines how deeply nested a given \ list (or, in fact, any expression) is. " }], "Text", Evaluatable->False, AspectRatioFixed->True], Cell[BoxData[{ \(Depth[{1, 2, 3}]\), "\n", \(Depth[{1, 2, {3, 4}, 5}]\), "\n", \(Depth[{1, 2, {3, {4}}, 5}]\)}], "Input", AspectRatioFixed->True], Cell[TextData[{ StyleBox["A lot of people would argue that the depth of an atom such as 2 \ should be 0, since there is nothing nested inside. But, our friends at WRI \ have decided that it's 1. \n\nHere is a little mock-up of this function. We \ will only cope with ", FontFamily->"Times"], StyleBox["IntLists", FontFamily->"Times", FontWeight->"Bold"], StyleBox[" here, i.e., lists built from integer atoms. Note the definition \ by cases below. The first definition takes care of lists containing only \ atoms. ", FontFamily->"Times"] }], "Text", Evaluatable->False, AspectRatioFixed->True], Cell[BoxData[{ \(Clear[depth]\), "\n", \(\(depth[{xx___Integer}] := 2;\)\), "\n", \(\(depth[LL_List] := Max[depth /@ Cases[LL, _List]] + 1;\)\)}], "Input", AspectRatioFixed->True], Cell[BoxData[{ \(depth[{1, 2, 3}]\), "\n", \(depth[{1, 2, {4, 5}, 3}]\), "\n", \(depth[{1, 2, {4, {5}}, 3}]\)}], "Input", AspectRatioFixed->True], Cell[TextData[{ "This example shows that sometimes it is more convenient not to take \ definitions too seriously. It would be much easier to define depth not just \ on lists, but also on integer atoms. Then we could avoid the selection \ operation. The real ", StyleBox["Depth", "SmallText"], " function is defined on any expression at any rate." }], "Text", Evaluatable->False, AspectRatioFixed->True], Cell[BoxData[ \(Depth[5]\)], "Input", AspectRatioFixed->True], Cell["\<\ Clear[depth] depth[x_Integer] := 1; depth[LL_List] := Max[Map[depth,LL]] + 1;\ \>", "Input", AspectRatioFixed->True], Cell[BoxData[{ \(depth[3]\), "\n", \(depth[{1, 2, 3}]\), "\n", \(depth[{1, 2, {4, 5}, 3}]\), "\n", \(depth[{1, 2, {4, {5}}, 3}]\)}], "Input", AspectRatioFixed->True], Cell[TextData[{ StyleBox["In general, our second, somewhat dirty solution is often much \ easier to handle in practice: define the function also on the atoms, here \ the integers. Then it suffices to do the following to define a function ", FontFamily->"Times"], Cell[BoxData[ \(TraditionalForm\`f\)]], StyleBox[" for all IntLists:\n\n(1) specify ", FontFamily->"Times"], Cell[BoxData[ \(TraditionalForm\`f(x)\)]], StyleBox[" for integers ", FontFamily->"Times"], Cell[BoxData[ \(TraditionalForm\`x\)]], StyleBox[", \n(2) specify ", FontFamily->"Times"], Cell[BoxData[ \(TraditionalForm\`f({L\_1, \[Ellipsis], L\_n})\)]], StyleBox[" where all the ", FontFamily->"Times"], Cell[BoxData[ \(TraditionalForm\`L\_i\)]], StyleBox[" are either ", FontFamily->"Times"], StyleBox["IntLists", FontFamily->"Times", FontWeight->"Bold"], StyleBox[" or integers,\n assuming that a value for ", FontFamily->"Times"], Cell[BoxData[ \(TraditionalForm\`f(L\_i)\)]], StyleBox[" has already been defined.", FontFamily->"Times"] }], "Text", Evaluatable->False, AspectRatioFixed->True] }, Closed]], Cell[CellGroupData[{ Cell[" Example: Summing up Lists", "Subsubsection", Evaluatable->False, AspectRatioFixed->True, CellTags->"c:33"], Cell[TextData[{ StyleBox["Here is an example of an operation that is defined by recursion: \ adding up all the elements in a list. We would like a function ", FontFamily->"Times"], StyleBox["listSum", FontFamily->"Times", FontWeight->"Bold"], StyleBox[" such that on input ", FontFamily->"Times"] }], "Text", Evaluatable->False, AspectRatioFixed->True], Cell[BoxData[ \(L = {1, 2, {3, {4, 5}, {{6}}, 7, 8}}\)], "Input", AspectRatioFixed->True], Cell[TextData[{ "we get output 36. Note that ", Cell[BoxData[ \(TraditionalForm\`L[\([3]\)]\)]], " is a list of length ", Cell[BoxData[ \(TraditionalForm\`5\ > \ Length[L]\)]], ", so simple induction on the length of a list would not work here. \n\nWe \ use the trick from the last section, and define listSum also for integer \ atoms. For compound lists, we apply it recursively, and add the resulting \ partial sums together. " }], "Text", Evaluatable->False, AspectRatioFixed->True], Cell["\<\ Clear[listSum] listSum[x_Integer] := x; listSum[LL_List] := Plus@@Map[listSum,LL];\ \>", "Input", AspectRatioFixed->True], Cell[BoxData[ \(listSum[L]\)], "Input", AspectRatioFixed->True], Cell[TextData[{ StyleBox["Just for the record, there is a more efficient way of doing this \ in Mathematica. First, we can flatten out the ", FontFamily->"Times"], StyleBox["IntList", FontFamily->"Times", FontWeight->"Bold"], StyleBox[" into a plain list of integers, and then we can Apply Plus. Note \ that associativity of addition is crucial for the two approaches to yield the \ same result. ", FontFamily->"Times"] }], "Text", Evaluatable->False, AspectRatioFixed->True], Cell[BoxData[ \(listSum2[L_List] := Plus @@ Flatten[L]\)], "Input", AspectRatioFixed->True], Cell[BoxData[ \(listSum2[L]\)], "Input", AspectRatioFixed->True], Cell[TextData[StyleBox["Needless to say, the Flatten operation itself is \ defined recursively, so this trick does not eliminate recursion, it just \ hides it.", FontFamily->"Times"]], "Text", Evaluatable->False, AspectRatioFixed->True] }, Closed]] }, Closed]], Cell[CellGroupData[{ Cell[TextData[{ " Why ", Cell[BoxData[ \(TraditionalForm\`2\ + \ 2\ = \ 4\)]], ". (optional)" }], "Subsection", Evaluatable->False, AspectRatioFixed->True, CellTags->"c:34"], Cell["\<\ \tThe natural numbers were made by god, \teverything else is made by humans. \t\t\t\t\tL. Kronecker \t\t\t\t\t\t\t\t \ \>", "Text", Evaluatable->False, AspectRatioFixed->True], Cell[TextData[{ StyleBox["Kronecker is a famous 19th century number theorist who thought \ that numbers, and in particular natural numbers are the only truly \ fundamental building blocks of mathematics, everything else can be \ constructed from them. We will now show how to take the natural numbers \ themselves apart. This last example is quite important in the theory of \ computation. It shows that, in the presence of recursion, addition can be \ expressed in terms of the more primitive operation successor (i.e., adding 1 \ to the argument). This approach does not yield practical algorithms for the \ integers; it is much better to represent numbers by sequences of digits, and \ manipulate the digits directly. However, similar techniques allow one to \ define complicated operations on data structures starting with just a few \ primitive operations. We will return to this topic when we implement lists in \ C++.\n\nThe idea is that we can think of the non-negative integers also as \ some kind of recursively defined data structure. Let's call these numbers ", FontFamily->"Times"], StyleBox["Nat", FontFamily->"Times", FontWeight->"Bold"], StyleBox[". The starting point is ", FontFamily->"Times"], StyleBox["0", FontFamily->"Times", FontWeight->"Bold"], StyleBox[", an indecomposable atom, and given any number ", FontFamily->"Times"], Cell[BoxData[ \(TraditionalForm\`n\)]], StyleBox[" there is another one ", FontFamily->"Times"], Cell[BoxData[ \(TraditionalForm\`S(n)\)]], StyleBox[", the successor of ", FontFamily->"Times"], Cell[BoxData[ \(TraditionalForm\`n\)]], StyleBox[". There are two construction rules, and a rule that says that \ only the objects described by these two rules are admissible.\n ", FontFamily->"Times"] }], "Text", Evaluatable->False, AspectRatioFixed->True], Cell[TextData[{ StyleBox[" ", FontFamily->"Times"], StyleBox["Nat Axioms", FontFamily->"Times", FontWeight->"Bold"], StyleBox["\n\t (N1) ", FontFamily->"Times"], StyleBox["0", FontFamily->"Times", FontWeight->"Bold"], StyleBox[" is in ", FontFamily->"Times"], StyleBox["Nat,", FontFamily->"Times", FontWeight->"Bold"], StyleBox["\n\t (N2) for any ", FontFamily->"Times"], StyleBox[" ", FontFamily->"Times", FontWeight->"Bold"], Cell[BoxData[ \(TraditionalForm\`n\)]], StyleBox[" in ", FontFamily->"Times"], StyleBox["Nat", FontFamily->"Times", FontWeight->"Bold"], StyleBox[", ", FontFamily->"Times"], Cell[BoxData[ \(TraditionalForm\`S(n)\)]], StyleBox[" is again in ", FontFamily->"Times"], StyleBox["Nat", FontFamily->"Times", FontWeight->"Bold"], StyleBox[". \n\t (N3) Nothing else is in ", FontFamily->"Times"], StyleBox["Nat", FontFamily->"Times", FontWeight->"Bold"], StyleBox[".", FontFamily->"Times"] }], "Text", Evaluatable->False, AspectRatioFixed->True], Cell[TextData[{ StyleBox["The third condition appears to be somewhat more vague than the \ other two, but it can be made precise: ", FontFamily->"Times"], StyleBox["Nat", FontFamily->"Times", FontWeight->"Bold"], StyleBox[" is the least set (in the sense of set inclusion) that satisfies \ conditions (N1) and (N2). \nThis approach is very similar to the \ representation of natural numbers as von Neumann ordinals ", FontFamily->"Times"], Cell[BoxData[ \(TraditionalForm\`N\_n = \ {N\_0, \[Ellipsis], N\_\(n - 1\)}\)]], " ", StyleBox["that we saw a while ago. The difference is that the purpose of \ that construction was to show that sets are powerful enough to express \ natural numbers. Here, we are not really interested in what exactly the \ natural numbers are, we are just trying to pin down their essential \ properties (we only care about the abstract data type, but not about any \ concrete implementation).", FontFamily->"Times"] }], "Text", Evaluatable->False, AspectRatioFixed->True], Cell[TextData[{ StyleBox["For example, ", FontFamily->"Times"], StyleBox["3", FontFamily->"Times", FontWeight->"Bold"], StyleBox[" corresponds to ", FontFamily->"Times"], Cell[BoxData[ \(TraditionalForm\`\(S\^3\)(0)\)]], StyleBox[". From this point of view, natural numbers are indeed deeply \ nested. \n", FontFamily->"Times"] }], "Text", Evaluatable->False, AspectRatioFixed->True], Cell["\<\ Given this one successor function, and recursion, we can now build \ all the standard arithmetic functions such as addition and multiplication. \ \ \>", "Text", Evaluatable->False, AspectRatioFixed->True], Cell[BoxData[{ \(Clear[add, S]\), "\n", \(\(add[x_, 0] = x;\)\), "\n", \(\(add[x_, S[n_]] := S[add[x, n]];\)\)}], "Input", AspectRatioFixed->True], Cell[BoxData[ \(add[S[S[0]], S[S[S[S[S[0]]]]]]\)], "Input", AspectRatioFixed->True], Cell["\<\ This is rather hard to read and write. Let's write conversion \ functions to and from successor notation. \ \>", "Text", Evaluatable->False, AspectRatioFixed->True], Cell[BoxData[{ \(\(toS[n_] := Nest[S, 0, n];\)\), "\n", \(\(fromS[0] := 0;\)\), "\n", \(\(fromS[S[xx_]] := fromS[xx] + 1;\)\)}], "Input", AspectRatioFixed->True], Cell[BoxData[{ \(add[toS[2], toS[5]]\), "\n", \(fromS[%]\)}], "Input", AspectRatioFixed->True], Cell["So, 2 plus 5 is 7. Good. ", "Text", Evaluatable->False, AspectRatioFixed->True], Cell[BoxData[ \(\(Trace[add[toS[2], toS[5]], add[_, _]]\ // \ Flatten\)\ // \ TableForm\)], "Input", AspectRatioFixed->True], Cell["\<\ One more example that shows that complicated operations can be built from \ simpler ones using recursion: multiplication. Multiplication turns out to be \ nothing but a complicated sequence of applications of the Sessor function. \ \ \>", "Text", Evaluatable->False, AspectRatioFixed->True], Cell[BoxData[{ \(Clear[mult]\), "\n", \(\(mult[x_, 0] = 0;\)\), "\n", \(\(mult[x_, S[n_]] := add[mult[x, n], x];\)\)}], "Input", AspectRatioFixed->True], Cell[BoxData[{ \(mult[toS[3], toS[5]]\), "\n", \(fromS[%]\)}], "Input", AspectRatioFixed->True], Cell[BoxData[ \(Trace[mult[toS[3], toS[5]], mult[__]]\)], "Input", AspectRatioFixed->True], Cell[BoxData[ \(Trace[mult[toS[3], toS[5]], S[_]]\)], "Input", AspectRatioFixed->True], Cell["\<\ And, lastly, exponentiation. We follow exactly the same pattern. \ \ \>", "Text", Evaluatable->False, AspectRatioFixed->True], Cell[BoxData[{ \(Clear[exp]\), "\n", \(\(exp[x_, 0] = S[0];\)\), "\n", \(\(exp[x_, S[n_]] := mult[exp[x, n], x];\)\)}], "Input", AspectRatioFixed->True], Cell[BoxData[{ \(exp[toS[2], toS[3]]\), "\n", \(fromS[%]\)}], "Input", AspectRatioFixed->True], Cell[BoxData[ \(Trace[exp[toS[2], toS[3]], add[__]]\)], "Input", AspectRatioFixed->True], Cell["\<\ This is just the tip of an iceberg. We can define a whole sequence \ of functions following this pattern, functions that grow more and more \ rapidly. \ \>", "Text", Evaluatable->False, AspectRatioFixed->True], Cell[CellGroupData[{ Cell["Comment", "Subsubsection", Evaluatable->False, AspectRatioFixed->True, CellTags->"c:35"], Cell[TextData[{ StyleBox["The two axioms for the construction of ", FontFamily->"Times"], StyleBox["Nat", FontFamily->"Times", FontWeight->"Bold"], StyleBox[" are not really enough to get off the ground. We need to know a \ little more, for example, ", FontFamily->"Times"], Cell[BoxData[ \(TraditionalForm\`0\ \[NotEqual] \ S(x)\)]], StyleBox[" for all ", FontFamily->"Times"], Cell[BoxData[ \(TraditionalForm\`x\)]], StyleBox[". Or, ", FontFamily->"Times"], Cell[BoxData[ \(TraditionalForm\`S( x)\ = \ \(\(S(y)\)\ \ \[DoubleLongRightArrow]\ x\ = \ y\)\)]], StyleBox[". The collection of all these basic facts is called the ", FontFamily->"Times"], StyleBox["Peano Axioms", FontFamily->"Times", FontColor->RGBColor[0, 0, 1]], StyleBox[" for the natural numbers. These axioms are only about 100 years \ old, so before the turn of the century mathematicians were arguing about \ numbers without ever feeling the need to spell out the basics in such great \ detail. The study of axiom systems, proofs, computability and such like \ belongs to a relatively new area of mathematics, viz. mathematical logic. It \ is surprising that this very careful treatment has become important many \ years later in computer science. In fact, some people claim that logic is to \ computer science what analyis was to physics. \n\nThe full collection of \ Peano Axioms can be found in the printed handout. ", FontFamily->"Times"] }], "Text", Evaluatable->False, AspectRatioFixed->True] }, Closed]] }, Closed]] }, Closed]], Cell[CellGroupData[{ Cell["Trees", "Section", Evaluatable->False, AspectRatioFixed->True, CellTags->"c:36"], Cell[" Definition by Pictures", "Subsection", Evaluatable->False, AspectRatioFixed->True, CellTags->"c:37"], Cell[CellGroupData[{ Cell[" A Nonrecursive Definition", "Subsection", Evaluatable->False, AspectRatioFixed->True, CellTags->"c:38"], Cell[CellGroupData[{ Cell["Binary Trees", "Subsubsection", Evaluatable->False, AspectRatioFixed->True, CellTags->"c:39"], Cell[TextData[{ StyleBox["We consider the set Bin of all sequences over ", FontFamily->"Times"], Cell[BoxData[ \(TraditionalForm\`\([2]\)\ = \ {1, 2}\)]], StyleBox[". A sequence ", FontFamily->"Times"], Cell[BoxData[ \(TraditionalForm\`x\)]], " is a ", StyleBox["prefix", FontColor->RGBColor[0, 0, 1]], " of a sequence ", Cell[BoxData[ \(TraditionalForm\`y\)]], " if there is a sequence ", Cell[BoxData[ \(TraditionalForm\`z\)]], " (possibly empty) such that ", Cell[BoxData[ \(TraditionalForm\`y\ = \ x\ \[CirclePlus]\ z\)]], " (where ", Cell[BoxData[ \(TraditionalForm\`\[CirclePlus]\)]], " denotes the catenation operation). A set ", Cell[BoxData[ \(TraditionalForm\`T\ \[SubsetEqual] \ Bin\)]], " is a (ordered binary) tree if it is closed with respect to prefixes:\n\t\ \t", Cell[BoxData[ \(TraditionalForm\`y\ \ \[Element] \ T\)]], ", ", Cell[BoxData[ \(TraditionalForm\`x\)]], " a prefix of ", Cell[BoxData[ \(TraditionalForm\`y\)]], " \[DoubleLongRightArrow]", StyleBox[" ", FontFamily->"Times"], Cell[BoxData[ \(TraditionalForm\`x\ \[Element] \ T\)]], ".", StyleBox["\nWe are mostly interested in the case where ", FontFamily->"Times"], Cell[BoxData[ \(TraditionalForm\`T\)]], " is finite, but the definition also makes sense for infinite trees. ", StyleBox["The elements of ", FontFamily->"Times"], Cell[BoxData[ \(TraditionalForm\`T\)]], " are referred to as ", StyleBox["nodes", FontColor->RGBColor[0, 0, 1]], ". Unless ", Cell[BoxData[ \(TraditionalForm\`T\)]], " is empty, it always contains the node \[Epsilon]", StyleBox[" (the empty sequence), called the ", FontFamily->"Times"], StyleBox["root", FontFamily->"Times", FontColor->RGBColor[0, 0, 1]], StyleBox[" of the tree. ", FontFamily->"Times"], "Node ", Cell[BoxData[ \(TraditionalForm\`y\)]], " is a ", StyleBox["child", FontColor->RGBColor[0, 0, 1]], " of node ", Cell[BoxData[ \(TraditionalForm\`x\)]], " if ", Cell[BoxData[ \(TraditionalForm\`y = x\ 1\)]], " or ", Cell[BoxData[ \(TraditionalForm\`y\ = \ x\ 2\)]], ". Conversely, ", Cell[BoxData[ \(TraditionalForm\`x\)]], " is the ", StyleBox["parent", FontColor->RGBColor[0, 0, 1]], " of ", Cell[BoxData[ \(TraditionalForm\`y\)]], ". ", StyleBox["A node that has no children is called a ", FontFamily->"Times"], StyleBox["leaf", FontFamily->"Times", FontColor->RGBColor[0, 0, 1]], StyleBox[" , all other nodes are called ", FontFamily->"Times"], StyleBox["internal", FontFamily->"Times", FontColor->RGBColor[0, 0, 1]], StyleBox[" nodes. For a node ", FontFamily->"Times"], Cell[BoxData[ \(TraditionalForm\`x\)]], " we refer to ", Cell[BoxData[ \(TraditionalForm\`\(\(|\)\(\ \)\(x\)\(|\)\)\)]], ", the length of the sequence, as the ", StyleBox["depth", FontColor->RGBColor[0, 0, 1]], " of the node. The depth of the tree is the maximum of all the depths of \ the nodes. It is easy to see that this is the same as the maximum depth of \ all leaves. " }], "Text", Evaluatable->False, AspectRatioFixed->True], Cell[TextData[{ StyleBox["In a finite tree, every node of the tree lies between the root \ and a leaf in the following sense. For any leaf ", FontFamily->"Times"], Cell[BoxData[ \(TraditionalForm\`x\)]], " t", StyleBox["here is a unique sequence of nodes \n\t\t", FontFamily->"Times"], Cell[BoxData[ \(TraditionalForm\`\[Epsilon]\ = \ x\_0, \ x\_1, \ \[Ellipsis], \ x\_\(\(\ \)\(d\)\)\ = \ x\)]], StyleBox["\nwhere ", FontFamily->"Times"], Cell[BoxData[ \(TraditionalForm\`x\_\(i + 1\)\)]], " is a child of ", Cell[BoxData[ \(TraditionalForm\`x\_i\)]], ". This sequence is a ", StyleBox["branch", FontColor->RGBColor[0, 0, 1]], " in the tree. The length of the branch is the depth of the leaf. Every \ node in the tree lies on at least one branch. ", StyleBox["\nGiven ", FontFamily->"Times"], Cell[BoxData[ \(TraditionalForm\`x\)]], ", the branch is trivial to construct: ", Cell[BoxData[ \(TraditionalForm\`x\_i\)]], " is the initial segment of length ", Cell[BoxData[ \(TraditionalForm\`i\)]], " of ", Cell[BoxData[ \(TraditionalForm\`x\)]], ". " }], "Text", Evaluatable->False, AspectRatioFixed->True], Cell[TextData[{ StyleBox["In most applications, the nodes carry some additional \ information. This can be modeled in terms of a labelling function ", FontFamily->"Times"], Cell[BoxData[ \(TraditionalForm\`\(\(\ \)\(\[Lambda]\ : \ T\ \[LongRightArrow]\ A\)\)\)]], " where ", Cell[BoxData[ \(TraditionalForm\`A\)]], " is the set of all possible labels. Sometimes the internal nodes carry \ no information, only the leaves do. " }], "Text", Evaluatable->False, AspectRatioFixed->True] }, Closed]], Cell[CellGroupData[{ Cell["Generalizations", "Subsubsection", Evaluatable->False, AspectRatioFixed->True, CellTags->"c:40"], Cell[TextData[{ StyleBox["How can we generalize the binary trees from the last section? \ One obvious generalization is to consider sequences over ", FontFamily->"Times"], Cell[BoxData[ \(TraditionalForm\`\([k]\)\ = \ {1, \[Ellipsis], k}\)]], " rather than just ", Cell[BoxData[ \(TraditionalForm\`{1, 2}\)]], ". ", StyleBox["This produces ", FontFamily->"Times"], StyleBox["k-ary", FontFamily->"Times", FontColor->RGBColor[0, 0, 1]], StyleBox[" trees. A ", FontFamily->"Times"], StyleBox["full k-ary", FontFamily->"Times", FontColor->RGBColor[0, 0, 1]], StyleBox[" tree is a k-ary tree where every node has exactly k children, or \ none at all. A ", FontFamily->"Times"], StyleBox["complete k-ary", FontFamily->"Times", FontColor->RGBColor[0, 0, 1]], StyleBox[" tree is a full k-ary tree all of whose branches have the same \ length. ", FontFamily->"Times"] }], "Text", Evaluatable->False, AspectRatioFixed->True], Cell[TextData[{ StyleBox["Actually, we can push things one step further: let ", FontFamily->"Times"], Cell[BoxData[ \(TraditionalForm\`T\)]], " be a set of sequences over ", Cell[BoxData[ \(TraditionalForm\`\(\[DoubleStruckCapitalN]\^+\)\)]], ", the positive natural numbers, closed under prefixes. This models a tree \ where the number of children at each node is potentially unbounded, and may \ be infinite. For example, ", Cell[BoxData[ \(TraditionalForm\`T\ = \ {\ \[Epsilon], \ 1, \ 2, \ \[Ellipsis], n, \ \[Ellipsis]\ }\)]], " is a tree of depth 1 where the root has infinitely many children. Note \ that ", StyleBox["Mathematica", FontSlant->"Italic"], " expressions are finite trees of exactly this type: every node has a \ finite but not a priori bounded number of children. " }], "Text", Evaluatable->False, AspectRatioFixed->True], Cell[TextData[{ StyleBox["Note that we still can talk about branches in an infinite tree, \ the only difference is that the may be infinite sequences rather than finite \ ones. Here is food for thought: the complete infinite tree ", FontFamily->"Times"], Cell[BoxData[ \(TraditionalForm\`T\ = \ Bin\)]], " is countable (there are only countably many nodes), but it has \ uncountably many branches. Proof by diagonalization." }], "Text", Evaluatable->False, AspectRatioFixed->True] }, Closed]] }, Closed]], Cell[CellGroupData[{ Cell[" A Recursive Definition", "Subsection", Evaluatable->False, AspectRatioFixed->True, CellTags->"c:41"], Cell[TextData[{ StyleBox["Again, the nonrecursive definition is a bit static. If one is \ interested in trees as a dynamic structure, a recursive definition is \ preferable: start with basic trees, and build more complicated ones from \ smaller ones. An informal description might look similar to the following. \n\ \n(1) A single node is a tree, the node is the root of this tree.\n(2) \ Given trees ", FontFamily->"Times"], Cell[BoxData[ \(TraditionalForm\`T\_1, \[Ellipsis], \ T\_n\)]], " we can from a new tree by choosing a new node ", Cell[BoxData[ \(TraditionalForm\`r\)]], " as the root, and attaching the roots of the ", Cell[BoxData[ \(TraditionalForm\`T\_i\)]], " as the children of ", Cell[BoxData[ \(TraditionalForm\`\(\(\ \)\(r\)\)\)]], ". \n\nNote that this description rules out the empty tree, but for most \ applications that is not a problem. \nFurthermore, this definition is \ bottom-up: to get a big tree, we start at the leaves, think of them as trees \ (of depth 0), collect them into a few trees of depth 1, collect those into \ trees of depth 2, and so forth. Clearly, there is an alternative top-down \ approach: start at the root, a tree of depth 0 with a single leaf. Attach \ children to the leaf, obtaining a tree of depth 1, with a number of leafes. \ Attach new children to these leaves, and so forth until the tree is finished. \ " }], "Text", Evaluatable->False, AspectRatioFixed->True], Cell[TextData[{ StyleBox["What are the crucial properties of a tree expressed in both \ definitions? A tree is a collection of nodes together with a parent/child \ relationship between the nodes. The parent/child relation satisfies the \ following conditions: \n\n(1) ", FontFamily->"Times"], StyleBox["Root Axiom. ", FontFamily->"Times", FontWeight->"Bold"], StyleBox["There is exactly one node that has no parent (the root).\n(2) ", FontFamily->"Times"], StyleBox["Unique Parent", FontFamily->"Times", FontWeight->"Bold"], StyleBox[". Every node other than the root has exactly one parent. \n(3) \ ", FontFamily->"Times"], StyleBox["Accessibility", FontFamily->"Times", FontWeight->"Bold"], StyleBox[". Every node has the root as an ancestor. \n(4) ", FontFamily->"Times"], StyleBox["Order", FontFamily->"Times", FontWeight->"Bold"], StyleBox[". The children of each nodes are ordered. ", FontFamily->"Times"] }], "Text", Evaluatable->False, AspectRatioFixed->True], Cell[TextData[StyleBox["\nAxioms (2) and (3) guarantee the there is a unique \ path from any node to the root. There cannot be any alternative routes or \ cycles in a tree. \nThe last axiom could be omitted to produce unordered \ trees, which are important for example in graph theory. For implementations, \ order comes naturally, so we will not consider unordered trees. ", FontFamily->"Times"]], "Text", Evaluatable->False, AspectRatioFixed->True], Cell["\<\ You should convince yourself that our two definitions both produce \ these properties, and that they are equivalent in the sense that they \ describe the same class of entities (except for small technical problems such \ as the absence of the empty tree in the recursive definition). The main advantage of the recursive description is that it makes it easy to \ prove assertions about trees: assume the assertion holds for all small trees, \ and show it still holds for the larger trees obtained from the smaller ones. \ In terms of algorithms, we can often compute data associated with a tree by \ first computing the data for the subtrees, and then combining these partial \ results to get the proper result for the big tree. Here are some examples. \ \>", "Text", Evaluatable->False, AspectRatioFixed->True] }, Closed]], Cell[CellGroupData[{ Cell[" A Basic Property of Trees", "Subsection", Evaluatable->False, AspectRatioFixed->True, CellTags->"c:42"], Cell["\<\ Here is a simple lemma, that is the single most important reason \ why trees are important in computer science. \ \>", "Text", Evaluatable->False, AspectRatioFixed->True], Cell[TextData[{ StyleBox["Lemma", FontFamily->"Times", FontWeight->"Bold"], StyleBox[": Let ", FontFamily->"Times"], Cell[BoxData[ \(TraditionalForm\`T\)]], StyleBox[" be a complete binary tree of depth ", FontFamily->"Times"], Cell[BoxData[ \(TraditionalForm\`k\)]], StyleBox[". Then ", FontFamily->"Times"], Cell[BoxData[ \(TraditionalForm\`T\)]], StyleBox[" has ", FontFamily->"Times"], Cell[BoxData[ \(TraditionalForm\`2\^k\)]], StyleBox[" leaves, and ", FontFamily->"Times"], Cell[BoxData[ \(TraditionalForm\`2\^\(k + 1\) - \ 1\)]], StyleBox[" nodes. \n\nProof:\nYes, finally, another opportunity to use \ induction. To liven things up a little, we'll do both claims at once. \nBase \ case: ", FontFamily->"Times"], Cell[BoxData[ \(TraditionalForm\`k\ = \ 0\)]], StyleBox[". Then there is only the root, so both claims are correct. \n\ Induction step: Assume true for ", FontFamily->"Times"], Cell[BoxData[ \(TraditionalForm\`\(\(\ \)\(k\)\)\)]], StyleBox[", show for ", FontFamily->"Times"], Cell[BoxData[ \(TraditionalForm\`k + 1\)]], StyleBox[". \nLet ", FontFamily->"Times"], Cell[BoxData[ \(TraditionalForm\`T\)]], StyleBox[" be a complete binary tree of depth", FontFamily->"Times"], Cell[BoxData[ \(TraditionalForm\`\(\(\ \)\(k + 1\)\)\)]], StyleBox[". Consider the tree ", FontFamily->"Times"], Cell[BoxData[ \(TraditionalForm\`T\^\[Prime]\)]], StyleBox[" obtained from ", FontFamily->"Times"], Cell[BoxData[ \(TraditionalForm\`T\)]], StyleBox[" by deleting all leaves. A little thought shows that ", FontFamily->"Times"], Cell[BoxData[ \(TraditionalForm\`T\^\[Prime]\)]], StyleBox[" is a complete binary tree of depth ", FontFamily->"Times"], Cell[BoxData[ \(TraditionalForm\`k\)]], StyleBox[". \nHence, ", FontFamily->"Times"], Cell[BoxData[ \(TraditionalForm\`T\^\[Prime]\)]], StyleBox[" has ", FontFamily->"Times"], Cell[BoxData[ \(TraditionalForm\`2\^k\)]], StyleBox[" leaves. But every leaf ", FontFamily->"Times"], Cell[BoxData[ \(TraditionalForm\`x\)]], StyleBox[" in ", FontFamily->"Times"], Cell[BoxData[ \(TraditionalForm\`T\^\[Prime]\)]], StyleBox[" is the parent of exactly two leaves in T. Right? Hence, there \ are ", FontFamily->"Times"], Cell[BoxData[ \(TraditionalForm\`2\^\(k + 1\)\)]], StyleBox[" leaves in ", FontFamily->"Times"], Cell[BoxData[ \(TraditionalForm\`T\)]], StyleBox[". Likewise, the total number of nodes in T is the number of nodes \ in ", FontFamily->"Times"], Cell[BoxData[ \(TraditionalForm\`T\^\[Prime]\)]], StyleBox[", plus ", FontFamily->"Times"], Cell[BoxData[ \(TraditionalForm\`2\^\(k + 1\)\)]], StyleBox[": ", FontFamily->"Times"], Cell[BoxData[ \(TraditionalForm\`2\^\(k + 1\)\ - \ 1\ + \ 2\^\(k + 1\)\ = \ 2\^\(k + 2\)\ - \ 1\)]], StyleBox[". Done. \nQED", FontFamily->"Times"] }], "Text", Evaluatable->False, AspectRatioFixed->True], Cell[TextData[{ StyleBox["\nWhy is this important? In CS applications, the tree is just as \ skeleton that is used to store information. The data can be attached to all \ nodes in a tree, or sometimes just the leaves. The reason this type of \ storage is of interest comes from the last lemma: in a suitable tree with ", FontFamily->"Times"], Cell[BoxData[ \(TraditionalForm\`n\)]], StyleBox[" nodes (or ", FontFamily->"Times"], Cell[BoxData[ \(TraditionalForm\`n\)]], StyleBox[" leaves), the length of a path from the root to a given node (or \ a given leaf) has length ", FontFamily->"Times"], Cell[BoxData[ \(TraditionalForm\`O(log\ n)\)]], StyleBox[". Hence, there are many algorithms operating on trees that deal \ with n data items, but take only ", FontFamily->"Times"], Cell[BoxData[ \(TraditionalForm\`O(\ log\ n)\)]], StyleBox[" steps. Note that this is true only for trees that are \ sufficiently similar to a complete tree. In the degenerate case where the \ whole tree consists only of one branch it still takes ", FontFamily->"Times"], Cell[BoxData[ \(TraditionalForm\`O(n)\)]], StyleBox[" steps to get to a node. Of course, this tree is really just a \ list. ", FontFamily->"Times"] }], "Text", Evaluatable->False, AspectRatioFixed->True] }, Closed]], Cell[CellGroupData[{ Cell[" A Mathematica Prototype", "Subsection", Evaluatable->False, AspectRatioFixed->True, CellTags->"c:43"], Cell[TextData[StyleBox["Trees are an excellent example of a data type that is \ used everywhere in Mathematica, but is actually difficult to implement \ directly in any reasonably way. We could use sets of lists closed under \ prefixes, but that is entirely too tedious. Here is a sledge hammer \ approach. We use expressions ", FontFamily->"Times"]], "Text", Evaluatable->False, AspectRatioFixed->True], Cell[TextData[{ "\n\t\tt = T[ lab, ", Cell[BoxData[ \(TraditionalForm\`T\_1\)]], ",..., ", Cell[BoxData[ \(TraditionalForm\`T\_k\)]], " ]\n" }], "InlineInput"], Cell[TextData[{ StyleBox["to denote a node in a tree. The lab field is where the \ information associated with the node is stored (the label of the node), and \ the ", FontFamily->"Times"], Cell[BoxData[ \(TraditionalForm\`T\_i\)]], StyleBox[" are the children of node ", FontFamily->"Times"], Cell[BoxData[ \(TraditionalForm\`t\)]], StyleBox[". This is very similar to the implementation in C++ that we will \ consider in a short while. The problem with this approach is that the \ children are actually physically present in the parent node, it would be much \ better to have pointers. Alas, no pointers in Mathematica. \nSo, in the end \ the root is actually the whole tree!\nSome examples:", FontFamily->"Times"] }], "Text", Evaluatable->False, AspectRatioFixed->True], Cell[BoxData[ \(t1 = T[0, T[1], T[2]]\)], "Input", AspectRatioFixed->True], Cell[BoxData[ \(TreeForm[t1]\)], "Input", AspectRatioFixed->True], Cell["\<\ Just about useless. This is a complete binary tree of depth 1, the \ root is labeled 0, and the two children are labeled 1 and 2. Here is a full (but not complete) binary tree of depth 2:\ \>", "Text", Evaluatable->False, AspectRatioFixed->True], Cell[BoxData[ \(t2 = T[0, T[1, T[2], T[3]], T[4]]\)], "Input", AspectRatioFixed->True], Cell["\<\ How about computing the depth of trees? The Mathematica function \ Depth is not quite appropriate here. For example\ \>", "Text", Evaluatable->False, AspectRatioFixed->True], Cell[BoxData[ \(Depth[t2]\)], "Input", AspectRatioFixed->True], Cell["\<\ This is because Mathematica thinks of, say, the number 2 inside the \ one leaf as another level down, and adds 1 to everything for good measure. Here is the right definition, make sure you understand what is going \ on.\ \>", "Text", Evaluatable->False, AspectRatioFixed->True], Cell["\<\ Clear[depth] depth[T[_]] := 0; depth[T[_,tt__]] := Max[ Map[depth,{tt}] ] + 1;\ \>", "Input", AspectRatioFixed->True], Cell[BoxData[{ \(depth[t1]\), "\n", \(depth[t2]\)}], "Input", AspectRatioFixed->True], Cell["\<\ This is because Mathematica thinks of, say, the number 2 inside the \ one leaf as another level down, and adds 1 to everything for good measure. And here is a function that computes the total number of nodes in a tree. \ \ \>", "Text", Evaluatable->False, AspectRatioFixed->True], Cell[BoxData[{ \(Clear[size]\), "\n", \(\(size[T[_]] := 1;\)\), "\n", \(size[T[_, tt__]] := Plus @@ \(size /@ {tt}\) + 1\)}], "Input", AspectRatioFixed->True], Cell[BoxData[ \(size[t2]\)], "Input", AspectRatioFixed->True], Cell["Of course, we could cheat and do something like ", "Text", Evaluatable->False, AspectRatioFixed->True], Cell[BoxData[{ \(Clear[size]\), "\n", \(size[t_T] := Length[Flatten[t]]\)}], "Input", AspectRatioFixed->True], Cell[BoxData[ \(size[t1]\)], "Input", AspectRatioFixed->True], Cell["\<\ The reason this is not a good idea here is that we will ultimately \ reimplement things in C++, and Flatten is not a concept that carries over \ easily. The recursive approach in the first definition, however, can be \ ported very easily. \ \>", "Text", Evaluatable->False, AspectRatioFixed->True], Cell[TextData[{ "How about a function ", StyleBox["CBT", "SmallText"], " that computes a complete binary tree given its depth as input? Moreover, \ let us define the labels in such a way that Flatten produces ", StyleBox["Range[0,n-1]", "SmallText"], " where n is the number of nodes in the tree. Va bene? \n\nThe crucial \ idea is to build ", StyleBox[" ", "SmallText"], Cell[BoxData[ \(TraditionalForm\`CBT[n + 1]\)], "SmallText"], " from two copies of ", StyleBox["CBT[n]", "SmallText"], ". Here is a first attempt. " }], "Text", Evaluatable->False, AspectRatioFixed->True], Cell[BoxData[{ \(\(CBT[0] = T[0];\)\), "\n", \(CBT[n_] := \ With[\ {tt = CBT[n - 1]}, \ T[n, tt, tt\ ]\ ]\)}], "Input",\ AspectRatioFixed->True], Cell[TextData[{ "The With construct avoids a double call to ", StyleBox["CBT", "SmallText"], "." }], "Text", Evaluatable->False, AspectRatioFixed->True], Cell[BoxData[{ \(CBT[1]\), "\n", \(CBT[2]\), "\n", \(CBT[3]\)}], "Input", AspectRatioFixed->True], Cell[BoxData[ \(TreeForm[CBT[3]]\)], "Input", AspectRatioFixed->True], Cell["\<\ The structure is fine, but the labels are wrong: currently the \ label indicates how far the node is from a leaf (this is called the height of \ the node). No good. We have to add a suitable offset to the labels of the two component trees. \ The new root should always be labeled 0, of course. How do we add an offset \ to all labels? Substitution is one way. \ \>", "Text", Evaluatable->False, AspectRatioFixed->True], Cell[BoxData[{ \(t2\), "\n", \(t2 /. x_Integer \[Rule] x + 10\)}], "Input", AspectRatioFixed->True], Cell["\<\ Since you all remember the lemma counting the number of nodes in a \ complete binary tree, the rest is easy. \ \>", "Text", Evaluatable->False, AspectRatioFixed->True], Cell["\<\ Clear[CBT] CBT[0] = T[0]; CBT[n_] := \tWith[ {t = CBT[n - 1]}, \tT[0, t /. x_Integer \[Rule] x + 1, t /. x_Integer \[Rule] x + 2^n]];\ \>", \ "Input", AspectRatioFixed->True], Cell[BoxData[{ \(CBT[2]\), "\n", \(Flatten[%]\)}], "Input", AspectRatioFixed->True], Cell[BoxData[{ \(CBT[3]\), "\n", \(Flatten[%]\)}], "Input", AspectRatioFixed->True], Cell["Works. ", "Text", Evaluatable->False, AspectRatioFixed->True] }, Closed]], Cell[CellGroupData[{ Cell[" Expression Trees", "Subsection", Evaluatable->False, AspectRatioFixed->True, CellTags->"c:44"], Cell[TextData[{ "One of the most important applications of the concept of a tree is in the \ analysis of syntactcial structures. For example, and arithmetic expressions \ such as \"", StyleBox["5 + 3 * 9", "SmallText"], "\" can be construed as a tree: " }], "Text", Evaluatable->False, AspectRatioFixed->True], Cell["exp = T[ plus, T[5], T[times,T[3],T[9]] ]", "Input", AspectRatioFixed->True], Cell[TextData[{ "The leaves of the tree represent the atomic values in the expression, so \ the leaf nodes are lableled by integers (or whatever other data type we might \ be interested in). The interior nodes are labeled by arithmetic operators, \ in this case plus and times. \n\nNote that the tree representation of the \ expression contains more information: unless we know the precedence rules \ for plus and times, the expression \"", StyleBox["5 + 3 * 9", "SmallText"], "\" is ambiguous. In the tree, however, the operation plus (the label of \ the root) is by necessity the last one to be performed. \n\nConstructing \ trees out of expressions is a standard task solved in any compiler. We will \ here only implement a much simpler function: evaluation of an expression \ tree. The function eval, when applied to an expression tree with integer \ leaves, and interior node labels plus and times will compute the value of \ the corresponding arithmetic expression. \n" }], "Text", Evaluatable->False, AspectRatioFixed->True], Cell["\<\ eval[t_T] := \tSwitch[ First[t], \t\tplus,\t\tPlus@@(eval /@ Rest[t]), \t\ttimes,\t\tTimes@@(eval /@ Rest[t]), \t\t_,\t\t\tFirst[t] ];\ \>", "Input", AspectRatioFixed->True], Cell[BoxData[ \(eval[exp]\)], "Input", AspectRatioFixed->True], Cell[BoxData[ \(TableForm[Flatten[Trace[eval[exp], eval[__]]]]\)], "Input", AspectRatioFixed->True], Cell["\<\ Note that the correctness of this program follows easily by \ induction on, say, the depth of the tree: the recursive calls are made to \ trees of smaller depth, so we may assume that the algorithm works properly \ for these more shallow trees. Here is a beautiful method to compute factorials: first build the right \ expression tree, then ship it to eval. \ \>", "Text", Evaluatable->False, AspectRatioFixed->True], Cell[BoxData[{ \(Fold[T[times, #1, T[#2]] &, T[1], Range[2, 10]]\), "\n", \(eval[%]\)}], "Input", AspectRatioFixed->True], Cell["\<\ In Mathematica, it is also very easy to go into the opposite \ direction: given an arithmetic expression, convert it into a tree. Again, the \ easiest way of doing this is by recursion. Here is a simple procedure that \ only deals with expressions formed with Plus and Times. The Sequence \ construct below takes an arbitrary expression and turns it into a sequence.\ \ \>", "Text"], Cell["ff[ Sequence@@{1,2,3} ]", "Input"], Cell["\<\ Clear[toTree] toTree[ exp_Plus ] := \tT[ plus, Sequence@@Map[toTree,exp] ]; toTree[ exp_Times ] := \tT[ times, Sequence@@Map[toTree,exp] ]; toTree[ x_ ] := T[x];\ \>", "Input"], Cell["toTree[ a + 5 b + b c ]", "Input"], Cell["% // eval", "Input"], Cell[TextData[{ "The last calculation indicates that ", Cell[BoxData[ \(TraditionalForm\`toTree\ \[SmallCircle]\ eval\ = \ Id\)]], " for certain types of expressions (with forma variables rather than \ integers as leaves), and we could prove this more formally by induction. \ Since we can reconstruct the expression from the tree, the conversion \ procdure from expressions to trees must be correct (in the sense that we do \ not lose any information). " }], "Text"] }, Closed]], Cell[CellGroupData[{ Cell[" Searching", "Subsection", Evaluatable->False, AspectRatioFixed->True, CellTags->"c:45"], Cell[TextData[{ "Another standard applications trees is to speed up searching. The basic \ problem is very simple to describe, and has countless applications. For the \ sake of simplicity we will only consider integers, but the problem clearly \ makes sense for many other entities.\n\n", StyleBox["Searching", FontWeight->"Bold"], "\nGiven a list ", Cell[BoxData[ \(TraditionalForm\`L\)]], " of integers, and an integer ", Cell[BoxData[ \(TraditionalForm\`x\)]], ", determine whether ", Cell[BoxData[ \(TraditionalForm\`x\)]], " occurs in the list. \n\nMore precisely, we want an algorithm that returns \ the position of ", Cell[BoxData[ \(TraditionalForm\`x\)]], " in the list if it is in fact there, and returns No or some such \ otherwise. Note that there may be multiple answers if we allow repetitions in \ the list. To avoid these complications, let us assume that the lists has no \ repetitions." }], "Text"], Cell[CellGroupData[{ Cell["Linear Search", "Subsubsection", CellTags->"c:46"], Cell[TextData[{ "The brute force answer is to search through the list from one end to the \ other, and stop if the element is found. If we get to the end without \ encountering ", Cell[BoxData[ \(TraditionalForm\`x\)]], ", we return No. To make the output type uniform, let us agree to return 0 \ if the element is not found, and a position ", Cell[BoxData[ \(TraditionalForm\`p\)]], ", ", Cell[BoxData[ \(TraditionalForm\`1\ \[LessEqual] \ p\ \[LessEqual] \ Length[L]\)]], ", otherwise. This can be done in a loop, but we can also use recursion and \ pattern matching. " }], "Text"], Cell["\<\ Clear[bruteSearch] bruteSearch[{},_,_] := 0; bruteSearch[ {a_,aa___}, x_, p_ ] := \tIf[ x == a, \t\tp, \t\tbruteSearch[ {aa}, x, p+1 ] \t]; bruteSearch[ L_List, x_ ] := bruteSearch[ L, x, 1 ];\ \>", "Input"], Cell["bruteSearch[ Prime[Range[10]], 5 ] ", "Input"], Cell["bruteSearch[ Prime[Range[10]], 6 ] ", "Input"] }, Closed]], Cell[CellGroupData[{ Cell["Binary Search", "Subsubsection", CellTags->"c:47"], Cell[TextData[{ "In general, this method is best possible if we cannot make any assumptions \ about ", Cell[BoxData[ \(TraditionalForm\`L\)]], ". However, it is often safe to assume that we have a sorted list of \ distinct integers ", Cell[BoxData[ \(TraditionalForm\`L\)]], ". Can the order be exploited to speed up the search? Certainly. We can \ compare ", Cell[BoxData[ \(TraditionalForm\`x\)]], " to the middle element of the list ", Cell[BoxData[ \(TraditionalForm\`y\)]], ". If ", Cell[BoxData[ \(TraditionalForm\`y = x\)]], ", we are done in one step. Otherwise, if ", Cell[BoxData[ \(TraditionalForm\`x\ < \ y\)]], " we continue our search in the left half of the list, and in the right \ half if ", Cell[BoxData[ \(TraditionalForm\`x\ > \ y\)]], ". This is called binary search (as opposed to the brute force linear \ search). \nOne can show that binary search is very efficient, it takes only \ at most ", Cell[BoxData[ \(TraditionalForm\`log\ n\)]], " steps as opposed to the ", Cell[BoxData[ \(TraditionalForm\`n\)]], " steps for the simple algorithm, ", Cell[BoxData[ \(TraditionalForm\`n\)]], " being the length of the list. Here is a while version of this algorithm, \ make sure you know how to handle the recursive version. " }], "Text"], Cell["\<\ binSearch[L_List, x_] := Module[{lo, hi, m, xx, res}, \tlo = 1; hi = Length[L]; \tres = 0; go = True; \tWhile[ go && lo \[LessEqual] hi, \t\tm = Floor[(lo + hi)/2]; \t\txx = L\[LeftDoubleBracket]m\[RightDoubleBracket]; \t\tIf[ x == xx, go = False; res = m ]; \t\tIf[ x < xx, hi = m - 1, lo = m + 1 ]; \t]; \tres ]\ \>", "Input", AspectRatioFixed->True, FontFamily->"Courier"], Cell[BoxData[{ \(binSearch[Range[10], 3.5]\), "\n", \(binSearch[Range[10], 3]\), "\n", \(binSearch[Range[10], 7]\), "\n", \(binSearch[Range[10], \(-1\)]\)}], "Input", AspectRatioFixed->True], Cell[TextData[{ "Why bother with this more complicated version? The reason is that the \ length of the list is cut in half in each pass of the while-loop. As a \ consequence, the number of steps in this algorithms is only at most ", Cell[BoxData[ \(TraditionalForm\`log\ n\)]], " for a search list of length ", Cell[BoxData[ \(TraditionalForm\`\(\(\ \)\(n\)\)\)]], ". Since we are only looking at a small fraction of the elements of the \ list, the question of correctness becomes rather interesting here. Note the \ fact that the search list is sorted is crucial.\n\n", StyleBox["Claim", FontWeight->"Bold"], ": The binSearch algorithm correctly finds the position of an element ", Cell[BoxData[ \(TraditionalForm\`x\)]], " in a sorted list ", Cell[BoxData[ \(TraditionalForm\`L\)]], " without duplicates, and returns 0 if ", Cell[BoxData[ \(TraditionalForm\`x\)]], " is not in the list.\nProof.\nConsider a sorted list ", Cell[BoxData[ \(TraditionalForm\`L\ = \ {a\_1, \ a\_2, \ \[Ellipsis], \ a\_n}\)]], " without repetions. We claim that the algorithm correctly finds ", Cell[BoxData[ \(TraditionalForm\`x\)]], " in the part ", Cell[BoxData[ \(TraditionalForm\`\(\(\ \)\({a\_lo, \ a\_2, \ \[Ellipsis], \ a\_hi}\)\(\ \)\)\)]], " for ", Cell[BoxData[ \(TraditionalForm\`1\ \[LessEqual] \ lo\ \[LessEqual] \ hi\ \[LessEqual] \ n\)]], ". This suffices, since the algorithm starts with ", Cell[BoxData[ \(TraditionalForm\`lo\ = \ 1\)]], " and ", Cell[BoxData[ \(TraditionalForm\`hi\ = \ n\)]], ". We use induction on ", Cell[BoxData[ \(TraditionalForm\`k\ = \ hi\ - \ lo\)]], ". The base case ", Cell[BoxData[ \(TraditionalForm\`k\ = \ 0\)]], " is obvious. \nInduction step: Suppose ", Cell[BoxData[ \(TraditionalForm\`k\ > \ 0\)]], " and let ", Cell[BoxData[ \(TraditionalForm\`\(\(m\)\(\ \)\(=\)\(\ \)\(\[LeftFloor]\ \(hi\ - \ \ lo\)\/2\[RightFloor]\ = \ \[LeftFloor]\ k/2\[RightFloor]\)\(\ \)\)\)]], ". \nCase 1: ", Cell[BoxData[ \(TraditionalForm\`x\ = \ a\_m\)]], ". Then the algorithm stops, and returns the right position. \nCase 2: ", Cell[BoxData[ \(TraditionalForm\`x\ < \ a\_m\)]], ". Since the list is sorted, that means that\n\t ", Cell[BoxData[ \(TraditionalForm\`x\)]], " occurs in ", Cell[BoxData[ \(TraditionalForm\`\(\(\ \)\({a\_lo, \ a\_2, \ \[Ellipsis], \ a\_hi}\)\)\)]], " iff ", Cell[BoxData[ \(TraditionalForm\`x\)]], " occurs in ", Cell[BoxData[ \(TraditionalForm\`\(\(\ \)\({a\_lo, \ a\_2, \ \[Ellipsis], \ a\_\(m - 1\)}\)\)\)]], ". \nBut ", Cell[BoxData[ \(TraditionalForm\`m - 1 - lo < k\)]], ", so we may assume by induction that we report the right answer in the \ subsequent execution of the loop. \nCase 3: ", Cell[BoxData[ \(TraditionalForm\`x\ > \ a\_m\)]], ". Entirely analogous to case 2. \n\[EmptySquare]\n" }], "Text"] }, Closed]], Cell[CellGroupData[{ Cell["Binary Tree Search", "Subsubsection", CellTags->"c:48"], Cell["\<\ What does that have to do with trees? We can think of the the \ binary search algorithm as taking place on a binary tree rather than a flat \ list: the list elements are the labels of the tree, and they are distributed \ in such a way that for any node \ \>", "Text"], Cell["\<\ \tT[ x, TL, TR ] \ \>", "InlineInput"], Cell["\<\ in the tree, all the labels in the subtree TL are less than x, and \ all the labels in the right subtree are bigger than x. The search begins at \ the root, stops if the element is found, and otherwise continues in the left \ or right subtree. Note that we can port our list search algorithm very easily to this tree data \ structure. The only problem is that we can no longer return the position of \ the node where the search element is found as an integer. But, we can use a \ binary sequence to describe the path to the node. (This is essentially \ exactly what Mathematica's Position command does). \ \>", "Text"], Cell["\<\ Clear[binTreeSearch,t] binTreeSearch[T[],_,_] = {}; binTreeSearch[t_T,xx_,p_] := Module[{pp}, \tIf[ xx==t\[LeftDoubleBracket]1\[RightDoubleBracket], Return[p] ]; \tIf[ xx < t\[LeftDoubleBracket]1\[RightDoubleBracket], \t\tbinTreeSearch[ t\[LeftDoubleBracket]2\[RightDoubleBracket], xx, \ Append[p,1] ], \t\tpp = binTreeSearch[ t\[LeftDoubleBracket]3\[RightDoubleBracket], xx, \ Append[p,2] ]; \t\tIf[pp=={},{},pp] \t] ]; binTreeSearch[ t_T, x_ ] = binTreeSearch[ t, x, {} ];\ \>", "Input"], Cell["\<\ In order to test this function, we have to be able to produce \ binary search trees. By hand, this is too tedious to consider, so let us \ write a little function that takes a sorted list and turns it into a search \ tree. Needless to say, the algorithm will be recursive: the middle element of \ the list is the root, the first half goes into the left subtree, and the \ second half goes into the right subtree. \ \>", "Text"], Cell["\<\ toSearchTree[ {} ] := T[]; toSearchTree[ {x_} ] := T[ x, T[], T[] ]; toSearchTree[ L_List ] := With[ {med = Ceiling[Length[L]/2]}, \t\tT[ L[[med]], \t\t toSearchTree[ Take[L,med-1] ], \t\t toSearchTree[ Drop[L,med] ] ] ] \ \>", "Input"], Cell["toSearchTree[ Range[7] ]", "Input"], Cell["pt = toSearchTree[ Prime[Range[20]] ];", "Input"], Cell["binTreeSearch[ pt, 5 ]", "Input"], Cell["\<\ This says that 5 occurs as the right son of the left son of the \ left son of the root. If we try to check, we have to remember that the first \ field in our tree nodes is the label, the second the left son, and the third \ the right son. So:\ \>", "Text"], Cell["pt[[2,2,3]]", "Input"], Cell["But number 10 is not in the tree. ", "Text"], Cell["binTreeSearch[ pt, 10 ]", "Input"] }, Closed]] }, Closed]] }, Closed]] }, Open ]] }, FrontEndVersion->"5.0 for X", ScreenRectangle->{{0, 1280}, {0, 1024}}, WindowToolbars->{}, CellGrouping->Automatic, WindowSize->{952, 638}, WindowMargins->{{19, Automatic}, {1, Automatic}}, PrintingStartingPageNumber->401, PrivateNotebookOptions->{"ColorPalette"->{RGBColor, 256}}, ShowCellLabel->True, ShowCellTags->False, RenderingOptions->{"ObjectDithering"->True, "RasterDithering"->False}, CharacterEncoding->Automatic, Magnification->1.5, StyleDefinitions -> "Classic.nb" ] (******************************************************************* Cached data follows. If you edit this Notebook file directly, not using Mathematica, you must remove the line containing CacheID at the top of the file. The cache data will then be recreated when you save this file from within Mathematica. *******************************************************************) (*CellTagsOutline CellTagsIndex->{ "c:1"->{ Cell[1829, 55, 93, 3, 125, "Title", Evaluatable->False, CellTags->"c:1"]}, "c:2"->{ Cell[1947, 62, 104, 3, 88, "Section", Evaluatable->False, CellTags->"c:2"]}, "c:3"->{ Cell[2846, 85, 196, 8, 42, "Subsection", Evaluatable->False, CellTags->"c:3"]}, "c:4"->{ Cell[6381, 201, 189, 8, 30, "Subsection", Evaluatable->False, CellTags->"c:4"]}, "c:5"->{ Cell[7601, 250, 104, 3, 28, "Subsection", Evaluatable->False, CellTags->"c:5"]}, "c:6"->{ Cell[9875, 324, 111, 3, 28, "Subsection", Evaluatable->False, CellTags->"c:6"]}, "c:7"->{ Cell[12325, 405, 104, 3, 28, "Subsection", Evaluatable->False, CellTags->"c:7"]}, "c:8"->{ Cell[12454, 412, 97, 3, 70, "Subsubsection", Evaluatable->False, CellTags->"c:8"]}, "c:9"->{ Cell[15467, 529, 97, 3, 70, "Subsubsection", Evaluatable->False, CellTags->"c:9"]}, "c:10"->{ Cell[17208, 602, 116, 3, 28, "Subsection", Evaluatable->False, CellTags->"c:10"]}, "c:11"->{ Cell[17349, 609, 111, 3, 70, "Subsubsection", Evaluatable->False, CellTags->"c:11"]}, "c:12"->{ Cell[21832, 767, 115, 3, 70, "Subsubsection", Evaluatable->False, CellTags->"c:12"]}, "c:13"->{ Cell[23129, 811, 115, 3, 70, "Subsubsection", Evaluatable->False, CellTags->"c:13"]}, "c:14"->{ Cell[25565, 886, 126, 3, 70, "Subsubsection", Evaluatable->False, CellTags->"c:14"]}, "c:15"->{ Cell[28310, 967, 97, 3, 28, "Subsection", Evaluatable->False, CellTags->"c:15"]}, "c:16"->{ Cell[31808, 1105, 107, 3, 28, "Subsection", Evaluatable->False, CellTags->"c:16"]}, "c:17"->{ Cell[33796, 1156, 66, 1, 70, "Subsubsection", CellTags->"c:17"]}, "c:18"->{ Cell[41123, 1391, 75, 1, 70, "Subsubsection", CellTags->"c:18"]}, "c:19"->{ Cell[43911, 1470, 68, 1, 70, "Subsubsection", CellTags->"c:19"]}, "c:20"->{ Cell[46950, 1553, 78, 1, 70, "Subsubsection", CellTags->"c:20"]}, "c:21"->{ Cell[48877, 1612, 60, 1, 70, "Subsubsection", CellTags->"c:21"]}, "c:22"->{ Cell[50870, 1675, 69, 1, 70, "Subsubsection", CellTags->"c:22"]}, "c:23"->{ Cell[55884, 1839, 112, 3, 47, "Section", Evaluatable->False, CellTags->"c:23"]}, "c:24"->{ Cell[56021, 1846, 111, 3, 70, "Subsection", Evaluatable->False, CellTags->"c:24"]}, "c:25"->{ Cell[62481, 2030, 112, 3, 70, "Subsection", Evaluatable->False, CellTags->"c:25"]}, "c:26"->{ Cell[66387, 2173, 108, 3, 70, "Subsection", Evaluatable->False, CellTags->"c:26"]}, "c:27"->{ Cell[70714, 2316, 105, 3, 70, "Subsection", Evaluatable->False, CellTags->"c:27"]}, "c:28"->{ Cell[70844, 2323, 105, 3, 70, "Subsubsection", Evaluatable->False, CellTags->"c:28"]}, "c:29"->{ Cell[74745, 2447, 112, 3, 70, "Subsubsection", Evaluatable->False, CellTags->"c:29"]}, "c:30"->{ Cell[77217, 2530, 126, 3, 70, "Subsection", Evaluatable->False, CellTags->"c:30"]}, "c:31"->{ Cell[77368, 2537, 105, 3, 70, "Subsubsection", Evaluatable->False, CellTags->"c:31"]}, "c:32"->{ Cell[82180, 2688, 110, 3, 70, "Subsubsection", Evaluatable->False, CellTags->"c:32"]}, "c:33"->{ Cell[85729, 2807, 121, 3, 70, "Subsubsection", Evaluatable->False, CellTags->"c:33"]}, "c:34"->{ Cell[88030, 2889, 195, 8, 70, "Subsection", Evaluatable->False, CellTags->"c:34"]}, "c:35"->{ Cell[95657, 3148, 100, 3, 70, "Subsubsection", Evaluatable->False, CellTags->"c:35"]}, "c:36"->{ Cell[97390, 3197, 92, 3, 47, "Section", Evaluatable->False, CellTags->"c:36"]}, "c:37"->{ Cell[97485, 3202, 113, 3, 70, "Subsection", Evaluatable->False, CellTags->"c:37"]}, "c:38"->{ Cell[97623, 3209, 116, 3, 70, "Subsection", Evaluatable->False, CellTags->"c:38"]}, "c:39"->{ Cell[97764, 3216, 105, 3, 70, "Subsubsection", Evaluatable->False, CellTags->"c:39"]}, "c:40"->{ Cell[102985, 3400, 108, 3, 70, "Subsubsection", Evaluatable->False, CellTags->"c:40"]}, "c:41"->{ Cell[105563, 3479, 113, 3, 70, "Subsection", Evaluatable->False, CellTags->"c:41"]}, "c:42"->{ Cell[109536, 3577, 116, 3, 70, "Subsection", Evaluatable->False, CellTags->"c:42"]}, "c:43"->{ Cell[114400, 3735, 114, 3, 70, "Subsection", Evaluatable->False, CellTags->"c:43"]}, "c:44"->{ Cell[120763, 3969, 107, 3, 70, "Subsection", Evaluatable->False, CellTags->"c:44"]}, "c:45"->{ Cell[124498, 4079, 100, 3, 70, "Subsection", Evaluatable->False, CellTags->"c:45"]}, "c:46"->{ Cell[125593, 4112, 58, 1, 70, "Subsubsection", CellTags->"c:46"]}, "c:47"->{ Cell[126640, 4150, 58, 1, 70, "Subsubsection", CellTags->"c:47"]}, "c:48"->{ Cell[131799, 4307, 63, 1, 70, "Subsubsection", CellTags->"c:48"]} } *) (*CellTagsIndex CellTagsIndex->{ {"c:1", 135528, 4423}, {"c:2", 135630, 4427}, {"c:3", 135734, 4431}, {"c:4", 135841, 4435}, {"c:5", 135949, 4439}, {"c:6", 136057, 4443}, {"c:7", 136165, 4447}, {"c:8", 136274, 4451}, {"c:9", 136385, 4455}, {"c:10", 136497, 4459}, {"c:11", 136608, 4463}, {"c:12", 136722, 4467}, {"c:13", 136836, 4471}, {"c:14", 136950, 4475}, {"c:15", 137064, 4479}, {"c:16", 137174, 4483}, {"c:17", 137286, 4487}, {"c:18", 137374, 4490}, {"c:19", 137462, 4493}, {"c:20", 137550, 4496}, {"c:21", 137638, 4499}, {"c:22", 137726, 4502}, {"c:23", 137814, 4505}, {"c:24", 137923, 4509}, {"c:25", 138035, 4513}, {"c:26", 138147, 4517}, {"c:27", 138259, 4521}, {"c:28", 138371, 4525}, {"c:29", 138486, 4529}, {"c:30", 138601, 4533}, {"c:31", 138713, 4537}, {"c:32", 138828, 4541}, {"c:33", 138943, 4545}, {"c:34", 139058, 4549}, {"c:35", 139170, 4553}, {"c:36", 139285, 4557}, {"c:37", 139393, 4561}, {"c:38", 139505, 4565}, {"c:39", 139617, 4569}, {"c:40", 139732, 4573}, {"c:41", 139848, 4577}, {"c:42", 139961, 4581}, {"c:43", 140074, 4585}, {"c:44", 140187, 4589}, {"c:45", 140300, 4593}, {"c:46", 140413, 4597}, {"c:47", 140502, 4600}, {"c:48", 140591, 4603} } *) (*NotebookFileOutline Notebook[{ Cell[1754, 51, 50, 0, 44, "SmallText"], Cell[CellGroupData[{ Cell[1829, 55, 93, 3, 125, "Title", Evaluatable->False, CellTags->"c:1"], Cell[CellGroupData[{ Cell[1947, 62, 104, 3, 88, "Section", Evaluatable->False, CellTags->"c:2"], Cell[2054, 67, 767, 14, 218, "Text", Evaluatable->False], Cell[CellGroupData[{ Cell[2846, 85, 196, 8, 42, "Subsection", Evaluatable->False, CellTags->"c:3"], Cell[3045, 95, 753, 21, 70, "Text", Evaluatable->False], Cell[3801, 118, 98, 5, 70, "Input"], Cell[3902, 125, 66, 2, 70, "Input"], Cell[3971, 129, 447, 13, 70, "Text", Evaluatable->False], Cell[4421, 144, 85, 2, 70, "Input"], Cell[4509, 148, 374, 10, 70, "Text", Evaluatable->False], Cell[4886, 160, 90, 2, 70, "Input"], Cell[4979, 164, 569, 9, 70, "Text", Evaluatable->False], Cell[5551, 175, 125, 2, 70, "Text", Evaluatable->False], Cell[5679, 179, 211, 4, 70, "Text", Evaluatable->False], Cell[5893, 185, 451, 11, 70, "Text", Evaluatable->False] }, Closed]], Cell[CellGroupData[{ Cell[6381, 201, 189, 8, 30, "Subsection", Evaluatable->False, CellTags->"c:4"], Cell[6573, 211, 619, 20, 70, "Text", Evaluatable->False], Cell[7195, 233, 170, 4, 70, "Input"], Cell[7368, 239, 22, 0, 70, "Input"], Cell[7393, 241, 74, 0, 70, "Text"], Cell[7470, 243, 94, 2, 70, "Input"] }, Closed]], Cell[CellGroupData[{ Cell[7601, 250, 104, 3, 28, "Subsection", Evaluatable->False, CellTags->"c:5"], Cell[7708, 255, 313, 10, 70, "Text", Evaluatable->False], Cell[8024, 267, 870, 19, 70, "Text", Evaluatable->False], Cell[8897, 288, 182, 4, 70, "Input"], Cell[9082, 294, 141, 4, 70, "Input"], Cell[9226, 300, 284, 7, 70, "Text", Evaluatable->False], Cell[9513, 309, 246, 6, 70, "Input"], Cell[9762, 317, 76, 2, 70, "Input"] }, Closed]], Cell[CellGroupData[{ Cell[9875, 324, 111, 3, 28, "Subsection", Evaluatable->False, CellTags->"c:6"], Cell[9989, 329, 924, 24, 70, "Text", Evaluatable->False], Cell[10916, 355, 184, 6, 70, "Input"], Cell[11103, 363, 406, 14, 70, "Text", Evaluatable->False], Cell[11512, 379, 166, 4, 70, "Input"], Cell[11681, 385, 138, 4, 70, "Input"], Cell[11822, 391, 466, 9, 70, "Text", Evaluatable->False] }, Closed]], Cell[CellGroupData[{ Cell[12325, 405, 104, 3, 28, "Subsection", Evaluatable->False, CellTags->"c:7"], Cell[CellGroupData[{ Cell[12454, 412, 97, 3, 70, "Subsubsection", Evaluatable->False, CellTags->"c:8"], Cell[12554, 417, 518, 18, 70, "Text", Evaluatable->False], Cell[13075, 437, 105, 5, 70, "Input"], Cell[13183, 444, 68, 2, 70, "Input"], Cell[13254, 448, 273, 10, 70, "Text", Evaluatable->False], Cell[13530, 460, 87, 2, 70, "Input"], Cell[13620, 464, 292, 10, 70, "Text", Evaluatable->False], Cell[13915, 476, 101, 2, 70, "Input"], Cell[14019, 480, 760, 24, 70, "Text", Evaluatable->False], Cell[14782, 506, 93, 2, 70, "Input"], Cell[14878, 510, 440, 10, 70, "Text", Evaluatable->False], Cell[15321, 522, 109, 2, 70, "Input"] }, Closed]], Cell[CellGroupData[{ Cell[15467, 529, 97, 3, 70, "Subsubsection", Evaluatable->False, CellTags->"c:9"], Cell[15567, 534, 335, 10, 70, "Text", Evaluatable->False], Cell[15905, 546, 143, 6, 70, "Input"], Cell[16051, 554, 68, 2, 70, "Input"], Cell[16122, 558, 87, 2, 70, "Input"], Cell[16212, 562, 123, 2, 70, "Text", Evaluatable->False], Cell[16338, 566, 77, 2, 70, "Input"], Cell[16418, 570, 261, 6, 70, "Text", Evaluatable->False], Cell[16682, 578, 107, 2, 70, "Input"], Cell[16792, 582, 81, 2, 70, "Input"], Cell[16876, 586, 68, 2, 70, "Input"], Cell[16947, 590, 212, 6, 70, "Text", Evaluatable->False] }, Closed]] }, Closed]], Cell[CellGroupData[{ Cell[17208, 602, 116, 3, 28, "Subsection", Evaluatable->False, CellTags->"c:10"], Cell[CellGroupData[{ Cell[17349, 609, 111, 3, 70, "Subsubsection", Evaluatable->False, CellTags->"c:11"], Cell[17463, 614, 877, 21, 70, "Text", Evaluatable->False], Cell[18343, 637, 186, 5, 70, "Input"], Cell[18532, 644, 76, 2, 70, "Input"], Cell[18611, 648, 328, 7, 70, "Text", Evaluatable->False], Cell[18942, 657, 95, 2, 70, "Input"], Cell[19040, 661, 156, 5, 70, "Input"], Cell[19199, 668, 195, 6, 70, "Text", Evaluatable->False], Cell[19397, 676, 47, 0, 70, "Input"], Cell[19447, 678, 56, 3, 70, "Input"], Cell[19506, 683, 393, 8, 70, "Text", Evaluatable->False], Cell[19902, 693, 119, 6, 70, "Input"], Cell[20024, 701, 86, 2, 70, "Input"], Cell[20113, 705, 201, 5, 70, "Text", Evaluatable->False], Cell[20317, 712, 103, 2, 70, "Input"], Cell[20423, 716, 228, 6, 70, "Text", Evaluatable->False], Cell[20654, 724, 115, 3, 70, "Input"], Cell[20772, 729, 73, 2, 70, "Input"], Cell[20848, 733, 350, 11, 70, "Text", Evaluatable->False], Cell[21201, 746, 479, 12, 70, "Text", Evaluatable->False], Cell[21683, 760, 112, 2, 70, "Input"] }, Closed]], Cell[CellGroupData[{ Cell[21832, 767, 115, 3, 70, "Subsubsection", Evaluatable->False, CellTags->"c:12"], Cell[21950, 772, 205, 6, 70, "Text", Evaluatable->False], Cell[22158, 780, 183, 4, 70, "Input"], Cell[22344, 786, 76, 2, 70, "Input"], Cell[22423, 790, 73, 2, 70, "Input"], Cell[22499, 794, 593, 12, 70, "Text", Evaluatable->False] }, Closed]], Cell[CellGroupData[{ Cell[23129, 811, 115, 3, 70, "Subsubsection", Evaluatable->False, CellTags->"c:13"], Cell[23247, 816, 764, 20, 70, "Text", Evaluatable->False], Cell[24014, 838, 94, 4, 70, "Input"], Cell[24111, 844, 618, 13, 70, "Text", Evaluatable->False], Cell[24732, 859, 281, 7, 70, "Input"], Cell[25016, 868, 368, 8, 70, "Text", Evaluatable->False], Cell[25387, 878, 141, 3, 70, "Input"] }, Closed]], Cell[CellGroupData[{ Cell[25565, 886, 126, 3, 70, "Subsubsection", Evaluatable->False, CellTags->"c:14"], Cell[25694, 891, 1791, 47, 70, "Text", Evaluatable->False], Cell[27488, 940, 34, 0, 70, "Input"], Cell[27525, 942, 263, 6, 70, "Text"], Cell[27791, 950, 346, 7, 70, "Input"], Cell[28140, 959, 45, 0, 70, "Input"], Cell[28188, 961, 73, 0, 70, "Input"] }, Closed]] }, Closed]], Cell[CellGroupData[{ Cell[28310, 967, 97, 3, 28, "Subsection", Evaluatable->False, CellTags->"c:15"], Cell[28410, 972, 363, 8, 70, "Text", Evaluatable->False], Cell[28776, 982, 194, 7, 70, "Input"], Cell[28973, 991, 90, 2, 70, "Input"], Cell[29066, 995, 285, 7, 70, "Text", Evaluatable->False], Cell[29354, 1004, 102, 3, 70, "Input"], Cell[29459, 1009, 229, 6, 70, "Text", Evaluatable->False], Cell[29691, 1017, 156, 6, 70, "Input"], Cell[29850, 1025, 86, 2, 70, "Input"], Cell[29939, 1029, 293, 8, 70, "Text", Evaluatable->False], Cell[30235, 1039, 93, 3, 70, "Input"], Cell[30331, 1044, 135, 5, 70, "Text", Evaluatable->False], Cell[30469, 1051, 100, 3, 70, "Input"], Cell[30572, 1056, 245, 8, 70, "Text", Evaluatable->False], Cell[30820, 1066, 150, 6, 70, "Input"], Cell[30973, 1074, 86, 2, 70, "Input"], Cell[31062, 1078, 104, 2, 70, "Input"], Cell[31169, 1082, 106, 2, 70, "Input"], Cell[31278, 1086, 310, 8, 70, "Text", Evaluatable->False], Cell[31591, 1096, 180, 4, 70, "Input"] }, Closed]], Cell[CellGroupData[{ Cell[31808, 1105, 107, 3, 28, "Subsection", Evaluatable->False, CellTags->"c:16"], Cell[31918, 1110, 1853, 42, 70, "Text", Evaluatable->False], Cell[CellGroupData[{ Cell[33796, 1156, 66, 1, 70, "Subsubsection", CellTags->"c:17"], Cell[33865, 1159, 447, 9, 70, "Text", Evaluatable->False], Cell[34315, 1170, 2128, 56, 70, "Text"], Cell[36446, 1228, 588, 15, 70, "Text", Evaluatable->False], Cell[37037, 1245, 394, 13, 70, "InputOnly"], Cell[37434, 1260, 157, 4, 70, "Input"], Cell[37594, 1266, 509, 12, 70, "Text"], Cell[38106, 1280, 118, 2, 70, "Input"], Cell[38227, 1284, 158, 6, 70, "Text"], Cell[38388, 1292, 91, 1, 70, "Input"], Cell[38482, 1295, 115, 5, 70, "Text"], Cell[38600, 1302, 142, 4, 70, "Input"], Cell[38745, 1308, 1121, 36, 70, "Text", Evaluatable->False], Cell[39869, 1346, 172, 7, 70, "Input"], Cell[40044, 1355, 269, 6, 70, "Text", Evaluatable->False], Cell[40316, 1363, 104, 3, 70, "Input"], Cell[40423, 1368, 79, 2, 70, "Text", Evaluatable->False], Cell[40505, 1372, 172, 3, 70, "Input"], Cell[40680, 1377, 406, 9, 70, "Text", Evaluatable->False] }, Closed]], Cell[CellGroupData[{ Cell[41123, 1391, 75, 1, 70, "Subsubsection", CellTags->"c:18"], Cell[41201, 1394, 2156, 58, 70, "Text", Evaluatable->False], Cell[43360, 1454, 514, 11, 70, "Text"] }, Closed]], Cell[CellGroupData[{ Cell[43911, 1470, 68, 1, 70, "Subsubsection", CellTags->"c:19"], Cell[43982, 1473, 1508, 36, 70, "Text", Evaluatable->False], Cell[45493, 1511, 231, 4, 70, "Text"], Cell[45727, 1517, 265, 8, 70, "Input"], Cell[45995, 1527, 98, 2, 70, "Input"], Cell[46096, 1531, 817, 17, 70, "Text"] }, Closed]], Cell[CellGroupData[{ Cell[46950, 1553, 78, 1, 70, "Subsubsection", CellTags->"c:20"], Cell[47031, 1556, 331, 6, 70, "Text"], Cell[47365, 1564, 824, 25, 70, "Input"], Cell[48192, 1591, 230, 6, 70, "Input"], Cell[48425, 1599, 415, 8, 70, "Text"] }, Closed]], Cell[CellGroupData[{ Cell[48877, 1612, 60, 1, 70, "Subsubsection", CellTags->"c:21"], Cell[48940, 1615, 1079, 19, 70, "Text"], Cell[50022, 1636, 553, 22, 70, "Input"], Cell[50578, 1660, 139, 5, 70, "Input"], Cell[50720, 1667, 113, 3, 70, "Text"] }, Closed]], Cell[CellGroupData[{ Cell[50870, 1675, 69, 1, 70, "Subsubsection", CellTags->"c:22"], Cell[50942, 1678, 2042, 41, 70, "Text"], Cell[52987, 1721, 99, 4, 70, "Input"], Cell[53089, 1727, 78, 3, 70, "Input"], Cell[53170, 1732, 406, 7, 70, "Text"], Cell[53579, 1741, 177, 4, 70, "Input"], Cell[53759, 1747, 177, 4, 70, "Input"], Cell[53939, 1753, 124, 3, 70, "Text"], Cell[54066, 1758, 160, 5, 70, "Input"], Cell[54229, 1765, 42, 4, 70, "Input"], Cell[54274, 1771, 716, 21, 70, "Text"], Cell[54993, 1794, 93, 3, 70, "Input"], Cell[55089, 1799, 61, 4, 70, "Input"], Cell[55153, 1805, 203, 4, 70, "Text"], Cell[55359, 1811, 369, 16, 70, "Input"], Cell[55731, 1829, 92, 3, 70, "Input"] }, Closed]] }, Closed]] }, Closed]], Cell[CellGroupData[{ Cell[55884, 1839, 112, 3, 47, "Section", Evaluatable->False, CellTags->"c:23"], Cell[CellGroupData[{ Cell[56021, 1846, 111, 3, 70, "Subsection", Evaluatable->False, CellTags->"c:24"], Cell[56135, 1851, 3376, 91, 70, "Text", Evaluatable->False], Cell[59514, 1944, 2186, 57, 70, "Text", Evaluatable->False], Cell[61703, 2003, 741, 22, 70, "Text", Evaluatable->False] }, Closed]], Cell[CellGroupData[{ Cell[62481, 2030, 112, 3, 70, "Subsection", Evaluatable->False, CellTags->"c:25"], Cell[62596, 2035, 538, 14, 70, "Text", Evaluatable->False], Cell[63137, 2051, 177, 4, 70, "Input"], Cell[63317, 2057, 76, 2, 70, "Input"], Cell[63396, 2061, 489, 12, 70, "Text", Evaluatable->False], Cell[63888, 2075, 120, 5, 70, "Input"], Cell[64011, 2082, 76, 2, 70, "Input"], Cell[64090, 2086, 349, 12, 70, "Text", Evaluatable->False], Cell[64442, 2100, 145, 4, 70, "Input"], Cell[64590, 2106, 139, 6, 70, "Text", Evaluatable->False], Cell[64732, 2114, 94, 2, 70, "Input"], Cell[64829, 2118, 400, 12, 70, "Text", Evaluatable->False], Cell[65232, 2132, 192, 4, 70, "Input"], Cell[65427, 2138, 86, 2, 70, "Input"], Cell[65516, 2142, 834, 26, 70, "Text", Evaluatable->False] }, Closed]], Cell[CellGroupData[{ Cell[66387, 2173, 108, 3, 70, "Subsection", Evaluatable->False, CellTags->"c:26"], Cell[66498, 2178, 1641, 39, 70, "Text", Evaluatable->False], Cell[68142, 2219, 130, 5, 70, "Input"], Cell[68275, 2226, 115, 2, 70, "Text", Evaluatable->False], Cell[68393, 2230, 161, 4, 70, "Input"], Cell[68557, 2236, 93, 2, 70, "Text", Evaluatable->False], Cell[68653, 2240, 139, 4, 70, "Input"], Cell[68795, 2246, 132, 3, 70, "Input"], Cell[68930, 2251, 302, 7, 70, "Text", Evaluatable->False], Cell[69235, 2260, 162, 4, 70, "Input"], Cell[69400, 2266, 72, 2, 70, "Input"], Cell[69475, 2270, 656, 20, 70, "Text", Evaluatable->False], Cell[70134, 2292, 132, 3, 70, "Input"], Cell[70269, 2297, 132, 3, 70, "Input"], Cell[70404, 2302, 175, 5, 70, "Text", Evaluatable->False], Cell[70582, 2309, 95, 2, 70, "Input"] }, Closed]], Cell[CellGroupData[{ Cell[70714, 2316, 105, 3, 70, "Subsection", Evaluatable->False, CellTags->"c:27"], Cell[CellGroupData[{ Cell[70844, 2323, 105, 3, 70, "Subsubsection", Evaluatable->False, CellTags->"c:28"], Cell[70952, 2328, 2514, 65, 70, "Text", Evaluatable->False], Cell[73469, 2395, 149, 6, 70, "Input"], Cell[73621, 2403, 84, 2, 70, "Input"], Cell[73708, 2407, 351, 10, 70, "Text", Evaluatable->False], Cell[74062, 2419, 143, 5, 70, "Input"], Cell[74208, 2426, 84, 2, 70, "Input"], Cell[74295, 2430, 309, 8, 70, "Text", Evaluatable->False], Cell[74607, 2440, 101, 2, 70, "Input"] }, Closed]], Cell[CellGroupData[{ Cell[74745, 2447, 112, 3, 70, "Subsubsection", Evaluatable->False, CellTags->"c:29"], Cell[74860, 2452, 1843, 54, 70, "Text", Evaluatable->False], Cell[76706, 2508, 72, 2, 70, "Input"], Cell[76781, 2512, 309, 8, 70, "Text", Evaluatable->False], Cell[77093, 2522, 75, 2, 70, "Input"] }, Closed]] }, Closed]], Cell[CellGroupData[{ Cell[77217, 2530, 126, 3, 70, "Subsection", Evaluatable->False, CellTags->"c:30"], Cell[CellGroupData[{ Cell[77368, 2537, 105, 3, 70, "Subsubsection", Evaluatable->False, CellTags->"c:31"], Cell[77476, 2542, 3444, 102, 70, "Text", Evaluatable->False], Cell[80923, 2646, 1220, 37, 70, "Text", Evaluatable->False] }, Closed]], Cell[CellGroupData[{ Cell[82180, 2688, 110, 3, 70, "Subsubsection", Evaluatable->False, CellTags->"c:32"], Cell[82293, 2693, 247, 7, 70, "Text", Evaluatable->False], Cell[82543, 2702, 161, 4, 70, "Input"], Cell[82707, 2708, 620, 15, 70, "Text", Evaluatable->False], Cell[83330, 2725, 195, 4, 70, "Input"], Cell[83528, 2731, 161, 4, 70, "Input"], Cell[83692, 2737, 412, 9, 70, "Text", Evaluatable->False], Cell[84107, 2748, 67, 2, 70, "Input"], Cell[84177, 2752, 130, 5, 70, "Input"], Cell[84310, 2759, 186, 5, 70, "Input"], Cell[84499, 2766, 1193, 36, 70, "Text", Evaluatable->False] }, Closed]], Cell[CellGroupData[{ Cell[85729, 2807, 121, 3, 70, "Subsubsection", Evaluatable->False, CellTags->"c:33"], Cell[85853, 2812, 380, 11, 70, "Text", Evaluatable->False], Cell[86236, 2825, 95, 2, 70, "Input"], Cell[86334, 2829, 517, 13, 70, "Text", Evaluatable->False], Cell[86854, 2844, 133, 5, 70, "Input"], Cell[86990, 2851, 69, 2, 70, "Input"], Cell[87062, 2855, 501, 13, 70, "Text", Evaluatable->False], Cell[87566, 2870, 97, 2, 70, "Input"], Cell[87666, 2874, 70, 2, 70, "Input"], Cell[87739, 2878, 242, 5, 70, "Text", Evaluatable->False] }, Closed]] }, Closed]], Cell[CellGroupData[{ Cell[88030, 2889, 195, 8, 70, "Subsection", Evaluatable->False, CellTags->"c:34"], Cell[88228, 2899, 211, 8, 70, "Text", Evaluatable->False], Cell[88442, 2909, 1889, 41, 70, "Text", Evaluatable->False], Cell[90334, 2952, 1117, 46, 70, "Text", Evaluatable->False], Cell[91454, 3000, 1042, 23, 70, "Text", Evaluatable->False], Cell[92499, 3025, 426, 15, 70, "Text", Evaluatable->False], Cell[92928, 3042, 218, 6, 70, "Text", Evaluatable->False], Cell[93149, 3050, 162, 4, 70, "Input"], Cell[93314, 3056, 89, 2, 70, "Input"], Cell[93406, 3060, 178, 5, 70, "Text", Evaluatable->False], Cell[93587, 3067, 177, 4, 70, "Input"], Cell[93767, 3073, 105, 3, 70, "Input"], Cell[93875, 3078, 89, 2, 70, "Text", Evaluatable->False], Cell[93967, 3082, 139, 3, 70, "Input"], Cell[94109, 3087, 305, 8, 70, "Text", Evaluatable->False], Cell[94417, 3097, 168, 4, 70, "Input"], Cell[94588, 3103, 106, 3, 70, "Input"], Cell[94697, 3108, 96, 2, 70, "Input"], Cell[94796, 3112, 92, 2, 70, "Input"], Cell[94891, 3116, 139, 5, 70, "Text", Evaluatable->False], Cell[95033, 3123, 168, 4, 70, "Input"], Cell[95204, 3129, 105, 3, 70, "Input"], Cell[95312, 3134, 94, 2, 70, "Input"], Cell[95409, 3138, 223, 6, 70, "Text", Evaluatable->False], Cell[CellGroupData[{ Cell[95657, 3148, 100, 3, 70, "Subsubsection", Evaluatable->False, CellTags->"c:35"], Cell[95760, 3153, 1569, 37, 70, "Text", Evaluatable->False] }, Closed]] }, Closed]] }, Closed]], Cell[CellGroupData[{ Cell[97390, 3197, 92, 3, 47, "Section", Evaluatable->False, CellTags->"c:36"], Cell[97485, 3202, 113, 3, 70, "Subsection", Evaluatable->False, CellTags->"c:37"], Cell[CellGroupData[{ Cell[97623, 3209, 116, 3, 70, "Subsection", Evaluatable->False, CellTags->"c:38"], Cell[CellGroupData[{ Cell[97764, 3216, 105, 3, 70, "Subsubsection", Evaluatable->False, CellTags->"c:39"], Cell[97872, 3221, 3311, 116, 70, "Text", Evaluatable->False], Cell[101186, 3339, 1234, 40, 70, "Text", Evaluatable->False], Cell[102423, 3381, 525, 14, 70, "Text", Evaluatable->False] }, Closed]], Cell[CellGroupData[{ Cell[102985, 3400, 108, 3, 70, "Subsubsection", Evaluatable->False, CellTags->"c:40"], Cell[103096, 3405, 1005, 31, 70, "Text", Evaluatable->False], Cell[104104, 3438, 905, 22, 70, "Text", Evaluatable->False], Cell[105012, 3462, 502, 11, 70, "Text", Evaluatable->False] }, Closed]] }, Closed]], Cell[CellGroupData[{ Cell[105563, 3479, 113, 3, 70, "Subsection", Evaluatable->False, CellTags->"c:41"], Cell[105679, 3484, 1475, 30, 70, "Text", Evaluatable->False], Cell[107157, 3516, 1051, 29, 70, "Text", Evaluatable->False], Cell[108211, 3547, 457, 7, 70, "Text", Evaluatable->False], Cell[108671, 3556, 828, 16, 70, "Text", Evaluatable->False] }, Closed]], Cell[CellGroupData[{ Cell[109536, 3577, 116, 3, 70, "Subsection", Evaluatable->False, CellTags->"c:42"], Cell[109655, 3582, 184, 5, 70, "Text", Evaluatable->False], Cell[109842, 3589, 3174, 106, 70, "Text", Evaluatable->False], Cell[113019, 3697, 1344, 33, 70, "Text", Evaluatable->False] }, Closed]], Cell[CellGroupData[{ Cell[114400, 3735, 114, 3, 70, "Subsection", Evaluatable->False, CellTags->"c:43"], Cell[114517, 3740, 411, 7, 70, "Text", Evaluatable->False], Cell[114931, 3749, 181, 8, 70, "InlineInput"], Cell[115115, 3759, 812, 19, 70, "Text", Evaluatable->False], Cell[115930, 3780, 80, 2, 70, "Input"], Cell[116013, 3784, 71, 2, 70, "Input"], Cell[116087, 3788, 260, 6, 70, "Text", Evaluatable->False], Cell[116350, 3796, 92, 2, 70, "Input"], Cell[116445, 3800, 188, 5, 70, "Text", Evaluatable->False], Cell[116636, 3807, 68, 2, 70, "Input"], Cell[116707, 3811, 293, 8, 70, "Text", Evaluatable->False], Cell[117003, 3821, 129, 5, 70, "Input"], Cell[117135, 3828, 96, 3, 70, "Input"], Cell[117234, 3833, 295, 8, 70, "Text", Evaluatable->False], Cell[117532, 3843, 174, 4, 70, "Input"], Cell[117709, 3849, 67, 2, 70, "Input"], Cell[117779, 3853, 112, 2, 70, "Text", Evaluatable->False], Cell[117894, 3857, 120, 3, 70, "Input"], Cell[118017, 3862, 67, 2, 70, "Input"], Cell[118087, 3866, 312, 8, 70, "Text", Evaluatable->False], Cell[118402, 3876, 612, 16, 70, "Text", Evaluatable->False], Cell[119017, 3894, 156, 4, 70, "Input"], Cell[119176, 3900, 162, 6, 70, "Text", Evaluatable->False], Cell[119341, 3908, 113, 4, 70, "Input"], Cell[119457, 3914, 75, 2, 70, "Input"], Cell[119535, 3918, 435, 10, 70, "Text", Evaluatable->False], Cell[119973, 3930, 110, 3, 70, "Input"], Cell[120086, 3935, 181, 5, 70, "Text", Evaluatable->False], Cell[120270, 3942, 188, 8, 70, "Input"], Cell[120461, 3952, 94, 3, 70, "Input"], Cell[120558, 3957, 94, 3, 70, "Input"], Cell[120655, 3962, 71, 2, 70, "Text", Evaluatable->False] }, Closed]], Cell[CellGroupData[{ Cell[120763, 3969, 107, 3, 70, "Subsection", Evaluatable->False, CellTags->"c:44"], Cell[120873, 3974, 321, 8, 70, "Text", Evaluatable->False], Cell[121197, 3984, 84, 1, 70, "Input"], Cell[121284, 3987, 1049, 17, 70, "Text", Evaluatable->False], Cell[122336, 4006, 186, 8, 70, "Input"], Cell[122525, 4016, 68, 2, 70, "Input"], Cell[122596, 4020, 105, 2, 70, "Input"], Cell[122704, 4024, 433, 10, 70, "Text", Evaluatable->False], Cell[123140, 4036, 132, 3, 70, "Input"], Cell[123275, 4041, 392, 7, 70, "Text"], Cell[123670, 4050, 40, 0, 70, "Input"], Cell[123713, 4052, 188, 7, 70, "Input"], Cell[123904, 4061, 40, 0, 70, "Input"], Cell[123947, 4063, 26, 0, 70, "Input"], Cell[123976, 4065, 485, 9, 70, "Text"] }, Closed]], Cell[CellGroupData[{ Cell[124498, 4079, 100, 3, 70, "Subsection", Evaluatable->False, CellTags->"c:45"], Cell[124601, 4084, 967, 24, 70, "Text"], Cell[CellGroupData[{ Cell[125593, 4112, 58, 1, 70, "Subsubsection", CellTags->"c:46"], Cell[125654, 4115, 617, 15, 70, "Text"], Cell[126274, 4132, 219, 9, 70, "Input"], Cell[126496, 4143, 52, 0, 70, "Input"], Cell[126551, 4145, 52, 0, 70, "Input"] }, Closed]], Cell[CellGroupData[{ Cell[126640, 4150, 58, 1, 70, "Subsubsection", CellTags->"c:47"], Cell[126701, 4153, 1365, 39, 70, "Text"], Cell[128069, 4194, 398, 15, 70, "Input"], Cell[128470, 4211, 211, 5, 70, "Input"], Cell[128684, 4218, 3078, 84, 70, "Text"] }, Closed]], Cell[CellGroupData[{ Cell[131799, 4307, 63, 1, 70, "Subsubsection", CellTags->"c:48"], Cell[131865, 4310, 278, 5, 70, "Text"], Cell[132146, 4317, 49, 4, 70, "InlineInput"], Cell[132198, 4323, 631, 12, 70, "Text"], Cell[132832, 4337, 500, 15, 70, "Input"], Cell[133335, 4354, 437, 7, 70, "Text"], Cell[133775, 4363, 253, 9, 70, "Input"], Cell[134031, 4374, 41, 0, 70, "Input"], Cell[134075, 4376, 55, 0, 70, "Input"], Cell[134133, 4378, 39, 0, 70, "Input"], Cell[134175, 4380, 267, 5, 70, "Text"], Cell[134445, 4387, 28, 0, 70, "Input"], Cell[134476, 4389, 50, 0, 70, "Text"], Cell[134529, 4391, 40, 0, 70, "Input"] }, Closed]] }, Closed]] }, Closed]] }, Open ]] } ] *) (******************************************************************* End of Mathematica Notebook file. *******************************************************************)