ads.toc

\select@language {english}
\hypertarget {x:book:ads}{}
\contentsline {chapter}{Acknowledgements}{vii}{chapter*.1}
\contentsline {chapter}{Preface}{x}{chapter*.2}
\contentsline {chapter}{\numberline {1}Set Theory}{1}{chapter.1}
\contentsline {section}{\numberline {1.1}Set Notation and Relations}{1}{section.1.1}
\contentsline {subsection}{\numberline {1.1.1}The notion of a set}{1}{subsection.1.1.1}
\contentsline {subsection}{\numberline {1.1.2}Subsets}{3}{subsection.1.1.2}
\contentsline {subsection}{\numberline {1.1.3}Exercises}{4}{subsection.1.1.3}
\contentsline {section}{\numberline {1.2}Basic Set Operations}{5}{section.1.2}
\contentsline {subsection}{\numberline {1.2.1}Definitions}{5}{subsection.1.2.1}
\contentsline {subsection}{\numberline {1.2.2}Set Operations and their Venn Diagrams}{5}{subsection.1.2.2}
\contentsline {subsection}{\numberline {1.2.3}SageMath Note: Sets}{8}{subsection.1.2.3}
\contentsline {subsection}{\numberline {1.2.4}Exercises}{9}{subsection.1.2.4}
\contentsline {section}{\numberline {1.3}Cartesian Products and Power Sets}{10}{section.1.3}
\contentsline {subsection}{\numberline {1.3.1}Cartesian Products}{10}{subsection.1.3.1}
\contentsline {subsection}{\numberline {1.3.2}Power Sets}{11}{subsection.1.3.2}
\contentsline {subsection}{\numberline {1.3.3}SageMath Note: Cartesian Products and Power Sets}{11}{subsection.1.3.3}
\contentsline {subsection}{\numberline {1.3.4}Exercises}{12}{subsection.1.3.4}
\contentsline {section}{\numberline {1.4}Binary Representation of Positive Integers}{13}{section.1.4}
\contentsline {subsection}{\numberline {1.4.1}Grouping by Twos}{13}{subsection.1.4.1}
\contentsline {subsection}{\numberline {1.4.2}A Conversion Algorithm}{13}{subsection.1.4.2}
\contentsline {subsection}{\numberline {1.4.3}Exercises}{15}{subsection.1.4.3}
\contentsline {section}{\numberline {1.5}Summation Notation and Generalizations}{16}{section.1.5}
\contentsline {subsection}{\numberline {1.5.1}Sums}{16}{subsection.1.5.1}
\contentsline {subsection}{\numberline {1.5.2}Generalizations}{17}{subsection.1.5.2}
\contentsline {subsection}{\numberline {1.5.3}Exercises}{18}{subsection.1.5.3}
\contentsline {chapter}{\numberline {2}Combinatorics}{20}{chapter.2}
\contentsline {section}{\numberline {2.1}Basic Counting Techniques - The Rule of Products}{20}{section.2.1}
\contentsline {subsection}{\numberline {2.1.1}What is Combinatorics?}{20}{subsection.2.1.1}
\contentsline {subsection}{\numberline {2.1.2}The Rule Of Products}{21}{subsection.2.1.2}
\contentsline {subsection}{\numberline {2.1.3}Exercises}{22}{subsection.2.1.3}
\contentsline {section}{\numberline {2.2}Permutations}{24}{section.2.2}
\contentsline {subsection}{\numberline {2.2.1}Ordering Things}{24}{subsection.2.2.1}
\contentsline {subsection}{\numberline {2.2.2}Exercises}{27}{subsection.2.2.2}
\contentsline {section}{\numberline {2.3}Partitions of Sets and the Law of Addition}{29}{section.2.3}
\contentsline {subsection}{\numberline {2.3.1}Partitions}{29}{subsection.2.3.1}
\contentsline {subsection}{\numberline {2.3.2}Addition Laws}{30}{subsection.2.3.2}
\contentsline {subsection}{\numberline {2.3.3}Exercises}{32}{subsection.2.3.3}
\contentsline {section}{\numberline {2.4}Combinations and the Binomial Theorem}{33}{section.2.4}
\contentsline {subsection}{\numberline {2.4.1}Combinations}{33}{subsection.2.4.1}
\contentsline {subsection}{\numberline {2.4.2}The Binomial Theorem}{35}{subsection.2.4.2}
\contentsline {subsection}{\numberline {2.4.3}SageMath Note}{36}{subsection.2.4.3}
\contentsline {subsection}{\numberline {2.4.4}Exercises}{37}{subsection.2.4.4}
\contentsline {chapter}{\numberline {3}Logic}{39}{chapter.3}
\contentsline {section}{\numberline {3.1}Propositions and Logical Operators}{39}{section.3.1}
\contentsline {subsection}{\numberline {3.1.1}Propositions}{39}{subsection.3.1.1}
\contentsline {subsection}{\numberline {3.1.2}Logical Operations}{40}{subsection.3.1.2}
\contentsline {subsection}{\numberline {3.1.3}Exercises}{43}{subsection.3.1.3}
\contentsline {section}{\numberline {3.2}Truth Tables and Propositions Generated by a Set}{44}{section.3.2}
\contentsline {subsection}{\numberline {3.2.1}Truth Tables}{44}{subsection.3.2.1}
\contentsline {subsection}{\numberline {3.2.2}Propositions Generated by a Set}{44}{subsection.3.2.2}
\contentsline {subsection}{\numberline {3.2.3}Exercises}{45}{subsection.3.2.3}
\contentsline {section}{\numberline {3.3}Equivalence and Implication}{46}{section.3.3}
\contentsline {subsection}{\numberline {3.3.1}Tautologies and Contradictions}{46}{subsection.3.3.1}
\contentsline {subsection}{\numberline {3.3.2}Equivalence}{47}{subsection.3.3.2}
\contentsline {subsection}{\numberline {3.3.3}Implication}{47}{subsection.3.3.3}
\contentsline {subsection}{\numberline {3.3.4}A Universal Operation}{48}{subsection.3.3.4}
\contentsline {subsection}{\numberline {3.3.5}Exercises}{48}{subsection.3.3.5}
\contentsline {section}{\numberline {3.4}The Laws of Logic}{49}{section.3.4}
\contentsline {subsection}{\numberline {3.4.1}}{49}{subsection.3.4.1}
\contentsline {subsection}{\numberline {3.4.2}Exercises}{50}{subsection.3.4.2}
\contentsline {section}{\numberline {3.5}Mathematical Systems and Proofs}{51}{section.3.5}
\contentsline {subsection}{\numberline {3.5.1}Mathematical Systems}{51}{subsection.3.5.1}
\contentsline {subsection}{\numberline {3.5.2}Direct Proof}{52}{subsection.3.5.2}
\contentsline {subsection}{\numberline {3.5.3}Indirect Proof}{54}{subsection.3.5.3}
\contentsline {subsection}{\numberline {3.5.4}Exercises}{55}{subsection.3.5.4}
\contentsline {section}{\numberline {3.6}Propositions over a Universe}{56}{section.3.6}
\contentsline {subsection}{\numberline {3.6.1}Propositions over a Universe}{56}{subsection.3.6.1}
\contentsline {subsection}{\numberline {3.6.2}Truth Sets}{57}{subsection.3.6.2}
\contentsline {subsection}{\numberline {3.6.3}Exercises}{58}{subsection.3.6.3}
\contentsline {section}{\numberline {3.7}Mathematical Induction}{59}{section.3.7}
\contentsline {subsection}{\numberline {3.7.1}Introduction, First Example}{59}{subsection.3.7.1}
\contentsline {subsection}{\numberline {3.7.2}More Examples}{61}{subsection.3.7.2}
\contentsline {subsection}{\numberline {3.7.3}Course of Values Induction}{63}{subsection.3.7.3}
\contentsline {subsection}{\numberline {3.7.4}Exercises}{64}{subsection.3.7.4}
\contentsline {section}{\numberline {3.8}Quantifiers}{65}{section.3.8}
\contentsline {subsection}{\numberline {3.8.1}The Existential Quantifier}{66}{subsection.3.8.1}
\contentsline {subsection}{\numberline {3.8.2}The Universal Quantifier}{66}{subsection.3.8.2}
\contentsline {subsection}{\numberline {3.8.3}The Negation of Quantified Propositions}{66}{subsection.3.8.3}
\contentsline {subsection}{\numberline {3.8.4}Multiple Quantifiers}{67}{subsection.3.8.4}
\contentsline {subsection}{\numberline {3.8.5}Exercises}{68}{subsection.3.8.5}
\contentsline {section}{\numberline {3.9}A Review of Methods of Proof}{69}{section.3.9}
\contentsline {subsection}{\numberline {3.9.1}Key Concepts in Proof}{70}{subsection.3.9.1}
\contentsline {subsection}{\numberline {3.9.2}The Art of Proving \(P \Rightarrow C\)}{70}{subsection.3.9.2}
\contentsline {subsection}{\numberline {3.9.3}Exercises}{72}{subsection.3.9.3}
\contentsline {chapter}{\numberline {4}More on Sets}{73}{chapter.4}
\contentsline {section}{\numberline {4.1}Methods of Proof for Sets}{73}{section.4.1}
\contentsline {subsection}{\numberline {4.1.1}Examples and Counterexamples}{73}{subsection.4.1.1}
\contentsline {subsection}{\numberline {4.1.2}Proof Using Venn Diagrams}{74}{subsection.4.1.2}
\contentsline {subsection}{\numberline {4.1.3}Proof using Set-membership Tables}{75}{subsection.4.1.3}
\contentsline {subsection}{\numberline {4.1.4}Proof Using Definitions}{75}{subsection.4.1.4}
\contentsline {subsection}{\numberline {4.1.5}Exercises}{77}{subsection.4.1.5}
\contentsline {section}{\numberline {4.2}Laws of Set Theory}{78}{section.4.2}
\contentsline {subsection}{\numberline {4.2.1}Tables of Laws}{78}{subsection.4.2.1}
\contentsline {subsection}{\numberline {4.2.2}Proof Using Previously Proven Theorems}{79}{subsection.4.2.2}
\contentsline {subsection}{\numberline {4.2.3}Proof Using the Indirect Method/\penalty \exhyphenpenalty {}Contradiction}{79}{subsection.4.2.3}
\contentsline {subsection}{\numberline {4.2.4}Exercises}{80}{subsection.4.2.4}
\contentsline {section}{\numberline {4.3}Minsets}{81}{section.4.3}
\contentsline {subsection}{\numberline {4.3.1}Definition of Minsets}{81}{subsection.4.3.1}
\contentsline {subsection}{\numberline {4.3.2}Properties of Minsets}{83}{subsection.4.3.2}
\contentsline {subsection}{\numberline {4.3.3}Exercises}{83}{subsection.4.3.3}
\contentsline {section}{\numberline {4.4}The Duality Principle}{84}{section.4.4}
\contentsline {subsection}{\numberline {4.4.1}}{84}{subsection.4.4.1}
\contentsline {subsection}{\numberline {4.4.2}Exercises}{85}{subsection.4.4.2}
\contentsline {chapter}{\numberline {5}Introduction to Matrix Algebra}{86}{chapter.5}
\contentsline {section}{\numberline {5.1}Basic Definitions and Operations}{86}{section.5.1}
\contentsline {subsection}{\numberline {5.1.1}Matrix Order and Equality}{86}{subsection.5.1.1}
\contentsline {subsection}{\numberline {5.1.2}Matrix Addition and Scalar Multiplication}{87}{subsection.5.1.2}
\contentsline {subsection}{\numberline {5.1.3}Matrix Multiplication}{88}{subsection.5.1.3}
\contentsline {subsection}{\numberline {5.1.4}Exercises}{90}{subsection.5.1.4}
\contentsline {section}{\numberline {5.2}Special Types of Matrices}{92}{section.5.2}
\contentsline {subsection}{\numberline {5.2.1}Diagonal Matrices}{92}{subsection.5.2.1}
\contentsline {subsection}{\numberline {5.2.2}The Identity Matrix and Matrix Inverses}{93}{subsection.5.2.2}
\contentsline {subsection}{\numberline {5.2.3}Exercises}{95}{subsection.5.2.3}
\contentsline {section}{\numberline {5.3}Laws of Matrix Algebra}{96}{section.5.3}
\contentsline {subsection}{\numberline {5.3.1}The Laws}{96}{subsection.5.3.1}
\contentsline {subsection}{\numberline {5.3.2}Commentary}{96}{subsection.5.3.2}
\contentsline {subsection}{\numberline {5.3.3}Exercises}{97}{subsection.5.3.3}
\contentsline {section}{\numberline {5.4}Matrix Oddities}{97}{section.5.4}
\contentsline {subsection}{\numberline {5.4.1}Dissimilarities with elementary algebra}{97}{subsection.5.4.1}
\contentsline {subsection}{\numberline {5.4.2}Exercises}{98}{subsection.5.4.2}
\contentsline {chapter}{\numberline {6}Relations}{100}{chapter.6}
\contentsline {section}{\numberline {6.1}Basic Definitions}{100}{section.6.1}
\contentsline {subsection}{\numberline {6.1.1}Relations between two sets}{100}{subsection.6.1.1}
\contentsline {subsection}{\numberline {6.1.2}Relations on a Set}{101}{subsection.6.1.2}
\contentsline {subsection}{\numberline {6.1.3}Composition of Relations}{102}{subsection.6.1.3}
\contentsline {subsection}{\numberline {6.1.4}Exercises}{103}{subsection.6.1.4}
\contentsline {section}{\numberline {6.2}Graphs of Relations on a Set}{103}{section.6.2}
\contentsline {subsection}{\numberline {6.2.1}Digraphs}{104}{subsection.6.2.1}
\contentsline {subsection}{\numberline {6.2.2}Exercises}{106}{subsection.6.2.2}
\contentsline {section}{\numberline {6.3}Properties of Relations}{106}{section.6.3}
\contentsline {subsection}{\numberline {6.3.1}Individual Properties}{106}{subsection.6.3.1}
\contentsline {subsection}{\numberline {6.3.2}Partial Orderings}{107}{subsection.6.3.2}
\contentsline {subsection}{\numberline {6.3.3}Equivalence Relations}{110}{subsection.6.3.3}
\contentsline {subsection}{\numberline {6.3.4}Exercises}{111}{subsection.6.3.4}
\contentsline {section}{\numberline {6.4}Matrices of Relations}{116}{section.6.4}
\contentsline {subsection}{\numberline {6.4.1}Representing a Relation with a Matrix}{116}{subsection.6.4.1}
\contentsline {subsection}{\numberline {6.4.2}Composition as Matrix Multiplication}{116}{subsection.6.4.2}
\contentsline {subsection}{\numberline {6.4.3}Exercises}{118}{subsection.6.4.3}
\contentsline {section}{\numberline {6.5}Closure Operations on Relations}{119}{section.6.5}
\contentsline {subsection}{\numberline {6.5.1}Transitive Closure}{119}{subsection.6.5.1}
\contentsline {subsection}{\numberline {6.5.2}Algorithms for computing transitive closure}{121}{subsection.6.5.2}
\contentsline {subsection}{\numberline {6.5.3}Exercises}{122}{subsection.6.5.3}
\contentsline {chapter}{\numberline {7}Functions}{124}{chapter.7}
\contentsline {section}{\numberline {7.1}Definition and Notation}{124}{section.7.1}
\contentsline {subsection}{\numberline {7.1.1}Fundamentals}{124}{subsection.7.1.1}
\contentsline {subsection}{\numberline {7.1.2}Functions of Two Variables}{126}{subsection.7.1.2}
\contentsline {subsection}{\numberline {7.1.3}SageMath Note}{126}{subsection.7.1.3}
\contentsline {subsection}{\numberline {7.1.4}Non-Functions}{127}{subsection.7.1.4}
\contentsline {subsection}{\numberline {7.1.5}Exercises}{127}{subsection.7.1.5}
\contentsline {section}{\numberline {7.2}Properties of Functions}{128}{section.7.2}
\contentsline {subsection}{\numberline {7.2.1}Properties}{128}{subsection.7.2.1}
\contentsline {subsection}{\numberline {7.2.2}Counting}{129}{subsection.7.2.2}
\contentsline {subsection}{\numberline {7.2.3}Exercises}{131}{subsection.7.2.3}
\contentsline {section}{\numberline {7.3}Function Composition}{132}{section.7.3}
\contentsline {subsection}{\numberline {7.3.1}Function Equality}{132}{subsection.7.3.1}
\contentsline {subsection}{\numberline {7.3.2}Function Composition}{133}{subsection.7.3.2}
\contentsline {subsection}{\numberline {7.3.3}Inverse Functions}{134}{subsection.7.3.3}
\contentsline {subsection}{\numberline {7.3.4}Exercises}{136}{subsection.7.3.4}
\contentsline {chapter}{\numberline {8}Recursion and Recurrence Relations}{139}{chapter.8}
\contentsline {section}{\numberline {8.1}The Many Faces of Recursion}{139}{section.8.1}
\contentsline {subsection}{\numberline {8.1.1}Binomial Coefficients}{139}{subsection.8.1.1}
\contentsline {subsection}{\numberline {8.1.2}Polynomials and Their Evaluation}{140}{subsection.8.1.2}
\contentsline {subsection}{\numberline {8.1.3}Recursive Searching - The Binary Search}{141}{subsection.8.1.3}
\contentsline {subsection}{\numberline {8.1.4}Recursively Defined Sequences}{142}{subsection.8.1.4}
\contentsline {subsection}{\numberline {8.1.5}Recursion}{143}{subsection.8.1.5}
\contentsline {subsection}{\numberline {8.1.6}Iteration}{143}{subsection.8.1.6}
\contentsline {subsection}{\numberline {8.1.7}Induction and Recursion}{144}{subsection.8.1.7}
\contentsline {subsection}{\numberline {8.1.8}Exercises}{145}{subsection.8.1.8}
\contentsline {section}{\numberline {8.2}Sequences}{145}{section.8.2}
\contentsline {subsection}{\numberline {8.2.1}Sequences and Ways They Are Defined}{145}{subsection.8.2.1}
\contentsline {subsection}{\numberline {8.2.2}A Fundamental Problem}{146}{subsection.8.2.2}
\contentsline {subsection}{\numberline {8.2.3}Exercises}{147}{subsection.8.2.3}
\contentsline {section}{\numberline {8.3}Recurrence Relations}{148}{section.8.3}
\contentsline {subsection}{\numberline {8.3.1}Definition and Terminology}{148}{subsection.8.3.1}
\contentsline {subsection}{\numberline {8.3.2}Solving Recurrence Relations}{149}{subsection.8.3.2}
\contentsline {subsection}{\numberline {8.3.3}Recurrence relations obtained from ``solutions''}{149}{subsection.8.3.3}
\contentsline {subsection}{\numberline {8.3.4}Solution of Nonhomogeneous Finite Order Linear Relations}{153}{subsection.8.3.4}
\contentsline {subsection}{\numberline {8.3.5}Exercises}{157}{subsection.8.3.5}
\contentsline {section}{\numberline {8.4}Some Common Recurrence Relations}{158}{section.8.4}
\contentsline {subsection}{\numberline {8.4.1}A First Basic Example}{158}{subsection.8.4.1}
\contentsline {subsection}{\numberline {8.4.2}An Analysis of the Binary Search Algorithm}{159}{subsection.8.4.2}
\contentsline {subsubsection}{\numberline {8.4.2.1}}{159}{subsubsection.8.4.2.1}
\contentsline {subsubsection}{\numberline {8.4.2.2}Review of Logarithms}{161}{subsubsection.8.4.2.2}
\contentsline {subsubsection}{\numberline {8.4.2.3}}{162}{subsubsection.8.4.2.3}
\contentsline {subsection}{\numberline {8.4.3}Analysis of Bubble Sort and Merge Sort}{163}{subsection.8.4.3}
\contentsline {subsection}{\numberline {8.4.4}Derangements}{164}{subsection.8.4.4}
\contentsline {subsection}{\numberline {8.4.5}Exercises}{166}{subsection.8.4.5}
\contentsline {section}{\numberline {8.5}Generating Functions}{166}{section.8.5}
\contentsline {subsection}{\numberline {8.5.1}Definition}{167}{subsection.8.5.1}
\contentsline {subsection}{\numberline {8.5.2}Solution of a Recurrence Relation Using Generating Functions}{167}{subsection.8.5.2}
\contentsline {subsection}{\numberline {8.5.3}Operations on Sequences}{170}{subsection.8.5.3}
\contentsline {subsection}{\numberline {8.5.4}Operations on Generating Functions}{172}{subsection.8.5.4}
\contentsline {subsection}{\numberline {8.5.5}Closed Form Expressions for Generating Functions}{174}{subsection.8.5.5}
\contentsline {subsection}{\numberline {8.5.6}Extra for Experts}{177}{subsection.8.5.6}
\contentsline {subsection}{\numberline {8.5.7}Exercises}{178}{subsection.8.5.7}
\contentsline {chapter}{\numberline {9}Graph Theory}{181}{chapter.9}
\contentsline {section}{\numberline {9.1}Graphs - General Introduction}{181}{section.9.1}
\contentsline {subsection}{\numberline {9.1.1}Definitions}{181}{subsection.9.1.1}
\contentsline {subsection}{\numberline {9.1.2}Subgraphs}{185}{subsection.9.1.2}
\contentsline {subsection}{\numberline {9.1.3}Graph Isomorphisms}{187}{subsection.9.1.3}
\contentsline {subsection}{\numberline {9.1.4}Next Steps}{190}{subsection.9.1.4}
\contentsline {subsection}{\numberline {9.1.5}Exercises}{190}{subsection.9.1.5}
\contentsline {section}{\numberline {9.2}Data Structures for Graphs}{192}{section.9.2}
\contentsline {subsection}{\numberline {9.2.1}Basic Data Structures}{192}{subsection.9.2.1}
\contentsline {subsection}{\numberline {9.2.2}Sage Graphs}{194}{subsection.9.2.2}
\contentsline {subsection}{\numberline {9.2.3}Exercises}{195}{subsection.9.2.3}
\contentsline {section}{\numberline {9.3}Connectivity}{196}{section.9.3}
\contentsline {subsection}{\numberline {9.3.1}Preliminaries}{196}{subsection.9.3.1}
\contentsline {subsection}{\numberline {9.3.2}Adjacency Matrix Method}{196}{subsection.9.3.2}
\contentsline {subsection}{\numberline {9.3.3}Breadth-First Search}{197}{subsection.9.3.3}
\contentsline {subsection}{\numberline {9.3.4}Graph Measurements}{201}{subsection.9.3.4}
\contentsline {subsection}{\numberline {9.3.5}SageMath Note - Graph Searching}{202}{subsection.9.3.5}
\contentsline {subsection}{\numberline {9.3.6}Exercises}{203}{subsection.9.3.6}
\contentsline {section}{\numberline {9.4}Traversals: Eulerian and Hamiltonian Graphs}{206}{section.9.4}
\contentsline {subsection}{\numberline {9.4.1}Eulerian Graphs}{206}{subsection.9.4.1}
\contentsline {subsection}{\numberline {9.4.2}Hamiltonian Graphs}{208}{subsection.9.4.2}
\contentsline {subsection}{\numberline {9.4.3}Exercises}{214}{subsection.9.4.3}
\contentsline {section}{\numberline {9.5}Graph Optimization}{215}{section.9.5}
\contentsline {subsection}{\numberline {9.5.1}Weighted Graphs}{216}{subsection.9.5.1}
\contentsline {subsection}{\numberline {9.5.2}The Traveling Salesman Problem}{216}{subsection.9.5.2}
\contentsline {subsection}{\numberline {9.5.3}Networks and the Maximum Flow Problem}{220}{subsection.9.5.3}
\contentsline {subsection}{\numberline {9.5.4}Other Graph Optimization Problems}{225}{subsection.9.5.4}
\contentsline {subsection}{\numberline {9.5.5}Exercises}{225}{subsection.9.5.5}
\contentsline {section}{\numberline {9.6}Planarity and Colorings}{227}{section.9.6}
\contentsline {subsection}{\numberline {9.6.1}Planar Graphs}{228}{subsection.9.6.1}
\contentsline {subsection}{\numberline {9.6.2}Graph Coloring}{231}{subsection.9.6.2}
\contentsline {subsection}{\numberline {9.6.3}Exercises}{234}{subsection.9.6.3}
\contentsline {subsection}{\numberline {9.6.4}Further Reading}{235}{subsection.9.6.4}
\contentsline {chapter}{\numberline {10}Trees}{236}{chapter.10}
\contentsline {section}{\numberline {10.1}What Is a Tree?}{236}{section.10.1}
\contentsline {subsection}{\numberline {10.1.1}Definition}{236}{subsection.10.1.1}
\contentsline {subsection}{\numberline {10.1.2}Conditions for a graph to be a tree}{238}{subsection.10.1.2}
\contentsline {subsection}{\numberline {10.1.3}Exercises}{239}{subsection.10.1.3}
\contentsline {section}{\numberline {10.2}Spanning Trees}{239}{section.10.2}
\contentsline {subsection}{\numberline {10.2.1}Motivation}{239}{subsection.10.2.1}
\contentsline {subsection}{\numberline {10.2.2}Definition}{240}{subsection.10.2.2}
\contentsline {subsection}{\numberline {10.2.3}Prim's Algorithm}{241}{subsection.10.2.3}
\contentsline {subsection}{\numberline {10.2.4}Exercises}{244}{subsection.10.2.4}
\contentsline {section}{\numberline {10.3}Rooted Trees}{246}{section.10.3}
\contentsline {subsection}{\numberline {10.3.1}Definition and Terminology}{246}{subsection.10.3.1}
\contentsline {subsection}{\numberline {10.3.2}Kruskal's Algorithm}{248}{subsection.10.3.2}
\contentsline {subsection}{\numberline {10.3.3}SageMath Note - Implementation of Kruskal's Algorithm}{249}{subsection.10.3.3}
\contentsline {subsection}{\numberline {10.3.4}Exercises}{251}{subsection.10.3.4}
\contentsline {section}{\numberline {10.4}Binary Trees}{252}{section.10.4}
\contentsline {subsection}{\numberline {10.4.1}Definition of a binary tree}{252}{subsection.10.4.1}
\contentsline {subsection}{\numberline {10.4.2}Traversals of Binary Trees}{254}{subsection.10.4.2}
\contentsline {subsection}{\numberline {10.4.3}Expression Trees}{256}{subsection.10.4.3}
\contentsline {subsection}{\numberline {10.4.4}Counting Binary Trees}{259}{subsection.10.4.4}
\contentsline {subsection}{\numberline {10.4.5}SageMath Note - Power Series}{260}{subsection.10.4.5}
\contentsline {subsection}{\numberline {10.4.6}Exercises}{261}{subsection.10.4.6}
\contentsline {chapter}{\numberline {11}Algebraic Structures}{262}{chapter.11}
\contentsline {section}{\numberline {11.1}Operations}{262}{section.11.1}
\contentsline {subsection}{\numberline {11.1.1}What is an Operation?}{263}{subsection.11.1.1}
\contentsline {subsection}{\numberline {11.1.2}Properties of Operations}{263}{subsection.11.1.2}
\contentsline {subsection}{\numberline {11.1.3}Operation Tables}{265}{subsection.11.1.3}
\contentsline {subsection}{\numberline {11.1.4}Exercises}{265}{subsection.11.1.4}
\contentsline {section}{\numberline {11.2}Algebraic Systems}{265}{section.11.2}
\contentsline {subsection}{\numberline {11.2.1}Monoids at Two Levels}{266}{subsection.11.2.1}
\contentsline {subsection}{\numberline {11.2.2}Levels of Abstraction}{267}{subsection.11.2.2}
\contentsline {subsubsection}{\numberline {11.2.2.1}The Concrete Level}{267}{subsubsection.11.2.2.1}
\contentsline {subsubsection}{\numberline {11.2.2.2}The Axiomatic Level}{267}{subsubsection.11.2.2.2}
\contentsline {subsubsection}{\numberline {11.2.2.3}The Universal Level}{267}{subsubsection.11.2.2.3}
\contentsline {subsection}{\numberline {11.2.3}Groups}{268}{subsection.11.2.3}
\contentsline {subsection}{\numberline {11.2.4}Exercises}{269}{subsection.11.2.4}
\contentsline {section}{\numberline {11.3}Some General Properties of Groups}{270}{section.11.3}
\contentsline {subsection}{\numberline {11.3.1}First Theorems}{270}{subsection.11.3.1}
\contentsline {subsection}{\numberline {11.3.2}Exponents}{273}{subsection.11.3.2}
\contentsline {subsection}{\numberline {11.3.3}Exercises}{274}{subsection.11.3.3}
\contentsline {section}{\numberline {11.4}Greatest Common Divisors and the Integers Modulo \(n\)}{275}{section.11.4}
\contentsline {subsection}{\numberline {11.4.1}Greatest Common Divisors}{275}{subsection.11.4.1}
\contentsline {subsection}{\numberline {11.4.2}The Euclidean Algorithm}{276}{subsection.11.4.2}
\contentsline {subsection}{\numberline {11.4.3}Modular Arithmetic}{279}{subsection.11.4.3}
\contentsline {subsection}{\numberline {11.4.4}Properties of Modular Arithmetic}{280}{subsection.11.4.4}
\contentsline {subsection}{\numberline {11.4.5}SageMath Note - Modular Arithmetic}{281}{subsection.11.4.5}
\contentsline {subsection}{\numberline {11.4.6}Exercises}{282}{subsection.11.4.6}
\contentsline {section}{\numberline {11.5}Subsystems}{283}{section.11.5}
\contentsline {subsection}{\numberline {11.5.1}Definition}{283}{subsection.11.5.1}
\contentsline {subsection}{\numberline {11.5.2}Subgroups}{284}{subsection.11.5.2}
\contentsline {subsection}{\numberline {11.5.3}Sage Note - Applying the condition for a subgroup of a finite group}{285}{subsection.11.5.3}
\contentsline {subsection}{\numberline {11.5.4}Cyclic Subgroups}{286}{subsection.11.5.4}
\contentsline {subsection}{\numberline {11.5.5}Exercises}{286}{subsection.11.5.5}
\contentsline {section}{\numberline {11.6}Direct Products}{288}{section.11.6}
\contentsline {subsection}{\numberline {11.6.1}Definition}{288}{subsection.11.6.1}
\contentsline {subsection}{\numberline {11.6.2}Direct Products of Groups}{289}{subsection.11.6.2}
\contentsline {subsection}{\numberline {11.6.3}Exercises}{293}{subsection.11.6.3}
\contentsline {section}{\numberline {11.7}Isomorphisms}{294}{section.11.7}
\contentsline {subsection}{\numberline {11.7.1}Group Isomorphisms}{296}{subsection.11.7.1}
\contentsline {subsection}{\numberline {11.7.2}Conditions for groups to not be isomorphic}{298}{subsection.11.7.2}
\contentsline {subsection}{\numberline {11.7.3}Exercises}{299}{subsection.11.7.3}
\contentsline {chapter}{\numberline {12}More Matrix Algebra}{300}{chapter.12}
\contentsline {section}{\numberline {12.1}Systems of Linear Equations}{300}{section.12.1}
\contentsline {subsection}{\numberline {12.1.1}Solutions}{300}{subsection.12.1.1}
\contentsline {subsection}{\numberline {12.1.2}Elementary Operations on Equations}{301}{subsection.12.1.2}
\contentsline {subsection}{\numberline {12.1.3}Transition to Matrices}{303}{subsection.12.1.3}
\contentsline {subsection}{\numberline {12.1.4}Elementary Row Operations}{303}{subsection.12.1.4}
\contentsline {subsection}{\numberline {12.1.5}The Gauss-Jordan Algorithm}{306}{subsection.12.1.5}
\contentsline {subsection}{\numberline {12.1.6}SageMath Note - Matrix Reduction}{307}{subsection.12.1.6}
\contentsline {subsection}{\numberline {12.1.7}Exercises}{308}{subsection.12.1.7}
\contentsline {section}{\numberline {12.2}Matrix Inversion}{309}{section.12.2}
\contentsline {subsection}{\numberline {12.2.1}Developing the Process}{309}{subsection.12.2.1}
\contentsline {subsection}{\numberline {12.2.2}The General Method for Computing Inverses}{311}{subsection.12.2.2}
\contentsline {subsection}{\numberline {12.2.3}Exercises}{312}{subsection.12.2.3}
\contentsline {section}{\numberline {12.3}An Introduction to Vector Spaces}{313}{section.12.3}
\contentsline {subsection}{\numberline {12.3.1}Motivation for the study of vector spaces}{313}{subsection.12.3.1}
\contentsline {subsection}{\numberline {12.3.2}Vector Spaces}{313}{subsection.12.3.2}
\contentsline {subsection}{\numberline {12.3.3}Exercises}{318}{subsection.12.3.3}
\contentsline {section}{\numberline {12.4}The Diagonalization Process}{320}{section.12.4}
\contentsline {subsection}{\numberline {12.4.1}Eigenvalues and Eigenvectors}{320}{subsection.12.4.1}
\contentsline {subsection}{\numberline {12.4.2}Diagonalization}{322}{subsection.12.4.2}
\contentsline {subsection}{\numberline {12.4.3}SageMath Note - Diagonalization}{326}{subsection.12.4.3}
\contentsline {subsection}{\numberline {12.4.4}Exercises}{327}{subsection.12.4.4}
\contentsline {section}{\numberline {12.5}Some Applications}{328}{section.12.5}
\contentsline {subsection}{\numberline {12.5.1}Diagonalization}{328}{subsection.12.5.1}
\contentsline {subsection}{\numberline {12.5.2}Path Counting}{330}{subsection.12.5.2}
\contentsline {subsection}{\numberline {12.5.3}Matrix Calculus}{331}{subsection.12.5.3}
\contentsline {subsection}{\numberline {12.5.4}SageMath Note - Matrix Exponential}{332}{subsection.12.5.4}
\contentsline {subsection}{\numberline {12.5.5}Exercises}{332}{subsection.12.5.5}
\contentsline {section}{\numberline {12.6}Linear Equations over the Integers Mod 2}{334}{section.12.6}
\contentsline {subsection}{\numberline {12.6.1}Row reduction mod 2}{334}{subsection.12.6.1}
\contentsline {subsection}{\numberline {12.6.2}Exercises}{335}{subsection.12.6.2}
\contentsline {chapter}{\numberline {13}Boolean Algebra}{337}{chapter.13}
\contentsline {section}{\numberline {13.1}Posets Revisited}{339}{section.13.1}
\contentsline {subsection}{\numberline {13.1.1}Exercises}{341}{subsection.13.1.1}
\contentsline {section}{\numberline {13.2}Lattices}{343}{section.13.2}
\contentsline {subsection}{\numberline {13.2.1}Exercises}{344}{subsection.13.2.1}
\contentsline {section}{\numberline {13.3}Boolean Algebras}{345}{section.13.3}
\contentsline {subsection}{\numberline {13.3.1}Exercises}{347}{subsection.13.3.1}
\contentsline {section}{\numberline {13.4}Atoms of a Boolean Algebra}{348}{section.13.4}
\contentsline {subsection}{\numberline {13.4.1}Exercises}{351}{subsection.13.4.1}
\contentsline {section}{\numberline {13.5}Finite Boolean Algebras as \(n\)-tuples of 0's and 1's}{352}{section.13.5}
\contentsline {subsection}{\numberline {13.5.1}Exercises}{353}{subsection.13.5.1}
\contentsline {section}{\numberline {13.6}Boolean Expressions}{353}{section.13.6}
\contentsline {subsection}{\numberline {13.6.1}Exercises}{357}{subsection.13.6.1}
\contentsline {section}{\numberline {13.7}A Brief Introduction to Switching Theory and Logic Design}{357}{section.13.7}
\contentsline {subsection}{\numberline {13.7.1}Exercises}{362}{subsection.13.7.1}
\contentsline {chapter}{\numberline {14}Monoids and Automata}{365}{chapter.14}
\contentsline {section}{\numberline {14.1}Monoids}{365}{section.14.1}
\contentsline {subsection}{\numberline {14.1.1}Exercises}{367}{subsection.14.1.1}
\contentsline {section}{\numberline {14.2}Free Monoids and Languages}{368}{section.14.2}
\contentsline {subsection}{\numberline {14.2.1}Exercises}{373}{subsection.14.2.1}
\contentsline {section}{\numberline {14.3}Automata, Finite-State Machines}{374}{section.14.3}
\contentsline {subsection}{\numberline {14.3.1}Exercises}{379}{subsection.14.3.1}
\contentsline {section}{\numberline {14.4}The Monoid of a Finite-State Machine}{379}{section.14.4}
\contentsline {subsection}{\numberline {14.4.1}Exercises}{382}{subsection.14.4.1}
\contentsline {section}{\numberline {14.5}The Machine of a Monoid}{382}{section.14.5}
\contentsline {subsection}{\numberline {14.5.1}Exercises}{383}{subsection.14.5.1}
\contentsline {chapter}{\numberline {15}Group Theory and Applications}{385}{chapter.15}
\contentsline {section}{\numberline {15.1}Cyclic Groups}{385}{section.15.1}
\contentsline {subsection}{\numberline {15.1.1}Exercises}{391}{subsection.15.1.1}
\contentsline {section}{\numberline {15.2}Cosets and Factor Groups}{391}{section.15.2}
\contentsline {subsection}{\numberline {15.2.1}Exercises}{396}{subsection.15.2.1}
\contentsline {section}{\numberline {15.3}Permutation Groups}{397}{section.15.3}
\contentsline {subsection}{\numberline {15.3.1}The Symmetric Groups}{397}{subsection.15.3.1}
\contentsline {subsection}{\numberline {15.3.2}Cycle Notation}{399}{subsection.15.3.2}
\contentsline {subsection}{\numberline {15.3.3}Parity of Permutations and the Alternating Group}{401}{subsection.15.3.3}
\contentsline {subsection}{\numberline {15.3.4}Dihedral Groups}{403}{subsection.15.3.4}
\contentsline {subsection}{\numberline {15.3.5}Exercises}{405}{subsection.15.3.5}
\contentsline {section}{\numberline {15.4}Normal Subgroups and Group Homomorphisms}{406}{section.15.4}
\contentsline {subsection}{\numberline {15.4.1}Normal Subgroups}{406}{subsection.15.4.1}
\contentsline {subsection}{\numberline {15.4.2}Homomorphisms}{409}{subsection.15.4.2}
\contentsline {subsection}{\numberline {15.4.3}Exercises}{412}{subsection.15.4.3}
\contentsline {section}{\numberline {15.5}Coding Theory, Group Codes}{413}{section.15.5}
\contentsline {subsection}{\numberline {15.5.1}Error Detection}{414}{subsection.15.5.1}
\contentsline {subsection}{\numberline {15.5.2}Error Correction}{415}{subsection.15.5.2}
\contentsline {subsection}{\numberline {15.5.3}Exercises}{417}{subsection.15.5.3}
\contentsline {chapter}{\numberline {16}An Introduction to Rings and Fields}{419}{chapter.16}
\contentsline {section}{\numberline {16.1}Rings, Basic Definitions and Concepts}{419}{section.16.1}
\contentsline {subsection}{\numberline {16.1.1}Basic Definitions}{419}{subsection.16.1.1}
\contentsline {subsection}{\numberline {16.1.2}Direct Products of Rings}{420}{subsection.16.1.2}
\contentsline {subsection}{\numberline {16.1.3}Multiplicative Inverses in Rings}{421}{subsection.16.1.3}
\contentsline {subsection}{\numberline {16.1.4}More universal concepts, isomorphisms and subrings}{422}{subsection.16.1.4}
\contentsline {subsection}{\numberline {16.1.5}Integral Domains and Zero Divisors}{424}{subsection.16.1.5}
\contentsline {subsection}{\numberline {16.1.6}Exercises}{425}{subsection.16.1.6}
\contentsline {section}{\numberline {16.2}Fields}{427}{section.16.2}
\contentsline {subsection}{\numberline {16.2.1}Exercises}{430}{subsection.16.2.1}
\contentsline {section}{\numberline {16.3}Polynomial Rings}{431}{section.16.3}
\contentsline {subsection}{\numberline {16.3.1}Exercises}{436}{subsection.16.3.1}
\contentsline {section}{\numberline {16.4}Field Extensions}{437}{section.16.4}
\contentsline {subsection}{\numberline {16.4.1}Exercises}{439}{subsection.16.4.1}
\contentsline {section}{\numberline {16.5}Power Series}{440}{section.16.5}
\contentsline {subsection}{\numberline {16.5.1}Definition}{440}{subsection.16.5.1}
\contentsline {subsection}{\numberline {16.5.2}Properties, Units}{442}{subsection.16.5.2}
\contentsline {subsection}{\numberline {16.5.3}Exercises}{444}{subsection.16.5.3}
\vspace {\normalbaselineskip }
\contentsline {chapter}{\numberline {A}Algorithms}{446}{appendix.A}
\contentsline {section}{\numberline {A.1}An Introduction to Algorithms}{446}{section.A.1}
\contentsline {subsection}{\numberline {A.1.1}Assignments}{446}{subsection.A.1.1}
\contentsline {subsection}{\numberline {A.1.2}Conditional steps}{447}{subsection.A.1.2}
\contentsline {subsection}{\numberline {A.1.3}Loops}{447}{subsection.A.1.3}
\contentsline {subsection}{\numberline {A.1.4}Exercises}{449}{subsection.A.1.4}
\contentsline {section}{\numberline {A.2}The Invariant Relation Theorem}{450}{section.A.2}
\contentsline {subsection}{\numberline {A.2.1}Two Exponentiation Algorithms}{450}{subsection.A.2.1}
\contentsline {subsection}{\numberline {A.2.2}Proving the correctness of the fast algorithm}{451}{subsection.A.2.2}
\contentsline {subsection}{\numberline {A.2.3}Exercises}{452}{subsection.A.2.3}
\contentsline {chapter}{\numberline {B}Python and SageMath}{453}{appendix.B}
\contentsline {section}{\numberline {B.1}Python Iterators}{453}{section.B.1}
\contentsline {subsection}{\numberline {B.1.1}Counting Subsets}{453}{subsection.B.1.1}
\contentsline {section}{\numberline {B.2}Dictionaries}{454}{section.B.2}
\contentsline {subsection}{\numberline {B.2.1}Colors of Fruits}{454}{subsection.B.2.1}
\contentsline {chapter}{\numberline {C}Determinants}{457}{appendix.C}
\contentsline {section}{\numberline {C.1}Definition}{457}{section.C.1}
\contentsline {section}{\numberline {C.2}Computation}{459}{section.C.2}
\contentsline {chapter}{\numberline {D}Hints and Solutions to Selected Exercises}{461}{appendix.D}
\contentsline {chapter}{\numberline {E}Notation}{541}{appendix.E}
\contentsline {chapter}{References}{545}{appendix*.1061}
\contentsline {chapter}{Index}{548}{section*.1062}
\contentsfinish