(***********************************************************************
Mathematica-Compatible Notebook
This notebook can be used on any computer system with Mathematica 4.0,
MathReader 4.0, or any compatible application. 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[ 76928, 2077]*)
(*NotebookOutlinePosition[ 77604, 2101]*)
(* CellTagsIndexPosition[ 77560, 2097]*)
(*WindowFrame->Normal*)
Notebook[{
Cell[TextData[{
"Data structures and efficient algorithms in ",
StyleBox["Mathematica",
FontSlant->"Italic"]
}], "Title"],
Cell["\<\
Daniel Lichtblau
Wolfram Research, Inc.
October, 1999\
\>", "Author"],
Cell[CellGroupData[{
Cell["Abstract", "Subsection"],
Cell[TextData[{
"Certain data structures and algorithms for their manipulation pervade \
computer science. It seems that many of these are not commonly encountered in \
",
StyleBox["Mathematica",
FontSlant->"Italic"],
" programming. In this talk we show how many data structures may be \
implemented and used effectively, giving simple ",
StyleBox["Mathematica",
FontSlant->"Italic"],
" examples."
}], "Text"]
}, Closed]],
Cell[CellGroupData[{
Cell["Initialization", "Subsection"],
Cell[BoxData[{
\(\(Off[General::spell];\)\), "\[IndentingNewLine]",
\(\(Off[General::spell1];\)\)}], "Input"]
}, Closed]],
Cell[CellGroupData[{
Cell["Introduction", "Subsection"],
Cell[TextData[{
"We will discuss definitions (briefly) of sparse arrays, stacks, queues, \
trees (especially the binary flavor), and bitvectors. We will show how these \
may be implemented in ",
StyleBox["Mathematica",
FontSlant->"Italic"],
" and will give simple but effective examples of each in use. In many cases \
we will also see, by way of contrast, equivalent simple code that is \
ineffective on sizable problems precisely because it ignores these basic \
techniques; think of this as a sort of morality play."
}], "Text"],
Cell["\<\
One will observe that some examples in subsequent sections make use \
of common techniques. For example, one sparse array example also uses a \
stack, and the queue implementation uses sparse arrays. This gives further \
credence to the claim that these simple methods are in some sense \
fundamental.\
\>", "Text"],
Cell["\<\
References for the techniques presented herein include:
(1980) Data Structure Techniques, Standish, Thomas. Addison Wesley.
(1974) The Design and Analysis of Computer Algorithms, Aho, Alfred, Hopcroft, \
John, Ullmann, Jeffrey. Addison Wesley.\
\>", "Text"]
}, Closed]],
Cell[CellGroupData[{
Cell["Tables (lists)", "Subsection"],
Cell[TextData[{
"The villain in many examples below is the garden-variety ",
StyleBox["Mathematica",
FontSlant->"Italic"],
" list. This is of course unfair. Lists are the most useful of data \
structures in ",
StyleBox["Mathematica",
FontSlant->"Italic"],
". They are actually fixed-length vectors (often called vectors or arrays \
elsewhere in computer science, as distinct from what are called linked \
lists), and this is their chief drawback. Specifically, one cannot extend \
them efficiently. Indeed, much of this notebook is devoted to examples where \
extensible data structures are a must. That said, applications for which a \
fixed size table may be used are typically the most efficient."
}], "Text"],
Cell[TextData[{
"There are several reasons for this. First, element retrieval is constant \
time. Second, all functional programming in ",
StyleBox["Mathematica",
FontSlant->"Italic"],
" is geared toward list structures. Third, when elements may all be \
represented by machine numbers of the same type, ",
StyleBox["Mathematica",
FontSlant->"Italic"],
" can used packed arrays internally which are both less memory-consumptive \
and faster for element access and other operations. Indeed, for many purposes \
one can use the ",
StyleBox["Compile",
FontWeight->"Bold"],
" function, getting still further improvement in speed."
}], "Text"],
Cell["\<\
To give some indication of relative speed of building a fixed size \
table vs. a nested list, we show simple examples below.\
\>", "Text"],
Cell[CellGroupData[{
Cell[BoxData[{
\(Timing[\(t1 = Table[N[j], {j, 10^6}];\)]\), "\[IndentingNewLine]",
\(\(t2 = {};\)\), "\[IndentingNewLine]",
\(Timing[Do[t2 = {t2, N[j]}, {j, 10^6}]]\), "\[IndentingNewLine]",
\(Timing[\(t3 = Flatten[t2];\)]\), "\[IndentingNewLine]",
\(t3 === t1\)}], "Input"],
Cell[BoxData[
\({1.02`\ Second, Null}\)], "Output"],
Cell[BoxData[
\({21.01`\ Second, Null}\)], "Output"],
Cell[BoxData[
\({2.3699999999999974`\ Second, Null}\)], "Output"],
Cell[BoxData[
\(True\)], "Output"]
}, Open ]],
Cell[TextData[{
"While it is clear that tables are faster to build for such an example, one \
can show that nested list construction at least has the appropriate linear \
complexity, hence is not a bad alternative for applications where \
fixed-length tables are inappropriate. We will see an example of this sort \
presently. It should also be noted that much of the speed advantage of ",
StyleBox["Table",
FontWeight->"Bold"],
" in the above example is due to use of packed arrays. For, say, tables of \
symbolic expressions, this is greatly diminished."
}], "Text"],
Cell[CellGroupData[{
Cell[BoxData[{
\(Timing[\(t1 = Table[a[j], {j, 10^5}];\)]\), "\[IndentingNewLine]",
\(\(t2 = {};\)\), "\[IndentingNewLine]",
\(Timing[Do[t2 = {t2, a[j]}, {j, 10^5}]]\), "\[IndentingNewLine]",
\(Timing[\(t3 = Flatten[t2];\)]\), "\[IndentingNewLine]",
\(t3 === t1\)}], "Input"],
Cell[BoxData[
\({0.9899999999999807`\ Second, Null}\)], "Output"],
Cell[BoxData[
\({1.660000000000025`\ Second, Null}\)], "Output"],
Cell[BoxData[
\({0.4899999999999807`\ Second, Null}\)], "Output"],
Cell[BoxData[
\(True\)], "Output"]
}, Open ]]
}, Closed]],
Cell[CellGroupData[{
Cell["Sparse arrays (hash tables)", "Subsection"],
Cell[TextData[{
StyleBox["Sparse arrays",
FontVariations->{"CompatibilityType"->0}],
" are quite simple, and are among the most heavily used of data structures \
in ",
StyleBox["Mathematica",
FontSlant->"Italic"],
StyleBox[" (often without giving that name to them).",
FontVariations->{"CompatibilityType"->0}],
StyleBox[" ",
FontSlant->"Italic"],
StyleBox["One uses them to store values associated to \"indices\" attached \
to a given \"head.\" But this head need not be an atom, and, unlike ",
FontVariations->{"CompatibilityType"->0}],
StyleBox["Mathematica",
FontSlant->"Italic",
FontVariations->{"CompatibilityType"->0}],
StyleBox[" part specifications, the indices need not be positive integers. \
When left-hand-sides of such indices are free of patterns, ",
FontVariations->{"CompatibilityType"->0}],
StyleBox["Mathematica",
FontSlant->"Italic",
FontVariations->{"CompatibilityType"->0}],
StyleBox[" will compute what is called a \"hash value\" for them; think of \
these as positive integers that can be used as an index into an actual table \
(more on this below).",
FontVariations->{"CompatibilityType"->0}]
}], "Text"],
Cell[TextData[{
StyleBox["Below we use the symbol ",
FontVariations->{"CompatibilityType"->0}],
StyleBox["a",
FontWeight->"Bold",
FontVariations->{"CompatibilityType"->0}],
StyleBox[" as a head for a sparse array defined for three particular \
indices.",
FontVariations->{"CompatibilityType"->0}]
}], "Text"],
Cell[CellGroupData[{
Cell[BoxData[{
\(Clear[a]\), "\[IndentingNewLine]",
\(\(\(a[4]\)[5] = 3;\)\), "\[IndentingNewLine]",
\(\(a["\", Pi] = {y7, 1};\)\), "\[IndentingNewLine]",
\(\(a[{1, 2, q}]\ = \ xyz;\)\), "\[IndentingNewLine]",
\(?? a\)}], "Input"],
Cell[BoxData[
\("Global`a"\)], "Print"],
Cell[BoxData[
InterpretationBox[GridBox[{
{GridBox[{
{\(\(a[4]\)[5] = 3\)}
},
GridBaseline->{Baseline, {1, 1}},
ColumnWidths->0.999,
ColumnAlignments->{Left}]},
{" "},
{GridBox[{
{\(a[{1, 2, q}] = xyz\)},
{" "},
{\(a["string index", \[Pi]] = {y7, 1}\)}
},
GridBaseline->{Baseline, {1, 1}},
ColumnWidths->0.999,
ColumnAlignments->{Left}]}
},
GridBaseline->{Baseline, {1, 1}},
ColumnAlignments->{Left}],
Definition[ a],
Editable->False]], "Print"]
}, Open ]],
Cell[TextData[{
"One might (and frequently will) choose to view such definitions as \
something other than a sparse array. For example, one often defines ",
StyleBox["Mathematica",
FontSlant->"Italic"],
" functions in this way. But most often function definitions will rely on \
",
StyleBox["Mathematica",
FontSlant->"Italic"],
" patterns and this disqualifies them from being sparse arrays in an \
important aspect.. Specifically, it is only families of associated values \
free of patterns that may be hashed. This is both because pattern matching \
relies heavily on technology that is intrinsically non-hashable and because \
rule ordering neecessary for pattern matching precludes look-up based on \
hashed values."
}], "Text"],
Cell[TextData[{
"What is the benefit of these sparse arrays? It all boils down to \
efficiency. The ",
StyleBox["Mathematica",
FontSlant->"Italic"],
" kernel will compute what is called a \"hash value\" for each \
left-hand-side, and use that to place it into an internal data structure with \
associated right-hand-value. While multiple left-hand-sides might have the \
same hash value and hence be placed in the same bin, the ",
StyleBox["Mathematica",
FontSlant->"Italic"],
" kernel checks that bins do not grow too large, rehashing to a larger \
space when need be. The upshot is that if we assume the computation of a hash \
value is constant time, then:\n(i) Adding new elements to such a table is, on \
average, constant time.\n(ii) Element look-up is, on average, constant time.\n\
Hence we may use such arrays to store values and retrieve them quickly. Below \
we show simple implementations of a union that does not sort its elements. \
One uses ",
StyleBox["Mathematica",
FontSlant->"Italic"],
" lists and the other uses a sparse array."
}], "Text"],
Cell[BoxData[
\(unionNoSort1[ll__List] :=
Module[{htable, mylist, all, result = {}},
all = Join[ll]; \[IndentingNewLine]Do[
If[\(! MemberQ[result, all[\([j]\)]]\), \[IndentingNewLine]AppendTo[
result, all[\([j]\)]]], \[IndentingNewLine]{j,
Length[all]}]; \[IndentingNewLine]result]\)], "Input"],
Cell[BoxData[
\(unionNoSort2[ll__List] :=
Module[{htable, newlist, all, result},
result = newlist[]; \[IndentingNewLine]all =
Join[ll]; \[IndentingNewLine]Do[
If[\(! TrueQ[htable[all[\([j]\)]]]\),
htable[all[\([j]\)]] = True; \[IndentingNewLine]result =
newlist[result, all[\([j]\)]]], {j,
Length[all]}]; \[IndentingNewLine]result =
Apply[List,
Flatten[result, Infinity, newlist]]; \[IndentingNewLine]Clear[
htable]; \[IndentingNewLine]result]\)], "Input"],
Cell["First we check that these give the same results.", "Text"],
Cell[CellGroupData[{
Cell[BoxData[{
\(\(uni1 =
unionNoSort1[Range[50],
Reverse[Range[100]], {300, 400, 399}];\)\), "\[IndentingNewLine]",
\(uni2 =
unionNoSort2[Range[50],
Reverse[Range[100]], {300, 400, 399}]\), "\[IndentingNewLine]",
\(uni1 === uni2\)}], "Input"],
Cell[BoxData[
\({1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20,
21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38,
39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 100, 99, 98, 97, 96,
95, 94, 93, 92, 91, 90, 89, 88, 87, 86, 85, 84, 83, 82, 81, 80, 79, 78,
77, 76, 75, 74, 73, 72, 71, 70, 69, 68, 67, 66, 65, 64, 63, 62, 61, 60,
59, 58, 57, 56, 55, 54, 53, 52, 51, 300, 400, 399}\)], "Output"],
Cell[BoxData[
\(True\)], "Output"]
}, Open ]],
Cell["Now we check speed and algorithmic complexity.", "Text"],
Cell[BoxData[{
\(Timing[\(u1 =
unionNoSort1[Range[1000],
Reverse[Range[1100]]];\)]\), "\[IndentingNewLine]",
\(Timing[\(u2 =
unionNoSort1[Range[2000],
Reverse[Range[2200]]];\)]\), "\[IndentingNewLine]",
\(Timing[\(u1b =
unionNoSort2[Range[10000],
Reverse[Range[11000]]];\)]\), "\[IndentingNewLine]",
\(Timing[\(u2b =
unionNoSort2[Range[20000], Reverse[Range[22000]]];\)]\)}], "Input"],
Cell["\<\
It is quite clear that unionNoSort1 has quadratic complexity \
whereas unionNoSort2 has only linear complexity.\
\>", "Text"],
Cell[TextData[{
"There are two further observations to be made about this implementation of \
unsorted union. First, the semantics are not entirely the same as in ",
StyleBox["Union",
FontWeight->"Bold"],
" because that latter will test equivalence using ",
StyleBox["SameQ",
FontWeight->"Bold"],
" whereas ",
StyleBox["unionNoSort2 ",
FontWeight->"Bold"],
"relies on hash look-up. Second, in addition to hashing we make rudimentary \
use of a sort of \"stack\" by nesting the result we construct. We will cover \
this in more detail in the next section."
}], "Text"],
Cell[CellGroupData[{
Cell["Application: sparse sets", "Subsubsection",
CellDingbat->None],
Cell["\<\
One might use sparse arrays to represent sets with cardinality \
relatively small by comparison to the universe of allowable elements. We show \
a simple implementation of such sets, including functions to find unions, \
intersections and complements of pairs of such sets.\
\>", "Text"],
Cell[BoxData[{
\(setLength[_] := 0\[IndentingNewLine]\), "\[IndentingNewLine]",
\(containsElement[set_, elem_] :=
Head[set[elem]] =!= set\[IndentingNewLine]\), "\[IndentingNewLine]",
\(addElement[set_, elem_] :=
If[Head[set[elem]] === set,
set[elem] =
elem; \ \(setLength[
set]++\);]\[IndentingNewLine]\), "\[IndentingNewLine]",
\(removeElement[set_, elem_] :=
If[containsElement[set, elem],
set[elem] =. ; \ \(setLength[
set]--\);]\[IndentingNewLine]\), "\[IndentingNewLine]",
\(displaySet[set_] :=
Map[#[\([2]\)] &,
DownValues[set]]\[IndentingNewLine]\), "\[IndentingNewLine]",
\(setClear[set_] := \((Clear[set]; \
setLength[set] = 0;)\)\[IndentingNewLine]\), "\[IndentingNewLine]",
\(setCopy[set1_, set2_] :=
Module[{elems = displaySet[set1], j, len}, \[IndentingNewLine]setClear[
set2]; \[IndentingNewLine]len =
Length[elems]; \[IndentingNewLine]For[j = 1,
j \[LessEqual] len, \(j++\),
addElement[set2,
elems[\([j]\)]]];]\[IndentingNewLine]\), "\[IndentingNewLine]",
\(setUnion[set1_, set2_, \ result_] :=
Module[{elems, j, len}, \[IndentingNewLine]setCopy[set1,
result]; \[IndentingNewLine]elems =
Map[#[\([2]\)] &, DownValues[set2]]; \[IndentingNewLine]len =
Length[elems]; \[IndentingNewLine]For[j = 1,
j \[LessEqual] len, \(j++\),
addElement[result,
elems[\([j]\)]]];]\[IndentingNewLine]\), "\[IndentingNewLine]",
\(setIntersection[set1_, set2_, result_] :=
Module[{elems, j, len}, \[IndentingNewLine]setClear[
result]; \[IndentingNewLine]elems =
Map[#[\([2]\)] &, DownValues[set2]]; \[IndentingNewLine]len =
Length[elems]; \[IndentingNewLine]For[j = 1,
j \[LessEqual] len, \(j++\),
If[containsElement[set1, elems[\([j]\)]],
addElement[result,
elems[\([j]\)]]]];]\[IndentingNewLine]\), \
"\[IndentingNewLine]",
\(setComplement[set1_, set2_, \ result_] :=
Module[{elems, j, len}, \[IndentingNewLine]setCopy[set1,
result]; \[IndentingNewLine]elems =
Map[#[\([2]\)] &, DownValues[set2]]; \[IndentingNewLine]len =
Length[elems]; \[IndentingNewLine]For[j = 1,
j \[LessEqual] len, \(j++\),
removeElement[result, elems[\([j]\)]]];]\)}], "Input"],
Cell["Here we show some simple examples.", "Text"],
Cell[CellGroupData[{
Cell[BoxData[{
\(SeedRandom[1111]\), "\[IndentingNewLine]",
\(Timing[
Do[addElement[set1,
Random[Integer, 10000]], {3000}]]\), "\[IndentingNewLine]",
\(Timing[
Do[addElement[set2,
Random[Integer,
10000]], {3000}]]\[IndentingNewLine]\), "\[IndentingNewLine]",
\(setLength[set1]\), "\[IndentingNewLine]",
\(setLength[set2]\)}], "Input"],
Cell[BoxData[
\({0.6299999999999955`\ Second, Null}\)], "Output"],
Cell[BoxData[
\({0.6500000000000057`\ Second, Null}\)], "Output"],
Cell[BoxData[
\(2598\)], "Output"],
Cell[BoxData[
\(2595\)], "Output"]
}, Open ]],
Cell[TextData[{
"We will use ",
StyleBox["Mathematica",
FontSlant->"Italic"],
" built-in logical operations on the set elements in order to check our set \
functions for correctness."
}], "Text"],
Cell[BoxData[{
\(\(elems1 = displaySet[set1];\)\), "\[IndentingNewLine]",
\(\(elems2 =
displaySet[set2];\)\[IndentingNewLine]\), "\[IndentingNewLine]",
\(\(elemsu = Union[elems1, elems2];\)\), "\[IndentingNewLine]",
\(\(elemsi = Intersection[elems1, elems2];\)\), "\[IndentingNewLine]",
\(\(elemsc = Complement[elems1, elems2];\)\)}], "Input"],
Cell[CellGroupData[{
Cell[BoxData[{
\(Timing[setUnion[set1, \ set2, \ setu]]\), "\[IndentingNewLine]",
\(Timing[
setIntersection[set1, \ set2, \ seti]]\), "\[IndentingNewLine]",
\(Timing[
setComplement[set1, \ set2, \
setc]]\[IndentingNewLine]\), "\[IndentingNewLine]",
\(Length[elemsu] == setLength[setu]\), "\[IndentingNewLine]",
\(Length[elemsi] == setLength[seti]\), "\[IndentingNewLine]",
\(Length[elemsc] == setLength[setc]\)}], "Input"],
Cell[BoxData[
\({1.6200000000000045`\ Second, Null}\)], "Output"],
Cell[BoxData[
\({0.5500000000000114`\ Second, Null}\)], "Output"],
Cell[BoxData[
\({1.5300000000000011`\ Second, Null}\)], "Output"],
Cell[BoxData[
\(True\)], "Output"],
Cell[BoxData[
\(True\)], "Output"],
Cell[BoxData[
\(True\)], "Output"]
}, Open ]],
Cell[TextData[{
"It is easy to demonstrate that the average complexity for adding or \
removing elements is ",
"O(",
StyleBox["1",
FontVariations->{"CompatibilityType"->0}],
")",
" (that is, constant time), as expected."
}], "Text"],
Cell[CellGroupData[{
Cell[BoxData[{
\(SeedRandom[1111]\), "\[IndentingNewLine]",
\(Timing[
Do[addElement[seta3K,
Random[Integer, 5000]], {3000}]]\), "\[IndentingNewLine]",
\(Timing[
Do[addElement[setb3K,
Random[Integer, 5000]], {3000}]]\), "\[IndentingNewLine]",
\(Timing[
Do[addElement[seta30K,
Random[Integer, 50000]], {30000}]]\), "\[IndentingNewLine]",
\(Timing[
Do[addElement[setb30K, Random[Integer, 50000]], {30000}]]\)}], "Input"],
Cell[BoxData[
\({0.6800000000000068`\ Second, Null}\)], "Output"],
Cell[BoxData[
\({0.7099999999999795`\ Second, Null}\)], "Output"],
Cell[BoxData[
\({7.1299999999999955`\ Second, Null}\)], "Output"],
Cell[BoxData[
\({7.3799999999999955`\ Second, Null}\)], "Output"]
}, Open ]],
Cell[CellGroupData[{
Cell[BoxData[{
\(Timing[setUnion[seta3K, setb3K, r3k]]\), "\[IndentingNewLine]",
\(Timing[setUnion[seta30K, setb30K, r30k]]\)}], "Input"],
Cell[BoxData[
\({1.4699999999999989`\ Second, Null}\)], "Output"],
Cell[BoxData[
\({14.880000000000024`\ Second, Null}\)], "Output"]
}, Open ]]
}, Open ]]
}, Closed]],
Cell[CellGroupData[{
Cell["Stacks", "Subsection"],
Cell[TextData[{
"Stacks are data structures with a top, wherein we remove the element most \
recently placed thereon; the descriptive phrase is \"last in, first out,\" or \
LIFO for short. Stacks may be represented conveniently in ",
StyleBox["Mathematica",
FontSlant->"Italic"],
" s nested lists. We push a new element onto the top by forming the nested \
list\nnewstack = {new,oldstack}."
}], "Text"],
Cell["\<\
One finds stack uses throughout computer science algorithms. For \
example they are extremely useful for walking through expression trees. We \
give a simple example below where we flatten an expression.\
\>", "Text"],
Cell[TextData[{
"First we give simple ",
StyleBox["Mathematica",
FontSlant->"Italic"],
" code to implement a stack."
}], "Text"],
Cell[BoxData[{
\(SetAttributes[push, HoldFirst]\), "\[IndentingNewLine]",
\(push[stack_,
elem_]\ := \ \(stack\ = \ {elem,
stack}\)\), "\[IndentingNewLine]",
\(SetAttributes[pop, HoldFirst]\), "\[IndentingNewLine]",
\(pop[{}] := Null\), "\[IndentingNewLine]",
\(pop[stack_]\ := \
With[{elem = First[stack]}, \[IndentingNewLine]stack = Last[stack];
elem]\), "\[IndentingNewLine]",
\(emptyStack[stack_]\ := \ stack == {}\)}], "Input"],
Cell[TextData[{
"Next we show a stripped-down ",
StyleBox["Mathematica",
FontSlant->"Italic"],
" implementation of ",
StyleBox["Flatten",
FontWeight->"Bold"],
StyleBox[". It relies on recursion to flatten sublists and then joins the \
results.",
FontVariations->{"CompatibilityType"->0}]
}], "Text"],
Cell[BoxData[{
\(myFlatten1[xx_List] :=
With[\[IndentingNewLine]{flatparts =
Map[myFlatten1, xx]}, \[IndentingNewLine]Join[
Apply[Sequence, flatparts]]]\), "\[IndentingNewLine]",
\(myFlatten1[xx_] := {xx}\)}], "Input"],
Cell[BoxData[{
\(\(test = {};\)\), "\[IndentingNewLine]",
\(Do[test = {j, test}, \ {j, 250}]\)}], "Input"],
Cell[TextData[{
"Attempting to do this without an adequate ",
StyleBox["$RecursionLimit",
FontWeight->"Bold"],
" setting can be hazardous to the health of your ",
StyleBox["Mathematica",
FontSlant->"Italic"],
" session."
}], "Text"],
Cell[CellGroupData[{
Cell[BoxData[
\(\(\(myFlatten1[test]\)\(\ \)\( (*\ Kids, \
don' t\ try\ this\ at\ \(home!\)\ *) \)\)\)], "Input"],
Cell[BoxData[
\($RecursionLimit::"reclim" \(\(:\)\(\ \)\)
"Recursion depth of \!\(256\) exceeded."\)], "Message"],
Cell[BoxData[
\($RecursionLimit::"reclim" \(\(:\)\(\ \)\)
"Recursion depth of \!\(256\) exceeded."\)], "Message"],
Cell[BoxData[
\($RecursionLimit::"reclim" \(\(:\)\(\ \)\)
"Recursion depth of \!\(256\) exceeded."\)], "Message"],
Cell[BoxData[
\(General::"stop" \(\(:\)\(\ \)\)
"Further output of \!\($RecursionLimit :: \"reclim\"\) will be \
suppressed during this calculation."\)], "Message"],
Cell[BoxData[
\(Join::"heads" \(\(:\)\(\ \)\)
"-- Message text not found -- (\!\(List\)) (\!\(Hold\)) (\!\(1\)) \
(\!\(2\))"\)], "Message"],
Cell[BoxData[
\(Join::"heads" \(\(:\)\(\ \)\)
"-- Message text not found -- (\!\(List\)) (\!\(Hold\)) (\!\(1\)) \
(\!\(3\))"\)], "Message"]
}, Open ]],
Cell["\<\
Next we show how to implement this without recursion. We initialize \
the length of our result to zero. We then walk through our expression \
left-to-right, depth first. Every element that is a list has its sub-elements \
pushed onto the main stack. Each non-list element gets put onto a secondary \
stack containing the result elements, and we increment the length of that \
result. When the main stack is empty we have put all non-list elements onto \
the secondary stack, so we simply pop off all elements therefrom and put them \
into a table.\
\>", "Text"],
Cell[BoxData[
\(myFlatten2[xx_List] :=
Module[\[IndentingNewLine]{stack1 = {}, \ len = 0, \ elem, \
stack2 = {}}, \[IndentingNewLine]Map[push[stack1, #] &, \
xx]; \[IndentingNewLine]While[\(! emptyStack[
stack1]\), \[IndentingNewLine]elem =
pop[stack1]; \[IndentingNewLine]If\ [
ListQ[elem], \[IndentingNewLine]Map[push[stack1, #] &, \
elem], \[IndentingNewLine]push[stack2,
elem]; \(len++\)];\[IndentingNewLine]]; \
\[IndentingNewLine]Table[pop[stack2], \ {len}]\[IndentingNewLine]]\)], "Input"],
Cell[CellGroupData[{
Cell[BoxData[
\(myFlatten2[test] === Flatten[test]\)], "Input"],
Cell[BoxData[
\(True\)], "Output"]
}, Open ]],
Cell[BoxData[
\(\(test2\ = \ {\ {a, b, {c, d}, {e, {f, g, h, {i, j}}}}, {{k, l}, m},
n, {{{o, p, {q}}, {{r, s}, t}, u}, {v, w}}, x};\)\)], "Input"],
Cell[CellGroupData[{
Cell[BoxData[
\(myFlatten2[test2] === Flatten[test2]\)], "Input"],
Cell[BoxData[
\(True\)], "Output"]
}, Open ]],
Cell["\<\
It should be mentioned that this simple example illustrates a very \
common use of stacks, as a tool for algorithms that require walks through \
tree structures.\
\>", "Text"]
}, Closed]],
Cell[CellGroupData[{
Cell["Queues", "Subsection"],
Cell["\<\
A queue is like a stack except that we now must retain a pointer to \
the \"front\" and another to the \"back\" because we put new elements in one \
end and remove from the other; this is \"first in, first out,\" or FIFO for \
short. We add at the front and remove at the back. We require routines to (i) \
get a new queue, (ii) check the length and in particular check if it is empty \
(could also have a check-for-full-queue function), (iii) add elements, and \
(iv) remove elements. One method is to use a fixed size table and have front \
and back indices that wrap around.\
\>", "Text"],
Cell[BoxData[{
\(qelems = 1; \ qlen = 2; \ qsize = 3; \ qfront = 4; \
qback = 5;\), "\[IndentingNewLine]",
\(newQueue[len_Integer] /; len > 0 := {Table[0, {len}], 0, len, 1,
1}\), "\[IndentingNewLine]",
\(emptyQueue[Q_] := Q[\([qlen]\)] \[Equal] 0\), "\[IndentingNewLine]",
\(queueLength[Q_] := Q[\([qlen]\)]\), "\[IndentingNewLine]",
\(SetAttributes[enQueue, HoldFirst]\), "\[IndentingNewLine]",
\(enQueue[Q_, elem_] :=
If[Q[\([qlen]\)] \[Equal] Q[\([qsize]\)],
Print["\"], \(Q[\([qlen]\)]++\); \
\[IndentingNewLine]Q[\([qelems, Q[\([qfront]\)]]\)] =
elem; \[IndentingNewLine]Q[\([qfront]\)] =
Mod[Q[\([qfront]\)] + 1, Q[\([qsize]\)],
1];]\), "\[IndentingNewLine]",
\(SetAttributes[deQueue, HoldFirst]\), "\[IndentingNewLine]",
\(deQueue[Q_] /; emptyQueue[Q] := Null\), "\[IndentingNewLine]",
\(deQueue[
Q_] := \((\(Q[\([qlen]\)]--\); \[IndentingNewLine]Q[\([qback]\)] =
Mod[Q[\([qback]\)] + 1, Q[\([qsize]\)],
1]; \[IndentingNewLine]Q[\([qelems,
Mod[Q[\([qback]\)] - 1, Q[\([qsize]\)], 1]]\)])\)\)}], "Input"],
Cell["Here is a simple example.", "Text"],
Cell[CellGroupData[{
Cell[BoxData[{
\(\(myQ = newQueue[7];\)\), "\[IndentingNewLine]",
\(\(Map[
enQueue[myQ, #] &, {"\", "\"}];\)\), \
"\[IndentingNewLine]",
\(queueLength[myQ]\), "\[IndentingNewLine]",
\(show1 = deQueue[myQ]\)}], "Input"],
Cell[BoxData[
\(2\)], "Output"],
Cell[BoxData[
\("Hello Dolly"\)], "Output"]
}, Open ]],
Cell[CellGroupData[{
Cell[BoxData[
\(\(Map[
enQueue[myQ, #] &, {"\", "\", "\", \
"\", "\", "\", "\"}];\)\)], "Input"],
Cell[BoxData[
\("Queue is full"\)], "Print"]
}, Open ]],
Cell["\<\
We ran out of space. We'll remove an element and then we can put on \
that last one.\
\>", "Text"],
Cell[CellGroupData[{
Cell[BoxData[
\(show2 = deQueue[myQ]\)], "Input"],
Cell[BoxData[
\("West Side Story"\)], "Output"]
}, Open ]],
Cell[BoxData[
\(enQueue[myQ, "\"]\)], "Input"],
Cell[TextData[{
"If one does not want to worry about running out of space, or does not want \
to preallocate alot of memory in order to avoid this, then it is convenient \
to represent queues in ",
StyleBox["Mathematica",
FontSlant->"Italic"],
" using a sparse array. We show a way to implement this below. We require a \
symbol to give to newQueue. It determines where we attach down-values for \
queue entries. A small subtlety is due to the desire to remove from memory \
elements no longer on the queue. To this end we keep a storage slot for one \
element in the queue structure. When we de-queue an element, we temporarily \
house it in that slot, remove the sparse array reference for that queue \
member, then return the warehoused value. An alternative would be to use \
Module and declare a local variable, but this adds overhead in execution \
time."
}], "Text"],
Cell[BoxData[{
\(newQueue[sym_Symbol] := \ {Unique[sym], 0, Null, 0,
0}\), "\[IndentingNewLine]",
\(\(Clear[queueLength, emptyQueue, enQueue, deQueue];\)\), "\n",
\(qptr = 1; qlen = 2; qelem = 3; qfront = 4; qback = 5;\), "\n",
\(queueLength[Q_]\ := \ Q[\([\)\(qlen\)\(]\)]\), "\n",
\(emptyQueue[Q_] := Q[\([\)\(qlen\)\(]\)] == 0\), "\n",
\(SetAttributes[enQueue, HoldFirst]\), "\n",
\(enQueue[Q_,
elem_] := \((\(Q[\([\)\(qlen\)\(]\)]++\); \(Q[\([qfront]\)]++\); \(Q[\
\([\)\(qptr\)\(]\)]\)[Q[\([qfront]\)]] = elem;)\)\), "\n",
\(SetAttributes[deQueue, HoldFirst]\), "\n",
\(deQueue[Q_] := \((\(Q[\([\)\(qlen\)\(]\)]--\); \(Q[\([qback]\)]++\);
Q[\([\)\(qelem\)\(]\)] = \(Q[\([\)\(qptr\)\(]\)]\)[
Q[\([qback]\)]]; \(Q[\([\)\(qptr\)\(]\)]\)[Q[\([qback]\)]] =. ;
Q[\([\)\(qelem\)\(]\)])\)\)}], "Input"],
Cell["\<\
Let us see how this process works. We repeat the previous example. \
This time we'll not run out of space.\
\>", "Text"],
Cell[CellGroupData[{
Cell[BoxData[{
\(\(myQ = newQueue[qq];\)\), "\[IndentingNewLine]",
\(\(Map[
enQueue[myQ, #] &, {"\", "\"}];\)\), \
"\[IndentingNewLine]",
\(queueLength[myQ]\), "\[IndentingNewLine]",
\(show1 = deQueue[myQ]\)}], "Input"],
Cell[BoxData[
\(2\)], "Output"],
Cell[BoxData[
\("Hello Dolly"\)], "Output"]
}, Open ]],
Cell[BoxData[
\(\(Map[
enQueue[myQ, #] &, {"\", "\", "\", \
"\", "\", "\", "\"}];\)\)], "Input"],
Cell[CellGroupData[{
Cell[BoxData[{
\(show2 = deQueue[myQ]\), "\[IndentingNewLine]",
\(queueLength[myQ]\)}], "Input"],
Cell[BoxData[
\("West Side Story"\)], "Output"],
Cell[BoxData[
\(7\)], "Output"]
}, Open ]],
Cell[TextData[{
"We can see exactly what is in our queue using the ",
StyleBox["Information",
FontWeight->"Bold"],
" function. This is in some sense cheating, because queues do not have a \
function to return all elements. Regard this as a useful debugging tool to \
check the correctness of our queue. Notice that we now have no sparse array \
reference to the original first two queue elements, so we are indeed \
recycling memory."
}], "Text"],
Cell[TextData[{
"One might hybridize these approaches to get the faster access associated \
with a fixed-size array, combined with the memory management associated with \
sparse functions. This hybridization can be accomplished by, say, doubling \
the size of the table every time the queue gets full, copying over the \
entries already on it. Again we sometimes have an O(",
StyleBox["n",
FontSlant->"Italic"],
") time for an en-queue operation, but the average is O(1). If so desired, \
one can get more subtle with memory management and allow for the queue table \
to shrink by some factor, say 1/2, whenever the fraction of entries falls \
below some threshhold, e.g 1/3, of the full capacity. This again can help to \
avoid wasting space in cases of once-large queues that have shrunk \
considerably. So long as fixed ratios are used it is not hard to show that \
average time for en-queue and de-queue will be O(1) even though occasionally \
such an operation is O(",
StyleBox["n",
FontSlant->"Italic"],
")."
}], "Text"],
Cell[CellGroupData[{
Cell[BoxData[
\(Information[Evaluate[myQ[\([qptr]\)]]]\)], "Input"],
Cell[BoxData[
\("Global`qq$13"\)], "Print"],
Cell[BoxData[
InterpretationBox[GridBox[{
{GridBox[{
{\(qq$13[3] = "My Fair Lady"\)},
{" "},
{\(qq$13[4] = "Les Miz"\)},
{" "},
{\(qq$13[5] = "Phantom"\)},
{" "},
{\(qq$13[6] = "Fiddler"\)},
{" "},
{\(qq$13[7] = "Mouse Trap"\)},
{" "},
{\(qq$13[8] = "Rent"\)},
{" "},
{\(qq$13[9] = "Sleuth"\)}
},
GridBaseline->{Baseline, {1, 1}},
ColumnWidths->0.999,
ColumnAlignments->{Left}]}
},
GridBaseline->{Baseline, {1, 1}},
ColumnAlignments->{Left}],
Definition[ qq$13],
Editable->False]], "Print"]
}, Open ]],
Cell[TextData[{
"The advantage to this second approach is we only use the memory we need, \
and we do not run out (subject to machine limitations). The disadvantage is \
that, while complexity of each operation is constant time, the constants can \
be high for adding and removing elements. This is because hash table look-up \
is happening behind the scenes, and this is alot slower than simple array \
indexing. Also note that since sparse arrays are implelemted using hashing, \
occasionally adding elements will be O(",
StyleBox["n",
FontSlant->"Italic"],
") because crowding in the table can force it to double in size. Thus it is \
the average time for adding that is constant."
}], "Text"],
Cell["\<\
Here is an application of queueing. Suppose we take the stack-based \
flattening code and everywhere replace stack uses with their queue analogues. \
What might be the result?\
\>", "Text"],
Cell[BoxData[
\(funnyFlatten[xx_List] :=
Module[\[IndentingNewLine]{q1 = newQ[s1], \ len = 0, \ elem, \
q2 = newQ[s2]}, \[IndentingNewLine]Map[enQ[q1, #] &, \
xx]; \[IndentingNewLine]While[\(! emptyQ[
q1]\), \[IndentingNewLine]elem =
deQ[q1]; \[IndentingNewLine]If\ [
ListQ[elem], \[IndentingNewLine]Map[enQ[q1, #] &, \
elem], \[IndentingNewLine]enQ[q2,
elem]; \(len++\)];\[IndentingNewLine]]; \
\[IndentingNewLine]Table[deQ[q2], \ {len}]\[IndentingNewLine]]\)], "Input"],
Cell[CellGroupData[{
Cell[BoxData[
\(funnyFlatten[test]\)], "Input"],
Cell[BoxData[
\({n, x, a, b, m, c, d, e, k, l, u, v, w, f, g, h, o, p, t, i, j, q, r,
s}\)], "Output"]
}, Open ]],
Cell["\<\
One checks that in addition to flattening, we have reordered the \
non-list elements based on nesting depth. For comparison, here is a \
functional programming approach to the same problem.\
\>", "Text"],
Cell[CellGroupData[{
Cell[BoxData[{
\(e1 = MapIndexed[C, test2, {\(-1\)}]\), "\[IndentingNewLine]",
\(e2 = Cases[e1, _C, Infinity]\), "\[IndentingNewLine]",
\(\(e3 =
Sort[e2, \((Length[#1[\([2]\)]] \[LessEqual]
Length[#2[\([2]\)]])\) &];\)\), "\[IndentingNewLine]",
\(Map[First, e3]\)}], "Input"],
Cell[BoxData[
\({n, x, a, b, m, c, d, e, k, l, u, v, w, f, g, h, o, p, t, i, j, q, r,
s}\)], "Output"]
}, Open ]],
Cell["\<\
It unfortunately only works if the elements in the (nested) lists \
are atomic. It is a more challenging problem to find a clever functional \
program that does not have this limitation.\
\>", "Text"],
Cell["\<\
While queues are of interest in their own right, it is important to \
realize that the method of implementation in this section is quite general. \
One can use similar structures, implemented as sparse arrays with other \
information e.g. length also available, for a variety of purposes. For \
example, sets that can evolve over time, with members being added, removed, \
or merged in from other sets, can be handled in this way.\
\>", "Text"]
}, Closed]],
Cell[CellGroupData[{
Cell["Trees", "Subsection"],
Cell[TextData[{
"Among the most pervasive data structures in computer science are trees. A \
tree consists of a root containing some atomic value, and children which are \
themselves either atomic values or subtrees. For example, the expression ",
StyleBox["(a+b)*c*Sin[x]",
FontWeight->"Bold"],
" can be regarded as a tree with ",
StyleBox["Times",
FontWeight->"Bold"],
" as its root and children that are respectively the subtree ",
StyleBox["Plus[a,b]",
FontWeight->"Bold"],
", the atom ",
StyleBox["c",
FontWeight->"Bold"],
", and the subtree ",
StyleBox["Sin[x]",
FontWeight->"Bold"],
" ."
}], "Text"],
Cell[TextData[{
"Trees are used in a variety of algorithms both for reasons of efficiency \
and because many data abstractions are best modelled via trees. Indeed, all \
",
StyleBox["Mathematica",
FontSlant->"Italic"],
" expressions fall into the class of structures known as \"directed acyclic \
graphs (DAGs), and these are a small generalization of trees."
}], "Text"],
Cell[TextData[{
"A particularly simple flavor is known as a binary tree. Each subtree has \
at most two children, referred to by the terms \"left\" and \"right.\" Such \
trees may be used to implement fast average-time sorting algorithms. The \
simplest example is shown below. We build a tree by placing new elements to \
the left or right of a given node according to ordering between node and new \
element. Once all are in the tree we flatten it; the result is a sorted \
version of the original set. If we have ",
StyleBox["n",
FontWeight->"Bold"],
" elements then the average-case complexity is ",
StyleBox["O(",
FontVariations->{"CompatibilityType"->0}],
StyleBox["n",
FontSlant->"Italic",
FontVariations->{"CompatibilityType"->0}],
StyleBox["*log(",
FontVariations->{"CompatibilityType"->0}],
StyleBox["n",
FontSlant->"Italic",
FontVariations->{"CompatibilityType"->0}],
StyleBox["))",
FontVariations->{"CompatibilityType"->0}],
". This is because each atom (typically) will be at depth not much more \
than ",
StyleBox["log(",
FontVariations->{"CompatibilityType"->0}],
StyleBox["n",
FontSlant->"Italic",
FontVariations->{"CompatibilityType"->0}],
StyleBox[")",
FontVariations->{"CompatibilityType"->0}],
", hence each of ",
StyleBox["n",
FontSlant->"Italic"],
" insertions averages that many steps."
}], "Text"],
Cell[TextData[{
"Below we implement an ordered binary tree. We use ",
StyleBox["Mathematica",
FontSlant->"Italic"],
" canonical ordering to compare elements. We also use ",
StyleBox["List",
FontWeight->"Bold"],
" as our head for each triple ",
StyleBox["{left,val,right}",
FontWeight->"Bold"],
". This effectively precludes use of lists for element values. One can use \
a different head to get around this drawback, but for our purposes this \
suffices."
}], "Text"],
Cell[BoxData[{
\(leftsubtree[{left_, _, _}]\ := \ left\), "\[IndentingNewLine]",
\(rightsubtree[{_, _, right_}] := right\), "\[IndentingNewLine]",
\(nodevalue[{_, val_, _}] := val\), "\[IndentingNewLine]",
\(\(emptyTree\ = \ {};\)\[IndentingNewLine]\), "\n",
\(treeInsert[emptyTree, \ elem_]\ := \ {emptyTree, elem,
emptyTree}\), "\n",
\(treeInsert[tree_, \ elem_]\ /; \ SameQ[nodevalue[tree], \ elem]\ :=
tree\), "\n",
\(treeInsert[tree_, \ elem_]\ /; \
OrderedQ[{nodevalue[tree], \ elem}]\ := \n\t{leftsubtree[tree], \
nodevalue[tree], \ treeInsert[rightsubtree[tree], \ elem]}\), "\n",
\(treeInsert[tree_, \
elem_]\ := \ {treeInsert[leftsubtree[tree], \ elem], \
nodevalue[tree], rightsubtree[tree]}\)}], "Input"],
Cell["\<\
Now we run a few examples and demonstrate that this does indeed \
sort the original list of elements. We gather timings to check algorithmic \
complexity.\
\>", "Text"],
Cell[CellGroupData[{
Cell[BoxData[{
\(\(len1k = 1000;\)\), "\[IndentingNewLine]",
\(\(ee1k = Table[Random[], {len1k}];\)\), "\[IndentingNewLine]",
\(\(ff1k = {};\)\), "\[IndentingNewLine]",
\(t1k =
First[Timing[\(Do[
ff1k = treeInsert[ff1k, ee1k[\([j]\)]], {j, len1k}];\)]]/
Second\), "\[IndentingNewLine]",
\(\(gg1k = Flatten[ff1k];\)\), "\[IndentingNewLine]",
\(gg1k === Sort[ee1k]\)}], "Input"],
Cell[BoxData[
\(1.539999999999992`\)], "Output"],
Cell[BoxData[
\(True\)], "Output"]
}, Open ]],
Cell[CellGroupData[{
Cell[BoxData[{
\(\(len5k = 5000;\)\), "\[IndentingNewLine]",
\(\(ee5k = Table[Random[], {len5k}];\)\), "\[IndentingNewLine]",
\(\(ff5k = {};\)\), "\[IndentingNewLine]",
\(t5k =
First[Timing[\(Do[
ff5k = treeInsert[ff5k, ee5k[\([j]\)]], {j, len5k}];\)]]/
Second\), "\[IndentingNewLine]",
\(\(gg5k = Flatten[ff5k];\)\), "\[IndentingNewLine]",
\(gg5k === Sort[ee5k]\)}], "Input"],
Cell[BoxData[
\(11.459999999999994`\)], "Output"],
Cell[BoxData[
\(True\)], "Output"]
}, Open ]],
Cell[CellGroupData[{
Cell[BoxData[{
\(\(len10k = 10000;\)\), "\[IndentingNewLine]",
\(\(ee10k = Table[Random[], {len10k}];\)\), "\[IndentingNewLine]",
\(\(ff10k = {};\)\), "\[IndentingNewLine]",
\(t10k =
First[Timing[\(Do[
ff10k = treeInsert[ff10k, ee10k[\([j]\)]], {j, len10k}];\)]]/
Second\), "\[IndentingNewLine]",
\(\(gg10k = Flatten[ff10k];\)\), "\[IndentingNewLine]",
\(gg10k === Sort[ee10k]\)}], "Input"],
Cell[BoxData[
\(24.530000000000015`\)], "Output"],
Cell[BoxData[
\(True\)], "Output"]
}, Open ]],
Cell[TextData[{
"With this data we can now see that the algorithmic complexity is roughly \
as billed, ",
"O(",
StyleBox["n",
FontSlant->"Italic"],
"*log(",
StyleBox["n",
FontSlant->"Italic"],
"))",
"."
}], "Text"],
Cell[CellGroupData[{
Cell[BoxData[
\({\((t5k/t1k)\)\ /\ \[IndentingNewLine]\((5000. *
Log[5000. ]/\((1000. *
Log[1000. ])\))\), \[IndentingNewLine]\((t10k/
t1k)\)\ /\ \[IndentingNewLine]\((10000. *
Log[10000. ]/\((1000. *
Log[1000. ])\))\), \[IndentingNewLine]\((t10k/
t5k)\)\ /\[IndentingNewLine]\((10000. *
Log[10000. ]/\((5000. *Log[5000. ])\))\)}\)], "Input"],
Cell[BoxData[
\({1.2070752289694655`, 1.1946428571428638`,
0.9897004167360672`}\)], "Output"]
}, Open ]],
Cell[TextData[{
"It should be noted that this sorting algorithm takes a minor shortcut. In \
ordering elements in a tree node as ",
StyleBox["{left,val,right}",
FontWeight->"Bold"],
" we may simply recover the sorted list using ",
StyleBox["Flatten",
FontWeight->"Bold"],
". A different internal node element ordering would not support this. We \
could more generally use a stack and walk the tree, as was done in the code \
to emulate ",
StyleBox["Flatten",
FontWeight->"Bold"],
", and this would still give the appropriate algorithmic complexity",
StyleBox[".",
FontWeight->"Bold"]
}], "Text"]
}, Closed]],
Cell[CellGroupData[{
Cell["Bitvectors", "Subsection"],
Cell[TextData[{
"Sometimes one needs to represent elements of the power set of a given set \
of ",
StyleBox["n", "InputWord"],
" elements, for n not too large. For such purposes one may represent \
elemets of the power set by integers in the range from 0 to ",
Cell[BoxData[
\(2\^n - 1\)]],
". A value m in this range can represent a given subset by its binary \
string, where 1's stand for those elements present in the subset."
}], "Text"],
Cell[TextData[{
"For example, say we have a set of 100 elements. We will use integers in \
the range from 0 to ",
Cell[BoxData[
\(2\^100 - 1\)]],
" to represent subsets, and take a random subset of, say, 128 elements in \
the power set (that is, subset whose elements are subsets of the original \
set). Actually, there is nonzero probability that my subset contains stricly \
fewer than 128 elements, but this is still okay for the examples below."
}], "Text"],
Cell[BoxData[
\(k = 100; len = 128;
subs = Union[Table[Random[Integer, {0, 2\^k - 1}], {len}]];\)], "Input"],
Cell["\<\
A reasonable question might be: \"How many elements of subs contain \
the third element of the original set?\" To answer this we represent the \
elements of the original set as \"bit masks\", that is, integer powers of \
two.\
\>", "Text"],
Cell[BoxData[
\(masks = Table[2\^m, {m, 0, k - 1}]; k =. \)], "Input"],
Cell[TextData[{
"So the third element of the set is ",
StyleBox["masks[[3]]", "InputWord",
FontWeight->"Bold"],
", which is 2^2, or 4. We form the function that takes an integer and \
computes its bitwise AND with ",
StyleBox["masks[[3]]", "InputWord",
FontWeight->"Bold"],
". We ",
StyleBox["Map", "InputWord",
FontWeight->"Bold"],
" this function over the subset list subs, then count the number of \
elements in the result that are positive. The bitwise operation has masked \
out all but the third binary digit of each member of ",
StyleBox["subs", "InputWord"],
", so the positive values resulting (all will be 4) are from those member \
that have a third binary digit set."
}], "Text"],
Cell[CellGroupData[{
Cell[BoxData[{
\(\(func\ = \ BitAnd[masks[\([3]\)], #] &;\)\n\), "\n",
\(Count[Map[func, \ subs], \ _?Positive]\)}], "Input"],
Cell[BoxData[
\(70\)], "Output"]
}, Open ]],
Cell[TextData[{
"Okay, easy enough. How about \"How many members of subs contain the sixth \
and eleventh elements of the original set, but not the fourteenth?\" (one \
might expect on average that this would be about an eighth of the number of \
elements in ",
StyleBox["subs", "InputWord"],
"). Same idea."
}], "Text"],
Cell[CellGroupData[{
Cell[BoxData[{
\(\(func2\ = \
BitAnd[masks[\([6]\)] + masks[\([11]\)] +
masks[\([14]\)], \ #] &;\)\), "\n",
\(\(criterion\ = \ \((# ==
masks[\([6]\)] + masks[\([11]\)])\) &;\)\n\), "\n",
\(Count[Map[func2, \ subs], \ _?criterion]\)}], "Input"],
Cell[BoxData[
\(11\)], "Output"]
}, Open ]],
Cell["\<\
What about \"How many elements contain at least two from among the \
fourth, tenth, twenty-eighth, and fifty-first elements of the original set?\" \
As before, we first mask appropriately.\
\>", "Text"],
Cell[BoxData[
\(\(func3\ = \
BitAnd[masks[\([4]\)] + masks[\([10]\)] + masks[\([28]\)] +
masks[\([51]\)], #] &;\)\)], "Input"],
Cell[TextData[{
"Now we simply ",
StyleBox["Count", "InputWord",
FontWeight->"Bold"],
" all those masked values whose binary ",
StyleBox["DigitCount", "InputWord",
FontWeight->"Bold"],
" is at least two."
}], "Text"],
Cell[CellGroupData[{
Cell[BoxData[
\(Count[
Map[func3, \ subs], \ _?\((DigitCount[#, 2, 1] >= 2 &)\)]\)], "Input"],
Cell[BoxData[
\(79\)], "Output"]
}, Open ]],
Cell[TextData[{
"It is a simple matter to perform the basic set operations on sets \
represented as bitvectors. Set union is obtained with ",
StyleBox["BitOr",
FontWeight->"Bold"],
", intersection with ",
StyleBox["BitAnd",
FontWeight->"Bold"],
", and complement is only a little more complicated."
}], "Text"],
Cell[BoxData[{
\(bitUnion[a_, b_] := BitOr[a, b]\), "\[IndentingNewLine]",
\(bitIntersection[a_, b_] := BitAnd[a, b]\), "\[IndentingNewLine]",
\(bitComplement[a_, b_] := BitAnd[a, BitNot[b]]\)}], "Input"],
Cell[CellGroupData[{
Cell["Application: working with a matrix modulo 2", "Subsubsection",
CellDingbat->None],
Cell[TextData[{
"For some number-theoretic algorithms such as factoring integers, one wants \
to find relations among a set of vectors modulo 2. Specifically, we suppose \
we have a matrix (regard it as a set of row vectors) where all elements are \
zeros and ones. We want to find elements of the null space. A simple way to \
get a generating set of this space is via ",
StyleBox["NullSpace[Transpose[mat], Modulus->2]", "InlineInput"],
"."
}], "Text"],
Cell["\<\
One problem is that even with packed arrays we still require four \
bytes per entry. Clearly we can pack bits tighter than that!. Moreover it is \
not hard to see that we can avoid some work if we are willing to settle for, \
say, just one null vector. To this end, another method for finding these null \
vectors will prove useful. We augment on the right of the matrix by an \
identity matrix and then row reduce modulo 2. The values in the augmented \
columns record the operations that were done. Hence any row that has zeroes \
in the original columns tells us how to obtain a null vector using the \
information in the augmented columns. If any row suits the purpose then the \
last one must do so, because pivots are in increasing columns. So we simply \
look at that last column. Code to do this is as follows. First we set up an \
example. It is \"typical\" for the type of application mentioned in that it \
is approximately square.\
\>", "Text"],
Cell[BoxData[{
\(\(len = 400;\)\), "\[IndentingNewLine]",
\(\(ncols = 390;\)\), "\[IndentingNewLine]",
\(\(SeedRandom[1111];\)\), "\[IndentingNewLine]",
\(\(mat\ = \ \[IndentingNewLine]Table[
Random[Integer], {len}, \ {ncols}];\)\), "\[IndentingNewLine]",
\(\(augmat\ = \
Transpose[Join[Transpose[mat], \ IdentityMatrix[len]]];\)\)}], "Input"],
Cell["\<\
Now we do the augmentation and row reduction. We ascertain that the \
original columns in the last row all have zeroes, and that the augmented part \
of that row gives a null vector.\
\>", "Text"],
Cell[CellGroupData[{
Cell[BoxData[{
\(Timing[\(rows =
RowReduce[augmat, Modulus \[Rule] 2];\)]\), "\[IndentingNewLine]",
\(\(first = Take[rows[\([len]\)], ncols];\)\), "\[IndentingNewLine]",
\(Max[first]\), "\[IndentingNewLine]",
\(\(last = Drop[rows[\([len]\)], ncols];\)\), "\[IndentingNewLine]",
\(Max[Mod[last . mat, 2]]\)}], "Input"],
Cell[BoxData[
\({17.8`\ Second, Null}\)], "Output"],
Cell[BoxData[
\(0\)], "Output"],
Cell[BoxData[
\(0\)], "Output"]
}, Open ]],
Cell["Let us compare to finding a null space directly.", "Text"],
Cell[CellGroupData[{
Cell[BoxData[{
\(Timing[\(nulls =
NullSpace[Transpose[mat],
Modulus \[Rule] 2];\)]\), "\[IndentingNewLine]",
\(Max[Mod[nulls[\([1]\)] . mat, 2]]\)}], "Input"],
Cell[BoxData[
\({5.890000000000001`\ Second, Null}\)], "Output"],
Cell[BoxData[
\(0\)], "Output"]
}, Open ]],
Cell[TextData[{
"Using ",
StyleBox["NullSpace", "InlineInput"],
" was alot faster. By approximately a factor of about three, which is now \
surprise if you think about the underlying Gaussian elimination that is done. \
Thus far we have neither used bit vectors nor seen an advantage to the \
augmented matrix row reduction method. Here it is. We can treat each vector \
as a bit vector, thus saving alot of space. As we are doing Gaussian \
elimination modulo 2, the only operation consists of adding vectors to one \
another elementwise. This is easily seen to be equivalent to bitwise \
exclusive-or. A second area for speed improvement is that we need not do full \
row reduction, but only triangulate until we have a row of zeroes in the \
original columns (unless one wants more independent generators of the null \
space)."
}], "Text"],
Cell["\<\
Below is code to implement this matrix triangulation method using \
bitvectors.\
\>", "Text"],
Cell[BoxData[{
\(getMaxPos[mat_, j_] :=
Module[{big = Developer`BitLength[mat[\([j]\)]], indx = j,
len = Length[mat], nbits},
Do[nbits = Developer`BitLength[mat[\([k]\)]]; \[IndentingNewLine]If[
nbits > big, big = nbits; \ indx = k], {k, j + 1,
len}]; \[IndentingNewLine]indx]\), "\[IndentingNewLine]",
\(getNullVec[mat_] :=
Module[{len = Length[mat], new = mat, j, k, indx, nbits, tmp1, tmp2,
jth, kth, bigrow, blen, bigblen},
bigrow = getMaxPos[new, 1]; \[IndentingNewLine]tmp1 =
Do[\[IndentingNewLine]If[j \[NotEqual] bigrow,
new[\([{j, bigrow}]\)] =
new[\([{bigrow, j}]\)]]; \[IndentingNewLine]jth =
new[\([j]\)]; \[IndentingNewLine]nbits =
Developer`BitLength[jth]; \[IndentingNewLine]bigblen =
0; \[IndentingNewLine]tmp2 =
Do[kth = new[\([k]\)]; \[IndentingNewLine]blen =
Developer`BitLength[kth]; \[IndentingNewLine]If[
blen \[Equal] nbits,
kth = BitXor[kth, jth]; \[IndentingNewLine]blen =
Developer`BitLength[kth]; \[IndentingNewLine]If[
blen \[LessEqual] len,
Return[IntegerDigits[kth, 2,
len]]]; \[IndentingNewLine]new[\([k]\)] =
kth;]; \[IndentingNewLine]If[blen > bigblen,
bigrow = k; \ bigblen = blen], {k, j + 1,
len}]; \[IndentingNewLine]If[tmp2 =!= Null,
Return[tmp2]], {j, 1,
len}]; \[IndentingNewLine]tmp1]\)}], "Input"],
Cell["\<\
We illustrate on the example above. We must first translate the \
matrix to a list of bitvectors (nonnegative integers).\
\>", "Text"],
Cell[BoxData[{
\(\(zerovec = Table[0, {len}];\)\), "\[IndentingNewLine]",
\(\(SeedRandom[1111];\)\), "\[IndentingNewLine]",
\(\(numvec1 =
Table[ii =
Table[Random[Integer], {ncols}]; \[IndentingNewLine]augvec =
zerovec; \[IndentingNewLine]augvec[\([j]\)] =
1; \[IndentingNewLine]FromDigits[Join[ii, augvec],
2], \[IndentingNewLine]{j, len}];\)\)}], "Input"],
Cell["\<\
Now we obtain a null vector for this matrix and check that it is \
indeed such.\
\>", "Text"],
Cell[CellGroupData[{
Cell[BoxData[{
\(Timing[\(nullvec = getNullVec[numvec1];\)]\), "\[IndentingNewLine]",
\(Max[Mod[nullvec . mat, 2]]\)}], "Input"],
Cell[BoxData[
\({8.049999999999997`\ Second, Null}\)], "Output"],
Cell[BoxData[
\(0\)], "Output"]
}, Open ]],
Cell[TextData[{
"Still slower than using ",
StyleBox["Nullspace", "InlineInput"],
" directly. But the interesting fact is that the asymptotic complexity is \
better. If we double the size of the input then the ",
StyleBox["Nullspace", "InlineInput"],
" or ",
StyleBox["RowReduce", "InlineInput"],
" methods will take around eight times longer, as they are O(",
Cell[BoxData[
\(TraditionalForm\`n\^3\)]],
") complexity algorithms. In contrast, for inputs in the size range up to \
several thousands, the bitvector formulation is only O(",
Cell[BoxData[
\(TraditionalForm\`n\^2\)]],
"). This is because the bitwise operations are sufficiently fast as to be \
treated as constant speed up to a large size, so in effect other code in the \
loops dominates. We illustrate by multiplying the size of the example by \
four."
}], "Text"],
Cell[BoxData[{
\(\(len = 1600;\)\), "\[IndentingNewLine]",
\(\(ncols = 1560;\)\), "\[IndentingNewLine]",
\(\(SeedRandom[1111];\)\), "\[IndentingNewLine]",
\(\(mat\ = \ \[IndentingNewLine]Table[
Random[Integer], {len}, \ {ncols}];\)\), "\[IndentingNewLine]",
\(\(augmat\ = \
Transpose[Join[Transpose[mat], \ IdentityMatrix[len]]];\)\)}], "Input"],
Cell[BoxData[{
\(\(zerovec = Table[0, {len}];\)\), "\[IndentingNewLine]",
\(\(SeedRandom[1111];\)\), "\[IndentingNewLine]",
\(\(numvec1 =
Table[ii =
Table[Random[Integer], {ncols}]; \[IndentingNewLine]augvec =
zerovec; \[IndentingNewLine]augvec[\([j]\)] =
1; \[IndentingNewLine]FromDigits[Join[ii, augvec],
2], \[IndentingNewLine]{j, len}];\)\)}], "Input"],
Cell[CellGroupData[{
Cell[BoxData[{
\(Timing[\(nulls =
NullSpace[Transpose[mat],
Modulus \[Rule] 2];\)]\), "\[IndentingNewLine]",
\(Max[Mod[nulls[\([1]\)] . mat, 2]]\)}], "Input"],
Cell[BoxData[
\({341.03`\ Second, Null}\)], "Output"],
Cell[BoxData[
\(0\)], "Output"]
}, Open ]],
Cell[CellGroupData[{
Cell[BoxData[{
\(Timing[\(nullvec = getNullVec[numvec1];\)]\), "\[IndentingNewLine]",
\(Max[Mod[nullvec . mat, 2]]\)}], "Input"],
Cell[BoxData[
\({131.16000000000003`\ Second, Null}\)], "Output"],
Cell[BoxData[
\(0\)], "Output"]
}, Open ]],
Cell[TextData[{
"At this size the bitvector approach is substantially faster than using ",
StyleBox["Nullspace", "InlineInput"],
". A reasonable question is whether one might in effect emulate ",
StyleBox["Nullspace", "InlineInput"],
" but using bit vectors. This can be done but in order to be as efficient \
as possible one would need the ability to check or set a given bit in a \
bignum in constant time, and this capability is not present in version 4 of \
",
StyleBox["Mathematica",
FontSlant->"Italic"],
"."
}], "Text"]
}, Open ]]
}, Closed]],
Cell[CellGroupData[{
Cell["Tree application: A rudimentary parser", "Subsection"],
Cell["\<\
In this section we present a not-too-complicated grammar and a \
random sentence generator for that grammar. Then we reverse this process and \
\"parse\" the sentences according to that grammar. Strictly speaking there is \
no issue of computational complexity in this section. Nonetheless it is shown \
because it is a cute example of tree construction, it is generally relevant \
to computer science (where parsing theory is a common theme), and because \
more complicated parsers will frequently work in similar manner but require, \
say, stacks as intermediate data structures. Indeed, more complicated \
grammars generally require preprocessing that is itself computationally \
intensive and in need of useful data structures. A good reference for all \
this is
(1977) Principles of Complier Design, Aho, Alfred, and Ullman, Jeffrey. \
Addison Wesley.
(aka \"The Dragon Book\"). In particular see chapter 5.\
\>", "Text"],
Cell[TextData[{
"First we give our grammar. It is quite capable of producing a variety of \
nonsense sentences, as we will soon see. With minor modifications one could \
probably use it to turn out scripts for bad movies. We use ",
StyleBox["Hold",
FontWeight->"Bold"],
" to prevent infinite recursion. We also weight the probabilities of \
\"empty\" productions in adjective and adverb clauses so that they will not \
be terribly long."
}], "Text"],
Cell[BoxData[{
\(\(NIL = "\<\>";\)\), "\[IndentingNewLine]",
\(sentence :=
Hold[Or[declarative, interrogative,
imperative]]\), "\[IndentingNewLine]",
\(declarative := {subject, predicatepast}\), "\[IndentingNewLine]",
\(interrogative := {qverb, subject,
predicatepresent}\), "\[IndentingNewLine]",
\(imperative := {actverb, subject}\), "\[IndentingNewLine]",
\(subject :=
Hold[nounclause || {nounclause,
prepositionclause}]\), "\[IndentingNewLine]",
\(nounclause := Hold[{adjectiveclause, noun}]\), "\[IndentingNewLine]",
\(noun :=
Or["\", "\", "\", "\", "\", \
"\", "\", "\", "\", "\", \
"\", "\", "\", "\"]\), "\
\[IndentingNewLine]",
\(adjectiveclause := {article, adjectivelist}\), "\[IndentingNewLine]",
\(adjectivelist :=
Hold[myOr[ .6, Hold[tmpadjlist = adjective; \ NIL],
Hold[With[{tmp = randomPart[tmpadjlist]},
tmpadjlist =
Complement[tmpadjlist,
Unevaluated[Or[tmp]]]; \[IndentingNewLine]{tmp,
adjectivelist}]]]]\), "\[IndentingNewLine]",
\(article :=
Or["\", "\", "\", "\"]\), \
"\[IndentingNewLine]",
\(adjective :=
Or["\", "\", "\", "\", "\", \
"\", "\", "\", "\", \
"\", "\", "\", \ "\", \ "\"]\), "\
\[IndentingNewLine]",
\(\(tmpadjlist = adjective;\)\), "\[IndentingNewLine]",
\(prepositionclause := {preposition,
nounclause}\), "\[IndentingNewLine]",
\(preposition :=
Or["\", "\", "\", "\", "\", \
"\", "\"]\), "\[IndentingNewLine]",
\(predicatepresent := {verbpresent, subject}\), "\[IndentingNewLine]",
\(predicatepast := {verbclause, subject}\), "\[IndentingNewLine]",
\(verbclause := Hold[{adverblist, verbpast}]\), "\[IndentingNewLine]",
\(adverblist :=
Hold[myOr[ .8, Hold[tmpadvlist = adverb; \ NIL],
Hold[With[{tmp = randomPart[tmpadvlist]},
tmpadvlist =
Complement[tmpadvlist,
Unevaluated[Or[tmp]]]; \[IndentingNewLine]{tmp,
adverblist}]]]]\), "\[IndentingNewLine]",
\(adverb :=
Or["\", "\", "\", "\", \
"\", "\"]\), "\[IndentingNewLine]",
\(\(tmpadvlist = adverb;\)\), "\[IndentingNewLine]",
\(verbpast :=
Or["\", "\", "\", "\", "\", "\
\", "\", "\"]\), "\[IndentingNewLine]",
\(verbpresent :=
Or["\", "\", "\", "\", "\", \
"\", "\", "\", "\"]\), \
"\[IndentingNewLine]",
\(qverb :=
Or["\", "\", "\", "\"]\), "\
\[IndentingNewLine]",
\(actverb :=
Or["\", "\", "\", "\", \
"\"]\)}], "Input"],
Cell["\<\
Now generate random sentences from that grammar. We also provide a \
means to format the results.\
\>", "Text"],
Cell[BoxData[{
\(randomPart[type_] :=
Switch[Head[type], Hold, randomPart[type[\([1]\)]], String, type, List,
If[Length[type] \[Equal] 0, "\<\>", Flatten[Map[randomPart, type]]],
myOr, With[{rnd = Random[]},
randomPart[If[rnd < type[\([1]\)], type[\([2]\)], type[\([3]\)]]]],
Or, randomPart[
type[\([Random[
Integer, {1, Length[type]}]]\)]]]\), "\[IndentingNewLine]",
\(randomSentence[] :=
Apply[sentenceType,
randomPart[sentence] /. "\<\>" \[Rule]
Sequence[]]\), "\[IndentingNewLine]",
\(isQ[type_, a_] := MemberQ[type, a]\), "\[IndentingNewLine]",
\(Format[sentence_sentenceType] :=
Module[{word = First[sentence], words, punc},
words = Map[StringJoin[#, "\< \>"] &,
sentence]; \[IndentingNewLine]punc =
If[isQ[qverb, word], "\",
If[isQ[actverb,
word], "\", "\<.\>"]]; \[IndentingNewLine]words[\([Length[
words]]\)] =
StringReplacePart[Last[words],
punc, \(-1\)]; \[IndentingNewLine]words[\([1]\)] =
StringReplacePart[First[words],
ToUpperCase[StringTake[First[words], 1]],
1]; \[IndentingNewLine]Apply[StringJoin, words]]\)}], "Input"],
Cell["\<\
Here is a set of random sentences. Note that our random generator \
is rigged to go slightly beyond strict syntax, in that adjectives and adverbs \
are never reused within the same clause.\
\>", "Text"],
Cell[CellGroupData[{
Cell[BoxData[
\(Table[randomSentence[], {20}] // TableForm\)], "Input"],
Cell[BoxData[
InterpretationBox[GridBox[{
{"\<\"A red shark grated a sheep above this crazy sheep.\"\>"},
{"\<\"That wet hideous mad red hatter gnashed the delectable \
village in that cow.\"\>"},
{"\<\"Fix that shark in this red big ball!\"\>"},
{"\<\"Launch the village!\"\>"},
{"\<\"Could the repugnant ball salivate that cow from this wet \
delectable buffalo?\"\>"},
{"\<\"Did the librarian grate the slimy hatter?\"\>"},
{"\<\"Break a slimy village from that repugnant village!\"\>"},
{"\<\"The hideous librarian jumped a programmer at a ball.\"\>"},
{"\<\"Squeeze the programmer in that city!\"\>"},
{"\<\"Could the mad librarian with the silly city salivate the \
ball?\"\>"},
{"\<\"Did the attorney jump that ball?\"\>"},
{"\<\"A attorney at this attorney milked a village.\"\>"},
{"\<\"Will the wet lazy hideous mild-mannered mad red attorney near \
a lazy programmer eat a dog?\"\>"},
{"\<\"This city threw that librarian from a delectable slimy \
village.\"\>"},
{"\<\"Squeeze the attorney!\"\>"},
{"\<\"Fix the crazy programmer under the red crazy repugnant wet \
silly cow!\"\>"},
{"\<\"Will a red librarian milk that big moon?\"\>"},
{"\<\"A city with the hideous wet big city ate a sheep.\"\>"},
{"\<\"Fix this mad librarian in a programmer!\"\>"},
{"\<\"Should that shark under that red crazy skyscraper salivate \
this city near that lazy silly hatter?\"\>"}
},
RowSpacings->1,
ColumnSpacings->3,
RowAlignments->Baseline,
ColumnAlignments->{Left}],
TableForm[ {
sentenceType[
"a", "red", "shark", "grated", "a", "sheep", "above", "this", "crazy",
"sheep"],
sentenceType[
"that", "wet", "hideous", "mad", "red", "hatter", "gnashed", "the",
"delectable", "village", "in", "that", "cow"],
sentenceType[
"fix", "that", "shark", "in", "this", "red", "big", "ball"],
sentenceType[ "launch", "the", "village"],
sentenceType[
"could", "the", "repugnant", "ball", "salivate", "that", "cow",
"from", "this", "wet", "delectable", "buffalo"],
sentenceType[
"did", "the", "librarian", "grate", "the", "slimy", "hatter"],
sentenceType[
"break", "a", "slimy", "village", "from", "that", "repugnant",
"village"],
sentenceType[
"the", "hideous", "librarian", "jumped", "a", "programmer", "at", "a",
"ball"],
sentenceType[ "squeeze", "the", "programmer", "in", "that", "city"],
sentenceType[
"could", "the", "mad", "librarian", "with", "the", "silly", "city",
"salivate", "the", "ball"],
sentenceType[ "did", "the", "attorney", "jump", "that", "ball"],
sentenceType[
"a", "attorney", "at", "this", "attorney", "milked", "a", "village"],
sentenceType[
"will", "the", "wet", "lazy", "hideous", "mild-mannered", "mad",
"red", "attorney", "near", "a", "lazy", "programmer", "eat", "a",
"dog"],
sentenceType[
"this", "city", "threw", "that", "librarian", "from", "a",
"delectable", "slimy", "village"],
sentenceType[ "squeeze", "the", "attorney"],
sentenceType[
"fix", "the", "crazy", "programmer", "under", "the", "red", "crazy",
"repugnant", "wet", "silly", "cow"],
sentenceType[
"will", "a", "red", "librarian", "milk", "that", "big", "moon"],
sentenceType[
"a", "city", "with", "the", "hideous", "wet", "big", "city", "ate",
"a", "sheep"],
sentenceType[
"fix", "this", "mad", "librarian", "in", "a", "programmer"],
sentenceType[
"should", "that", "shark", "under", "that", "red", "crazy",
"skyscraper", "salivate", "this", "city", "near", "that", "lazy",
"silly", "hatter"]}]]], "Output"]
}, Open ]],
Cell["\<\
Now for the parser. We will break down each sentence part and \
indicate this by encapsulating it in a special head. When we encounter empty \
subexpressions e.g. adjective lists with no adjectives, we do not return \
them; for many purposes this is acceptable and of course one could easily \
modify the parsing code below to indicate where these lists would be. Note \
that this parser assumes the input is valid, and makes no attempt to detect \
errors. \
\>", "Text"],
Cell[BoxData[{
\(getNextWord[{}] := "\<\>"\), "\[IndentingNewLine]",
\(getNextWord[a_] := First[a]\), "\[IndentingNewLine]",
\(atomParse[hed_, a_] := {hed[getNextWord[a]],
1}\), "\[IndentingNewLine]",
\(sentenceParse[a_sentenceType] :=
With[{b = Apply[List, a]},
If[isQ[qverb, First[b]], interrogativeParse[b],
If[isQ[actverb, First[b]], imperativeParse[b],
declarativeParse[b]]]]\), "\[IndentingNewLine]",
\(declarativeParse[a_] :=
Module[{b = subjectParse[a], c},
c = predicatepastParse[
Drop[a, b[\([2]\)]]]; \[IndentingNewLine]"\"[b[\([1]\)], c[\([1]\)]]]\), "\[IndentingNewLine]",
\(interrogativeParse[a_] :=
Module[{b = atomParse["\", a], c, d},
c = subjectParse[Drop[a, b[\([2]\)]]]; \[IndentingNewLine]d =
predicatepresentParse[
Drop[a, b[\([2]\)] +
c[\([2]\)]]]; \[IndentingNewLine]"\"[
b[\([1]\)], c[\([1]\)], d[\([1]\)]]]\), "\[IndentingNewLine]",
\(imperativeParse[a_] :=
Module[{b = atomParse["\", a], c},
c = subjectParse[
Drop[a, b[\([2]\)]]]; \[IndentingNewLine]"\"[b[\([1]\)], c[\([1]\)]]]\), "\[IndentingNewLine]",
\(subjectParse[a_] :=
Module[{b = nounclauseParse[a], c},
c = Drop[a,
b[\([2]\)]]; \[IndentingNewLine]If[\(! isQ[preposition,
getNextWord[c]]\), {"\"[b[\([1]\)]], b[\([2]\)]},
c = prepositionclauseParse[c]; \[IndentingNewLine]{"\"[
b[\([1]\)], c[\([1]\)]],
b[\([2]\)] + c[\([2]\)]}]]\), "\[IndentingNewLine]",
\(predicatepastParse[a_] :=
Module[{b = verbclauseParse[a], c},
c = subjectParse[
Drop[a, b[\([2]\)]]]; \[IndentingNewLine]{"\"[
b[\([1]\)], c[\([1]\)]],
b[\([2]\)] + c[\([2]\)]}]\), "\[IndentingNewLine]",
\(predicatepresentParse[a_] :=
Module[{b = atomParse["\", a], c},
c = subjectParse[
Drop[a, b[\([2]\)]]]; \[IndentingNewLine]{"\"[
b[\([1]\)], c[\([1]\)]],
b[\([2]\)] + c[\([2]\)]}]\), "\[IndentingNewLine]",
\(verbclauseParse[a_] :=
Module[{b = adverblistParse[a], c},
c = atomParse["\",
Drop[a, b[\([2]\)]]]; \[IndentingNewLine]If[
b[\([2]\)] \[Equal] 0,
c, {"\"[b[\([1]\)], c[\([1]\)]],
b[\([2]\)] + c[\([2]\)]}]]\), "\[IndentingNewLine]",
\(nounclauseParse[a_] :=
Module[{b = adjectiveclauseParse[a], c},
c = atomParse["\",
Drop[a, b[\([2]\)]]]; \[IndentingNewLine]{"\"[
b[\([1]\)], c[\([1]\)]],
b[\([2]\)] + c[\([2]\)]}]\), "\[IndentingNewLine]",
\(adjectiveclauseParse[a_] :=
Module[{b = atomParse["\", a], c},
c = adjectivelistParse[Drop[a, b[\([2]\)]]]; \[IndentingNewLine]If[
c[\([2]\)] \[Equal] 0,
b, {"\"[b[\([1]\)], c[\([1]\)]],
b[\([2]\)] + c[\([2]\)]}]]\), "\[IndentingNewLine]",
\(adjectivelistParse[a_] :=
Module[{b = a, c, result, len = 0},
result = "\"[]; \[IndentingNewLine]While[
isQ[adjective, getNextWord[b]],
c = atomParse["\", b]; \[IndentingNewLine]len +=
c[\([2]\)]; \[IndentingNewLine]result = "\"[
result, c[\([1]\)]]; \[IndentingNewLine]b =
Drop[b, c[\([2]\)]]]; \[IndentingNewLine]{Flatten[result,
Infinity, "\"], len}]\), "\[IndentingNewLine]",
\(prepositionclauseParse[a_] :=
Module[{b = atomParse["\", a], c},
c = nounclauseParse[
Drop[a, b[\([2]\)]]]; \[IndentingNewLine]{"\"[b[\([1]\)], c[\([1]\)]],
b[\([2]\)] + c[\([2]\)]}]\), "\[IndentingNewLine]",
\(adverblistParse[a_] :=
Module[{b = a, c, result, len = 0},
result = "\"[]; \[IndentingNewLine]While[
isQ[adverb, getNextWord[b]],
c = atomParse["\", b]; \[IndentingNewLine]len +=
c[\([2]\)]; \[IndentingNewLine]result = "\"[result,
c[\([1]\)]]; \[IndentingNewLine]b =
Drop[b, c[\([2]\)]]]; \[IndentingNewLine]{Flatten[result,
Infinity, "\"], len}]\)}], "Input"],
Cell[CellGroupData[{
Cell[BoxData[
\(Table[sentenceParse[bb[j] = randomSentence[]], \ {j, 5}]\)], "Input"],
Cell[BoxData[
\({"DECLARATIVE SENTENCE"[
"SUBJECT"[
"NOUN CLAUSE"[
"ADJECTIVE CLAUSE"["ARTICLE"["a"],
"ADJECTIVE LIST"["ADJECTIVE"["mild-mannered"],
"ADJECTIVE"["mad"]]], "NOUN"["sheep"]],
"PREPOSITION CLAUSE"["PREPOSITION"["from"],
"NOUN CLAUSE"["ARTICLE"["this"], "NOUN"["village"]]]],
"PREDICATE"["VERB (PAST TENSE)"["grated"],
"SUBJECT"["NOUN CLAUSE"["ARTICLE"["the"], "NOUN"["librarian"]]]]],
"INTERROGATIVE SENTENCE"["QUESTION VERB"["did"],
"SUBJECT"["NOUN CLAUSE"["ARTICLE"["this"], "NOUN"["attorney"]]],
"PREDICATE"["VERB (PRESENT TENSE)"["throw"],
"SUBJECT"[
"NOUN CLAUSE"[
"ADJECTIVE CLAUSE"["ARTICLE"["a"],
"ADJECTIVE LIST"["ADJECTIVE"["wet"], "ADJECTIVE"["slimy"]]],
"NOUN"["programmer"]]]]],
"IMPERATIVE SENTENCE"["ACTION VERB"["squeeze"],
"SUBJECT"[
"NOUN CLAUSE"[
"ADJECTIVE CLAUSE"["ARTICLE"["that"],
"ADJECTIVE LIST"["ADJECTIVE"["slimy"]]], "NOUN"["attorney"]]]],
"DECLARATIVE SENTENCE"[
"SUBJECT"["NOUN CLAUSE"["ARTICLE"["this"], "NOUN"["village"]],
"PREPOSITION CLAUSE"["PREPOSITION"["in"],
"NOUN CLAUSE"["ARTICLE"["a"], "NOUN"["village"]]]],
"PREDICATE"["VERB (PAST TENSE)"["ate"],
"SUBJECT"[
"NOUN CLAUSE"[
"ADJECTIVE CLAUSE"["ARTICLE"["that"],
"ADJECTIVE LIST"["ADJECTIVE"["delectable"],
"ADJECTIVE"["lazy"]]], "NOUN"["moon"]]]]],
"DECLARATIVE SENTENCE"[
"SUBJECT"[
"NOUN CLAUSE"[
"ADJECTIVE CLAUSE"["ARTICLE"["this"],
"ADJECTIVE LIST"["ADJECTIVE"["crazy"]]], "NOUN"["shark"]],
"PREPOSITION CLAUSE"["PREPOSITION"["under"],
"NOUN CLAUSE"["ARTICLE"["the"], "NOUN"["hatter"]]]],
"PREDICATE"["VERB (PAST TENSE)"["jumped"],
"SUBJECT"["NOUN CLAUSE"["ARTICLE"["this"], "NOUN"["buffalo"]],
"PREPOSITION CLAUSE"["PREPOSITION"["with"],
"NOUN CLAUSE"[
"ADJECTIVE CLAUSE"["ARTICLE"["this"],
"ADJECTIVE LIST"["ADJECTIVE"["repugnant"]]],
"NOUN"["ball"]]]]]]}\)], "Output"]
}, Open ]]
}, Closed]]
},
FrontEndVersion->"4.1 for X",
ScreenRectangle->{{0, 1152}, {0, 864}},
WindowSize->{771, 669},
WindowMargins->{{172, Automatic}, {Automatic, 53}},
StyleDefinitions -> "Classroom.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->{}
*)
(*CellTagsIndex
CellTagsIndex->{}
*)
(*NotebookFileOutline
Notebook[{
Cell[1717, 49, 129, 4, 120, "Title"],
Cell[1849, 55, 79, 4, 87, "Author"],
Cell[CellGroupData[{
Cell[1953, 63, 30, 0, 52, "Subsection"],
Cell[1986, 65, 427, 11, 64, "Text"]
}, Closed]],
Cell[CellGroupData[{
Cell[2450, 81, 36, 0, 36, "Subsection"],
Cell[2489, 83, 118, 2, 63, "Input"]
}, Closed]],
Cell[CellGroupData[{
Cell[2644, 90, 34, 0, 36, "Subsection"],
Cell[2681, 92, 541, 10, 82, "Text"],
Cell[3225, 104, 325, 6, 64, "Text"],
Cell[3553, 112, 268, 5, 88, "Text"]
}, Closed]],
Cell[CellGroupData[{
Cell[3858, 122, 36, 0, 36, "Subsection"],
Cell[3897, 124, 730, 14, 100, "Text"],
Cell[4630, 140, 664, 15, 82, "Text"],
Cell[5297, 157, 148, 3, 28, "Text"],
Cell[CellGroupData[{
Cell[5470, 164, 299, 5, 111, "Input"],
Cell[5772, 171, 55, 1, 47, "Output"],
Cell[5830, 174, 56, 1, 47, "Output"],
Cell[5889, 177, 69, 1, 47, "Output"],
Cell[5961, 180, 38, 1, 47, "Output"]
}, Open ]],
Cell[6014, 184, 578, 10, 82, "Text"],
Cell[CellGroupData[{
Cell[6617, 198, 299, 5, 111, "Input"],
Cell[6919, 205, 69, 1, 47, "Output"],
Cell[6991, 208, 68, 1, 47, "Output"],
Cell[7062, 211, 69, 1, 47, "Output"],
Cell[7134, 214, 38, 1, 47, "Output"]
}, Open ]]
}, Closed]],
Cell[CellGroupData[{
Cell[7221, 221, 49, 0, 36, "Subsection"],
Cell[7273, 223, 1194, 27, 100, "Text"],
Cell[8470, 252, 330, 9, 28, "Text"],
Cell[CellGroupData[{
Cell[8825, 265, 270, 5, 111, "Input"],
Cell[9098, 272, 43, 1, 23, "Print"],
Cell[9144, 275, 697, 21, 95, "Print"]
}, Open ]],
Cell[9856, 299, 751, 15, 100, "Text"],
Cell[10610, 316, 1087, 21, 190, "Text"],
Cell[11700, 339, 351, 6, 111, "Input"],
Cell[12054, 347, 572, 11, 143, "Input"],
Cell[12629, 360, 64, 0, 28, "Text"],
Cell[CellGroupData[{
Cell[12718, 364, 293, 7, 79, "Input"],
Cell[13014, 373, 476, 6, 111, "Output"],
Cell[13493, 381, 38, 1, 47, "Output"]
}, Open ]],
Cell[13546, 385, 62, 0, 28, "Text"],
Cell[13611, 387, 486, 11, 95, "Input"],
Cell[14100, 400, 135, 3, 28, "Text"],
Cell[14238, 405, 593, 14, 82, "Text"],
Cell[CellGroupData[{
Cell[14856, 423, 70, 1, 45, "Subsubsection"],
Cell[14929, 426, 297, 5, 46, "Text"],
Cell[15229, 433, 2483, 49, 591, "Input"],
Cell[17715, 484, 50, 0, 28, "Text"],
Cell[CellGroupData[{
Cell[17790, 488, 405, 10, 127, "Input"],
Cell[18198, 500, 69, 1, 47, "Output"],
Cell[18270, 503, 69, 1, 47, "Output"],
Cell[18342, 506, 38, 1, 47, "Output"],
Cell[18383, 509, 38, 1, 47, "Output"]
}, Open ]],
Cell[18436, 513, 205, 6, 28, "Text"],
Cell[18644, 521, 376, 6, 127, "Input"],
Cell[CellGroupData[{
Cell[19045, 531, 472, 9, 143, "Input"],
Cell[19520, 542, 69, 1, 47, "Output"],
Cell[19592, 545, 69, 1, 47, "Output"],
Cell[19664, 548, 69, 1, 47, "Output"],
Cell[19736, 551, 38, 1, 47, "Output"],
Cell[19777, 554, 38, 1, 47, "Output"],
Cell[19818, 557, 38, 1, 47, "Output"]
}, Open ]],
Cell[19871, 561, 246, 8, 28, "Text"],
Cell[CellGroupData[{
Cell[20142, 573, 498, 12, 111, "Input"],
Cell[20643, 587, 69, 1, 47, "Output"],
Cell[20715, 590, 69, 1, 47, "Output"],
Cell[20787, 593, 69, 1, 47, "Output"],
Cell[20859, 596, 69, 1, 47, "Output"]
}, Open ]],
Cell[CellGroupData[{
Cell[20965, 602, 146, 2, 63, "Input"],
Cell[21114, 606, 69, 1, 47, "Output"],
Cell[21186, 609, 69, 1, 47, "Output"]
}, Open ]]
}, Open ]]
}, Closed]],
Cell[CellGroupData[{
Cell[21316, 617, 28, 0, 36, "Subsection"],
Cell[21347, 619, 412, 8, 94, "Text"],
Cell[21762, 629, 227, 4, 46, "Text"],
Cell[21992, 635, 138, 5, 28, "Text"],
Cell[22133, 642, 500, 10, 143, "Input"],
Cell[22636, 654, 321, 10, 28, "Text"],
Cell[22960, 666, 257, 5, 95, "Input"],
Cell[23220, 673, 115, 2, 63, "Input"],
Cell[23338, 677, 250, 8, 28, "Text"],
Cell[CellGroupData[{
Cell[23613, 689, 124, 2, 47, "Input"],
Cell[23740, 693, 124, 2, 23, "Message"],
Cell[23867, 697, 124, 2, 23, "Message"],
Cell[23994, 701, 124, 2, 23, "Message"],
Cell[24121, 705, 175, 3, 39, "Message"],
Cell[24299, 710, 150, 3, 23, "Message"],
Cell[24452, 715, 150, 3, 23, "Message"]
}, Open ]],
Cell[24617, 721, 571, 9, 82, "Text"],
Cell[25191, 732, 598, 10, 207, "Input"],
Cell[CellGroupData[{
Cell[25814, 746, 67, 1, 47, "Input"],
Cell[25884, 749, 38, 1, 47, "Output"]
}, Open ]],
Cell[25937, 753, 163, 2, 63, "Input"],
Cell[CellGroupData[{
Cell[26125, 759, 69, 1, 47, "Input"],
Cell[26197, 762, 38, 1, 47, "Output"]
}, Open ]],
Cell[26250, 766, 185, 4, 46, "Text"]
}, Closed]],
Cell[CellGroupData[{
Cell[26472, 775, 28, 0, 36, "Subsection"],
Cell[26503, 777, 601, 9, 100, "Text"],
Cell[27107, 788, 1181, 21, 239, "Input"],
Cell[28291, 811, 41, 0, 28, "Text"],
Cell[CellGroupData[{
Cell[28357, 815, 277, 6, 95, "Input"],
Cell[28637, 823, 35, 1, 47, "Output"],
Cell[28675, 826, 47, 1, 47, "Output"]
}, Open ]],
Cell[CellGroupData[{
Cell[28759, 832, 182, 3, 63, "Input"],
Cell[28944, 837, 48, 1, 23, "Print"]
}, Open ]],
Cell[29007, 841, 108, 3, 28, "Text"],
Cell[CellGroupData[{
Cell[29140, 848, 53, 1, 47, "Input"],
Cell[29196, 851, 51, 1, 47, "Output"]
}, Open ]],
Cell[29262, 855, 59, 1, 47, "Input"],
Cell[29324, 858, 883, 15, 118, "Text"],
Cell[30210, 875, 892, 15, 191, "Input"],
Cell[31105, 892, 130, 3, 28, "Text"],
Cell[CellGroupData[{
Cell[31260, 899, 278, 6, 95, "Input"],
Cell[31541, 907, 35, 1, 47, "Output"],
Cell[31579, 910, 47, 1, 47, "Output"]
}, Open ]],
Cell[31641, 914, 182, 3, 63, "Input"],
Cell[CellGroupData[{
Cell[31848, 921, 105, 2, 63, "Input"],
Cell[31956, 925, 51, 1, 47, "Output"],
Cell[32010, 928, 35, 1, 47, "Output"]
}, Open ]],
Cell[32060, 932, 456, 9, 64, "Text"],
Cell[32519, 943, 1044, 19, 136, "Text"],
Cell[CellGroupData[{
Cell[33588, 966, 71, 1, 47, "Input"],
Cell[33662, 969, 47, 1, 23, "Print"],
Cell[33712, 972, 808, 24, 239, "Print"]
}, Open ]],
Cell[34535, 999, 706, 12, 100, "Text"],
Cell[35244, 1013, 199, 4, 46, "Text"],
Cell[35446, 1019, 573, 10, 207, "Input"],
Cell[CellGroupData[{
Cell[36044, 1033, 51, 1, 47, "Input"],
Cell[36098, 1036, 113, 2, 47, "Output"]
}, Open ]],
Cell[36226, 1041, 213, 4, 46, "Text"],
Cell[CellGroupData[{
Cell[36464, 1049, 320, 6, 95, "Input"],
Cell[36787, 1057, 113, 2, 47, "Output"]
}, Open ]],
Cell[36915, 1062, 210, 4, 46, "Text"],
Cell[37128, 1068, 454, 7, 64, "Text"]
}, Closed]],
Cell[CellGroupData[{
Cell[37619, 1080, 27, 0, 36, "Subsection"],
Cell[37649, 1082, 648, 19, 64, "Text"],
Cell[38300, 1103, 381, 8, 64, "Text"],
Cell[38684, 1113, 1403, 36, 100, "Text"],
Cell[40090, 1151, 493, 13, 64, "Text"],
Cell[40586, 1166, 815, 14, 207, "Input"],
Cell[41404, 1182, 178, 4, 46, "Text"],
Cell[CellGroupData[{
Cell[41607, 1190, 436, 9, 127, "Input"],
Cell[42046, 1201, 52, 1, 47, "Output"],
Cell[42101, 1204, 38, 1, 47, "Output"]
}, Open ]],
Cell[CellGroupData[{
Cell[42176, 1210, 436, 9, 127, "Input"],
Cell[42615, 1221, 53, 1, 47, "Output"],
Cell[42671, 1224, 38, 1, 47, "Output"]
}, Open ]],
Cell[CellGroupData[{
Cell[42746, 1230, 450, 9, 127, "Input"],
Cell[43199, 1241, 53, 1, 47, "Output"],
Cell[43255, 1244, 38, 1, 47, "Output"]
}, Open ]],
Cell[43308, 1248, 236, 11, 28, "Text"],
Cell[CellGroupData[{
Cell[43569, 1263, 442, 8, 127, "Input"],
Cell[44014, 1273, 104, 2, 47, "Output"]
}, Open ]],
Cell[44133, 1278, 627, 16, 64, "Text"]
}, Closed]],
Cell[CellGroupData[{
Cell[44797, 1299, 32, 0, 36, "Subsection"],
Cell[44832, 1301, 457, 10, 64, "Text"],
Cell[45292, 1313, 473, 9, 64, "Text"],
Cell[45768, 1324, 117, 2, 51, "Input"],
Cell[45888, 1328, 249, 5, 46, "Text"],
Cell[46140, 1335, 74, 1, 47, "Input"],
Cell[46217, 1338, 721, 17, 82, "Text"],
Cell[CellGroupData[{
Cell[46963, 1359, 135, 2, 79, "Input"],
Cell[47101, 1363, 36, 1, 47, "Output"]
}, Open ]],
Cell[47152, 1367, 326, 7, 46, "Text"],
Cell[CellGroupData[{
Cell[47503, 1378, 298, 6, 95, "Input"],
Cell[47804, 1386, 36, 1, 47, "Output"]
}, Open ]],
Cell[47855, 1390, 212, 4, 46, "Text"],
Cell[48070, 1396, 155, 3, 47, "Input"],
Cell[48228, 1401, 234, 8, 28, "Text"],
Cell[CellGroupData[{
Cell[48487, 1413, 103, 2, 47, "Input"],
Cell[48593, 1417, 36, 1, 47, "Output"]
}, Open ]],
Cell[48644, 1421, 328, 9, 46, "Text"],
Cell[48975, 1432, 218, 3, 79, "Input"],
Cell[CellGroupData[{
Cell[49218, 1439, 89, 1, 45, "Subsubsection"],
Cell[49310, 1442, 460, 8, 64, "Text"],
Cell[49773, 1452, 966, 14, 136, "Text"],
Cell[50742, 1468, 388, 7, 127, "Input"],
Cell[51133, 1477, 206, 4, 46, "Text"],
Cell[CellGroupData[{
Cell[51364, 1485, 352, 6, 111, "Input"],
Cell[51719, 1493, 55, 1, 47, "Output"],
Cell[51777, 1496, 35, 1, 47, "Output"],
Cell[51815, 1499, 35, 1, 47, "Output"]
}, Open ]],
Cell[51865, 1503, 64, 0, 28, "Text"],
Cell[CellGroupData[{
Cell[51954, 1507, 191, 4, 63, "Input"],
Cell[52148, 1513, 68, 1, 47, "Output"],
Cell[52219, 1516, 35, 1, 47, "Output"]
}, Open ]],
Cell[52269, 1520, 848, 14, 118, "Text"],
Cell[53120, 1536, 103, 3, 28, "Text"],
Cell[53226, 1541, 1662, 29, 383, "Input"],
Cell[54891, 1572, 144, 3, 28, "Text"],
Cell[55038, 1577, 431, 8, 143, "Input"],
Cell[55472, 1587, 103, 3, 28, "Text"],
Cell[CellGroupData[{
Cell[55600, 1594, 137, 2, 63, "Input"],
Cell[55740, 1598, 68, 1, 47, "Output"],
Cell[55811, 1601, 35, 1, 47, "Output"]
}, Open ]],
Cell[55861, 1605, 863, 19, 100, "Text"],
Cell[56727, 1626, 390, 7, 127, "Input"],
Cell[57120, 1635, 431, 8, 143, "Input"],
Cell[CellGroupData[{
Cell[57576, 1647, 191, 4, 63, "Input"],
Cell[57770, 1653, 57, 1, 47, "Output"],
Cell[57830, 1656, 35, 1, 47, "Output"]
}, Open ]],
Cell[CellGroupData[{
Cell[57902, 1662, 137, 2, 63, "Input"],
Cell[58042, 1666, 69, 1, 47, "Output"],
Cell[58114, 1669, 35, 1, 47, "Output"]
}, Open ]],
Cell[58164, 1673, 544, 12, 64, "Text"]
}, Open ]]
}, Closed]],
Cell[CellGroupData[{
Cell[58757, 1691, 60, 0, 36, "Subsection"],
Cell[58820, 1693, 937, 15, 178, "Text"],
Cell[59760, 1710, 459, 9, 64, "Text"],
Cell[60222, 1721, 3235, 66, 591, "Input"],
Cell[63460, 1789, 121, 3, 28, "Text"],
Cell[63584, 1794, 1312, 26, 223, "Input"],
Cell[64899, 1822, 212, 4, 46, "Text"],
Cell[CellGroupData[{
Cell[65136, 1830, 75, 1, 47, "Input"],
Cell[65214, 1833, 4114, 84, 389, "Output"]
}, Open ]],
Cell[69343, 1920, 481, 8, 82, "Text"],
Cell[69827, 1930, 4622, 89, 831, "Input"],
Cell[CellGroupData[{
Cell[74474, 2023, 89, 1, 47, "Input"],
Cell[74566, 2026, 2334, 47, 351, "Output"]
}, Open ]]
}, Closed]]
}
]
*)
(***********************************************************************
End of Mathematica Notebook file.
***********************************************************************)