(* Content-type: application/vnd.wolfram.mathematica *) (*** Wolfram Notebook File ***) (* http://www.wolfram.com/nb *) (* CreatedBy='Mathematica 11.1' *) (*CacheID: 234*) (* Internal cache information: NotebookFileLineBreakTest NotebookFileLineBreakTest NotebookDataPosition[ 158, 7] NotebookDataLength[ 168419, 4556] NotebookOptionsPosition[ 144580, 4022] NotebookOutlinePosition[ 144917, 4037] CellTagsIndexPosition[ 144874, 4034] WindowFrame->Normal*) (* Beginning of Notebook Content *) Notebook[{ Cell[TextData[{ "Data structures and efficient algorithms in ", StyleBox["Mathematica", FontSlant->"Italic"] }], "Title",ExpressionUUID->"a638dc7e-3a7a-4b8f-88e0-14e60e9b6b6e"], Cell["\<\ Daniel Lichtblau Wolfram Research, Inc. October, 1999\ \>", "Author",ExpressionUUID->"45e778cf-c6b9-433b-a0c6-bb08baf82cab"], Cell[CellGroupData[{ Cell["Abstract", "Subsection",ExpressionUUID->"1535e809-1679-4769-b45e-7e47f1c7e106"], 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",ExpressionUUID->"4711285a-7dd2-4a70-a997-0856e23f9084"] }, Open ]], Cell[CellGroupData[{ Cell["Initialization", "Subsection",ExpressionUUID->"e43a76cf-be65-4d78-bcfe-87a686f00edb"], Cell[BoxData[{ RowBox[{ RowBox[{"Off", "[", RowBox[{"General", "::", "spell"}], "]"}], ";"}], "\[IndentingNewLine]", RowBox[{ RowBox[{"Off", "[", RowBox[{"General", "::", "spell1"}], "]"}], ";"}]}], "Input",ExpressionUUID\ ->"989800b9-947c-4c1f-9a39-287b74982035"] }, Open ]], Cell[CellGroupData[{ Cell["Introduction", "Subsection",ExpressionUUID->"a1aa03b5-677d-4999-908d-3818618355ac"], 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",ExpressionUUID->"7285f81e-ce24-48d8-988a-73a035acfa2a"], 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",ExpressionUUID->"6061229d-c549-46db-bdf0-b1022fdad58b"], 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",ExpressionUUID->"9cc8c238-9866-49e8-8e64-5fb93575db83"] }, Open ]], Cell[CellGroupData[{ Cell["Tables (lists)", "Subsection",ExpressionUUID->"8979f4a1-1e42-47d7-807d-b4bbe3ddc707"], 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",ExpressionUUID->"caaffcf0-0908-4278-8c6f-26d2614dc9a2"], 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",ExpressionUUID->"c6319569-814b-4c5a-8755-1c1742b808a2"], Cell["\<\ To give some indication of relative speed of building a fixed size table vs. \ a nested list, we show simple examples below.\ \>", "Text",ExpressionUUID->"1beec0ab-f407-4432-a7b9-4b14261b4a37"], Cell[CellGroupData[{ Cell[BoxData[{ RowBox[{"Timing", "[", RowBox[{ RowBox[{"t1", "=", RowBox[{"Table", "[", RowBox[{ RowBox[{"N", "[", "j", "]"}], ",", RowBox[{"{", RowBox[{"j", ",", RowBox[{"10", "^", "6"}]}], "}"}]}], "]"}]}], ";"}], "]"}], "\[IndentingNewLine]", RowBox[{ RowBox[{"t2", "=", RowBox[{"{", "}"}]}], ";"}], "\[IndentingNewLine]", RowBox[{"Timing", "[", RowBox[{"Do", "[", RowBox[{ RowBox[{"t2", "=", RowBox[{"{", RowBox[{"t2", ",", RowBox[{"N", "[", "j", "]"}]}], "}"}]}], ",", RowBox[{"{", RowBox[{"j", ",", RowBox[{"10", "^", "6"}]}], "}"}]}], "]"}], "]"}], "\[IndentingNewLine]", RowBox[{"Timing", "[", RowBox[{ RowBox[{"t3", "=", RowBox[{"Flatten", "[", "t2", "]"}]}], ";"}], "]"}], "\[IndentingNewLine]", RowBox[{"t3", "===", "t1"}]}], "Input",ExpressionUUID->"4dc2ff6b-35a3-49d8-\ 8547-ce8a9954760d"], Cell[BoxData[ RowBox[{"{", RowBox[{ RowBox[{"1.02`", " ", "Second"}], ",", "Null"}], "}"}]], "Output",Expressio\ nUUID->"e396fd25-9067-435b-9e92-3b9fa797089b"], Cell[BoxData[ RowBox[{"{", RowBox[{ RowBox[{"21.01`", " ", "Second"}], ",", "Null"}], "}"}]], "Output",Expressi\ onUUID->"4f418124-29da-4593-adda-de466de4a51c"], Cell[BoxData[ RowBox[{"{", RowBox[{ RowBox[{"2.3699999999999974`", " ", "Second"}], ",", "Null"}], "}"}]], "Output",ExpressionUUID->"22564a6c-da28-4ab4-8e23-8e15091a445a"], Cell[BoxData["True"], "Output",ExpressionUUID->"35ef11c6-9365-436d-bc14-2f670f3e3696"] }, 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\ \[Hyphen]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",ExpressionUUID->"b4a4d589-bea9-4f9e-9038-9d718bec5e8e"], Cell[CellGroupData[{ Cell[BoxData[{ RowBox[{"Timing", "[", RowBox[{ RowBox[{"t1", "=", RowBox[{"Table", "[", RowBox[{ RowBox[{"a", "[", "j", "]"}], ",", RowBox[{"{", RowBox[{"j", ",", RowBox[{"10", "^", "5"}]}], "}"}]}], "]"}]}], ";"}], "]"}], "\[IndentingNewLine]", RowBox[{ RowBox[{"t2", "=", RowBox[{"{", "}"}]}], ";"}], "\[IndentingNewLine]", RowBox[{"Timing", "[", RowBox[{"Do", "[", RowBox[{ RowBox[{"t2", "=", RowBox[{"{", RowBox[{"t2", ",", RowBox[{"a", "[", "j", "]"}]}], "}"}]}], ",", RowBox[{"{", RowBox[{"j", ",", RowBox[{"10", "^", "5"}]}], "}"}]}], "]"}], "]"}], "\[IndentingNewLine]", RowBox[{"Timing", "[", RowBox[{ RowBox[{"t3", "=", RowBox[{"Flatten", "[", "t2", "]"}]}], ";"}], "]"}], "\[IndentingNewLine]", RowBox[{"t3", "===", "t1"}]}], "Input",ExpressionUUID->"dc946fab-6598-4414-\ a349-f3caa067b91c"], Cell[BoxData[ RowBox[{"{", RowBox[{ RowBox[{"0.9899999999999807`", " ", "Second"}], ",", "Null"}], "}"}]], "Output",ExpressionUUID->"13476bd2-00fc-4b0e-93c6-8e06ea429f0e"], Cell[BoxData[ RowBox[{"{", RowBox[{ RowBox[{"1.660000000000025`", " ", "Second"}], ",", "Null"}], "}"}]], "Output",ExpressionUUID->"a9863fb5-df62-435b-9fb2-c958f1606c57"], Cell[BoxData[ RowBox[{"{", RowBox[{ RowBox[{"0.4899999999999807`", " ", "Second"}], ",", "Null"}], "}"}]], "Output",ExpressionUUID->"3c60d86a-7da2-48a8-9862-20ff39ab26a3"], Cell[BoxData["True"], "Output",ExpressionUUID->"c4702f65-87d0-4e70-bf65-ee75e8cb60e0"] }, Open ]] }, Open ]], Cell[CellGroupData[{ Cell["Sparse arrays (hash tables)", "Subsection",ExpressionUUID->"483b3cbd-1fdf-42b4-83bf-cba4604700c7"], 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",ExpressionUUID->"fabe6c80-4d8c-40a9-a5c5-af31a8f3ff41"], 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",ExpressionUUID->"37c41588-f96d-42e3-a0b5-f22e17f0d72c"], Cell[CellGroupData[{ Cell[BoxData[{ RowBox[{"Clear", "[", "a", "]"}], "\[IndentingNewLine]", RowBox[{ RowBox[{ RowBox[{ RowBox[{"a", "[", "4", "]"}], "[", "5", "]"}], "=", "3"}], ";"}], "\[IndentingNewLine]", RowBox[{ RowBox[{ RowBox[{"a", "[", RowBox[{"\"\\"", ",", "Pi"}], "]"}], "=", RowBox[{"{", RowBox[{"y7", ",", "1"}], "}"}]}], ";"}], "\[IndentingNewLine]", RowBox[{ RowBox[{ RowBox[{"a", "[", RowBox[{"{", RowBox[{"1", ",", "2", ",", "q"}], "}"}], "]"}], " ", "=", " ", "xyz"}], ";"}], "\[IndentingNewLine]", RowBox[{"??", "a"}]}], "Input",ExpressionUUID->"71228841-3626-4d6e-abe1-\ 7200afefe745"], Cell[BoxData["\<\"Global`a\"\>"], "Print",ExpressionUUID->"d1f38d1d-c834-413d-ab27-8bb09b5c127b"], Cell[BoxData[ InterpretationBox[GridBox[{ {GridBox[{ { RowBox[{ RowBox[{ RowBox[{"a", "[", "4", "]"}], "[", "5", "]"}], "=", "3"}]} }, BaselinePosition->{Baseline, {1, 1}}, GridBoxAlignment->{ "Columns" -> {{Left}}, "ColumnsIndexed" -> {}, "Rows" -> {{Baseline}}, "RowsIndexed" -> {}}, GridBoxItemSize->{"Columns" -> {{ Scaled[0.999]}}, "ColumnsIndexed" -> {}, "Rows" -> {{1.}}, "RowsIndexed" -> {}}]}, {" "}, {GridBox[{ { RowBox[{ RowBox[{"a", "[", RowBox[{"{", RowBox[{"1", ",", "2", ",", "q"}], "}"}], "]"}], "=", "xyz"}]}, {" "}, { RowBox[{ RowBox[{"a", "[", RowBox[{"\<\"string index\"\>", ",", "\[Pi]"}], "]"}], "=", RowBox[{"{", RowBox[{"y7", ",", "1"}], "}"}]}]} }, BaselinePosition->{Baseline, {1, 1}}, GridBoxAlignment->{ "Columns" -> {{Left}}, "ColumnsIndexed" -> {}, "Rows" -> {{Baseline}}, "RowsIndexed" -> {}}, GridBoxItemSize->{"Columns" -> {{ Scaled[0.999]}}, "ColumnsIndexed" -> {}, "Rows" -> {{1.}}, "RowsIndexed" -> {}}]} }, BaselinePosition->{Baseline, {1, 1}}, GridBoxAlignment->{ "Columns" -> {{Left}}, "ColumnsIndexed" -> {}, "Rows" -> {{Baseline}}, "RowsIndexed" -> {}}], Definition[a], Editable->False]], "Print",ExpressionUUID->"574b8a47-dc3f-40b8-8df2-\ db9547c4729c"] }, 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",ExpressionUUID->"81271925-3ef9-4fc6-95d5-48b64734513b"], 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",ExpressionUUID->"f4b342ba-2741-4ae7-a71a-358561afab04"], Cell[BoxData[ RowBox[{ RowBox[{"unionNoSort1", "[", "ll__List", "]"}], ":=", RowBox[{"Module", "[", RowBox[{ RowBox[{"{", RowBox[{"htable", ",", "mylist", ",", "all", ",", RowBox[{"result", "=", RowBox[{"{", "}"}]}]}], "}"}], ",", RowBox[{ RowBox[{"all", "=", RowBox[{"Join", "[", "ll", "]"}]}], ";", "\[IndentingNewLine]", RowBox[{"Do", "[", RowBox[{ RowBox[{"If", "[", RowBox[{ RowBox[{"!", RowBox[{"MemberQ", "[", RowBox[{"result", ",", RowBox[{"all", "[", RowBox[{"[", "j", "]"}], "]"}]}], "]"}]}], ",", "\[IndentingNewLine]", RowBox[{"AppendTo", "[", RowBox[{"result", ",", RowBox[{"all", "[", RowBox[{"[", "j", "]"}], "]"}]}], "]"}]}], "]"}], ",", "\[IndentingNewLine]", RowBox[{"{", RowBox[{"j", ",", RowBox[{"Length", "[", "all", "]"}]}], "}"}]}], "]"}], ";", "\[IndentingNewLine]", "result"}]}], "]"}]}]], "Input",ExpressionUUID->\ "360a1ef3-2d73-47f0-a69d-28ad6a712d6b"], Cell[BoxData[ RowBox[{ RowBox[{"unionNoSort2", "[", "ll__List", "]"}], ":=", RowBox[{"Module", "[", RowBox[{ RowBox[{"{", RowBox[{"htable", ",", "newlist", ",", "all", ",", "result"}], "}"}], ",", RowBox[{ RowBox[{"result", "=", RowBox[{"newlist", "[", "]"}]}], ";", "\[IndentingNewLine]", RowBox[{"all", "=", RowBox[{"Join", "[", "ll", "]"}]}], ";", "\[IndentingNewLine]", RowBox[{"Do", "[", RowBox[{ RowBox[{"If", "[", RowBox[{ RowBox[{"!", RowBox[{"TrueQ", "[", RowBox[{"htable", "[", RowBox[{"all", "[", RowBox[{"[", "j", "]"}], "]"}], "]"}], "]"}]}], ",", RowBox[{ RowBox[{ RowBox[{"htable", "[", RowBox[{"all", "[", RowBox[{"[", "j", "]"}], "]"}], "]"}], "=", "True"}], ";", "\[IndentingNewLine]", RowBox[{"result", "=", RowBox[{"newlist", "[", RowBox[{"result", ",", RowBox[{"all", "[", RowBox[{"[", "j", "]"}], "]"}]}], "]"}]}]}]}], "]"}], ",", RowBox[{"{", RowBox[{"j", ",", RowBox[{"Length", "[", "all", "]"}]}], "}"}]}], "]"}], ";", "\[IndentingNewLine]", RowBox[{"result", "=", RowBox[{"Apply", "[", RowBox[{"List", ",", RowBox[{"Flatten", "[", RowBox[{"result", ",", "Infinity", ",", "newlist"}], "]"}]}], "]"}]}], ";", "\[IndentingNewLine]", RowBox[{"Clear", "[", "htable", "]"}], ";", "\[IndentingNewLine]", "result"}]}], "]"}]}]], "Input",ExpressionUUID->"b0ebedad-69e9-4c1e-8c9b-\ 8791be03084d"], Cell["First we check that these give the same results.", "Text",ExpressionUUID->"80c54d5d-f556-428d-983f-71f55ab1571d"], Cell[CellGroupData[{ Cell[BoxData[{ RowBox[{ RowBox[{"uni1", "=", RowBox[{"unionNoSort1", "[", RowBox[{ RowBox[{"Range", "[", "50", "]"}], ",", RowBox[{"Reverse", "[", RowBox[{"Range", "[", "100", "]"}], "]"}], ",", RowBox[{"{", RowBox[{"300", ",", "400", ",", "399"}], "}"}]}], "]"}]}], ";"}], "\[IndentingNewLine]", RowBox[{"uni2", "=", RowBox[{"unionNoSort2", "[", RowBox[{ RowBox[{"Range", "[", "50", "]"}], ",", RowBox[{"Reverse", "[", RowBox[{"Range", "[", "100", "]"}], "]"}], ",", RowBox[{"{", RowBox[{"300", ",", "400", ",", "399"}], "}"}]}], "]"}]}], "\[IndentingNewLine]", RowBox[{"uni1", "===", "uni2"}]}], "Input",ExpressionUUID->"490b5e9a-d3e7-\ 41ee-bded-19a93e3304e7"], Cell[BoxData[ RowBox[{"{", RowBox[{ "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",ExpressionUUID\ ->"90a01c5d-7ac7-43d4-ab15-b29c8ed15e90"], Cell[BoxData["True"], "Output",ExpressionUUID->"2351002d-daef-4adf-b1b7-9430dbe8c91e"] }, Open ]], Cell["Now we check speed and algorithmic complexity.", "Text",ExpressionUUID->"9a4b04e7-e813-42e7-a963-01c439ab414b"], Cell[BoxData[{ RowBox[{"Timing", "[", RowBox[{ RowBox[{"u1", "=", RowBox[{"unionNoSort1", "[", RowBox[{ RowBox[{"Range", "[", "1000", "]"}], ",", RowBox[{"Reverse", "[", RowBox[{"Range", "[", "1100", "]"}], "]"}]}], "]"}]}], ";"}], "]"}], "\[IndentingNewLine]", RowBox[{"Timing", "[", RowBox[{ RowBox[{"u2", "=", RowBox[{"unionNoSort1", "[", RowBox[{ RowBox[{"Range", "[", "2000", "]"}], ",", RowBox[{"Reverse", "[", RowBox[{"Range", "[", "2200", "]"}], "]"}]}], "]"}]}], ";"}], "]"}], "\[IndentingNewLine]", RowBox[{"Timing", "[", RowBox[{ RowBox[{"u1b", "=", RowBox[{"unionNoSort2", "[", RowBox[{ RowBox[{"Range", "[", "10000", "]"}], ",", RowBox[{"Reverse", "[", RowBox[{"Range", "[", "11000", "]"}], "]"}]}], "]"}]}], ";"}], "]"}], "\[IndentingNewLine]", RowBox[{"Timing", "[", RowBox[{ RowBox[{"u2b", "=", RowBox[{"unionNoSort2", "[", RowBox[{ RowBox[{"Range", "[", "20000", "]"}], ",", RowBox[{"Reverse", "[", RowBox[{"Range", "[", "22000", "]"}], "]"}]}], "]"}]}], ";"}], "]"}]}], "Input",ExpressionUUID->"bfc17474-3741-4cad-8649-b778da9ac294"], Cell["\<\ It is quite clear that unionNoSort1 has quadratic complexity whereas \ unionNoSort2 has only linear complexity.\ \>", "Text",ExpressionUUID->"deb2063f-755c-42b2-aedc-8073e4c27478"], 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",ExpressionUUID->"61271dfb-e6b8-4e70-b692-844ff17b3386"], Cell[CellGroupData[{ Cell["Application: sparse sets", "Subsubsection", CellDingbat->None,ExpressionUUID->"df2cf222-0d1d-4e24-aba6-eb2648319f1c"], 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",ExpressionUUID->"a7959a95-1b14-4bdf-ad6e-b3d456457e6d"], Cell[BoxData[{ RowBox[{ RowBox[{ RowBox[{"setLength", "[", "_", "]"}], ":=", "0"}], "\[IndentingNewLine]"}], "\[IndentingNewLine]", RowBox[{ RowBox[{ RowBox[{"containsElement", "[", RowBox[{"set_", ",", "elem_"}], "]"}], ":=", RowBox[{ RowBox[{"Head", "[", RowBox[{"set", "[", "elem", "]"}], "]"}], "=!=", "set"}]}], "\[IndentingNewLine]"}], "\[IndentingNewLine]", RowBox[{ RowBox[{ RowBox[{"addElement", "[", RowBox[{"set_", ",", "elem_"}], "]"}], ":=", RowBox[{"If", "[", RowBox[{ RowBox[{ RowBox[{"Head", "[", RowBox[{"set", "[", "elem", "]"}], "]"}], "===", "set"}], ",", RowBox[{ RowBox[{ RowBox[{"set", "[", "elem", "]"}], "=", "elem"}], ";", " ", RowBox[{ RowBox[{"setLength", "[", "set", "]"}], "++"}], ";"}]}], "]"}]}], "\[IndentingNewLine]"}], "\[IndentingNewLine]", RowBox[{ RowBox[{ RowBox[{"removeElement", "[", RowBox[{"set_", ",", "elem_"}], "]"}], ":=", RowBox[{"If", "[", RowBox[{ RowBox[{"containsElement", "[", RowBox[{"set", ",", "elem"}], "]"}], ",", RowBox[{ RowBox[{ RowBox[{"set", "[", "elem", "]"}], "=."}], ";", " ", RowBox[{ RowBox[{"setLength", "[", "set", "]"}], "--"}], ";"}]}], "]"}]}], "\[IndentingNewLine]"}], "\[IndentingNewLine]", RowBox[{ RowBox[{ RowBox[{"displaySet", "[", "set_", "]"}], ":=", RowBox[{"Map", "[", RowBox[{ RowBox[{ RowBox[{"#", "[", RowBox[{"[", "2", "]"}], "]"}], "&"}], ",", RowBox[{"DownValues", "[", "set", "]"}]}], "]"}]}], "\[IndentingNewLine]"}], "\[IndentingNewLine]", RowBox[{ RowBox[{ RowBox[{"setClear", "[", "set_", "]"}], ":=", RowBox[{"(", RowBox[{ RowBox[{"Clear", "[", "set", "]"}], ";", " ", RowBox[{ RowBox[{"setLength", "[", "set", "]"}], "=", "0"}], ";"}], ")"}]}], "\[IndentingNewLine]"}], "\[IndentingNewLine]", RowBox[{ RowBox[{ RowBox[{"setCopy", "[", RowBox[{"set1_", ",", "set2_"}], "]"}], ":=", RowBox[{"Module", "[", RowBox[{ RowBox[{"{", RowBox[{ RowBox[{"elems", "=", RowBox[{"displaySet", "[", "set1", "]"}]}], ",", "j", ",", "len"}], "}"}], ",", "\[IndentingNewLine]", RowBox[{ RowBox[{"setClear", "[", "set2", "]"}], ";", "\[IndentingNewLine]", RowBox[{"len", "=", RowBox[{"Length", "[", "elems", "]"}]}], ";", "\[IndentingNewLine]", RowBox[{"For", "[", RowBox[{ RowBox[{"j", "=", "1"}], ",", RowBox[{"j", "\[LessEqual]", "len"}], ",", RowBox[{"j", "++"}], ",", RowBox[{"addElement", "[", RowBox[{"set2", ",", RowBox[{"elems", "[", RowBox[{"[", "j", "]"}], "]"}]}], "]"}]}], "]"}], ";"}]}], "]"}]}], "\[IndentingNewLine]"}], "\[IndentingNewLine]", RowBox[{ RowBox[{ RowBox[{"setUnion", "[", RowBox[{"set1_", ",", "set2_", ",", " ", "result_"}], "]"}], ":=", RowBox[{"Module", "[", RowBox[{ RowBox[{"{", RowBox[{"elems", ",", "j", ",", "len"}], "}"}], ",", "\[IndentingNewLine]", RowBox[{ RowBox[{"setCopy", "[", RowBox[{"set1", ",", "result"}], "]"}], ";", "\[IndentingNewLine]", RowBox[{"elems", "=", RowBox[{"Map", "[", RowBox[{ RowBox[{ RowBox[{"#", "[", RowBox[{"[", "2", "]"}], "]"}], "&"}], ",", RowBox[{"DownValues", "[", "set2", "]"}]}], "]"}]}], ";", "\[IndentingNewLine]", RowBox[{"len", "=", RowBox[{"Length", "[", "elems", "]"}]}], ";", "\[IndentingNewLine]", RowBox[{"For", "[", RowBox[{ RowBox[{"j", "=", "1"}], ",", RowBox[{"j", "\[LessEqual]", "len"}], ",", RowBox[{"j", "++"}], ",", RowBox[{"addElement", "[", RowBox[{"result", ",", RowBox[{"elems", "[", RowBox[{"[", "j", "]"}], "]"}]}], "]"}]}], "]"}], ";"}]}], "]"}]}], "\[IndentingNewLine]"}], "\[IndentingNewLine]", RowBox[{ RowBox[{ RowBox[{"setIntersection", "[", RowBox[{"set1_", ",", "set2_", ",", "result_"}], "]"}], ":=", RowBox[{"Module", "[", RowBox[{ RowBox[{"{", RowBox[{"elems", ",", "j", ",", "len"}], "}"}], ",", "\[IndentingNewLine]", RowBox[{ RowBox[{"setClear", "[", "result", "]"}], ";", "\[IndentingNewLine]", RowBox[{"elems", "=", RowBox[{"Map", "[", RowBox[{ RowBox[{ RowBox[{"#", "[", RowBox[{"[", "2", "]"}], "]"}], "&"}], ",", RowBox[{"DownValues", "[", "set2", "]"}]}], "]"}]}], ";", "\[IndentingNewLine]", RowBox[{"len", "=", RowBox[{"Length", "[", "elems", "]"}]}], ";", "\[IndentingNewLine]", RowBox[{"For", "[", RowBox[{ RowBox[{"j", "=", "1"}], ",", RowBox[{"j", "\[LessEqual]", "len"}], ",", RowBox[{"j", "++"}], ",", RowBox[{"If", "[", RowBox[{ RowBox[{"containsElement", "[", RowBox[{"set1", ",", RowBox[{"elems", "[", RowBox[{"[", "j", "]"}], "]"}]}], "]"}], ",", RowBox[{"addElement", "[", RowBox[{"result", ",", RowBox[{"elems", "[", RowBox[{"[", "j", "]"}], "]"}]}], "]"}]}], "]"}]}], "]"}], ";"}]}], "]"}]}], "\[IndentingNewLine]"}], "\[IndentingNewLine]", RowBox[{ RowBox[{"setComplement", "[", RowBox[{"set1_", ",", "set2_", ",", " ", "result_"}], "]"}], ":=", RowBox[{"Module", "[", RowBox[{ RowBox[{"{", RowBox[{"elems", ",", "j", ",", "len"}], "}"}], ",", "\[IndentingNewLine]", RowBox[{ RowBox[{"setCopy", "[", RowBox[{"set1", ",", "result"}], "]"}], ";", "\[IndentingNewLine]", RowBox[{"elems", "=", RowBox[{"Map", "[", RowBox[{ RowBox[{ RowBox[{"#", "[", RowBox[{"[", "2", "]"}], "]"}], "&"}], ",", RowBox[{"DownValues", "[", "set2", "]"}]}], "]"}]}], ";", "\[IndentingNewLine]", RowBox[{"len", "=", RowBox[{"Length", "[", "elems", "]"}]}], ";", "\[IndentingNewLine]", RowBox[{"For", "[", RowBox[{ RowBox[{"j", "=", "1"}], ",", RowBox[{"j", "\[LessEqual]", "len"}], ",", RowBox[{"j", "++"}], ",", RowBox[{"removeElement", "[", RowBox[{"result", ",", RowBox[{"elems", "[", RowBox[{"[", "j", "]"}], "]"}]}], "]"}]}], "]"}], ";"}]}], "]"}]}]}], "Input",ExpressionUUID->"92af6229-e43b-4981-b970-60869f231fe2"], Cell["Here we show some simple examples.", "Text",ExpressionUUID->"cc0248f8-e90f-412a-a67e-9aae5d69d5aa"], Cell[CellGroupData[{ Cell[BoxData[{ RowBox[{"SeedRandom", "[", "1111", "]"}], "\[IndentingNewLine]", RowBox[{"Timing", "[", RowBox[{"Do", "[", RowBox[{ RowBox[{"addElement", "[", RowBox[{"set1", ",", RowBox[{"Random", "[", RowBox[{"Integer", ",", "10000"}], "]"}]}], "]"}], ",", RowBox[{"{", "3000", "}"}]}], "]"}], "]"}], "\[IndentingNewLine]", RowBox[{ RowBox[{"Timing", "[", RowBox[{"Do", "[", RowBox[{ RowBox[{"addElement", "[", RowBox[{"set2", ",", RowBox[{"Random", "[", RowBox[{"Integer", ",", "10000"}], "]"}]}], "]"}], ",", RowBox[{"{", "3000", "}"}]}], "]"}], "]"}], "\[IndentingNewLine]"}], "\[IndentingNewLine]", RowBox[{"setLength", "[", "set1", "]"}], "\[IndentingNewLine]", RowBox[{"setLength", "[", "set2", "]"}]}], "Input",ExpressionUUID->"cecc62bb-\ 7e2c-4cdd-a03a-cd91e220f60d"], Cell[BoxData[ RowBox[{"{", RowBox[{ RowBox[{"0.6299999999999955`", " ", "Second"}], ",", "Null"}], "}"}]], "Output",ExpressionUUID->"1bbab1a8-79cf-48dc-b428-8917671bed9a"], Cell[BoxData[ RowBox[{"{", RowBox[{ RowBox[{"0.6500000000000057`", " ", "Second"}], ",", "Null"}], "}"}]], "Output",ExpressionUUID->"728d33e5-8327-4452-8be5-a5b387c9337f"], Cell[BoxData["2598"], "Output",ExpressionUUID->"6f509985-3ee3-4e63-89a7-c5ff5c1b20bd"], Cell[BoxData["2595"], "Output",ExpressionUUID->"30a47b12-a367-4b7e-8b07-4f2d0b1db366"] }, 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",ExpressionUUID->"c7ac1807-2bbd-4701-ab7c-1a63849e1d3d"], Cell[BoxData[{ RowBox[{ RowBox[{"elems1", "=", RowBox[{"displaySet", "[", "set1", "]"}]}], ";"}], "\[IndentingNewLine]", RowBox[{ RowBox[{ RowBox[{"elems2", "=", RowBox[{"displaySet", "[", "set2", "]"}]}], ";"}], "\[IndentingNewLine]"}], "\[IndentingNewLine]", RowBox[{ RowBox[{"elemsu", "=", RowBox[{"Union", "[", RowBox[{"elems1", ",", "elems2"}], "]"}]}], ";"}], "\[IndentingNewLine]", RowBox[{ RowBox[{"elemsi", "=", RowBox[{"Intersection", "[", RowBox[{"elems1", ",", "elems2"}], "]"}]}], ";"}], "\[IndentingNewLine]", RowBox[{ RowBox[{"elemsc", "=", RowBox[{"Complement", "[", RowBox[{"elems1", ",", "elems2"}], "]"}]}], ";"}]}], "Input",ExpressionUUI\ D->"dddda0f2-c7fe-4c16-a07a-66b7c0d30da0"], Cell[CellGroupData[{ Cell[BoxData[{ RowBox[{"Timing", "[", RowBox[{"setUnion", "[", RowBox[{"set1", ",", " ", "set2", ",", " ", "setu"}], "]"}], "]"}], "\[IndentingNewLine]", RowBox[{"Timing", "[", RowBox[{"setIntersection", "[", RowBox[{"set1", ",", " ", "set2", ",", " ", "seti"}], "]"}], "]"}], "\[IndentingNewLine]", RowBox[{ RowBox[{"Timing", "[", RowBox[{"setComplement", "[", RowBox[{"set1", ",", " ", "set2", ",", " ", "setc"}], "]"}], "]"}], "\[IndentingNewLine]"}], "\[IndentingNewLine]", RowBox[{ RowBox[{"Length", "[", "elemsu", "]"}], "==", RowBox[{"setLength", "[", "setu", "]"}]}], "\[IndentingNewLine]", RowBox[{ RowBox[{"Length", "[", "elemsi", "]"}], "==", RowBox[{"setLength", "[", "seti", "]"}]}], "\[IndentingNewLine]", RowBox[{ RowBox[{"Length", "[", "elemsc", "]"}], "==", RowBox[{"setLength", "[", "setc", "]"}]}]}], "Input",ExpressionUUID->\ "2c50d47f-e147-41b0-bebc-b7311fd301e1"], Cell[BoxData[ RowBox[{"{", RowBox[{ RowBox[{"1.6200000000000045`", " ", "Second"}], ",", "Null"}], "}"}]], "Output",ExpressionUUID->"2d6ec448-5bbf-4f21-b839-d380b8279587"], Cell[BoxData[ RowBox[{"{", RowBox[{ RowBox[{"0.5500000000000114`", " ", "Second"}], ",", "Null"}], "}"}]], "Output",ExpressionUUID->"01310d41-e039-41e2-8a08-3e85b13c2f92"], Cell[BoxData[ RowBox[{"{", RowBox[{ RowBox[{"1.5300000000000011`", " ", "Second"}], ",", "Null"}], "}"}]], "Output",ExpressionUUID->"0ddd0215-e277-4bb6-b73e-a9c6924fc1db"], Cell[BoxData["True"], "Output",ExpressionUUID->"8f9e78a4-318e-49b0-ad46-c216c6bb4ed6"], Cell[BoxData["True"], "Output",ExpressionUUID->"5673be57-f958-41d7-9dbe-ef26eb046177"], Cell[BoxData["True"], "Output",ExpressionUUID->"923c218f-df92-4554-be99-a87c3fccafac"] }, 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",ExpressionUUID->"de3d5ff1-7784-40f1-8f81-6d70edec2baa"], Cell[CellGroupData[{ Cell[BoxData[{ RowBox[{"SeedRandom", "[", "1111", "]"}], "\[IndentingNewLine]", RowBox[{"Timing", "[", RowBox[{"Do", "[", RowBox[{ RowBox[{"addElement", "[", RowBox[{"seta3K", ",", RowBox[{"Random", "[", RowBox[{"Integer", ",", "5000"}], "]"}]}], "]"}], ",", RowBox[{"{", "3000", "}"}]}], "]"}], "]"}], "\[IndentingNewLine]", RowBox[{"Timing", "[", RowBox[{"Do", "[", RowBox[{ RowBox[{"addElement", "[", RowBox[{"setb3K", ",", RowBox[{"Random", "[", RowBox[{"Integer", ",", "5000"}], "]"}]}], "]"}], ",", RowBox[{"{", "3000", "}"}]}], "]"}], "]"}], "\[IndentingNewLine]", RowBox[{"Timing", "[", RowBox[{"Do", "[", RowBox[{ RowBox[{"addElement", "[", RowBox[{"seta30K", ",", RowBox[{"Random", "[", RowBox[{"Integer", ",", "50000"}], "]"}]}], "]"}], ",", RowBox[{"{", "30000", "}"}]}], "]"}], "]"}], "\[IndentingNewLine]", RowBox[{"Timing", "[", RowBox[{"Do", "[", RowBox[{ RowBox[{"addElement", "[", RowBox[{"setb30K", ",", RowBox[{"Random", "[", RowBox[{"Integer", ",", "50000"}], "]"}]}], "]"}], ",", RowBox[{"{", "30000", "}"}]}], "]"}], "]"}]}], "Input",ExpressionUUID->\ "8aef2653-1867-4431-abca-1581fcc5fed1"], Cell[BoxData[ RowBox[{"{", RowBox[{ RowBox[{"0.6800000000000068`", " ", "Second"}], ",", "Null"}], "}"}]], "Output",ExpressionUUID->"e87a8a8a-d38f-4488-89a4-4ef218434b00"], Cell[BoxData[ RowBox[{"{", RowBox[{ RowBox[{"0.7099999999999795`", " ", "Second"}], ",", "Null"}], "}"}]], "Output",ExpressionUUID->"b1bd0547-897f-43cc-b57c-39cfd0b34347"], Cell[BoxData[ RowBox[{"{", RowBox[{ RowBox[{"7.1299999999999955`", " ", "Second"}], ",", "Null"}], "}"}]], "Output",ExpressionUUID->"c4fef80f-3d74-414a-a63f-f5800291dd74"], Cell[BoxData[ RowBox[{"{", RowBox[{ RowBox[{"7.3799999999999955`", " ", "Second"}], ",", "Null"}], "}"}]], "Output",ExpressionUUID->"770c8eae-0a38-42df-8cdc-ab414f24747f"] }, Open ]], Cell[CellGroupData[{ Cell[BoxData[{ RowBox[{"Timing", "[", RowBox[{"setUnion", "[", RowBox[{"seta3K", ",", "setb3K", ",", "r3k"}], "]"}], "]"}], "\[IndentingNewLine]", RowBox[{"Timing", "[", RowBox[{"setUnion", "[", RowBox[{"seta30K", ",", "setb30K", ",", "r30k"}], "]"}], "]"}]}], "Input",E\ xpressionUUID->"f68b9302-648a-4f9b-9ec4-907bb71d652a"], Cell[BoxData[ RowBox[{"{", RowBox[{ RowBox[{"1.4699999999999989`", " ", "Second"}], ",", "Null"}], "}"}]], "Output",ExpressionUUID->"16a9e78c-f5c1-46c8-a82f-3cea586ad8b8"], Cell[BoxData[ RowBox[{"{", RowBox[{ RowBox[{"14.880000000000024`", " ", "Second"}], ",", "Null"}], "}"}]], "Output",ExpressionUUID->"f3a095f4-0949-4f7a-966e-94663e1f9b98"] }, Open ]] }, Open ]] }, Open ]], Cell[CellGroupData[{ Cell["Stacks", "Subsection",ExpressionUUID->"e3da8166-17c7-491b-9160-27ec94353c74"], 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",ExpressionUUID->"a5e391a5-fed8-4fd0-ab1a-cd600c4e26b5"], 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",ExpressionUUID->"d2a47128-a4ad-408b-8fec-5052782849a6"], Cell[TextData[{ "First we give simple ", StyleBox["Mathematica", FontSlant->"Italic"], " code to implement a stack." }], "Text",ExpressionUUID->"24c4e263-2350-4c01-a914-cc64a6f61c74"], Cell[BoxData[{ RowBox[{"SetAttributes", "[", RowBox[{"push", ",", "HoldFirst"}], "]"}], "\[IndentingNewLine]", RowBox[{ RowBox[{"push", "[", RowBox[{"stack_", ",", "elem_"}], "]"}], " ", ":=", " ", RowBox[{"stack", " ", "=", " ", RowBox[{"{", RowBox[{"elem", ",", "stack"}], "}"}]}]}], "\[IndentingNewLine]", RowBox[{"SetAttributes", "[", RowBox[{"pop", ",", "HoldFirst"}], "]"}], "\[IndentingNewLine]", RowBox[{ RowBox[{"pop", "[", RowBox[{"{", "}"}], "]"}], ":=", "Null"}], "\[IndentingNewLine]", RowBox[{ RowBox[{"pop", "[", "stack_", "]"}], " ", ":=", " ", RowBox[{"With", "[", RowBox[{ RowBox[{"{", RowBox[{"elem", "=", RowBox[{"First", "[", "stack", "]"}]}], "}"}], ",", "\[IndentingNewLine]", RowBox[{ RowBox[{"stack", "=", RowBox[{"Last", "[", "stack", "]"}]}], ";", "elem"}]}], "]"}]}], "\[IndentingNewLine]", RowBox[{ RowBox[{"emptyStack", "[", "stack_", "]"}], " ", ":=", " ", RowBox[{"stack", "==", RowBox[{"{", "}"}]}]}]}], "Input",ExpressionUUID->"21150b7f-9f75-4d62-9e97-\ af3a6e321aa3"], 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",ExpressionUUID->"e4d2777a-7835-4423-90f0-bd7d00597a21"], Cell[BoxData[{ RowBox[{ RowBox[{"myFlatten1", "[", "xx_List", "]"}], ":=", RowBox[{"With", "[", "\[IndentingNewLine]", RowBox[{ RowBox[{"{", RowBox[{"flatparts", "=", RowBox[{"Map", "[", RowBox[{"myFlatten1", ",", "xx"}], "]"}]}], "}"}], ",", "\[IndentingNewLine]", RowBox[{"Join", "[", RowBox[{"Apply", "[", RowBox[{"Sequence", ",", "flatparts"}], "]"}], "]"}]}], "]"}]}], "\[IndentingNewLine]", RowBox[{ RowBox[{"myFlatten1", "[", "xx_", "]"}], ":=", RowBox[{"{", "xx", "}"}]}]}], "Input",ExpressionUUID->"04830634-bd80-4f47-\ bf75-bd1da8e0f57c"], Cell[BoxData[{ RowBox[{ RowBox[{"test", "=", RowBox[{"{", "}"}]}], ";"}], "\[IndentingNewLine]", RowBox[{"Do", "[", RowBox[{ RowBox[{"test", "=", RowBox[{"{", RowBox[{"j", ",", "test"}], "}"}]}], ",", " ", RowBox[{"{", RowBox[{"j", ",", "250"}], "}"}]}], "]"}]}], "Input",ExpressionUUID->\ "56584c4b-828c-491e-a09c-5e7d6959e58e"], 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",ExpressionUUID->"b397c67a-54c8-4b7d-892f-1f6923c5d3a3"], Cell[CellGroupData[{ Cell[BoxData[ RowBox[{ RowBox[{"myFlatten1", "[", "test", "]"}], " ", RowBox[{"(*", " ", RowBox[{"Kids", ",", " ", RowBox[{ RowBox[{"don", "'"}], "t", " ", "try", " ", "this", " ", "at", " ", RowBox[{"home", "!"}]}]}], " ", "*)"}]}]], "Input",ExpressionUUID->\ "79e7b5d9-4ef1-4adf-b3a4-ea072ff66d5e"], Cell[BoxData[ RowBox[{ RowBox[{"$RecursionLimit", "::", "\<\"reclim\"\>"}], RowBox[{ ":", " "}], "\<\"Recursion depth of \\!\\(256\\) exceeded.\"\>"}]], \ "Message",ExpressionUUID->"f4f90c03-9ec5-43cf-b5b9-1612863b7811"], Cell[BoxData[ RowBox[{ RowBox[{"$RecursionLimit", "::", "\<\"reclim\"\>"}], RowBox[{ ":", " "}], "\<\"Recursion depth of \\!\\(256\\) exceeded.\"\>"}]], \ "Message",ExpressionUUID->"b7a6d36d-c9a0-4067-a7d3-5a904b711674"], Cell[BoxData[ RowBox[{ RowBox[{"$RecursionLimit", "::", "\<\"reclim\"\>"}], RowBox[{ ":", " "}], "\<\"Recursion depth of \\!\\(256\\) exceeded.\"\>"}]], \ "Message",ExpressionUUID->"881b1214-b0bf-4184-b107-86a56bc36993"], Cell[BoxData[ RowBox[{ RowBox[{"General", "::", "\<\"stop\"\>"}], RowBox[{ ":", " "}], "\<\"Further output of \\!\\($RecursionLimit :: \ \\\"reclim\\\"\\) will be suppressed during this calculation.\"\>"}]], \ "Message",ExpressionUUID->"06eeaa4a-8cbf-41ef-9c94-ea892f8bdaf5"], Cell[BoxData[ RowBox[{ RowBox[{"Join", "::", "\<\"heads\"\>"}], RowBox[{ ":", " "}], "\<\"-- Message text not found -- (\\!\\(List\\)) \ (\\!\\(Hold\\)) (\\!\\(1\\)) (\\!\\(2\\))\"\>"}]], "Message",ExpressionUUID->\ "f9563299-ee4f-4847-8044-16c270bff466"], Cell[BoxData[ RowBox[{ RowBox[{"Join", "::", "\<\"heads\"\>"}], RowBox[{ ":", " "}], "\<\"-- Message text not found -- (\\!\\(List\\)) \ (\\!\\(Hold\\)) (\\!\\(1\\)) (\\!\\(3\\))\"\>"}]], "Message",ExpressionUUID->\ "41221970-a8aa-4808-9f95-2328c5d60c03"] }, 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",ExpressionUUID->"54de8bcb-4b01-4c50-bfb8-52f4197f8fe5"], Cell[BoxData[ RowBox[{ RowBox[{"myFlatten2", "[", "xx_List", "]"}], ":=", RowBox[{"Module", "[", "\[IndentingNewLine]", RowBox[{ RowBox[{"{", RowBox[{ RowBox[{"stack1", "=", RowBox[{"{", "}"}]}], ",", " ", RowBox[{"len", "=", "0"}], ",", " ", "elem", ",", " ", RowBox[{"stack2", "=", RowBox[{"{", "}"}]}]}], "}"}], ",", "\[IndentingNewLine]", RowBox[{ RowBox[{"Map", "[", RowBox[{ RowBox[{ RowBox[{"push", "[", RowBox[{"stack1", ",", "#"}], "]"}], "&"}], ",", " ", "xx"}], "]"}], ";", "\[IndentingNewLine]", RowBox[{"While", "[", RowBox[{ RowBox[{"!", RowBox[{"emptyStack", "[", "stack1", "]"}]}], ",", "\[IndentingNewLine]", RowBox[{ RowBox[{"elem", "=", RowBox[{"pop", "[", "stack1", "]"}]}], ";", "\[IndentingNewLine]", RowBox[{"If", " ", "[", RowBox[{ RowBox[{"ListQ", "[", "elem", "]"}], ",", "\[IndentingNewLine]", RowBox[{"Map", "[", RowBox[{ RowBox[{ RowBox[{"push", "[", RowBox[{"stack1", ",", "#"}], "]"}], "&"}], ",", " ", "elem"}], "]"}], ",", "\[IndentingNewLine]", RowBox[{ RowBox[{"push", "[", RowBox[{"stack2", ",", "elem"}], "]"}], ";", RowBox[{"len", "++"}]}]}], "]"}], ";"}]}], "\[IndentingNewLine]", "]"}], ";", "\[IndentingNewLine]", RowBox[{"Table", "[", RowBox[{ RowBox[{"pop", "[", "stack2", "]"}], ",", " ", RowBox[{"{", "len", "}"}]}], "]"}]}]}], "\[IndentingNewLine]", "]"}]}]], "Input",ExpressionUUID->"46b1d8c4-faf5-4c1f-ae5d-bfd5bd7a8086"], Cell[CellGroupData[{ Cell[BoxData[ RowBox[{ RowBox[{"myFlatten2", "[", "test", "]"}], "===", RowBox[{"Flatten", "[", "test", "]"}]}]], "Input",ExpressionUUID->"7369bb1b-\ fe8b-44f6-b454-f06e09f84339"], Cell[BoxData["True"], "Output",ExpressionUUID->"c59e550b-efbe-4ade-83bb-9fe77a07054c"] }, Open ]], Cell[BoxData[ RowBox[{ RowBox[{"test2", " ", "=", " ", RowBox[{"{", " ", RowBox[{ RowBox[{"{", RowBox[{"a", ",", "b", ",", RowBox[{"{", RowBox[{"c", ",", "d"}], "}"}], ",", RowBox[{"{", RowBox[{"e", ",", RowBox[{"{", RowBox[{"f", ",", "g", ",", "h", ",", RowBox[{"{", RowBox[{"i", ",", "j"}], "}"}]}], "}"}]}], "}"}]}], "}"}], ",", RowBox[{"{", RowBox[{ RowBox[{"{", RowBox[{"k", ",", "l"}], "}"}], ",", "m"}], "}"}], ",", "n", ",", RowBox[{"{", RowBox[{ RowBox[{"{", RowBox[{ RowBox[{"{", RowBox[{"o", ",", "p", ",", RowBox[{"{", "q", "}"}]}], "}"}], ",", RowBox[{"{", RowBox[{ RowBox[{"{", RowBox[{"r", ",", "s"}], "}"}], ",", "t"}], "}"}], ",", "u"}], "}"}], ",", RowBox[{"{", RowBox[{"v", ",", "w"}], "}"}]}], "}"}], ",", "x"}], "}"}]}], ";"}]], "Input",ExpressionUUID->"d011f3d1-c505-465d-b917-36d1a7a61d97"], Cell[CellGroupData[{ Cell[BoxData[ RowBox[{ RowBox[{"myFlatten2", "[", "test2", "]"}], "===", RowBox[{"Flatten", "[", "test2", "]"}]}]], "Input",ExpressionUUID->\ "9563e3e5-3b74-4f61-9cd4-ba38e3b085e4"], Cell[BoxData["True"], "Output",ExpressionUUID->"7c11924f-c5e9-4b61-b335-3b8273343ec5"] }, 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",ExpressionUUID->"91be0d5a-f2ab-4f37-969b-599597ba91e7"] }, Open ]], Cell[CellGroupData[{ Cell["Queues", "Subsection",ExpressionUUID->"749a715a-0a21-4144-9af2-988f66a9a110"], 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",ExpressionUUID->"aec2ab1b-4165-41ec-8a72-18a992ddb3f3"], Cell[BoxData[{ RowBox[{ RowBox[{"qelems", "=", "1"}], ";", " ", RowBox[{"qlen", "=", "2"}], ";", " ", RowBox[{"qsize", "=", "3"}], ";", " ", RowBox[{"qfront", "=", "4"}], ";", " ", RowBox[{"qback", "=", "5"}], ";"}], "\[IndentingNewLine]", RowBox[{ RowBox[{ RowBox[{"newQueue", "[", "len_Integer", "]"}], "/;", RowBox[{"len", ">", "0"}]}], ":=", RowBox[{"{", RowBox[{ RowBox[{"Table", "[", RowBox[{"0", ",", RowBox[{"{", "len", "}"}]}], "]"}], ",", "0", ",", "len", ",", "1", ",", "1"}], "}"}]}], "\[IndentingNewLine]", RowBox[{ RowBox[{"emptyQueue", "[", "Q_", "]"}], ":=", RowBox[{ RowBox[{"Q", "[", RowBox[{"[", "qlen", "]"}], "]"}], "\[Equal]", "0"}]}], "\[IndentingNewLine]", RowBox[{ RowBox[{"queueLength", "[", "Q_", "]"}], ":=", RowBox[{"Q", "[", RowBox[{"[", "qlen", "]"}], "]"}]}], "\[IndentingNewLine]", RowBox[{"SetAttributes", "[", RowBox[{"enQueue", ",", "HoldFirst"}], "]"}], "\[IndentingNewLine]", RowBox[{ RowBox[{"enQueue", "[", RowBox[{"Q_", ",", "elem_"}], "]"}], ":=", RowBox[{"If", "[", RowBox[{ RowBox[{ RowBox[{"Q", "[", RowBox[{"[", "qlen", "]"}], "]"}], "\[Equal]", RowBox[{"Q", "[", RowBox[{"[", "qsize", "]"}], "]"}]}], ",", RowBox[{"Print", "[", "\"\\"", "]"}], ",", RowBox[{ RowBox[{ RowBox[{"Q", "[", RowBox[{"[", "qlen", "]"}], "]"}], "++"}], ";", "\[IndentingNewLine]", RowBox[{ RowBox[{"Q", "[", RowBox[{"[", RowBox[{"qelems", ",", RowBox[{"Q", "[", RowBox[{"[", "qfront", "]"}], "]"}]}], "]"}], "]"}], "=", "elem"}], ";", "\[IndentingNewLine]", RowBox[{ RowBox[{"Q", "[", RowBox[{"[", "qfront", "]"}], "]"}], "=", RowBox[{"Mod", "[", RowBox[{ RowBox[{ RowBox[{"Q", "[", RowBox[{"[", "qfront", "]"}], "]"}], "+", "1"}], ",", RowBox[{"Q", "[", RowBox[{"[", "qsize", "]"}], "]"}], ",", "1"}], "]"}]}], ";"}]}], "]"}]}], "\[IndentingNewLine]", RowBox[{"SetAttributes", "[", RowBox[{"deQueue", ",", "HoldFirst"}], "]"}], "\[IndentingNewLine]", RowBox[{ RowBox[{ RowBox[{"deQueue", "[", "Q_", "]"}], "/;", RowBox[{"emptyQueue", "[", "Q", "]"}]}], ":=", "Null"}], "\[IndentingNewLine]", RowBox[{ RowBox[{"deQueue", "[", "Q_", "]"}], ":=", RowBox[{"(", RowBox[{ RowBox[{ RowBox[{"Q", "[", RowBox[{"[", "qlen", "]"}], "]"}], "--"}], ";", "\[IndentingNewLine]", RowBox[{ RowBox[{"Q", "[", RowBox[{"[", "qback", "]"}], "]"}], "=", RowBox[{"Mod", "[", RowBox[{ RowBox[{ RowBox[{"Q", "[", RowBox[{"[", "qback", "]"}], "]"}], "+", "1"}], ",", RowBox[{"Q", "[", RowBox[{"[", "qsize", "]"}], "]"}], ",", "1"}], "]"}]}], ";", "\[IndentingNewLine]", RowBox[{"Q", "[", RowBox[{"[", RowBox[{"qelems", ",", RowBox[{"Mod", "[", RowBox[{ RowBox[{ RowBox[{"Q", "[", RowBox[{"[", "qback", "]"}], "]"}], "-", "1"}], ",", RowBox[{"Q", "[", RowBox[{"[", "qsize", "]"}], "]"}], ",", "1"}], "]"}]}], "]"}], "]"}]}], ")"}]}]}], "Input",ExpressionUUID->"e2e4d706-67ba-4217-8a05-\ 31f4bd37c0e7"], Cell["Here is a simple example.", "Text",ExpressionUUID->"96eb481e-e111-41d7-9cb9-6244bbc7350b"], Cell[CellGroupData[{ Cell[BoxData[{ RowBox[{ RowBox[{"myQ", "=", RowBox[{"newQueue", "[", "7", "]"}]}], ";"}], "\[IndentingNewLine]", RowBox[{ RowBox[{"Map", "[", RowBox[{ RowBox[{ RowBox[{"enQueue", "[", RowBox[{"myQ", ",", "#"}], "]"}], "&"}], ",", RowBox[{"{", RowBox[{"\"\\"", ",", "\"\\""}], "}"}]}], "]"}], ";"}], "\[IndentingNewLine]", RowBox[{"queueLength", "[", "myQ", "]"}], "\[IndentingNewLine]", RowBox[{"show1", "=", RowBox[{"deQueue", "[", "myQ", "]"}]}]}], "Input",ExpressionUUID->"5604e265-\ c199-4ecf-b311-0cdff76d415b"], Cell[BoxData["2"], "Output",ExpressionUUID->"ce2df55c-bfbf-4b46-ac58-8142d349616e"], Cell[BoxData["\<\"Hello Dolly\"\>"], "Output",ExpressionUUID->"f2441029-6edd-4716-95a7-5ae18c88664a"] }, Open ]], Cell[CellGroupData[{ Cell[BoxData[ RowBox[{ RowBox[{"Map", "[", RowBox[{ RowBox[{ RowBox[{"enQueue", "[", RowBox[{"myQ", ",", "#"}], "]"}], "&"}], ",", RowBox[{"{", RowBox[{ "\"\\"", ",", "\"\\"", ",", "\"\\"", ",", "\"\\"", ",", "\"\\"", ",", "\"\\"", ",", "\"\\""}], "}"}]}], "]"}], ";"}]], "Input",ExpressionUUID-\ >"a5d3d64a-d118-4375-8a7e-a1948865810a"], Cell[BoxData["\<\"Queue is full\"\>"], "Print",ExpressionUUID->"695379f4-82cf-4c28-8def-47fed67f2d6b"] }, Open ]], Cell["\<\ We ran out of space. We'll remove an element and then we can put on that last \ one.\ \>", "Text",ExpressionUUID->"9cd5ec35-7637-4e43-a50c-bbe9785f9741"], Cell[CellGroupData[{ Cell[BoxData[ RowBox[{"show2", "=", RowBox[{"deQueue", "[", "myQ", "]"}]}]], "Input",ExpressionUUID->"301b40a9-\ 5bff-4472-aaf6-535ca76a095c"], Cell[BoxData["\<\"West Side Story\"\>"], "Output",ExpressionUUID->"3724cc44-bd2b-4487-8c77-627a2d17dd8e"] }, Open ]], Cell[BoxData[ RowBox[{"enQueue", "[", RowBox[{"myQ", ",", "\"\\""}], "]"}]], "Input",ExpressionUUID->\ "df921993-691e-4f89-ac31-33ed59305281"], 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",ExpressionUUID->"02c389cd-b905-4945-9178-9ca63f269328"], Cell[BoxData[{ RowBox[{ RowBox[{"newQueue", "[", "sym_Symbol", "]"}], ":=", " ", RowBox[{"{", RowBox[{ RowBox[{"Unique", "[", "sym", "]"}], ",", "0", ",", "Null", ",", "0", ",", "0"}], "}"}]}], "\[IndentingNewLine]", RowBox[{ RowBox[{"Clear", "[", RowBox[{"queueLength", ",", "emptyQueue", ",", "enQueue", ",", "deQueue"}], "]"}], ";"}], "\n", RowBox[{ RowBox[{"qptr", "=", "1"}], ";", RowBox[{"qlen", "=", "2"}], ";", RowBox[{"qelem", "=", "3"}], ";", RowBox[{"qfront", "=", "4"}], ";", RowBox[{"qback", "=", "5"}], ";"}], "\n", RowBox[{ RowBox[{"queueLength", "[", "Q_", "]"}], " ", ":=", " ", RowBox[{"Q", "[", RowBox[{"[", "qlen", "]"}], "]"}]}], "\n", RowBox[{ RowBox[{"emptyQueue", "[", "Q_", "]"}], ":=", RowBox[{ RowBox[{"Q", "[", RowBox[{"[", "qlen", "]"}], "]"}], "==", "0"}]}], "\n", RowBox[{"SetAttributes", "[", RowBox[{"enQueue", ",", "HoldFirst"}], "]"}], "\n", RowBox[{ RowBox[{"enQueue", "[", RowBox[{"Q_", ",", "elem_"}], "]"}], ":=", RowBox[{"(", RowBox[{ RowBox[{ RowBox[{"Q", "[", RowBox[{"[", "qlen", "]"}], "]"}], "++"}], ";", RowBox[{ RowBox[{"Q", "[", RowBox[{"[", "qfront", "]"}], "]"}], "++"}], ";", RowBox[{ RowBox[{ RowBox[{"Q", "[", RowBox[{"[", "qptr", "]"}], "]"}], "[", RowBox[{"Q", "[", RowBox[{"[", "qfront", "]"}], "]"}], "]"}], "=", "elem"}], ";"}], ")"}]}], "\n", RowBox[{"SetAttributes", "[", RowBox[{"deQueue", ",", "HoldFirst"}], "]"}], "\n", RowBox[{ RowBox[{"deQueue", "[", "Q_", "]"}], ":=", RowBox[{"(", RowBox[{ RowBox[{ RowBox[{"Q", "[", RowBox[{"[", "qlen", "]"}], "]"}], "--"}], ";", RowBox[{ RowBox[{"Q", "[", RowBox[{"[", "qback", "]"}], "]"}], "++"}], ";", RowBox[{ RowBox[{"Q", "[", RowBox[{"[", "qelem", "]"}], "]"}], "=", RowBox[{ RowBox[{"Q", "[", RowBox[{"[", "qptr", "]"}], "]"}], "[", RowBox[{"Q", "[", RowBox[{"[", "qback", "]"}], "]"}], "]"}]}], ";", RowBox[{ RowBox[{ RowBox[{"Q", "[", RowBox[{"[", "qptr", "]"}], "]"}], "[", RowBox[{"Q", "[", RowBox[{"[", "qback", "]"}], "]"}], "]"}], "=."}], ";", RowBox[{"Q", "[", RowBox[{"[", "qelem", "]"}], "]"}]}], ")"}]}]}], "Input",ExpressionUUID->\ "c33be860-2a17-4f25-8943-81c50e9a2185"], Cell["\<\ Let us see how this process works. We repeat the previous example. This time \ we'll not run out of space.\ \>", "Text",ExpressionUUID->"526e674a-f294-48a2-9226-3bc4477b0c95"], Cell[CellGroupData[{ Cell[BoxData[{ RowBox[{ RowBox[{"myQ", "=", RowBox[{"newQueue", "[", "qq", "]"}]}], ";"}], "\[IndentingNewLine]", RowBox[{ RowBox[{"Map", "[", RowBox[{ RowBox[{ RowBox[{"enQueue", "[", RowBox[{"myQ", ",", "#"}], "]"}], "&"}], ",", RowBox[{"{", RowBox[{"\"\\"", ",", "\"\\""}], "}"}]}], "]"}], ";"}], "\[IndentingNewLine]", RowBox[{"queueLength", "[", "myQ", "]"}], "\[IndentingNewLine]", RowBox[{"show1", "=", RowBox[{"deQueue", "[", "myQ", "]"}]}]}], "Input",ExpressionUUID->"bd301805-\ 71d1-4504-90fc-2f95df99fb58"], Cell[BoxData["2"], "Output",ExpressionUUID->"5c6859b3-bb3f-4b35-9955-03c40d6b624b"], Cell[BoxData["\<\"Hello Dolly\"\>"], "Output",ExpressionUUID->"30e5101d-ab43-457b-a1bb-90584232431a"] }, Open ]], Cell[BoxData[ RowBox[{ RowBox[{"Map", "[", RowBox[{ RowBox[{ RowBox[{"enQueue", "[", RowBox[{"myQ", ",", "#"}], "]"}], "&"}], ",", RowBox[{"{", RowBox[{ "\"\\"", ",", "\"\\"", ",", "\"\\"", ",", "\"\\"", ",", "\"\\"", ",", "\"\\"", ",", "\"\\""}], "}"}]}], "]"}], ";"}]], "Input",ExpressionUUID-\ >"aa462b12-fa25-43d4-a5b1-db238916ba53"], Cell[CellGroupData[{ Cell[BoxData[{ RowBox[{"show2", "=", RowBox[{"deQueue", "[", "myQ", "]"}]}], "\[IndentingNewLine]", RowBox[{"queueLength", "[", "myQ", "]"}]}], "Input",ExpressionUUID->\ "f94d5906-0cca-43b5-84d4-14e4a7d39db3"], Cell[BoxData["\<\"West Side Story\"\>"], "Output",ExpressionUUID->"26ec5d2d-72af-4704-8abc-d4ebe685dc2e"], Cell[BoxData["7"], "Output",ExpressionUUID->"dfe3d1e0-7d83-4815-8be9-06b3625623c8"] }, 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",ExpressionUUID->"82c89575-6265-47ff-91c5-53e76bc46694"], 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",ExpressionUUID->"6a88c046-85ef-4808-8d37-cea30f252681"], Cell[CellGroupData[{ Cell[BoxData[ RowBox[{"Information", "[", RowBox[{"Evaluate", "[", RowBox[{"myQ", "[", RowBox[{"[", "qptr", "]"}], "]"}], "]"}], "]"}]], "Input",ExpressionUUID->\ "476556a3-9910-4995-a328-c359e63795c2"], Cell[BoxData["\<\"Global`qq$13\"\>"], "Print",ExpressionUUID->"da3d2b31-3b03-4ba1-a9af-9d175fc809b1"], Cell[BoxData[ InterpretationBox[GridBox[{ {GridBox[{ { RowBox[{ RowBox[{"qq$13", "[", "3", "]"}], "=", "\<\"My Fair Lady\"\>"}]}, {" "}, { RowBox[{ RowBox[{"qq$13", "[", "4", "]"}], "=", "\<\"Les Miz\"\>"}]}, {" "}, { RowBox[{ RowBox[{"qq$13", "[", "5", "]"}], "=", "\<\"Phantom\"\>"}]}, {" "}, { RowBox[{ RowBox[{"qq$13", "[", "6", "]"}], "=", "\<\"Fiddler\"\>"}]}, {" "}, { RowBox[{ RowBox[{"qq$13", "[", "7", "]"}], "=", "\<\"Mouse Trap\"\>"}]}, {" "}, { RowBox[{ RowBox[{"qq$13", "[", "8", "]"}], "=", "\<\"Rent\"\>"}]}, {" "}, { RowBox[{ RowBox[{"qq$13", "[", "9", "]"}], "=", "\<\"Sleuth\"\>"}]} }, BaselinePosition->{Baseline, {1, 1}}, GridBoxAlignment->{ "Columns" -> {{Left}}, "ColumnsIndexed" -> {}, "Rows" -> {{Baseline}}, "RowsIndexed" -> {}}, GridBoxItemSize->{"Columns" -> {{ Scaled[0.999]}}, "ColumnsIndexed" -> {}, "Rows" -> {{1.}}, "RowsIndexed" -> {}}]} }, BaselinePosition->{Baseline, {1, 1}}, GridBoxAlignment->{ "Columns" -> {{Left}}, "ColumnsIndexed" -> {}, "Rows" -> {{Baseline}}, "RowsIndexed" -> {}}], Definition[qq$13], Editable->False]], "Print",ExpressionUUID->"900e46ef-f1c1-42c1-800e-\ 2122db6e978c"] }, 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",ExpressionUUID->"0e78c52c-9d73-4491-9ab2-6fafa51f0501"], 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",ExpressionUUID->"014e9ccc-ab8c-44d2-b215-1aee627c2722"], Cell[BoxData[ RowBox[{ RowBox[{"funnyFlatten", "[", "xx_List", "]"}], ":=", RowBox[{"Module", "[", "\[IndentingNewLine]", RowBox[{ RowBox[{"{", RowBox[{ RowBox[{"q1", "=", RowBox[{"newQ", "[", "s1", "]"}]}], ",", " ", RowBox[{"len", "=", "0"}], ",", " ", "elem", ",", " ", RowBox[{"q2", "=", RowBox[{"newQ", "[", "s2", "]"}]}]}], "}"}], ",", "\[IndentingNewLine]", RowBox[{ RowBox[{"Map", "[", RowBox[{ RowBox[{ RowBox[{"enQ", "[", RowBox[{"q1", ",", "#"}], "]"}], "&"}], ",", " ", "xx"}], "]"}], ";", "\[IndentingNewLine]", RowBox[{"While", "[", RowBox[{ RowBox[{"!", RowBox[{"emptyQ", "[", "q1", "]"}]}], ",", "\[IndentingNewLine]", RowBox[{ RowBox[{"elem", "=", RowBox[{"deQ", "[", "q1", "]"}]}], ";", "\[IndentingNewLine]", RowBox[{"If", " ", "[", RowBox[{ RowBox[{"ListQ", "[", "elem", "]"}], ",", "\[IndentingNewLine]", RowBox[{"Map", "[", RowBox[{ RowBox[{ RowBox[{"enQ", "[", RowBox[{"q1", ",", "#"}], "]"}], "&"}], ",", " ", "elem"}], "]"}], ",", "\[IndentingNewLine]", RowBox[{ RowBox[{"enQ", "[", RowBox[{"q2", ",", "elem"}], "]"}], ";", RowBox[{"len", "++"}]}]}], "]"}], ";"}]}], "\[IndentingNewLine]", "]"}], ";", "\[IndentingNewLine]", RowBox[{"Table", "[", RowBox[{ RowBox[{"deQ", "[", "q2", "]"}], ",", " ", RowBox[{"{", "len", "}"}]}], "]"}]}]}], "\[IndentingNewLine]", "]"}]}]], "Input",ExpressionUUID->"073f3894-8e82-4430-aaa4-4df65a8938f2"], Cell[CellGroupData[{ Cell[BoxData[ RowBox[{"funnyFlatten", "[", "test", "]"}]], "Input",ExpressionUUID->"617c3521-1120-4ce8-a4d8-884ee8ba3d03"], Cell[BoxData[ RowBox[{"{", RowBox[{ "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",ExpressionUUID->"72124c2b-73ac-460e-86d0-\ f858dd9e2356"] }, 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",ExpressionUUID->"0ddbfe19-0122-46d1-8c4b-0a8a4a95be88"], Cell[CellGroupData[{ Cell[BoxData[{ RowBox[{"e1", "=", RowBox[{"MapIndexed", "[", RowBox[{"C", ",", "test2", ",", RowBox[{"{", RowBox[{"-", "1"}], "}"}]}], "]"}]}], "\[IndentingNewLine]", RowBox[{"e2", "=", RowBox[{"Cases", "[", RowBox[{"e1", ",", "_C", ",", "Infinity"}], "]"}]}], "\[IndentingNewLine]", RowBox[{ RowBox[{"e3", "=", RowBox[{"Sort", "[", RowBox[{"e2", ",", RowBox[{ RowBox[{"(", RowBox[{ RowBox[{"Length", "[", RowBox[{"#1", "[", RowBox[{"[", "2", "]"}], "]"}], "]"}], "\[LessEqual]", RowBox[{"Length", "[", RowBox[{"#2", "[", RowBox[{"[", "2", "]"}], "]"}], "]"}]}], ")"}], "&"}]}], "]"}]}], ";"}], "\[IndentingNewLine]", RowBox[{"Map", "[", RowBox[{"First", ",", "e3"}], "]"}]}], "Input",ExpressionUUID->"cb4fefa3-\ 6510-4da4-9bb3-acda8be08311"], Cell[BoxData[ RowBox[{"{", RowBox[{ "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",ExpressionUUID->"fc61b12c-c905-4d7b-8e5b-\ 170b97af64cc"] }, 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",ExpressionUUID->"d4e4e240-eee9-4201-ae5b-9c2c171e9cc4"], 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",ExpressionUUID->"7996eb1b-40a4-4bd9-b5f9-a56f27fbc061"] }, Open ]], Cell[CellGroupData[{ Cell["Trees", "Subsection",ExpressionUUID->"37a82a5e-6704-4196-a435-1a72791b41df"], 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",ExpressionUUID->"9ee425db-e460-4b36-be4f-d8fc3c4eb071"], 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",ExpressionUUID->"7afe25d1-1b4f-4477-add3-fca0328f7d0d"], 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",ExpressionUUID->"053ad205-2e75-4a4a-90ed-eb90a0ad61d0"], 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",ExpressionUUID->"91d0984d-3c23-42f9-a4cb-9dcc9ef614ca"], Cell[BoxData[{ RowBox[{ RowBox[{"leftsubtree", "[", RowBox[{"{", RowBox[{"left_", ",", "_", ",", "_"}], "}"}], "]"}], " ", ":=", " ", "left"}], "\[IndentingNewLine]", RowBox[{ RowBox[{"rightsubtree", "[", RowBox[{"{", RowBox[{"_", ",", "_", ",", "right_"}], "}"}], "]"}], ":=", "right"}], "\[IndentingNewLine]", RowBox[{ RowBox[{"nodevalue", "[", RowBox[{"{", RowBox[{"_", ",", "val_", ",", "_"}], "}"}], "]"}], ":=", "val"}], "\[IndentingNewLine]", RowBox[{ RowBox[{ RowBox[{"emptyTree", " ", "=", " ", RowBox[{"{", "}"}]}], ";"}], "\[IndentingNewLine]"}], "\n", RowBox[{ RowBox[{"treeInsert", "[", RowBox[{"emptyTree", ",", " ", "elem_"}], "]"}], " ", ":=", " ", RowBox[{"{", RowBox[{"emptyTree", ",", "elem", ",", "emptyTree"}], "}"}]}], "\n", RowBox[{ RowBox[{ RowBox[{"treeInsert", "[", RowBox[{"tree_", ",", " ", "elem_"}], "]"}], " ", "/;", " ", RowBox[{"SameQ", "[", RowBox[{ RowBox[{"nodevalue", "[", "tree", "]"}], ",", " ", "elem"}], "]"}]}], " ", ":=", "tree"}], "\n", RowBox[{ RowBox[{ RowBox[{"treeInsert", "[", RowBox[{"tree_", ",", " ", "elem_"}], "]"}], " ", "/;", " ", RowBox[{"OrderedQ", "[", RowBox[{"{", RowBox[{ RowBox[{"nodevalue", "[", "tree", "]"}], ",", " ", "elem"}], "}"}], "]"}]}], " ", ":=", "\n", "\t", RowBox[{"{", RowBox[{ RowBox[{"leftsubtree", "[", "tree", "]"}], ",", " ", RowBox[{"nodevalue", "[", "tree", "]"}], ",", " ", RowBox[{"treeInsert", "[", RowBox[{ RowBox[{"rightsubtree", "[", "tree", "]"}], ",", " ", "elem"}], "]"}]}], "}"}]}], "\n", RowBox[{ RowBox[{"treeInsert", "[", RowBox[{"tree_", ",", " ", "elem_"}], "]"}], " ", ":=", " ", RowBox[{"{", RowBox[{ RowBox[{"treeInsert", "[", RowBox[{ RowBox[{"leftsubtree", "[", "tree", "]"}], ",", " ", "elem"}], "]"}], ",", " ", RowBox[{"nodevalue", "[", "tree", "]"}], ",", RowBox[{"rightsubtree", "[", "tree", "]"}]}], "}"}]}]}], "Input",Expressio\ nUUID->"2f4b107a-e79e-4d90-aa10-0c8d47e6f910"], 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",ExpressionUUID->"bd58e03a-668c-43b3-bc8e-8d0ada16a88c"], Cell[CellGroupData[{ Cell[BoxData[{ RowBox[{ RowBox[{"len1k", "=", "1000"}], ";"}], "\[IndentingNewLine]", RowBox[{ RowBox[{"ee1k", "=", RowBox[{"Table", "[", RowBox[{ RowBox[{"Random", "[", "]"}], ",", RowBox[{"{", "len1k", "}"}]}], "]"}]}], ";"}], "\[IndentingNewLine]", RowBox[{ RowBox[{"ff1k", "=", RowBox[{"{", "}"}]}], ";"}], "\[IndentingNewLine]", RowBox[{"t1k", "=", RowBox[{ RowBox[{"First", "[", RowBox[{"Timing", "[", RowBox[{ RowBox[{"Do", "[", RowBox[{ RowBox[{"ff1k", "=", RowBox[{"treeInsert", "[", RowBox[{"ff1k", ",", RowBox[{"ee1k", "[", RowBox[{"[", "j", "]"}], "]"}]}], "]"}]}], ",", RowBox[{"{", RowBox[{"j", ",", "len1k"}], "}"}]}], "]"}], ";"}], "]"}], "]"}], "/", "Second"}]}], "\[IndentingNewLine]", RowBox[{ RowBox[{"gg1k", "=", RowBox[{"Flatten", "[", "ff1k", "]"}]}], ";"}], "\[IndentingNewLine]", RowBox[{"gg1k", "===", RowBox[{"Sort", "[", "ee1k", "]"}]}]}], "Input",ExpressionUUID->"a4dfc256-\ 41ef-4748-9680-9f031d32702b"], Cell[BoxData["1.539999999999992`"], "Output",ExpressionUUID->"2558f41f-a280-4e2a-a23c-578ec182285c"], Cell[BoxData["True"], "Output",ExpressionUUID->"a3dffde5-b0e9-4f9e-9e85-8a92c60b1d67"] }, Open ]], Cell[CellGroupData[{ Cell[BoxData[{ RowBox[{ RowBox[{"len5k", "=", "5000"}], ";"}], "\[IndentingNewLine]", RowBox[{ RowBox[{"ee5k", "=", RowBox[{"Table", "[", RowBox[{ RowBox[{"Random", "[", "]"}], ",", RowBox[{"{", "len5k", "}"}]}], "]"}]}], ";"}], "\[IndentingNewLine]", RowBox[{ RowBox[{"ff5k", "=", RowBox[{"{", "}"}]}], ";"}], "\[IndentingNewLine]", RowBox[{"t5k", "=", RowBox[{ RowBox[{"First", "[", RowBox[{"Timing", "[", RowBox[{ RowBox[{"Do", "[", RowBox[{ RowBox[{"ff5k", "=", RowBox[{"treeInsert", "[", RowBox[{"ff5k", ",", RowBox[{"ee5k", "[", RowBox[{"[", "j", "]"}], "]"}]}], "]"}]}], ",", RowBox[{"{", RowBox[{"j", ",", "len5k"}], "}"}]}], "]"}], ";"}], "]"}], "]"}], "/", "Second"}]}], "\[IndentingNewLine]", RowBox[{ RowBox[{"gg5k", "=", RowBox[{"Flatten", "[", "ff5k", "]"}]}], ";"}], "\[IndentingNewLine]", RowBox[{"gg5k", "===", RowBox[{"Sort", "[", "ee5k", "]"}]}]}], "Input",ExpressionUUID->"5d74aade-\ 412f-4f84-bb90-f4c3892321ca"], Cell[BoxData["11.459999999999994`"], "Output",ExpressionUUID->"bd88bd16-04be-490b-ac7c-2e8d5bfe777a"], Cell[BoxData["True"], "Output",ExpressionUUID->"d3325954-2f2e-4a69-bd35-d93cc8af2168"] }, Open ]], Cell[CellGroupData[{ Cell[BoxData[{ RowBox[{ RowBox[{"len10k", "=", "10000"}], ";"}], "\[IndentingNewLine]", RowBox[{ RowBox[{"ee10k", "=", RowBox[{"Table", "[", RowBox[{ RowBox[{"Random", "[", "]"}], ",", RowBox[{"{", "len10k", "}"}]}], "]"}]}], ";"}], "\[IndentingNewLine]", RowBox[{ RowBox[{"ff10k", "=", RowBox[{"{", "}"}]}], ";"}], "\[IndentingNewLine]", RowBox[{"t10k", "=", RowBox[{ RowBox[{"First", "[", RowBox[{"Timing", "[", RowBox[{ RowBox[{"Do", "[", RowBox[{ RowBox[{"ff10k", "=", RowBox[{"treeInsert", "[", RowBox[{"ff10k", ",", RowBox[{"ee10k", "[", RowBox[{"[", "j", "]"}], "]"}]}], "]"}]}], ",", RowBox[{"{", RowBox[{"j", ",", "len10k"}], "}"}]}], "]"}], ";"}], "]"}], "]"}], "/", "Second"}]}], "\[IndentingNewLine]", RowBox[{ RowBox[{"gg10k", "=", RowBox[{"Flatten", "[", "ff10k", "]"}]}], ";"}], "\[IndentingNewLine]", RowBox[{"gg10k", "===", RowBox[{"Sort", "[", "ee10k", "]"}]}]}], "Input",ExpressionUUID->"f38b135f-\ 538b-47e6-bcaa-5e8d192c1ce8"], Cell[BoxData["24.530000000000015`"], "Output",ExpressionUUID->"0c366671-1671-428e-a1c0-064a5f730f89"], Cell[BoxData["True"], "Output",ExpressionUUID->"b419eabe-1ee0-4380-8d7b-8eb718103bb6"] }, 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",ExpressionUUID->"cfed18a4-4c40-47ff-855b-33e2241f9484"], Cell[CellGroupData[{ Cell[BoxData[ RowBox[{"{", RowBox[{ RowBox[{ RowBox[{"(", RowBox[{"t5k", "/", "t1k"}], ")"}], " ", "/", " ", "\[IndentingNewLine]", RowBox[{"(", RowBox[{"5000.", "*", RowBox[{ RowBox[{"Log", "[", "5000.", "]"}], "/", RowBox[{"(", RowBox[{"1000.", "*", RowBox[{"Log", "[", "1000.", "]"}]}], ")"}]}]}], ")"}]}], ",", "\[IndentingNewLine]", RowBox[{ RowBox[{"(", RowBox[{"t10k", "/", "t1k"}], ")"}], " ", "/", " ", "\[IndentingNewLine]", RowBox[{"(", RowBox[{"10000.", "*", RowBox[{ RowBox[{"Log", "[", "10000.", "]"}], "/", RowBox[{"(", RowBox[{"1000.", "*", RowBox[{"Log", "[", "1000.", "]"}]}], ")"}]}]}], ")"}]}], ",", "\[IndentingNewLine]", RowBox[{ RowBox[{"(", RowBox[{"t10k", "/", "t5k"}], ")"}], " ", "/", "\[IndentingNewLine]", RowBox[{"(", RowBox[{"10000.", "*", RowBox[{ RowBox[{"Log", "[", "10000.", "]"}], "/", RowBox[{"(", RowBox[{"5000.", "*", RowBox[{"Log", "[", "5000.", "]"}]}], ")"}]}]}], ")"}]}]}], "}"}]], "Input",ExpressionUUID->"357656d7-0ab7-478f-940f-3adf886502c5"], Cell[BoxData[ RowBox[{"{", RowBox[{ "1.2070752289694655`", ",", "1.1946428571428638`", ",", "0.9897004167360672`"}], "}"}]], "Output",ExpressionUUID->"63b38f00-23fa-\ 42c1-a922-dbf5e98af278"] }, 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",ExpressionUUID->"6605b97f-3dca-40f8-964c-a607b6b12f24"] }, Open ]], Cell[CellGroupData[{ Cell["Bitvectors", "Subsection",ExpressionUUID->"ce591594-df91-4c56-bee1-6fde1a53f04a"], 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[ RowBox[{ SuperscriptBox["2", "n"], "-", "1"}]],ExpressionUUID-> "f0441f72-974c-41f1-9cea-079421f5423d"], ". 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",ExpressionUUID->"eed4cdd5-722f-4ade-ab44-55c79cf12ae8"], Cell[TextData[{ "For example, say we have a set of 100 elements. We will use integers in the \ range from 0 to ", Cell[BoxData[ RowBox[{ SuperscriptBox["2", "100"], "-", "1"}]],ExpressionUUID-> "46a1a780-f7ba-4d6b-8dba-36dc636d5119"], " 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 strictly \ fewer than 128 elements, but this is still okay for the examples below." }], "Text",ExpressionUUID->"3d767d8c-6904-415d-8a3b-6c3aec306ddb"], Cell[BoxData[ RowBox[{ RowBox[{"k", "=", "100"}], ";", RowBox[{"len", "=", "128"}], ";", RowBox[{"subs", "=", RowBox[{"Union", "[", RowBox[{"Table", "[", RowBox[{ RowBox[{"Random", "[", RowBox[{"Integer", ",", RowBox[{"{", RowBox[{"0", ",", RowBox[{ SuperscriptBox["2", "k"], "-", "1"}]}], "}"}]}], "]"}], ",", RowBox[{"{", "len", "}"}]}], "]"}], "]"}]}], ";"}]], "Input",ExpressionU\ UID->"d6d8f3ee-57e1-46f8-89a2-b0c647e57a8e"], 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",ExpressionUUID->"fa8d9226-1c34-446e-84d6-9d0f0ef1441e"], Cell[BoxData[ RowBox[{ RowBox[{"masks", "=", RowBox[{"Table", "[", RowBox[{ SuperscriptBox["2", "m"], ",", RowBox[{"{", RowBox[{"m", ",", "0", ",", RowBox[{"k", "-", "1"}]}], "}"}]}], "]"}]}], ";", RowBox[{"k", "=."}]}]], "Input",ExpressionUUID->"b1248fb4-6985-45f3-9701-\ 8a5ed8e38b9c"], 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",ExpressionUUID->"92a52676-ad23-4c94-bb99-6b27b10335a2"], Cell[CellGroupData[{ Cell[BoxData[{ RowBox[{ RowBox[{ RowBox[{"func", " ", "=", " ", RowBox[{ RowBox[{"BitAnd", "[", RowBox[{ RowBox[{"masks", "[", RowBox[{"[", "3", "]"}], "]"}], ",", "#"}], "]"}], "&"}]}], ";"}], "\n"}], "\n", RowBox[{"Count", "[", RowBox[{ RowBox[{"Map", "[", RowBox[{"func", ",", " ", "subs"}], "]"}], ",", " ", RowBox[{"_", "?", "Positive"}]}], "]"}]}], "Input",ExpressionUUID->\ "4ddd0058-0db6-4761-9d32-68e55287245d"], Cell[BoxData["70"], "Output",ExpressionUUID->"2337f686-7987-432f-a26a-1e64ac53dca2"] }, 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",ExpressionUUID->"91d14620-9d27-41bc-8c43-670404b362eb"], Cell[CellGroupData[{ Cell[BoxData[{ RowBox[{ RowBox[{"func2", " ", "=", " ", RowBox[{ RowBox[{"BitAnd", "[", RowBox[{ RowBox[{ RowBox[{"masks", "[", RowBox[{"[", "6", "]"}], "]"}], "+", RowBox[{"masks", "[", RowBox[{"[", "11", "]"}], "]"}], "+", RowBox[{"masks", "[", RowBox[{"[", "14", "]"}], "]"}]}], ",", " ", "#"}], "]"}], "&"}]}], ";"}], "\n", RowBox[{ RowBox[{ RowBox[{"criterion", " ", "=", " ", RowBox[{ RowBox[{"(", RowBox[{"#", "==", RowBox[{ RowBox[{"masks", "[", RowBox[{"[", "6", "]"}], "]"}], "+", RowBox[{"masks", "[", RowBox[{"[", "11", "]"}], "]"}]}]}], ")"}], "&"}]}], ";"}], "\n"}], "\n", RowBox[{"Count", "[", RowBox[{ RowBox[{"Map", "[", RowBox[{"func2", ",", " ", "subs"}], "]"}], ",", " ", RowBox[{"_", "?", "criterion"}]}], "]"}]}], "Input",ExpressionUUID->\ "0e2fa46d-0798-464e-941d-88b7fc7aaf37"], Cell[BoxData["11"], "Output",ExpressionUUID->"a508fd3f-9fee-4d78-9d32-46c467b5e388"] }, 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",ExpressionUUID->"02076379-e280-4e4b-8b3c-0c6c8a44477c"], Cell[BoxData[ RowBox[{ RowBox[{"func3", " ", "=", " ", RowBox[{ RowBox[{"BitAnd", "[", RowBox[{ RowBox[{ RowBox[{"masks", "[", RowBox[{"[", "4", "]"}], "]"}], "+", RowBox[{"masks", "[", RowBox[{"[", "10", "]"}], "]"}], "+", RowBox[{"masks", "[", RowBox[{"[", "28", "]"}], "]"}], "+", RowBox[{"masks", "[", RowBox[{"[", "51", "]"}], "]"}]}], ",", "#"}], "]"}], "&"}]}], ";"}]], "Input",ExpressionUUID->"6df84c5f-fb5f-4e2f-bee1-7bd7acb01bd5"], 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",ExpressionUUID->"90a3a831-342c-4c00-9cbd-242770752f51"], Cell[CellGroupData[{ Cell[BoxData[ RowBox[{"Count", "[", RowBox[{ RowBox[{"Map", "[", RowBox[{"func3", ",", " ", "subs"}], "]"}], ",", " ", RowBox[{"_", "?", RowBox[{"(", RowBox[{ RowBox[{ RowBox[{"DigitCount", "[", RowBox[{"#", ",", "2", ",", "1"}], "]"}], ">=", "2"}], "&"}], ")"}]}]}], "]"}]], "Input",ExpressionUUID->"902674c3-b7b5-4c50-9a30-\ d9cd563aa307"], Cell[BoxData["79"], "Output",ExpressionUUID->"8818f1c1-e363-41a9-ba8f-32b503cdb2c7"] }, 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",ExpressionUUID->"fdc11141-1b25-40e5-9c97-97acd951b892"], Cell[BoxData[{ RowBox[{ RowBox[{"bitUnion", "[", RowBox[{"a_", ",", "b_"}], "]"}], ":=", RowBox[{"BitOr", "[", RowBox[{"a", ",", "b"}], "]"}]}], "\[IndentingNewLine]", RowBox[{ RowBox[{"bitIntersection", "[", RowBox[{"a_", ",", "b_"}], "]"}], ":=", RowBox[{"BitAnd", "[", RowBox[{"a", ",", "b"}], "]"}]}], "\[IndentingNewLine]", RowBox[{ RowBox[{"bitComplement", "[", RowBox[{"a_", ",", "b_"}], "]"}], ":=", RowBox[{"BitAnd", "[", RowBox[{"a", ",", RowBox[{"BitNot", "[", "b", "]"}]}], "]"}]}]}], "Input",ExpressionUUID->\ "8fd69ada-12d2-4348-892b-9a517dc4fcc7"], Cell[CellGroupData[{ Cell["Application: working with a matrix modulo 2", "Subsubsection", CellDingbat->None,ExpressionUUID->"b95bea28-8769-4f5e-ae5f-1af377ad5fcc"], 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",ExpressionUUID->"7cd0f306-7252-4b13-9995-dfd707d3c7dc"], 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",ExpressionUUID->"39a5e289-c0f6-4b19-84cc-21692226de2c"], Cell[BoxData[{ RowBox[{ RowBox[{"len", "=", "400"}], ";"}], "\[IndentingNewLine]", RowBox[{ RowBox[{"ncols", "=", "390"}], ";"}], "\[IndentingNewLine]", RowBox[{ RowBox[{"SeedRandom", "[", "1111", "]"}], ";"}], "\[IndentingNewLine]", RowBox[{ RowBox[{"mat", " ", "=", " ", "\[IndentingNewLine]", RowBox[{"Table", "[", RowBox[{ RowBox[{"Random", "[", "Integer", "]"}], ",", RowBox[{"{", "len", "}"}], ",", " ", RowBox[{"{", "ncols", "}"}]}], "]"}]}], ";"}], "\[IndentingNewLine]", RowBox[{ RowBox[{"augmat", " ", "=", " ", RowBox[{"Transpose", "[", RowBox[{"Join", "[", RowBox[{ RowBox[{"Transpose", "[", "mat", "]"}], ",", " ", RowBox[{"IdentityMatrix", "[", "len", "]"}]}], "]"}], "]"}]}], ";"}]}], "Input",ExpressionUUID->"e201ad8a-c789-4521-a0f9-6319f0d89bdd"], 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",ExpressionUUID->"8fcc7e56-ae5e-4fa2-881c-852f57e0990d"], Cell[CellGroupData[{ Cell[BoxData[{ RowBox[{"Timing", "[", RowBox[{ RowBox[{"rows", "=", RowBox[{"RowReduce", "[", RowBox[{"augmat", ",", RowBox[{"Modulus", "\[Rule]", "2"}]}], "]"}]}], ";"}], "]"}], "\[IndentingNewLine]", RowBox[{ RowBox[{"first", "=", RowBox[{"Take", "[", RowBox[{ RowBox[{"rows", "[", RowBox[{"[", "len", "]"}], "]"}], ",", "ncols"}], "]"}]}], ";"}], "\[IndentingNewLine]", RowBox[{"Max", "[", "first", "]"}], "\[IndentingNewLine]", RowBox[{ RowBox[{"last", "=", RowBox[{"Drop", "[", RowBox[{ RowBox[{"rows", "[", RowBox[{"[", "len", "]"}], "]"}], ",", "ncols"}], "]"}]}], ";"}], "\[IndentingNewLine]", RowBox[{"Max", "[", RowBox[{"Mod", "[", RowBox[{ RowBox[{"last", ".", "mat"}], ",", "2"}], "]"}], "]"}]}], "Input",Expressi\ onUUID->"9417c1da-0a67-4fdc-ae6a-ce6d9f52b796"], Cell[BoxData[ RowBox[{"{", RowBox[{ RowBox[{"17.8`", " ", "Second"}], ",", "Null"}], "}"}]], "Output",Expressio\ nUUID->"38b2f2ff-4558-4906-9d56-d5d66a8d3738"], Cell[BoxData["0"], "Output",ExpressionUUID->"e21c4140-53a1-4028-b8fa-edd13bc4afa3"], Cell[BoxData["0"], "Output",ExpressionUUID->"c61fcda2-6c8b-4162-bbbe-d891246f6a9a"] }, Open ]], Cell["Let us compare to finding a null space directly.", "Text",ExpressionUUID->"66d93bda-f9de-4a4c-847d-990626848d47"], Cell[CellGroupData[{ Cell[BoxData[{ RowBox[{"Timing", "[", RowBox[{ RowBox[{"nulls", "=", RowBox[{"NullSpace", "[", RowBox[{ RowBox[{"Transpose", "[", "mat", "]"}], ",", RowBox[{"Modulus", "\[Rule]", "2"}]}], "]"}]}], ";"}], "]"}], "\[IndentingNewLine]", RowBox[{"Max", "[", RowBox[{"Mod", "[", RowBox[{ RowBox[{ RowBox[{"nulls", "[", RowBox[{"[", "1", "]"}], "]"}], ".", "mat"}], ",", "2"}], "]"}], "]"}]}], "Input",ExpressionUUID->"900462d3-1370-416e-8056-3f2c53933b64"], Cell[BoxData[ RowBox[{"{", RowBox[{ RowBox[{"5.890000000000001`", " ", "Second"}], ",", "Null"}], "}"}]], "Output",ExpressionUUID->"cb31cb9a-2ebb-458c-9921-76e369367a53"], Cell[BoxData["0"], "Output",ExpressionUUID->"ea5e526c-f102-4671-a359-3d3603bc644e"] }, 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",ExpressionUUID->"3f67a73b-5a17-4ef0-b691-c0428b05df3a"], Cell["\<\ Below is code to implement this matrix triangulation method using bitvectors.\ \ \>", "Text",ExpressionUUID->"a7fbddbc-1bb5-4adb-8f60-d820f9d72f9d"], Cell[BoxData[{ RowBox[{ RowBox[{"getMaxPos", "[", RowBox[{"mat_", ",", "j_"}], "]"}], ":=", RowBox[{"Module", "[", RowBox[{ RowBox[{"{", RowBox[{ RowBox[{"big", "=", RowBox[{"Developer`BitLength", "[", RowBox[{"mat", "[", RowBox[{"[", "j", "]"}], "]"}], "]"}]}], ",", RowBox[{"indx", "=", "j"}], ",", RowBox[{"len", "=", RowBox[{"Length", "[", "mat", "]"}]}], ",", "nbits"}], "}"}], ",", RowBox[{ RowBox[{"Do", "[", RowBox[{ RowBox[{ RowBox[{"nbits", "=", RowBox[{"Developer`BitLength", "[", RowBox[{"mat", "[", RowBox[{"[", "k", "]"}], "]"}], "]"}]}], ";", "\[IndentingNewLine]", RowBox[{"If", "[", RowBox[{ RowBox[{"nbits", ">", "big"}], ",", RowBox[{ RowBox[{"big", "=", "nbits"}], ";", " ", RowBox[{"indx", "=", "k"}]}]}], "]"}]}], ",", RowBox[{"{", RowBox[{"k", ",", RowBox[{"j", "+", "1"}], ",", "len"}], "}"}]}], "]"}], ";", "\[IndentingNewLine]", "indx"}]}], "]"}]}], "\[IndentingNewLine]", RowBox[{ RowBox[{"getNullVec", "[", "mat_", "]"}], ":=", RowBox[{"Module", "[", RowBox[{ RowBox[{"{", RowBox[{ RowBox[{"len", "=", RowBox[{"Length", "[", "mat", "]"}]}], ",", RowBox[{"new", "=", "mat"}], ",", "j", ",", "k", ",", "indx", ",", "nbits", ",", "tmp1", ",", "tmp2", ",", "jth", ",", "kth", ",", "bigrow", ",", "blen", ",", "bigblen"}], "}"}], ",", RowBox[{ RowBox[{"bigrow", "=", RowBox[{"getMaxPos", "[", RowBox[{"new", ",", "1"}], "]"}]}], ";", "\[IndentingNewLine]", RowBox[{"tmp1", "=", RowBox[{"Do", "[", "\[IndentingNewLine]", RowBox[{ RowBox[{ RowBox[{"If", "[", RowBox[{ RowBox[{"j", "\[NotEqual]", "bigrow"}], ",", RowBox[{ RowBox[{"new", "[", RowBox[{"[", RowBox[{"{", RowBox[{"j", ",", "bigrow"}], "}"}], "]"}], "]"}], "=", RowBox[{"new", "[", RowBox[{"[", RowBox[{"{", RowBox[{"bigrow", ",", "j"}], "}"}], "]"}], "]"}]}]}], "]"}], ";", "\[IndentingNewLine]", RowBox[{"jth", "=", RowBox[{"new", "[", RowBox[{"[", "j", "]"}], "]"}]}], ";", "\[IndentingNewLine]", RowBox[{"nbits", "=", RowBox[{"Developer`BitLength", "[", "jth", "]"}]}], ";", "\[IndentingNewLine]", RowBox[{"bigblen", "=", "0"}], ";", "\[IndentingNewLine]", RowBox[{"tmp2", "=", RowBox[{"Do", "[", RowBox[{ RowBox[{ RowBox[{"kth", "=", RowBox[{"new", "[", RowBox[{"[", "k", "]"}], "]"}]}], ";", "\[IndentingNewLine]", RowBox[{"blen", "=", RowBox[{"Developer`BitLength", "[", "kth", "]"}]}], ";", "\[IndentingNewLine]", RowBox[{"If", "[", RowBox[{ RowBox[{"blen", "\[Equal]", "nbits"}], ",", RowBox[{ RowBox[{"kth", "=", RowBox[{"BitXor", "[", RowBox[{"kth", ",", "jth"}], "]"}]}], ";", "\[IndentingNewLine]", RowBox[{"blen", "=", RowBox[{"Developer`BitLength", "[", "kth", "]"}]}], ";", "\[IndentingNewLine]", RowBox[{"If", "[", RowBox[{ RowBox[{"blen", "\[LessEqual]", "len"}], ",", RowBox[{"Return", "[", RowBox[{"IntegerDigits", "[", RowBox[{"kth", ",", "2", ",", "len"}], "]"}], "]"}]}], "]"}], ";", "\[IndentingNewLine]", RowBox[{ RowBox[{"new", "[", RowBox[{"[", "k", "]"}], "]"}], "=", "kth"}], ";"}]}], "]"}], ";", "\[IndentingNewLine]", RowBox[{"If", "[", RowBox[{ RowBox[{"blen", ">", "bigblen"}], ",", RowBox[{ RowBox[{"bigrow", "=", "k"}], ";", " ", RowBox[{"bigblen", "=", "blen"}]}]}], "]"}]}], ",", RowBox[{"{", RowBox[{"k", ",", RowBox[{"j", "+", "1"}], ",", "len"}], "}"}]}], "]"}]}], ";", "\[IndentingNewLine]", RowBox[{"If", "[", RowBox[{ RowBox[{"tmp2", "=!=", "Null"}], ",", RowBox[{"Return", "[", "tmp2", "]"}]}], "]"}]}], ",", RowBox[{"{", RowBox[{"j", ",", "1", ",", "len"}], "}"}]}], "]"}]}], ";", "\[IndentingNewLine]", "tmp1"}]}], "]"}]}]}], "Input",ExpressionUUID->\ "3717a256-ea57-4cad-bf03-11eda1501051"], Cell["\<\ We illustrate on the example above. We must first translate the matrix to a \ list of bitvectors (nonnegative integers).\ \>", "Text",ExpressionUUID->"168b9d14-9190-4ac2-94ff-f50e84d77be9"], Cell[BoxData[{ RowBox[{ RowBox[{"zerovec", "=", RowBox[{"Table", "[", RowBox[{"0", ",", RowBox[{"{", "len", "}"}]}], "]"}]}], ";"}], "\[IndentingNewLine]", RowBox[{ RowBox[{"SeedRandom", "[", "1111", "]"}], ";"}], "\[IndentingNewLine]", RowBox[{ RowBox[{"numvec1", "=", RowBox[{"Table", "[", RowBox[{ RowBox[{ RowBox[{"ii", "=", RowBox[{"Table", "[", RowBox[{ RowBox[{"Random", "[", "Integer", "]"}], ",", RowBox[{"{", "ncols", "}"}]}], "]"}]}], ";", "\[IndentingNewLine]", RowBox[{"augvec", "=", "zerovec"}], ";", "\[IndentingNewLine]", RowBox[{ RowBox[{"augvec", "[", RowBox[{"[", "j", "]"}], "]"}], "=", "1"}], ";", "\[IndentingNewLine]", RowBox[{"FromDigits", "[", RowBox[{ RowBox[{"Join", "[", RowBox[{"ii", ",", "augvec"}], "]"}], ",", "2"}], "]"}]}], ",", "\[IndentingNewLine]", RowBox[{"{", RowBox[{"j", ",", "len"}], "}"}]}], "]"}]}], ";"}]}], "Input",Expression\ UUID->"f5353b57-8b33-4535-b8e8-0c67cc270678"], Cell["\<\ Now we obtain a null vector for this matrix and check that it is indeed such.\ \ \>", "Text",ExpressionUUID->"dd8ad44c-06e3-4007-bdcd-07bf3858064e"], Cell[CellGroupData[{ Cell[BoxData[{ RowBox[{"Timing", "[", RowBox[{ RowBox[{"nullvec", "=", RowBox[{"getNullVec", "[", "numvec1", "]"}]}], ";"}], "]"}], "\[IndentingNewLine]", RowBox[{"Max", "[", RowBox[{"Mod", "[", RowBox[{ RowBox[{"nullvec", ".", "mat"}], ",", "2"}], "]"}], "]"}]}], "Input",Expre\ ssionUUID->"4fcd14de-c322-4321-a324-6fff6728d9fe"], Cell[BoxData[ RowBox[{"{", RowBox[{ RowBox[{"8.049999999999997`", " ", "Second"}], ",", "Null"}], "}"}]], "Output",ExpressionUUID->"e0ad5d75-566d-461d-b2a6-f95e3cc9b182"], Cell[BoxData["0"], "Output",ExpressionUUID->"2d810952-046c-454b-bc66-aa99bc0c5317"] }, 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[ FormBox[ SuperscriptBox["n", "3"], TraditionalForm]],ExpressionUUID-> "f5c1758a-d12d-4c3d-bfe5-1ce1883491a8"], ") complexity algorithms. In contrast, for inputs in the size range up to \ several thousands, the bitvector formulation is only O(", Cell[BoxData[ FormBox[ SuperscriptBox["n", "2"], TraditionalForm]],ExpressionUUID-> "83e136cd-d8ce-40b2-9934-df8e1ab7248c"], "). 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",ExpressionUUID->"0c380d6f-15a8-41da-bb30-5c487bbdf847"], Cell[BoxData[{ RowBox[{ RowBox[{"len", "=", "1600"}], ";"}], "\[IndentingNewLine]", RowBox[{ RowBox[{"ncols", "=", "1560"}], ";"}], "\[IndentingNewLine]", RowBox[{ RowBox[{"SeedRandom", "[", "1111", "]"}], ";"}], "\[IndentingNewLine]", RowBox[{ RowBox[{"mat", " ", "=", " ", "\[IndentingNewLine]", RowBox[{"Table", "[", RowBox[{ RowBox[{"Random", "[", "Integer", "]"}], ",", RowBox[{"{", "len", "}"}], ",", " ", RowBox[{"{", "ncols", "}"}]}], "]"}]}], ";"}], "\[IndentingNewLine]", RowBox[{ RowBox[{"augmat", " ", "=", " ", RowBox[{"Transpose", "[", RowBox[{"Join", "[", RowBox[{ RowBox[{"Transpose", "[", "mat", "]"}], ",", " ", RowBox[{"IdentityMatrix", "[", "len", "]"}]}], "]"}], "]"}]}], ";"}]}], "Input",ExpressionUUID->"44e55627-cc30-4f33-86dc-c35c9f42d5f9"], Cell[BoxData[{ RowBox[{ RowBox[{"zerovec", "=", RowBox[{"Table", "[", RowBox[{"0", ",", RowBox[{"{", "len", "}"}]}], "]"}]}], ";"}], "\[IndentingNewLine]", RowBox[{ RowBox[{"SeedRandom", "[", "1111", "]"}], ";"}], "\[IndentingNewLine]", RowBox[{ RowBox[{"numvec1", "=", RowBox[{"Table", "[", RowBox[{ RowBox[{ RowBox[{"ii", "=", RowBox[{"Table", "[", RowBox[{ RowBox[{"Random", "[", "Integer", "]"}], ",", RowBox[{"{", "ncols", "}"}]}], "]"}]}], ";", "\[IndentingNewLine]", RowBox[{"augvec", "=", "zerovec"}], ";", "\[IndentingNewLine]", RowBox[{ RowBox[{"augvec", "[", RowBox[{"[", "j", "]"}], "]"}], "=", "1"}], ";", "\[IndentingNewLine]", RowBox[{"FromDigits", "[", RowBox[{ RowBox[{"Join", "[", RowBox[{"ii", ",", "augvec"}], "]"}], ",", "2"}], "]"}]}], ",", "\[IndentingNewLine]", RowBox[{"{", RowBox[{"j", ",", "len"}], "}"}]}], "]"}]}], ";"}]}], "Input",Expression\ UUID->"11c2b2ef-a55a-498e-8e81-ad9992646b08"], Cell[CellGroupData[{ Cell[BoxData[{ RowBox[{"Timing", "[", RowBox[{ RowBox[{"nulls", "=", RowBox[{"NullSpace", "[", RowBox[{ RowBox[{"Transpose", "[", "mat", "]"}], ",", RowBox[{"Modulus", "\[Rule]", "2"}]}], "]"}]}], ";"}], "]"}], "\[IndentingNewLine]", RowBox[{"Max", "[", RowBox[{"Mod", "[", RowBox[{ RowBox[{ RowBox[{"nulls", "[", RowBox[{"[", "1", "]"}], "]"}], ".", "mat"}], ",", "2"}], "]"}], "]"}]}], "Input",ExpressionUUID->"17bc87ee-35e0-4a3f-bb3b-8482222b1781"], Cell[BoxData[ RowBox[{"{", RowBox[{ RowBox[{"341.03`", " ", "Second"}], ",", "Null"}], "}"}]], "Output",Express\ ionUUID->"7b6ae8b9-c3cc-4dff-b38d-c1ae22698a28"], Cell[BoxData["0"], "Output",ExpressionUUID->"b9e45fc3-1c6c-4043-9f00-d2132e83a289"] }, Open ]], Cell[CellGroupData[{ Cell[BoxData[{ RowBox[{"Timing", "[", RowBox[{ RowBox[{"nullvec", "=", RowBox[{"getNullVec", "[", "numvec1", "]"}]}], ";"}], "]"}], "\[IndentingNewLine]", RowBox[{"Max", "[", RowBox[{"Mod", "[", RowBox[{ RowBox[{"nullvec", ".", "mat"}], ",", "2"}], "]"}], "]"}]}], "Input",Expre\ ssionUUID->"420c04d1-d725-4e81-9242-d240635ab350"], Cell[BoxData[ RowBox[{"{", RowBox[{ RowBox[{"131.16000000000003`", " ", "Second"}], ",", "Null"}], "}"}]], "Output",ExpressionUUID->"f0c854a6-d7b4-4067-955c-a7e4a70cf8a1"], Cell[BoxData["0"], "Output",ExpressionUUID->"1d5037c0-e9fc-45f2-a9aa-fa0f237f7bc1"] }, 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",ExpressionUUID->"d1178cfb-d726-4962-ae93-bd016f746115"] }, Open ]] }, Open ]], Cell[CellGroupData[{ Cell["Tree application: A rudimentary parser", "Subsection",ExpressionUUID->"28e4fd38-2274-4a57-aac1-2ba5b7ea9fbe"], 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",ExpressionUUID->"9f4c24ca-dfa1-4f3e-9e4e-123967020d2e"], 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",ExpressionUUID->"f39a522a-4109-4ff2-8779-b4e15837e11e"], Cell[BoxData[{ RowBox[{ RowBox[{"NIL", "=", "\"\<\>\""}], ";"}], "\[IndentingNewLine]", RowBox[{"sentence", ":=", RowBox[{"Hold", "[", RowBox[{"Or", "[", RowBox[{"declarative", ",", "interrogative", ",", "imperative"}], "]"}], "]"}]}], "\[IndentingNewLine]", RowBox[{"declarative", ":=", RowBox[{"{", RowBox[{"subject", ",", "predicatepast"}], "}"}]}], "\[IndentingNewLine]", RowBox[{"interrogative", ":=", RowBox[{"{", RowBox[{"qverb", ",", "subject", ",", "predicatepresent"}], "}"}]}], "\[IndentingNewLine]", RowBox[{"imperative", ":=", RowBox[{"{", RowBox[{"actverb", ",", "subject"}], "}"}]}], "\[IndentingNewLine]", RowBox[{"subject", ":=", RowBox[{"Hold", "[", RowBox[{"nounclause", "||", RowBox[{"{", RowBox[{"nounclause", ",", "prepositionclause"}], "}"}]}], "]"}]}], "\[IndentingNewLine]", RowBox[{"nounclause", ":=", RowBox[{"Hold", "[", RowBox[{"{", RowBox[{"adjectiveclause", ",", "noun"}], "}"}], "]"}]}], "\[IndentingNewLine]", RowBox[{"noun", ":=", RowBox[{"Or", "[", RowBox[{ "\"\\"", ",", "\"\\"", ",", "\"\\"", ",", "\"\\"", ",", "\"\\"", ",", "\"\\"", ",", "\"\\"", ",", "\"\\"", ",", "\"\\"", ",", "\"\\"", ",", "\"\\"", ",", "\"\\"", ",", "\"\\"", ",", "\"\\""}], "]"}]}], "\[IndentingNewLine]", RowBox[{"adjectiveclause", ":=", RowBox[{"{", RowBox[{"article", ",", "adjectivelist"}], "}"}]}], "\[IndentingNewLine]", RowBox[{"adjectivelist", ":=", RowBox[{"Hold", "[", RowBox[{"myOr", "[", RowBox[{".6", ",", RowBox[{"Hold", "[", RowBox[{ RowBox[{"tmpadjlist", "=", "adjective"}], ";", " ", "NIL"}], "]"}], ",", RowBox[{"Hold", "[", RowBox[{"With", "[", RowBox[{ RowBox[{"{", RowBox[{"tmp", "=", RowBox[{"randomPart", "[", "tmpadjlist", "]"}]}], "}"}], ",", RowBox[{ RowBox[{"tmpadjlist", "=", RowBox[{"Complement", "[", RowBox[{"tmpadjlist", ",", RowBox[{"Unevaluated", "[", RowBox[{"Or", "[", "tmp", "]"}], "]"}]}], "]"}]}], ";", "\[IndentingNewLine]", RowBox[{"{", RowBox[{"tmp", ",", "adjectivelist"}], "}"}]}]}], "]"}], "]"}]}], "]"}], "]"}]}], "\[IndentingNewLine]", RowBox[{"article", ":=", RowBox[{"Or", "[", RowBox[{ "\"\\"", ",", "\"\\"", ",", "\"\\"", ",", "\"\\""}], "]"}]}], "\[IndentingNewLine]", RowBox[{"adjective", ":=", RowBox[{"Or", "[", RowBox[{ "\"\\"", ",", "\"\\"", ",", "\"\\"", ",", "\"\\"", ",", "\"\\"", ",", "\"\\"", ",", "\"\\"", ",", "\"\\"", ",", "\"\\"", ",", "\"\\"", ",", "\"\\"", ",", "\"\\"", ",", " ", "\"\\"", ",", " ", "\"\\""}], "]"}]}], "\[IndentingNewLine]", RowBox[{ RowBox[{"tmpadjlist", "=", "adjective"}], ";"}], "\[IndentingNewLine]", RowBox[{"prepositionclause", ":=", RowBox[{"{", RowBox[{"preposition", ",", "nounclause"}], "}"}]}], "\[IndentingNewLine]", RowBox[{"preposition", ":=", RowBox[{"Or", "[", RowBox[{ "\"\\"", ",", "\"\\"", ",", "\"\\"", ",", "\"\\"", ",", "\"\\"", ",", "\"\\"", ",", "\"\\""}], "]"}]}], "\[IndentingNewLine]", RowBox[{"predicatepresent", ":=", RowBox[{"{", RowBox[{"verbpresent", ",", "subject"}], "}"}]}], "\[IndentingNewLine]", RowBox[{"predicatepast", ":=", RowBox[{"{", RowBox[{"verbclause", ",", "subject"}], "}"}]}], "\[IndentingNewLine]", RowBox[{"verbclause", ":=", RowBox[{"Hold", "[", RowBox[{"{", RowBox[{"adverblist", ",", "verbpast"}], "}"}], "]"}]}], "\[IndentingNewLine]", RowBox[{"adverblist", ":=", RowBox[{"Hold", "[", RowBox[{"myOr", "[", RowBox[{".8", ",", RowBox[{"Hold", "[", RowBox[{ RowBox[{"tmpadvlist", "=", "adverb"}], ";", " ", "NIL"}], "]"}], ",", RowBox[{"Hold", "[", RowBox[{"With", "[", RowBox[{ RowBox[{"{", RowBox[{"tmp", "=", RowBox[{"randomPart", "[", "tmpadvlist", "]"}]}], "}"}], ",", RowBox[{ RowBox[{"tmpadvlist", "=", RowBox[{"Complement", "[", RowBox[{"tmpadvlist", ",", RowBox[{"Unevaluated", "[", RowBox[{"Or", "[", "tmp", "]"}], "]"}]}], "]"}]}], ";", "\[IndentingNewLine]", RowBox[{"{", RowBox[{"tmp", ",", "adverblist"}], "}"}]}]}], "]"}], "]"}]}], "]"}], "]"}]}], "\[IndentingNewLine]", RowBox[{"adverb", ":=", RowBox[{"Or", "[", RowBox[{ "\"\\"", ",", "\"\\"", ",", "\"\\"", ",", "\"\\"", ",", "\"\\"", ",", "\"\\""}], "]"}]}], "\[IndentingNewLine]", RowBox[{ RowBox[{"tmpadvlist", "=", "adverb"}], ";"}], "\[IndentingNewLine]", RowBox[{"verbpast", ":=", RowBox[{"Or", "[", RowBox[{ "\"\\"", ",", "\"\\"", ",", "\"\\"", ",", "\"\\"", ",", "\"\\"", ",", "\"\\"", ",", "\"\\"", ",", "\"\\""}], "]"}]}], "\[IndentingNewLine]", RowBox[{"verbpresent", ":=", RowBox[{"Or", "[", RowBox[{ "\"\\"", ",", "\"\\"", ",", "\"\\"", ",", "\"\\"", ",", "\"\\"", ",", "\"\\"", ",", "\"\\"", ",", "\"\\"", ",", "\"\\""}], "]"}]}], "\[IndentingNewLine]", RowBox[{"qverb", ":=", RowBox[{"Or", "[", RowBox[{ "\"\\"", ",", "\"\\"", ",", "\"\\"", ",", "\"\\""}], "]"}]}], "\[IndentingNewLine]", RowBox[{"actverb", ":=", RowBox[{"Or", "[", RowBox[{ "\"\\"", ",", "\"\\"", ",", "\"\\"", ",", "\"\\"", ",", "\"\\""}], "]"}]}]}], "Input",ExpressionUU\ ID->"2fd8de01-ed78-4177-a12b-7e626540595d"], Cell["\<\ Now generate random sentences from that grammar. We also provide a means to \ format the results.\ \>", "Text",ExpressionUUID->"b7d3e7b0-fdf5-484b-854f-f21cac9d04d1"], Cell[BoxData[{ RowBox[{ RowBox[{"randomPart", "[", "type_", "]"}], ":=", RowBox[{"Switch", "[", RowBox[{ RowBox[{"Head", "[", "type", "]"}], ",", "Hold", ",", RowBox[{"randomPart", "[", RowBox[{"type", "[", RowBox[{"[", "1", "]"}], "]"}], "]"}], ",", "String", ",", "type", ",", "List", ",", RowBox[{"If", "[", RowBox[{ RowBox[{ RowBox[{"Length", "[", "type", "]"}], "\[Equal]", "0"}], ",", "\"\<\>\"", ",", RowBox[{"Flatten", "[", RowBox[{"Map", "[", RowBox[{"randomPart", ",", "type"}], "]"}], "]"}]}], "]"}], ",", "myOr", ",", RowBox[{"With", "[", RowBox[{ RowBox[{"{", RowBox[{"rnd", "=", RowBox[{"Random", "[", "]"}]}], "}"}], ",", RowBox[{"randomPart", "[", RowBox[{"If", "[", RowBox[{ RowBox[{"rnd", "<", RowBox[{"type", "[", RowBox[{"[", "1", "]"}], "]"}]}], ",", RowBox[{"type", "[", RowBox[{"[", "2", "]"}], "]"}], ",", RowBox[{"type", "[", RowBox[{"[", "3", "]"}], "]"}]}], "]"}], "]"}]}], "]"}], ",", "Or", ",", RowBox[{"randomPart", "[", RowBox[{"type", "[", RowBox[{"[", RowBox[{"Random", "[", RowBox[{"Integer", ",", RowBox[{"{", RowBox[{"1", ",", RowBox[{"Length", "[", "type", "]"}]}], "}"}]}], "]"}], "]"}], "]"}], "]"}]}], "]"}]}], "\[IndentingNewLine]", RowBox[{ RowBox[{"randomSentence", "[", "]"}], ":=", RowBox[{"Apply", "[", RowBox[{"sentenceType", ",", RowBox[{ RowBox[{"randomPart", "[", "sentence", "]"}], "/.", RowBox[{"\"\<\>\"", "\[Rule]", RowBox[{"Sequence", "[", "]"}]}]}]}], "]"}]}], "\[IndentingNewLine]", RowBox[{ RowBox[{"isQ", "[", RowBox[{"type_", ",", "a_"}], "]"}], ":=", RowBox[{"MemberQ", "[", RowBox[{"type", ",", "a"}], "]"}]}], "\[IndentingNewLine]", RowBox[{ RowBox[{"Format", "[", "sentence_sentenceType", "]"}], ":=", RowBox[{"Module", "[", RowBox[{ RowBox[{"{", RowBox[{ RowBox[{"word", "=", RowBox[{"First", "[", "sentence", "]"}]}], ",", "words", ",", "punc"}], "}"}], ",", RowBox[{ RowBox[{"words", "=", RowBox[{"Map", "[", RowBox[{ RowBox[{ RowBox[{"StringJoin", "[", RowBox[{"#", ",", "\"\< \>\""}], "]"}], "&"}], ",", "sentence"}], "]"}]}], ";", "\[IndentingNewLine]", RowBox[{"punc", "=", RowBox[{"If", "[", RowBox[{ RowBox[{"isQ", "[", RowBox[{"qverb", ",", "word"}], "]"}], ",", "\"\\"", ",", RowBox[{"If", "[", RowBox[{ RowBox[{"isQ", "[", RowBox[{"actverb", ",", "word"}], "]"}], ",", "\"\\"", ",", "\"\<.\>\""}], "]"}]}], "]"}]}], ";", "\[IndentingNewLine]", RowBox[{ RowBox[{"words", "[", RowBox[{"[", RowBox[{"Length", "[", "words", "]"}], "]"}], "]"}], "=", RowBox[{"StringReplacePart", "[", RowBox[{ RowBox[{"Last", "[", "words", "]"}], ",", "punc", ",", RowBox[{"-", "1"}]}], "]"}]}], ";", "\[IndentingNewLine]", RowBox[{ RowBox[{"words", "[", RowBox[{"[", "1", "]"}], "]"}], "=", RowBox[{"StringReplacePart", "[", RowBox[{ RowBox[{"First", "[", "words", "]"}], ",", RowBox[{"ToUpperCase", "[", RowBox[{"StringTake", "[", RowBox[{ RowBox[{"First", "[", "words", "]"}], ",", "1"}], "]"}], "]"}], ",", "1"}], "]"}]}], ";", "\[IndentingNewLine]", RowBox[{"Apply", "[", RowBox[{"StringJoin", ",", "words"}], "]"}]}]}], "]"}]}]}], "Input",Expr\ essionUUID->"e4c3a427-102c-45cb-8263-7f8b262a290b"], 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",ExpressionUUID->"2d319ae0-0d27-442f-ab61-99641834be5c"], Cell[CellGroupData[{ Cell[BoxData[ RowBox[{ RowBox[{"Table", "[", RowBox[{ RowBox[{"randomSentence", "[", "]"}], ",", RowBox[{"{", "20", "}"}]}], "]"}], "//", "TableForm"}]], "Input",Expressio\ nUUID->"f0a46a96-2b11-4f87-b9f4-c2d5546421e6"], 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?\"\>"} }, GridBoxAlignment->{ "Columns" -> {{Left}}, "ColumnsIndexed" -> {}, "Rows" -> {{Baseline}}, "RowsIndexed" -> {}}, GridBoxSpacings->{"Columns" -> { Offset[0.27999999999999997`], { Offset[2.0999999999999996`]}, Offset[0.27999999999999997`]}, "ColumnsIndexed" -> {}, "Rows" -> { Offset[0.2], { Offset[0.4]}, Offset[0.2]}, "RowsIndexed" -> {}}], 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",ExpressionUUID->"5a68a069-0598-4053-983a-\ 8c7f4c0a802e"] }, 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",ExpressionUUID->"0c807d43-8cce-42f9-9afb-3996c8da43a7"], Cell[BoxData[{ RowBox[{ RowBox[{"getNextWord", "[", RowBox[{"{", "}"}], "]"}], ":=", "\"\<\>\""}], "\[IndentingNewLine]", RowBox[{ RowBox[{"getNextWord", "[", "a_", "]"}], ":=", RowBox[{"First", "[", "a", "]"}]}], "\[IndentingNewLine]", RowBox[{ RowBox[{"atomParse", "[", RowBox[{"hed_", ",", "a_"}], "]"}], ":=", RowBox[{"{", RowBox[{ RowBox[{"hed", "[", RowBox[{"getNextWord", "[", "a", "]"}], "]"}], ",", "1"}], "}"}]}], "\[IndentingNewLine]", RowBox[{ RowBox[{"sentenceParse", "[", "a_sentenceType", "]"}], ":=", RowBox[{"With", "[", RowBox[{ RowBox[{"{", RowBox[{"b", "=", RowBox[{"Apply", "[", RowBox[{"List", ",", "a"}], "]"}]}], "}"}], ",", RowBox[{"If", "[", RowBox[{ RowBox[{"isQ", "[", RowBox[{"qverb", ",", RowBox[{"First", "[", "b", "]"}]}], "]"}], ",", RowBox[{"interrogativeParse", "[", "b", "]"}], ",", RowBox[{"If", "[", RowBox[{ RowBox[{"isQ", "[", RowBox[{"actverb", ",", RowBox[{"First", "[", "b", "]"}]}], "]"}], ",", RowBox[{"imperativeParse", "[", "b", "]"}], ",", RowBox[{"declarativeParse", "[", "b", "]"}]}], "]"}]}], "]"}]}], "]"}]}], "\[IndentingNewLine]", RowBox[{ RowBox[{"declarativeParse", "[", "a_", "]"}], ":=", RowBox[{"Module", "[", RowBox[{ RowBox[{"{", RowBox[{ RowBox[{"b", "=", RowBox[{"subjectParse", "[", "a", "]"}]}], ",", "c"}], "}"}], ",", RowBox[{ RowBox[{"c", "=", RowBox[{"predicatepastParse", "[", RowBox[{"Drop", "[", RowBox[{"a", ",", RowBox[{"b", "[", RowBox[{"[", "2", "]"}], "]"}]}], "]"}], "]"}]}], ";", "\[IndentingNewLine]", RowBox[{"\"\\"", "[", RowBox[{ RowBox[{"b", "[", RowBox[{"[", "1", "]"}], "]"}], ",", RowBox[{"c", "[", RowBox[{"[", "1", "]"}], "]"}]}], "]"}]}]}], "]"}]}], "\[IndentingNewLine]", RowBox[{ RowBox[{"interrogativeParse", "[", "a_", "]"}], ":=", RowBox[{"Module", "[", RowBox[{ RowBox[{"{", RowBox[{ RowBox[{"b", "=", RowBox[{"atomParse", "[", RowBox[{"\"\\"", ",", "a"}], "]"}]}], ",", "c", ",", "d"}], "}"}], ",", RowBox[{ RowBox[{"c", "=", RowBox[{"subjectParse", "[", RowBox[{"Drop", "[", RowBox[{"a", ",", RowBox[{"b", "[", RowBox[{"[", "2", "]"}], "]"}]}], "]"}], "]"}]}], ";", "\[IndentingNewLine]", RowBox[{"d", "=", RowBox[{"predicatepresentParse", "[", RowBox[{"Drop", "[", RowBox[{"a", ",", RowBox[{ RowBox[{"b", "[", RowBox[{"[", "2", "]"}], "]"}], "+", RowBox[{"c", "[", RowBox[{"[", "2", "]"}], "]"}]}]}], "]"}], "]"}]}], ";", "\[IndentingNewLine]", RowBox[{"\"\\"", "[", RowBox[{ RowBox[{"b", "[", RowBox[{"[", "1", "]"}], "]"}], ",", RowBox[{"c", "[", RowBox[{"[", "1", "]"}], "]"}], ",", RowBox[{"d", "[", RowBox[{"[", "1", "]"}], "]"}]}], "]"}]}]}], "]"}]}], "\[IndentingNewLine]", RowBox[{ RowBox[{"imperativeParse", "[", "a_", "]"}], ":=", RowBox[{"Module", "[", RowBox[{ RowBox[{"{", RowBox[{ RowBox[{"b", "=", RowBox[{"atomParse", "[", RowBox[{"\"\\"", ",", "a"}], "]"}]}], ",", "c"}], "}"}], ",", RowBox[{ RowBox[{"c", "=", RowBox[{"subjectParse", "[", RowBox[{"Drop", "[", RowBox[{"a", ",", RowBox[{"b", "[", RowBox[{"[", "2", "]"}], "]"}]}], "]"}], "]"}]}], ";", "\[IndentingNewLine]", RowBox[{"\"\\"", "[", RowBox[{ RowBox[{"b", "[", RowBox[{"[", "1", "]"}], "]"}], ",", RowBox[{"c", "[", RowBox[{"[", "1", "]"}], "]"}]}], "]"}]}]}], "]"}]}], "\[IndentingNewLine]", RowBox[{ RowBox[{"subjectParse", "[", "a_", "]"}], ":=", RowBox[{"Module", "[", RowBox[{ RowBox[{"{", RowBox[{ RowBox[{"b", "=", RowBox[{"nounclauseParse", "[", "a", "]"}]}], ",", "c"}], "}"}], ",", RowBox[{ RowBox[{"c", "=", RowBox[{"Drop", "[", RowBox[{"a", ",", RowBox[{"b", "[", RowBox[{"[", "2", "]"}], "]"}]}], "]"}]}], ";", "\[IndentingNewLine]", RowBox[{"If", "[", RowBox[{ RowBox[{"!", RowBox[{"isQ", "[", RowBox[{"preposition", ",", RowBox[{"getNextWord", "[", "c", "]"}]}], "]"}]}], ",", RowBox[{"{", RowBox[{ RowBox[{"\"\\"", "[", RowBox[{"b", "[", RowBox[{"[", "1", "]"}], "]"}], "]"}], ",", RowBox[{"b", "[", RowBox[{"[", "2", "]"}], "]"}]}], "}"}], ",", RowBox[{ RowBox[{"c", "=", RowBox[{"prepositionclauseParse", "[", "c", "]"}]}], ";", "\[IndentingNewLine]", RowBox[{"{", RowBox[{ RowBox[{"\"\\"", "[", RowBox[{ RowBox[{"b", "[", RowBox[{"[", "1", "]"}], "]"}], ",", RowBox[{"c", "[", RowBox[{"[", "1", "]"}], "]"}]}], "]"}], ",", RowBox[{ RowBox[{"b", "[", RowBox[{"[", "2", "]"}], "]"}], "+", RowBox[{"c", "[", RowBox[{"[", "2", "]"}], "]"}]}]}], "}"}]}]}], "]"}]}]}], "]"}]}], "\[IndentingNewLine]", RowBox[{ RowBox[{"predicatepastParse", "[", "a_", "]"}], ":=", RowBox[{"Module", "[", RowBox[{ RowBox[{"{", RowBox[{ RowBox[{"b", "=", RowBox[{"verbclauseParse", "[", "a", "]"}]}], ",", "c"}], "}"}], ",", RowBox[{ RowBox[{"c", "=", RowBox[{"subjectParse", "[", RowBox[{"Drop", "[", RowBox[{"a", ",", RowBox[{"b", "[", RowBox[{"[", "2", "]"}], "]"}]}], "]"}], "]"}]}], ";", "\[IndentingNewLine]", RowBox[{"{", RowBox[{ RowBox[{"\"\\"", "[", RowBox[{ RowBox[{"b", "[", RowBox[{"[", "1", "]"}], "]"}], ",", RowBox[{"c", "[", RowBox[{"[", "1", "]"}], "]"}]}], "]"}], ",", RowBox[{ RowBox[{"b", "[", RowBox[{"[", "2", "]"}], "]"}], "+", RowBox[{"c", "[", RowBox[{"[", "2", "]"}], "]"}]}]}], "}"}]}]}], "]"}]}], "\[IndentingNewLine]", RowBox[{ RowBox[{"predicatepresentParse", "[", "a_", "]"}], ":=", RowBox[{"Module", "[", RowBox[{ RowBox[{"{", RowBox[{ RowBox[{"b", "=", RowBox[{"atomParse", "[", RowBox[{"\"\\"", ",", "a"}], "]"}]}], ",", "c"}], "}"}], ",", RowBox[{ RowBox[{"c", "=", RowBox[{"subjectParse", "[", RowBox[{"Drop", "[", RowBox[{"a", ",", RowBox[{"b", "[", RowBox[{"[", "2", "]"}], "]"}]}], "]"}], "]"}]}], ";", "\[IndentingNewLine]", RowBox[{"{", RowBox[{ RowBox[{"\"\\"", "[", RowBox[{ RowBox[{"b", "[", RowBox[{"[", "1", "]"}], "]"}], ",", RowBox[{"c", "[", RowBox[{"[", "1", "]"}], "]"}]}], "]"}], ",", RowBox[{ RowBox[{"b", "[", RowBox[{"[", "2", "]"}], "]"}], "+", RowBox[{"c", "[", RowBox[{"[", "2", "]"}], "]"}]}]}], "}"}]}]}], "]"}]}], "\[IndentingNewLine]", RowBox[{ RowBox[{"verbclauseParse", "[", "a_", "]"}], ":=", RowBox[{"Module", "[", RowBox[{ RowBox[{"{", RowBox[{ RowBox[{"b", "=", RowBox[{"adverblistParse", "[", "a", "]"}]}], ",", "c"}], "}"}], ",", RowBox[{ RowBox[{"c", "=", RowBox[{"atomParse", "[", RowBox[{"\"\\"", ",", RowBox[{"Drop", "[", RowBox[{"a", ",", RowBox[{"b", "[", RowBox[{"[", "2", "]"}], "]"}]}], "]"}]}], "]"}]}], ";", "\[IndentingNewLine]", RowBox[{"If", "[", RowBox[{ RowBox[{ RowBox[{"b", "[", RowBox[{"[", "2", "]"}], "]"}], "\[Equal]", "0"}], ",", "c", ",", RowBox[{"{", RowBox[{ RowBox[{"\"\\"", "[", RowBox[{ RowBox[{"b", "[", RowBox[{"[", "1", "]"}], "]"}], ",", RowBox[{"c", "[", RowBox[{"[", "1", "]"}], "]"}]}], "]"}], ",", RowBox[{ RowBox[{"b", "[", RowBox[{"[", "2", "]"}], "]"}], "+", RowBox[{"c", "[", RowBox[{"[", "2", "]"}], "]"}]}]}], "}"}]}], "]"}]}]}], "]"}]}], "\[IndentingNewLine]", RowBox[{ RowBox[{"nounclauseParse", "[", "a_", "]"}], ":=", RowBox[{"Module", "[", RowBox[{ RowBox[{"{", RowBox[{ RowBox[{"b", "=", RowBox[{"adjectiveclauseParse", "[", "a", "]"}]}], ",", "c"}], "}"}], ",", RowBox[{ RowBox[{"c", "=", RowBox[{"atomParse", "[", RowBox[{"\"\\"", ",", RowBox[{"Drop", "[", RowBox[{"a", ",", RowBox[{"b", "[", RowBox[{"[", "2", "]"}], "]"}]}], "]"}]}], "]"}]}], ";", "\[IndentingNewLine]", RowBox[{"{", RowBox[{ RowBox[{"\"\\"", "[", RowBox[{ RowBox[{"b", "[", RowBox[{"[", "1", "]"}], "]"}], ",", RowBox[{"c", "[", RowBox[{"[", "1", "]"}], "]"}]}], "]"}], ",", RowBox[{ RowBox[{"b", "[", RowBox[{"[", "2", "]"}], "]"}], "+", RowBox[{"c", "[", RowBox[{"[", "2", "]"}], "]"}]}]}], "}"}]}]}], "]"}]}], "\[IndentingNewLine]", RowBox[{ RowBox[{"adjectiveclauseParse", "[", "a_", "]"}], ":=", RowBox[{"Module", "[", RowBox[{ RowBox[{"{", RowBox[{ RowBox[{"b", "=", RowBox[{"atomParse", "[", RowBox[{"\"\\"", ",", "a"}], "]"}]}], ",", "c"}], "}"}], ",", RowBox[{ RowBox[{"c", "=", RowBox[{"adjectivelistParse", "[", RowBox[{"Drop", "[", RowBox[{"a", ",", RowBox[{"b", "[", RowBox[{"[", "2", "]"}], "]"}]}], "]"}], "]"}]}], ";", "\[IndentingNewLine]", RowBox[{"If", "[", RowBox[{ RowBox[{ RowBox[{"c", "[", RowBox[{"[", "2", "]"}], "]"}], "\[Equal]", "0"}], ",", "b", ",", RowBox[{"{", RowBox[{ RowBox[{"\"\\"", "[", RowBox[{ RowBox[{"b", "[", RowBox[{"[", "1", "]"}], "]"}], ",", RowBox[{"c", "[", RowBox[{"[", "1", "]"}], "]"}]}], "]"}], ",", RowBox[{ RowBox[{"b", "[", RowBox[{"[", "2", "]"}], "]"}], "+", RowBox[{"c", "[", RowBox[{"[", "2", "]"}], "]"}]}]}], "}"}]}], "]"}]}]}], "]"}]}], "\[IndentingNewLine]", RowBox[{ RowBox[{"adjectivelistParse", "[", "a_", "]"}], ":=", RowBox[{"Module", "[", RowBox[{ RowBox[{"{", RowBox[{ RowBox[{"b", "=", "a"}], ",", "c", ",", "result", ",", RowBox[{"len", "=", "0"}]}], "}"}], ",", RowBox[{ RowBox[{"result", "=", RowBox[{"\"\\"", "[", "]"}]}], ";", "\[IndentingNewLine]", RowBox[{"While", "[", RowBox[{ RowBox[{"isQ", "[", RowBox[{"adjective", ",", RowBox[{"getNextWord", "[", "b", "]"}]}], "]"}], ",", RowBox[{ RowBox[{"c", "=", RowBox[{"atomParse", "[", RowBox[{"\"\\"", ",", "b"}], "]"}]}], ";", "\[IndentingNewLine]", RowBox[{"len", "+=", RowBox[{"c", "[", RowBox[{"[", "2", "]"}], "]"}]}], ";", "\[IndentingNewLine]", RowBox[{"result", "=", RowBox[{"\"\\"", "[", RowBox[{"result", ",", RowBox[{"c", "[", RowBox[{"[", "1", "]"}], "]"}]}], "]"}]}], ";", "\[IndentingNewLine]", RowBox[{"b", "=", RowBox[{"Drop", "[", RowBox[{"b", ",", RowBox[{"c", "[", RowBox[{"[", "2", "]"}], "]"}]}], "]"}]}]}]}], "]"}], ";", "\[IndentingNewLine]", RowBox[{"{", RowBox[{ RowBox[{"Flatten", "[", RowBox[{"result", ",", "Infinity", ",", "\"\\""}], "]"}], ",", "len"}], "}"}]}]}], "]"}]}], "\[IndentingNewLine]", RowBox[{ RowBox[{"prepositionclauseParse", "[", "a_", "]"}], ":=", RowBox[{"Module", "[", RowBox[{ RowBox[{"{", RowBox[{ RowBox[{"b", "=", RowBox[{"atomParse", "[", RowBox[{"\"\\"", ",", "a"}], "]"}]}], ",", "c"}], "}"}], ",", RowBox[{ RowBox[{"c", "=", RowBox[{"nounclauseParse", "[", RowBox[{"Drop", "[", RowBox[{"a", ",", RowBox[{"b", "[", RowBox[{"[", "2", "]"}], "]"}]}], "]"}], "]"}]}], ";", "\[IndentingNewLine]", RowBox[{"{", RowBox[{ RowBox[{"\"\\"", "[", RowBox[{ RowBox[{"b", "[", RowBox[{"[", "1", "]"}], "]"}], ",", RowBox[{"c", "[", RowBox[{"[", "1", "]"}], "]"}]}], "]"}], ",", RowBox[{ RowBox[{"b", "[", RowBox[{"[", "2", "]"}], "]"}], "+", RowBox[{"c", "[", RowBox[{"[", "2", "]"}], "]"}]}]}], "}"}]}]}], "]"}]}], "\[IndentingNewLine]", RowBox[{ RowBox[{"adverblistParse", "[", "a_", "]"}], ":=", RowBox[{"Module", "[", RowBox[{ RowBox[{"{", RowBox[{ RowBox[{"b", "=", "a"}], ",", "c", ",", "result", ",", RowBox[{"len", "=", "0"}]}], "}"}], ",", RowBox[{ RowBox[{"result", "=", RowBox[{"\"\\"", "[", "]"}]}], ";", "\[IndentingNewLine]", RowBox[{"While", "[", RowBox[{ RowBox[{"isQ", "[", RowBox[{"adverb", ",", RowBox[{"getNextWord", "[", "b", "]"}]}], "]"}], ",", RowBox[{ RowBox[{"c", "=", RowBox[{"atomParse", "[", RowBox[{"\"\\"", ",", "b"}], "]"}]}], ";", "\[IndentingNewLine]", RowBox[{"len", "+=", RowBox[{"c", "[", RowBox[{"[", "2", "]"}], "]"}]}], ";", "\[IndentingNewLine]", RowBox[{"result", "=", RowBox[{"\"\\"", "[", RowBox[{"result", ",", RowBox[{"c", "[", RowBox[{"[", "1", "]"}], "]"}]}], "]"}]}], ";", "\[IndentingNewLine]", RowBox[{"b", "=", RowBox[{"Drop", "[", RowBox[{"b", ",", RowBox[{"c", "[", RowBox[{"[", "2", "]"}], "]"}]}], "]"}]}]}]}], "]"}], ";", "\[IndentingNewLine]", RowBox[{"{", RowBox[{ RowBox[{"Flatten", "[", RowBox[{"result", ",", "Infinity", ",", "\"\\""}], "]"}], ",", "len"}], "}"}]}]}], "]"}]}]}], "Input",ExpressionUUID->\ "784dd416-53c8-4015-a412-0e39f3c4afde"], Cell[CellGroupData[{ Cell[BoxData[ RowBox[{"Table", "[", RowBox[{ RowBox[{"sentenceParse", "[", RowBox[{ RowBox[{"bb", "[", "j", "]"}], "=", RowBox[{"randomSentence", "[", "]"}]}], "]"}], ",", " ", RowBox[{"{", RowBox[{"j", ",", "5"}], "}"}]}], "]"}]], "Input",ExpressionUUID->\ "4772d130-263f-4904-a519-5b57aaef54eb"], Cell[BoxData[ RowBox[{"{", RowBox[{ RowBox[{"\<\"DECLARATIVE SENTENCE\"\>", "[", RowBox[{ RowBox[{"\<\"SUBJECT\"\>", "[", RowBox[{ RowBox[{"\<\"NOUN CLAUSE\"\>", "[", RowBox[{ RowBox[{"\<\"ADJECTIVE CLAUSE\"\>", "[", RowBox[{ RowBox[{"\<\"ARTICLE\"\>", "[", "\<\"a\"\>", "]"}], ",", RowBox[{"\<\"ADJECTIVE LIST\"\>", "[", RowBox[{ RowBox[{"\<\"ADJECTIVE\"\>", "[", "\<\"mild-mannered\"\>", "]"}], ",", RowBox[{"\<\"ADJECTIVE\"\>", "[", "\<\"mad\"\>", "]"}]}], "]"}]}], "]"}], ",", RowBox[{"\<\"NOUN\"\>", "[", "\<\"sheep\"\>", "]"}]}], "]"}], ",", RowBox[{"\<\"PREPOSITION CLAUSE\"\>", "[", RowBox[{ RowBox[{"\<\"PREPOSITION\"\>", "[", "\<\"from\"\>", "]"}], ",", RowBox[{"\<\"NOUN CLAUSE\"\>", "[", RowBox[{ RowBox[{"\<\"ARTICLE\"\>", "[", "\<\"this\"\>", "]"}], ",", RowBox[{"\<\"NOUN\"\>", "[", "\<\"village\"\>", "]"}]}], "]"}]}], "]"}]}], "]"}], ",", RowBox[{"\<\"PREDICATE\"\>", "[", RowBox[{ RowBox[{"\<\"VERB (PAST TENSE)\"\>", "[", "\<\"grated\"\>", "]"}], ",", RowBox[{"\<\"SUBJECT\"\>", "[", RowBox[{"\<\"NOUN CLAUSE\"\>", "[", RowBox[{ RowBox[{"\<\"ARTICLE\"\>", "[", "\<\"the\"\>", "]"}], ",", RowBox[{"\<\"NOUN\"\>", "[", "\<\"librarian\"\>", "]"}]}], "]"}], "]"}]}], "]"}]}], "]"}], ",", RowBox[{"\<\"INTERROGATIVE SENTENCE\"\>", "[", RowBox[{ RowBox[{"\<\"QUESTION VERB\"\>", "[", "\<\"did\"\>", "]"}], ",", RowBox[{"\<\"SUBJECT\"\>", "[", RowBox[{"\<\"NOUN CLAUSE\"\>", "[", RowBox[{ RowBox[{"\<\"ARTICLE\"\>", "[", "\<\"this\"\>", "]"}], ",", RowBox[{"\<\"NOUN\"\>", "[", "\<\"attorney\"\>", "]"}]}], "]"}], "]"}], ",", RowBox[{"\<\"PREDICATE\"\>", "[", RowBox[{ RowBox[{"\<\"VERB (PRESENT TENSE)\"\>", "[", "\<\"throw\"\>", "]"}], ",", RowBox[{"\<\"SUBJECT\"\>", "[", RowBox[{"\<\"NOUN CLAUSE\"\>", "[", RowBox[{ RowBox[{"\<\"ADJECTIVE CLAUSE\"\>", "[", RowBox[{ RowBox[{"\<\"ARTICLE\"\>", "[", "\<\"a\"\>", "]"}], ",", RowBox[{"\<\"ADJECTIVE LIST\"\>", "[", RowBox[{ RowBox[{"\<\"ADJECTIVE\"\>", "[", "\<\"wet\"\>", "]"}], ",", RowBox[{"\<\"ADJECTIVE\"\>", "[", "\<\"slimy\"\>", "]"}]}], "]"}]}], "]"}], ",", RowBox[{"\<\"NOUN\"\>", "[", "\<\"programmer\"\>", "]"}]}], "]"}], "]"}]}], "]"}]}], "]"}], ",", RowBox[{"\<\"IMPERATIVE SENTENCE\"\>", "[", RowBox[{ RowBox[{"\<\"ACTION VERB\"\>", "[", "\<\"squeeze\"\>", "]"}], ",", RowBox[{"\<\"SUBJECT\"\>", "[", RowBox[{"\<\"NOUN CLAUSE\"\>", "[", RowBox[{ RowBox[{"\<\"ADJECTIVE CLAUSE\"\>", "[", RowBox[{ RowBox[{"\<\"ARTICLE\"\>", "[", "\<\"that\"\>", "]"}], ",", RowBox[{"\<\"ADJECTIVE LIST\"\>", "[", RowBox[{"\<\"ADJECTIVE\"\>", "[", "\<\"slimy\"\>", "]"}], "]"}]}], "]"}], ",", RowBox[{"\<\"NOUN\"\>", "[", "\<\"attorney\"\>", "]"}]}], "]"}], "]"}]}], "]"}], ",", RowBox[{"\<\"DECLARATIVE SENTENCE\"\>", "[", RowBox[{ RowBox[{"\<\"SUBJECT\"\>", "[", RowBox[{ RowBox[{"\<\"NOUN CLAUSE\"\>", "[", RowBox[{ RowBox[{"\<\"ARTICLE\"\>", "[", "\<\"this\"\>", "]"}], ",", RowBox[{"\<\"NOUN\"\>", "[", "\<\"village\"\>", "]"}]}], "]"}], ",", RowBox[{"\<\"PREPOSITION CLAUSE\"\>", "[", RowBox[{ RowBox[{"\<\"PREPOSITION\"\>", "[", "\<\"in\"\>", "]"}], ",", RowBox[{"\<\"NOUN CLAUSE\"\>", "[", RowBox[{ RowBox[{"\<\"ARTICLE\"\>", "[", "\<\"a\"\>", "]"}], ",", RowBox[{"\<\"NOUN\"\>", "[", "\<\"village\"\>", "]"}]}], "]"}]}], "]"}]}], "]"}], ",", RowBox[{"\<\"PREDICATE\"\>", "[", RowBox[{ RowBox[{"\<\"VERB (PAST TENSE)\"\>", "[", "\<\"ate\"\>", "]"}], ",", RowBox[{"\<\"SUBJECT\"\>", "[", RowBox[{"\<\"NOUN CLAUSE\"\>", "[", RowBox[{ RowBox[{"\<\"ADJECTIVE CLAUSE\"\>", "[", RowBox[{ RowBox[{"\<\"ARTICLE\"\>", "[", "\<\"that\"\>", "]"}], ",", RowBox[{"\<\"ADJECTIVE LIST\"\>", "[", RowBox[{ RowBox[{"\<\"ADJECTIVE\"\>", "[", "\<\"delectable\"\>", "]"}], ",", RowBox[{"\<\"ADJECTIVE\"\>", "[", "\<\"lazy\"\>", "]"}]}], "]"}]}], "]"}], ",", RowBox[{"\<\"NOUN\"\>", "[", "\<\"moon\"\>", "]"}]}], "]"}], "]"}]}], "]"}]}], "]"}], ",", RowBox[{"\<\"DECLARATIVE SENTENCE\"\>", "[", RowBox[{ RowBox[{"\<\"SUBJECT\"\>", "[", RowBox[{ RowBox[{"\<\"NOUN CLAUSE\"\>", "[", RowBox[{ RowBox[{"\<\"ADJECTIVE CLAUSE\"\>", "[", RowBox[{ RowBox[{"\<\"ARTICLE\"\>", "[", "\<\"this\"\>", "]"}], ",", RowBox[{"\<\"ADJECTIVE LIST\"\>", "[", RowBox[{"\<\"ADJECTIVE\"\>", "[", "\<\"crazy\"\>", "]"}], "]"}]}], "]"}], ",", RowBox[{"\<\"NOUN\"\>", "[", "\<\"shark\"\>", "]"}]}], "]"}], ",", RowBox[{"\<\"PREPOSITION CLAUSE\"\>", "[", RowBox[{ RowBox[{"\<\"PREPOSITION\"\>", "[", "\<\"under\"\>", "]"}], ",", RowBox[{"\<\"NOUN CLAUSE\"\>", "[", RowBox[{ RowBox[{"\<\"ARTICLE\"\>", "[", "\<\"the\"\>", "]"}], ",", RowBox[{"\<\"NOUN\"\>", "[", "\<\"hatter\"\>", "]"}]}], "]"}]}], "]"}]}], "]"}], ",", RowBox[{"\<\"PREDICATE\"\>", "[", RowBox[{ RowBox[{"\<\"VERB (PAST TENSE)\"\>", "[", "\<\"jumped\"\>", "]"}], ",", RowBox[{"\<\"SUBJECT\"\>", "[", RowBox[{ RowBox[{"\<\"NOUN CLAUSE\"\>", "[", RowBox[{ RowBox[{"\<\"ARTICLE\"\>", "[", "\<\"this\"\>", "]"}], ",", RowBox[{"\<\"NOUN\"\>", "[", "\<\"buffalo\"\>", "]"}]}], "]"}], ",", RowBox[{"\<\"PREPOSITION CLAUSE\"\>", "[", RowBox[{ RowBox[{"\<\"PREPOSITION\"\>", "[", "\<\"with\"\>", "]"}], ",", RowBox[{"\<\"NOUN CLAUSE\"\>", "[", RowBox[{ RowBox[{"\<\"ADJECTIVE CLAUSE\"\>", "[", RowBox[{ RowBox[{"\<\"ARTICLE\"\>", "[", "\<\"this\"\>", "]"}], ",", RowBox[{"\<\"ADJECTIVE LIST\"\>", "[", RowBox[{"\<\"ADJECTIVE\"\>", "[", "\<\"repugnant\"\>", "]"}], "]"}]}], "]"}], ",", RowBox[{"\<\"NOUN\"\>", "[", "\<\"ball\"\>", "]"}]}], "]"}]}], "]"}]}], "]"}]}], "]"}]}], "]"}]}], "}"}]], "Output",ExpressionUUID-\ >"7b82b37e-874a-440d-bc3e-8caf4b9598f1"] }, Open ]] }, Open ]] }, WindowSize->{771, 669}, WindowMargins->{{Automatic, 73}, {Automatic, 45}}, FrontEndVersion->"11.1 for Linux x86 (64-bit) (April 18, 2017)", StyleDefinitions->"Classroom.nb" ] (* End of Notebook Content *) (* Internal cache information *) (*CellTagsOutline CellTagsIndex->{} *) (*CellTagsIndex CellTagsIndex->{} *) (*NotebookFileOutline Notebook[{ Cell[558, 20, 180, 4, 107, "Title", "ExpressionUUID" -> \ "a638dc7e-3a7a-4b8f-88e0-14e60e9b6b6e"], Cell[741, 26, 134, 4, 82, "Author", "ExpressionUUID" -> \ "45e778cf-c6b9-433b-a0c6-bb08baf82cab"], Cell[CellGroupData[{ Cell[900, 34, 85, 0, 47, "Subsection", "ExpressionUUID" -> \ "1535e809-1679-4769-b45e-7e47f1c7e106"], Cell[988, 36, 473, 11, 61, "Text", "ExpressionUUID" -> \ "4711285a-7dd2-4a70-a997-0856e23f9084"] }, Open ]], Cell[CellGroupData[{ Cell[1498, 52, 91, 0, 47, "Subsection", "ExpressionUUID" -> \ "e43a76cf-be65-4d78-bcfe-87a686f00edb"], Cell[1592, 54, 279, 7, 72, "Input", "ExpressionUUID" -> \ "989800b9-947c-4c1f-9a39-287b74982035"] }, Open ]], Cell[CellGroupData[{ Cell[1908, 66, 89, 0, 47, "Subsection", "ExpressionUUID" -> \ "a1aa03b5-677d-4999-908d-3818618355ac"], Cell[2000, 68, 591, 10, 97, "Text", "ExpressionUUID" -> \ "7285f81e-ce24-48d8-988a-73a035acfa2a"], Cell[2594, 80, 378, 5, 61, "Text", "ExpressionUUID" -> \ "6061229d-c549-46db-bdf0-b1022fdad58b"], Cell[2975, 87, 323, 5, 103, "Text", "ExpressionUUID" -> \ "9cc8c238-9866-49e8-8e64-5fb93575db83"] }, Open ]], Cell[CellGroupData[{ Cell[3335, 97, 91, 0, 47, "Subsection", "ExpressionUUID" -> \ "8979f4a1-1e42-47d7-807d-b4bbe3ddc707"], Cell[3429, 99, 776, 14, 115, "Text", "ExpressionUUID" -> \ "caaffcf0-0908-4278-8c6f-26d2614dc9a2"], Cell[4208, 115, 706, 15, 98, "Text", "ExpressionUUID" -> \ "c6319569-814b-4c5a-8755-1c1742b808a2"], Cell[4917, 132, 203, 3, 43, "Text", "ExpressionUUID" -> \ "1beec0ab-f407-4432-a7b9-4b14261b4a37"], Cell[CellGroupData[{ Cell[5145, 139, 934, 31, 141, "Input", "ExpressionUUID" -> \ "4dc2ff6b-35a3-49d8-8547-ce8a9954760d"], Cell[6082, 172, 166, 4, 52, "Output", "ExpressionUUID" -> \ "e396fd25-9067-435b-9e92-3b9fa797089b"], Cell[6251, 178, 167, 4, 52, "Output", "ExpressionUUID" -> \ "4f418124-29da-4593-adda-de466de4a51c"], Cell[6421, 184, 181, 4, 52, "Output", "ExpressionUUID" -> \ "22564a6c-da28-4ab4-8e23-8e15091a445a"], Cell[6605, 190, 86, 0, 48, "Output", "ExpressionUUID" -> \ "35ef11c6-9365-436d-bc14-2f670f3e3696"] }, Open ]], Cell[6706, 193, 636, 10, 98, "Text", "ExpressionUUID" -> \ "b4a4d589-bea9-4f9e-9038-9d718bec5e8e"], Cell[CellGroupData[{ Cell[7367, 207, 934, 31, 141, "Input", "ExpressionUUID" -> \ "dc946fab-6598-4414-a349-f3caa067b91c"], Cell[8304, 240, 181, 4, 52, "Output", "ExpressionUUID" -> \ "13476bd2-00fc-4b0e-93c6-8e06ea429f0e"], Cell[8488, 246, 180, 4, 52, "Output", "ExpressionUUID" -> \ "a9863fb5-df62-435b-9fb2-c958f1606c57"], Cell[8671, 252, 181, 4, 52, "Output", "ExpressionUUID" -> \ "3c60d86a-7da2-48a8-9862-20ff39ab26a3"], Cell[8855, 258, 86, 0, 48, "Output", "ExpressionUUID" -> \ "c4702f65-87d0-4e70-bf65-ee75e8cb60e0"] }, Open ]] }, Open ]], Cell[CellGroupData[{ Cell[8990, 264, 104, 0, 47, "Subsection", "ExpressionUUID" -> \ "483b3cbd-1fdf-42b4-83bf-cba4604700c7"], Cell[9097, 266, 1217, 27, 115, "Text", "ExpressionUUID" -> \ "fabe6c80-4d8c-40a9-a5c5-af31a8f3ff41"], Cell[10317, 295, 374, 9, 26, "Text", "ExpressionUUID" -> \ "37c41588-f96d-42e3-a0b5-f22e17f0d72c"], Cell[CellGroupData[{ Cell[10716, 308, 658, 20, 138, "Input", "ExpressionUUID" -> \ "71228841-3626-4d6e-abe1-7200afefe745"], Cell[11377, 330, 97, 0, 24, "Print", "ExpressionUUID" -> \ "d1f38d1d-c834-413d-ab27-8bb09b5c127b"], Cell[11477, 332, 1495, 44, 102, "Print", "ExpressionUUID" -> \ "574b8a47-dc3f-40b8-8df2-db9547c4729c"] }, Open ]], Cell[12987, 379, 795, 14, 115, "Text", "ExpressionUUID" -> \ "81271925-3ef9-4fc6-95d5-48b64734513b"], Cell[13785, 395, 1129, 21, 205, "Text", "ExpressionUUID" -> \ "f4b342ba-2741-4ae7-a71a-358561afab04"], Cell[14917, 418, 1117, 31, 172, "Input", "ExpressionUUID" -> \ "360a1ef3-2d73-47f0-a69d-28ad6a712d6b"], Cell[16037, 451, 1682, 45, 216, "Input", "ExpressionUUID" -> \ "b0ebedad-69e9-4c1e-8c9b-8791be03084d"], Cell[17722, 498, 119, 0, 25, "Text", "ExpressionUUID" -> \ "80c54d5d-f556-428d-983f-71f55ab1571d"], Cell[CellGroupData[{ Cell[17866, 502, 750, 21, 93, "Input", "ExpressionUUID" -> \ "490b5e9a-d3e7-41ee-bded-19a93e3304e7"], Cell[18619, 525, 1301, 19, 160, "Output", "ExpressionUUID" -> \ "90a01c5d-7ac7-43d4-ab15-b29c8ed15e90"], Cell[19923, 546, 86, 0, 48, "Output", "ExpressionUUID" -> \ "2351002d-daef-4adf-b1b7-9430dbe8c91e"] }, Open ]], Cell[20024, 549, 117, 0, 25, "Text", "ExpressionUUID" -> \ "9a4b04e7-e813-42e7-a963-01c439ab414b"], Cell[20144, 551, 1222, 36, 124, "Input", "ExpressionUUID" -> \ "bfc17474-3741-4cad-8649-b778da9ac294"], Cell[21369, 589, 190, 3, 25, "Text", "ExpressionUUID" -> \ "deb2063f-755c-42b2-aedc-8073e4c27478"], Cell[21562, 594, 635, 14, 80, "Text", "ExpressionUUID" -> \ "61271dfb-e6b8-4e70-b692-844ff17b3386"], Cell[CellGroupData[{ Cell[22222, 612, 124, 1, 37, "Subsubsection", "ExpressionUUID" -> \ "df2cf222-0d1d-4e24-aba6-eb2648319f1c"], Cell[22349, 615, 352, 5, 61, "Text", "ExpressionUUID" -> \ "a7959a95-1b14-4bdf-ad6e-b3d456457e6d"], Cell[22704, 622, 6580, 185, 853, "Input", "ExpressionUUID" -> \ "92af6229-e43b-4981-b970-60869f231fe2"], Cell[29287, 809, 105, 0, 25, "Text", "ExpressionUUID" -> \ "cc0248f8-e90f-412a-a67e-9aae5d69d5aa"], Cell[CellGroupData[{ Cell[29417, 813, 871, 22, 154, "Input", "ExpressionUUID" -> \ "cecc62bb-7e2c-4cdd-a03a-cd91e220f60d"], Cell[30291, 837, 181, 4, 52, "Output", "ExpressionUUID" -> \ "1bbab1a8-79cf-48dc-b428-8917671bed9a"], Cell[30475, 843, 181, 4, 52, "Output", "ExpressionUUID" -> \ "728d33e5-8327-4452-8be5-a5b387c9337f"], Cell[30659, 849, 86, 0, 48, "Output", "ExpressionUUID" -> \ "6f509985-3ee3-4e63-89a7-c5ff5c1b20bd"], Cell[30748, 851, 86, 0, 48, "Output", "ExpressionUUID" -> \ "30a47b12-a367-4b7e-8b07-4f2d0b1db366"] }, Open ]], Cell[30849, 854, 255, 6, 43, "Text", "ExpressionUUID" -> \ "c7ac1807-2bbd-4701-ab7c-1a63849e1d3d"], Cell[31107, 862, 768, 23, 159, "Input", "ExpressionUUID" -> \ "dddda0f2-c7fe-4c16-a07a-66b7c0d30da0"], Cell[CellGroupData[{ Cell[31900, 889, 945, 23, 184, "Input", "ExpressionUUID" -> \ "2c50d47f-e147-41b0-bebc-b7311fd301e1"], Cell[32848, 914, 181, 4, 52, "Output", "ExpressionUUID" -> \ "2d6ec448-5bbf-4f21-b839-d380b8279587"], Cell[33032, 920, 181, 4, 52, "Output", "ExpressionUUID" -> \ "01310d41-e039-41e2-8a08-3e85b13c2f92"], Cell[33216, 926, 181, 4, 52, "Output", "ExpressionUUID" -> \ "0ddd0215-e277-4bb6-b73e-a9c6924fc1db"], Cell[33400, 932, 86, 0, 48, "Output", "ExpressionUUID" -> \ "8f9e78a4-318e-49b0-ad46-c216c6bb4ed6"], Cell[33489, 934, 86, 0, 48, "Output", "ExpressionUUID" -> \ "5673be57-f958-41d7-9dbe-ef26eb046177"], Cell[33578, 936, 86, 0, 48, "Output", "ExpressionUUID" -> \ "923c218f-df92-4554-be99-a87c3fccafac"] }, Open ]], Cell[33679, 939, 294, 8, 43, "Text", "ExpressionUUID" -> \ "de3d5ff1-7784-40f1-8f81-6d70edec2baa"], Cell[CellGroupData[{ Cell[33998, 951, 1271, 34, 137, "Input", "ExpressionUUID" -> \ "8aef2653-1867-4431-abca-1581fcc5fed1"], Cell[35272, 987, 181, 4, 52, "Output", "ExpressionUUID" -> \ "e87a8a8a-d38f-4488-89a4-4ef218434b00"], Cell[35456, 993, 181, 4, 52, "Output", "ExpressionUUID" -> \ "b1bd0547-897f-43cc-b57c-39cfd0b34347"], Cell[35640, 999, 181, 4, 52, "Output", "ExpressionUUID" -> \ "c4fef80f-3d74-414a-a63f-f5800291dd74"], Cell[35824, 1005, 181, 4, 52, "Output", "ExpressionUUID" -> \ "770c8eae-0a38-42df-8cdc-ab414f24747f"] }, Open ]], Cell[CellGroupData[{ Cell[36042, 1014, 346, 8, 76, "Input", "ExpressionUUID" -> \ "f68b9302-648a-4f9b-9ec4-907bb71d652a"], Cell[36391, 1024, 181, 4, 52, "Output", "ExpressionUUID" -> \ "16a9e78c-f5c1-46c8-a82f-3cea586ad8b8"], Cell[36575, 1030, 181, 4, 52, "Output", "ExpressionUUID" -> \ "f3a095f4-0949-4f7a-966e-94663e1f9b98"] }, Open ]] }, Open ]] }, Open ]], Cell[CellGroupData[{ Cell[36817, 1041, 83, 0, 47, "Subsection", "ExpressionUUID" -> \ "e3da8166-17c7-491b-9160-27ec94353c74"], Cell[36903, 1043, 462, 8, 91, "Text", "ExpressionUUID" -> \ "a5e391a5-fed8-4fd0-ab1a-cd600c4e26b5"], Cell[37368, 1053, 282, 4, 43, "Text", "ExpressionUUID" -> \ "d2a47128-a4ad-408b-8fec-5052782849a6"], Cell[37653, 1059, 188, 5, 25, "Text", "ExpressionUUID" -> \ "24c4e263-2350-4c01-a914-cc64a6f61c74"], Cell[37844, 1066, 1104, 30, 189, "Input", "ExpressionUUID" -> \ "21150b7f-9f75-4d62-9e97-af3a6e321aa3"], Cell[38951, 1098, 365, 10, 44, "Text", "ExpressionUUID" -> \ "e4d2777a-7835-4423-90f0-bd7d00597a21"], Cell[39319, 1110, 617, 17, 120, "Input", "ExpressionUUID" -> \ "04830634-bd80-4f47-bf75-bd1da8e0f57c"], Cell[39939, 1129, 364, 11, 74, "Input", "ExpressionUUID" -> \ "56584c4b-828c-491e-a09c-5e7d6959e58e"], Cell[40306, 1142, 296, 8, 44, "Text", "ExpressionUUID" -> \ "b397c67a-54c8-4b7d-892f-1f6923c5d3a3"], Cell[CellGroupData[{ Cell[40627, 1154, 326, 8, 50, "Input", "ExpressionUUID" -> \ "79e7b5d9-4ef1-4adf-b3a4-ea072ff66d5e"], Cell[40956, 1164, 228, 5, 24, "Message", "ExpressionUUID" -> \ "f4f90c03-9ec5-43cf-b5b9-1612863b7811"], Cell[41187, 1171, 228, 5, 24, "Message", "ExpressionUUID" -> \ "b7a6d36d-c9a0-4067-a7d3-5a904b711674"], Cell[41418, 1178, 228, 5, 24, "Message", "ExpressionUUID" -> \ "881b1214-b0bf-4184-b107-86a56bc36993"], Cell[41649, 1185, 283, 6, 45, "Message", "ExpressionUUID" -> \ "06eeaa4a-8cbf-41ef-9c94-ea892f8bdaf5"], Cell[41935, 1193, 263, 6, 24, "Message", "ExpressionUUID" -> \ "f9563299-ee4f-4847-8044-16c270bff466"], Cell[42201, 1201, 263, 6, 24, "Message", "ExpressionUUID" -> \ "41221970-a8aa-4808-9f95-2328c5d60c03"] }, Open ]], Cell[42479, 1210, 626, 9, 97, "Text", "ExpressionUUID" -> \ "54de8bcb-4b01-4c50-bfb8-52f4197f8fe5"], Cell[43108, 1221, 1726, 45, 282, "Input", "ExpressionUUID" -> \ "46b1d8c4-faf5-4c1f-ae5d-bfd5bd7a8086"], Cell[CellGroupData[{ Cell[44859, 1270, 185, 4, 48, "Input", "ExpressionUUID" -> \ "7369bb1b-fe8b-44f6-b454-f06e09f84339"], Cell[45047, 1276, 86, 0, 48, "Output", "ExpressionUUID" -> \ "c59e550b-efbe-4ade-83bb-9fe77a07054c"] }, Open ]], Cell[45148, 1279, 1081, 33, 76, "Input", "ExpressionUUID" -> \ "d011f3d1-c505-465d-b917-36d1a7a61d97"], Cell[CellGroupData[{ Cell[46254, 1316, 187, 4, 48, "Input", "ExpressionUUID" -> \ "9563e3e5-3b74-4f61-9cd4-ba38e3b085e4"], Cell[46444, 1322, 86, 0, 48, "Output", "ExpressionUUID" -> \ "7c11924f-c5e9-4b61-b335-3b8273343ec5"] }, Open ]], Cell[46545, 1325, 240, 4, 43, "Text", "ExpressionUUID" -> \ "91be0d5a-f2ab-4f37-969b-599597ba91e7"] }, Open ]], Cell[CellGroupData[{ Cell[46822, 1334, 83, 0, 47, "Subsection", "ExpressionUUID" -> \ "749a715a-0a21-4144-9af2-988f66a9a110"], Cell[46908, 1336, 656, 9, 97, "Text", "ExpressionUUID" -> \ "aec2ab1b-4165-41ec-8a72-18a992ddb3f3"], Cell[47567, 1347, 3340, 99, 350, "Input", "ExpressionUUID" -> \ "e2e4d706-67ba-4217-8a05-31f4bd37c0e7"], Cell[50910, 1448, 96, 0, 25, "Text", "ExpressionUUID" -> \ "96eb481e-e111-41d7-9cb9-6244bbc7350b"], Cell[CellGroupData[{ Cell[51031, 1452, 601, 16, 115, "Input", "ExpressionUUID" -> \ "5604e265-c199-4ecf-b311-0cdff76d415b"], Cell[51635, 1470, 83, 0, 48, "Output", "ExpressionUUID" -> \ "ce2df55c-bfbf-4b46-ac58-8142d349616e"], Cell[51721, 1472, 101, 0, 48, "Output", "ExpressionUUID" -> \ "f2441029-6edd-4716-95a7-5ae18c88664a"] }, Open ]], Cell[CellGroupData[{ Cell[51859, 1477, 464, 12, 76, "Input", "ExpressionUUID" -> \ "a5d3d64a-d118-4375-8a7e-a1948865810a"], Cell[52326, 1491, 102, 0, 24, "Print", "ExpressionUUID" -> \ "695379f4-82cf-4c28-8def-47fed67f2d6b"] }, Open ]], Cell[52443, 1494, 163, 3, 25, "Text", "ExpressionUUID" -> \ "9cd5ec35-7637-4e43-a50c-bbe9785f9741"], Cell[CellGroupData[{ Cell[52631, 1501, 146, 3, 48, "Input", "ExpressionUUID" -> \ "301b40a9-5bff-4472-aaf6-535ca76a095c"], Cell[52780, 1506, 105, 0, 48, "Output", "ExpressionUUID" -> \ "3724cc44-bd2b-4487-8c77-627a2d17dd8e"] }, Open ]], Cell[52900, 1509, 155, 3, 50, "Input", "ExpressionUUID" -> \ "df921993-691e-4f89-ac31-33ed59305281"], Cell[53058, 1514, 931, 14, 151, "Text", "ExpressionUUID" -> \ "02c389cd-b905-4945-9178-9ca63f269328"], Cell[53992, 1530, 2414, 74, 363, "Input", "ExpressionUUID" -> \ "c33be860-2a17-4f25-8943-81c50e9a2185"], Cell[56409, 1606, 185, 3, 25, "Text", "ExpressionUUID" -> \ "526e674a-f294-48a2-9226-3bc4477b0c95"], Cell[CellGroupData[{ Cell[56619, 1613, 602, 16, 115, "Input", "ExpressionUUID" -> \ "bd301805-71d1-4504-90fc-2f95df99fb58"], Cell[57224, 1631, 83, 0, 48, "Output", "ExpressionUUID" -> \ "5c6859b3-bb3f-4b35-9955-03c40d6b624b"], Cell[57310, 1633, 101, 0, 48, "Output", "ExpressionUUID" -> \ "30e5101d-ab43-457b-a1bb-90584232431a"] }, Open ]], Cell[57426, 1636, 464, 12, 76, "Input", "ExpressionUUID" -> \ "aa462b12-fa25-43d4-a5b1-db238916ba53"], Cell[CellGroupData[{ Cell[57915, 1652, 215, 4, 69, "Input", "ExpressionUUID" -> \ "f94d5906-0cca-43b5-84d4-14e4a7d39db3"], Cell[58133, 1658, 105, 0, 48, "Output", "ExpressionUUID" -> \ "26ec5d2d-72af-4704-8abc-d4ebe685dc2e"], Cell[58241, 1660, 83, 0, 48, "Output", "ExpressionUUID" -> \ "dfe3d1e0-7d83-4815-8be9-06b3625623c8"] }, Open ]], Cell[58339, 1663, 506, 9, 80, "Text", "ExpressionUUID" -> \ "82c89575-6265-47ff-91c5-53e76bc46694"], Cell[58848, 1674, 1090, 19, 151, "Text", "ExpressionUUID" -> \ "6a88c046-85ef-4808-8d37-cea30f252681"], Cell[CellGroupData[{ Cell[59963, 1697, 215, 5, 48, "Input", "ExpressionUUID" -> \ "476556a3-9910-4995-a328-c359e63795c2"], Cell[60181, 1704, 101, 0, 24, "Print", "ExpressionUUID" -> \ "da3d2b31-3b03-4ba1-a9af-9d175fc809b1"], Cell[60285, 1706, 1428, 45, 241, "Print", "ExpressionUUID" -> \ "900e46ef-f1c1-42c1-800e-2122db6e978c"] }, Open ]], Cell[61728, 1754, 756, 12, 115, "Text", "ExpressionUUID" -> \ "0e78c52c-9d73-4491-9ab2-6fafa51f0501"], Cell[62487, 1768, 254, 4, 43, "Text", "ExpressionUUID" -> \ "014e9ccc-ab8c-44d2-b215-1aee627c2722"], Cell[62744, 1774, 1714, 45, 282, "Input", "ExpressionUUID" -> \ "073f3894-8e82-4430-aaa4-4df65a8938f2"], Cell[CellGroupData[{ Cell[64483, 1823, 123, 1, 48, "Input", "ExpressionUUID" -> \ "617c3521-1120-4ce8-a4d8-884ee8ba3d03"], Cell[64609, 1826, 365, 7, 52, "Output", "ExpressionUUID" -> \ "72124c2b-73ac-460e-86d0-f858dd9e2356"] }, Open ]], Cell[64989, 1836, 268, 4, 43, "Text", "ExpressionUUID" -> \ "0ddbfe19-0122-46d1-8c4b-0a8a4a95be88"], Cell[CellGroupData[{ Cell[65282, 1844, 870, 25, 120, "Input", "ExpressionUUID" -> \ "cb4fefa3-6510-4da4-9bb3-acda8be08311"], Cell[66155, 1871, 365, 7, 52, "Output", "ExpressionUUID" -> \ "fc61b12c-c905-4d7b-8e5b-170b97af64cc"] }, Open ]], Cell[66535, 1881, 265, 4, 43, "Text", "ExpressionUUID" -> \ "d4e4e240-eee9-4201-ae5b-9c2c171e9cc4"], Cell[66803, 1887, 509, 7, 79, "Text", "ExpressionUUID" -> \ "7996eb1b-40a4-4bd9-b5f9-a56f27fbc061"] }, Open ]], Cell[CellGroupData[{ Cell[67349, 1899, 82, 0, 47, "Subsection", "ExpressionUUID" -> \ "37a82a5e-6704-4196-a435-1a72791b41df"], Cell[67434, 1901, 682, 19, 81, "Text", "ExpressionUUID" -> \ "9ee425db-e460-4b36-be4f-d8fc3c4eb071"], Cell[68119, 1922, 431, 8, 61, "Text", "ExpressionUUID" -> \ "7afe25d1-1b4f-4477-add3-fca0328f7d0d"], Cell[68553, 1932, 1417, 36, 116, "Text", "ExpressionUUID" -> \ "053ad205-2e75-4a4a-90ed-eb90a0ad61d0"], Cell[69973, 1970, 535, 13, 62, "Text", "ExpressionUUID" -> \ "91d0984d-3c23-42f9-a4cb-9dcc9ef614ca"], Cell[70511, 1985, 2111, 61, 299, "Input", "ExpressionUUID" -> \ "2f4b107a-e79e-4d90-aa10-0c8d47e6f910"], Cell[72625, 2048, 233, 4, 43, "Text", "ExpressionUUID" -> \ "bd58e03a-668c-43b3-bc8e-8d0ada16a88c"], Cell[CellGroupData[{ Cell[72883, 2056, 1091, 32, 182, "Input", "ExpressionUUID" -> \ "a4dfc256-41ef-4748-9680-9f031d32702b"], Cell[73977, 2090, 100, 0, 48, "Output", "ExpressionUUID" -> \ "2558f41f-a280-4e2a-a23c-578ec182285c"], Cell[74080, 2092, 86, 0, 48, "Output", "ExpressionUUID" -> \ "a3dffde5-b0e9-4f9e-9e85-8a92c60b1d67"] }, Open ]], Cell[CellGroupData[{ Cell[74203, 2097, 1091, 32, 182, "Input", "ExpressionUUID" -> \ "5d74aade-412f-4f84-bb90-f4c3892321ca"], Cell[75297, 2131, 101, 0, 48, "Output", "ExpressionUUID" -> \ "bd88bd16-04be-490b-ac7c-2e8d5bfe777a"], Cell[75401, 2133, 86, 0, 48, "Output", "ExpressionUUID" -> \ "d3325954-2f2e-4a69-bd35-d93cc8af2168"] }, Open ]], Cell[CellGroupData[{ Cell[75524, 2138, 1105, 32, 182, "Input", "ExpressionUUID" -> \ "f38b135f-538b-47e6-bcaa-5e8d192c1ce8"], Cell[76632, 2172, 101, 0, 48, "Output", "ExpressionUUID" -> \ "0c366671-1671-428e-a1c0-064a5f730f89"], Cell[76736, 2174, 86, 0, 48, "Output", "ExpressionUUID" -> \ "b419eabe-1ee0-4380-8d7b-8eb718103bb6"] }, Open ]], Cell[76837, 2177, 280, 11, 25, "Text", "ExpressionUUID" -> \ "cfed18a4-4c40-47ff-855b-33e2241f9484"], Cell[CellGroupData[{ Cell[77142, 2192, 1205, 36, 155, "Input", "ExpressionUUID" -> \ "357656d7-0ab7-478f-940f-3adf886502c5"], Cell[78350, 2230, 201, 5, 50, "Output", "ExpressionUUID" -> \ "63b38f00-23fa-42c1-a922-dbf5e98af278"] }, Open ]], Cell[78566, 2238, 666, 16, 81, "Text", "ExpressionUUID" -> \ "6605b97f-3dca-40f8-964c-a607b6b12f24"] }, Open ]], Cell[CellGroupData[{ Cell[79269, 2259, 87, 0, 47, "Subsection", "ExpressionUUID" -> \ "ce591594-df91-4c56-bee1-6fde1a53f04a"], Cell[79359, 2261, 597, 12, 62, "Text", "ExpressionUUID" -> \ "eed4cdd5-722f-4ade-ab44-55c79cf12ae8"], Cell[79959, 2275, 616, 11, 80, "Text", "ExpressionUUID" -> \ "3d767d8c-6904-415d-8a3b-6c3aec306ddb"], Cell[80578, 2288, 515, 15, 100, "Input", "ExpressionUUID" -> \ "d6d8f3ee-57e1-46f8-89a2-b0c647e57a8e"], Cell[81096, 2305, 302, 4, 46, "Text", "ExpressionUUID" -> \ "fa8d9226-1c34-446e-84d6-9d0f0ef1441e"], Cell[81401, 2311, 328, 10, 47, "Input", "ExpressionUUID" -> \ "b1248fb4-6985-45f3-9701-8a5ed8e38b9c"], Cell[81732, 2323, 761, 17, 82, "Text", "ExpressionUUID" -> \ "92a52676-ad23-4c94-bb99-6b27b10335a2"], Cell[CellGroupData[{ Cell[82518, 2344, 479, 15, 79, "Input", "ExpressionUUID" -> \ "4ddd0058-0db6-4761-9d32-68e55287245d"], Cell[83000, 2361, 84, 0, 47, "Output", "ExpressionUUID" -> \ "2337f686-7987-432f-a26a-1e64ac53dca2"] }, Open ]], Cell[83099, 2364, 378, 7, 46, "Text", "ExpressionUUID" -> \ "91d14620-9d27-41bc-8c43-670404b362eb"], Cell[CellGroupData[{ Cell[83502, 2375, 966, 31, 95, "Input", "ExpressionUUID" -> \ "0e2fa46d-0798-464e-941d-88b7fc7aaf37"], Cell[84471, 2408, 84, 0, 47, "Output", "ExpressionUUID" -> \ "a508fd3f-9fee-4d78-9d32-46c467b5e388"] }, Open ]], Cell[84570, 2411, 267, 4, 46, "Text", "ExpressionUUID" -> \ "02076379-e280-4e4b-8b3c-0c6c8a44477c"], Cell[84840, 2417, 533, 15, 47, "Input", "ExpressionUUID" -> \ "6df84c5f-fb5f-4e2f-bee1-7bd7acb01bd5"], Cell[85376, 2434, 280, 8, 28, "Text", "ExpressionUUID" -> \ "90a3a831-342c-4c00-9cbd-242770752f51"], Cell[CellGroupData[{ Cell[85681, 2446, 396, 12, 47, "Input", "ExpressionUUID" -> \ "902674c3-b7b5-4c50-9a30-d9cd563aa307"], Cell[86080, 2460, 84, 0, 47, "Output", "ExpressionUUID" -> \ "8818f1c1-e363-41a9-ba8f-32b503cdb2c7"] }, Open ]], Cell[86179, 2463, 374, 9, 46, "Text", "ExpressionUUID" -> \ "fdc11141-1b25-40e5-9c97-97acd951b892"], Cell[86556, 2474, 611, 17, 79, "Input", "ExpressionUUID" -> \ "8fd69ada-12d2-4348-892b-9a517dc4fcc7"], Cell[CellGroupData[{ Cell[87192, 2495, 143, 1, 45, "Subsubsection", "ExpressionUUID" -> \ "b95bea28-8769-4f5e-ae5f-1af377ad5fcc"], Cell[87338, 2498, 512, 8, 64, "Text", "ExpressionUUID" -> \ "7cd0f306-7252-4b13-9995-dfd707d3c7dc"], Cell[87853, 2508, 1021, 14, 136, "Text", "ExpressionUUID" -> \ "39a5e289-c0f6-4b19-84cc-21692226de2c"], Cell[88877, 2524, 839, 21, 127, "Input", "ExpressionUUID" -> \ "e201ad8a-c789-4521-a0f9-6319f0d89bdd"], Cell[89719, 2547, 261, 4, 46, "Text", "ExpressionUUID" -> \ "8fcc7e56-ae5e-4fa2-881c-852f57e0990d"], Cell[CellGroupData[{ Cell[90005, 2555, 873, 27, 111, "Input", "ExpressionUUID" -> \ "9417c1da-0a67-4fdc-ae6a-ce6d9f52b796"], Cell[90881, 2584, 166, 4, 47, "Output", "ExpressionUUID" -> \ "38b2f2ff-4558-4906-9d56-d5d66a8d3738"], Cell[91050, 2590, 83, 0, 47, "Output", "ExpressionUUID" -> \ "e21c4140-53a1-4028-b8fa-edd13bc4afa3"], Cell[91136, 2592, 83, 0, 47, "Output", "ExpressionUUID" -> \ "c61fcda2-6c8b-4162-bbbe-d891246f6a9a"] }, Open ]], Cell[91234, 2595, 119, 0, 28, "Text", "ExpressionUUID" -> \ "66d93bda-f9de-4a4c-847d-990626848d47"], Cell[CellGroupData[{ Cell[91378, 2599, 513, 15, 63, "Input", "ExpressionUUID" -> \ "900462d3-1370-416e-8056-3f2c53933b64"], Cell[91894, 2616, 180, 4, 47, "Output", "ExpressionUUID" -> \ "cb31cb9a-2ebb-458c-9921-76e369367a53"], Cell[92077, 2622, 83, 0, 47, "Output", "ExpressionUUID" -> \ "ea5e526c-f102-4671-a359-3d3603bc644e"] }, Open ]], Cell[92175, 2625, 900, 14, 118, "Text", "ExpressionUUID" -> \ "3f67a73b-5a17-4ef0-b691-c0428b05df3a"], Cell[93078, 2641, 158, 3, 25, "Text", "ExpressionUUID" -> \ "a7fbddbc-1bb5-4adb-8f60-d820f9d72f9d"], Cell[93239, 2646, 4848, 122, 548, "Input", "ExpressionUUID" -> \ "3717a256-ea57-4cad-bf03-11eda1501051"], Cell[98090, 2770, 199, 3, 25, "Text", "ExpressionUUID" -> \ "168b9d14-9190-4ac2-94ff-f50e84d77be9"], Cell[98292, 2775, 1089, 30, 190, "Input", "ExpressionUUID" -> \ "f5353b57-8b33-4535-b8e8-0c67cc270678"], Cell[99384, 2807, 158, 3, 25, "Text", "ExpressionUUID" -> \ "dd8ad44c-06e3-4007-bdcd-07bf3858064e"], Cell[CellGroupData[{ Cell[99567, 2814, 358, 10, 72, "Input", "ExpressionUUID" -> \ "4fcd14de-c322-4321-a324-6fff6728d9fe"], Cell[99928, 2826, 180, 4, 52, "Output", "ExpressionUUID" -> \ "e0ad5d75-566d-461d-b2a6-f95e3cc9b182"], Cell[100111, 2832, 83, 0, 48, "Output", "ExpressionUUID" -> \ "2d810952-046c-454b-bc66-aa99bc0c5317"] }, Open ]], Cell[100209, 2835, 1071, 22, 121, "Text", "ExpressionUUID" -> \ "0c380d6f-15a8-41da-bb30-5c487bbdf847"], Cell[101283, 2859, 841, 21, 161, "Input", "ExpressionUUID" -> \ "44e55627-cc30-4f33-86dc-c35c9f42d5f9"], Cell[102127, 2882, 1089, 30, 143, "Input", "ExpressionUUID" -> \ "11c2b2ef-a55a-498e-8e81-ad9992646b08"], Cell[CellGroupData[{ Cell[103241, 2916, 513, 15, 63, "Input", "ExpressionUUID" -> \ "17bc87ee-35e0-4a3f-bb3b-8482222b1781"], Cell[103757, 2933, 168, 4, 47, "Output", "ExpressionUUID" -> \ "7b6ae8b9-c3cc-4dff-b38d-c1ae22698a28"], Cell[103928, 2939, 83, 0, 47, "Output", "ExpressionUUID" -> \ "b9e45fc3-1c6c-4043-9f00-d2132e83a289"] }, Open ]], Cell[CellGroupData[{ Cell[104048, 2944, 358, 10, 63, "Input", "ExpressionUUID" -> \ "420c04d1-d725-4e81-9242-d240635ab350"], Cell[104409, 2956, 181, 4, 47, "Output", "ExpressionUUID" -> \ "f0c854a6-d7b4-4067-955c-a7e4a70cf8a1"], Cell[104593, 2962, 83, 0, 47, "Output", "ExpressionUUID" -> \ "1d5037c0-e9fc-45f2-a9aa-fa0f237f7bc1"] }, Open ]], Cell[104691, 2965, 588, 11, 64, "Text", "ExpressionUUID" -> \ "d1178cfb-d726-4962-ae93-bd016f746115"] }, Open ]] }, Open ]], Cell[CellGroupData[{ Cell[105328, 2982, 115, 0, 31, "Subsection", "ExpressionUUID" -> \ "28e4fd38-2274-4a57-aac1-2ba5b7ea9fbe"], Cell[105446, 2984, 992, 15, 193, "Text", "ExpressionUUID" -> \ "9f4c24ca-dfa1-4f3e-9e4e-123967020d2e"], Cell[106441, 3001, 509, 9, 80, "Text", "ExpressionUUID" -> \ "f39a522a-4109-4ff2-8779-b4e15837e11e"], Cell[106953, 3012, 6185, 158, 972, "Input", "ExpressionUUID" -> \ "2fd8de01-ed78-4177-a12b-7e626540595d"], Cell[113141, 3172, 176, 3, 25, "Text", "ExpressionUUID" -> \ "b7d3e7b0-fdf5-484b-854f-f21cac9d04d1"], Cell[113320, 3177, 3783, 105, 374, "Input", "ExpressionUUID" -> \ "e4c3a427-102c-45cb-8263-7f8b262a290b"], Cell[117106, 3284, 267, 4, 43, "Text", "ExpressionUUID" -> \ "2d319ae0-0d27-442f-ab61-99641834be5c"], Cell[CellGroupData[{ Cell[117398, 3292, 235, 6, 50, "Input", "ExpressionUUID" -> \ "f0a46a96-2b11-4f87-b9f4-c2d5546421e6"], Cell[117636, 3300, 4068, 87, 389, "Output", "ExpressionUUID" -> \ "5a68a069-0598-4053-983a-8c7f4c0a802e"] }, Open ]], Cell[121719, 3390, 534, 7, 79, "Text", "ExpressionUUID" -> \ "0c807d43-8cce-42f9-9afb-3996c8da43a7"], Cell[122256, 3399, 15053, 450, 1363, "Input", "ExpressionUUID" -> \ "784dd416-53c8-4015-a412-0e39f3c4afde"], Cell[CellGroupData[{ Cell[137334, 3853, 329, 9, 52, "Input", "ExpressionUUID" -> \ "4772d130-263f-4904-a519-5b57aaef54eb"], Cell[137666, 3864, 6886, 154, 628, "Output", "ExpressionUUID" -> \ "7b82b37e-874a-440d-bc3e-8caf4b9598f1"] }, Open ]] }, Open ]] } ] *) (* End of internal cache information *)