Discrete Mathematics with Coding

This book, for a first undergraduate course in Discrete Mathematics, systematically exploits the relationship between discrete mathematics and computer programming. Unlike most discrete mathematics texts focusing on one of the other, the book explores the rich and important connection between these two disciplines and shows how each discipline reinforces and enhances the other. The coding language used is VBA Excel. The language is easy to learn, has intuitive commands, and the reader can develop interesting programs from the outset. Additionally, the spreadsheet platform in Excel makes for convenient and transparent data input and output and provides a powerful venue for complex data manipulation. Manipulating data is greatly simplified using spreadsheet features and visualizing the data can make programming and debugging easier. Features * Introduces coding in VBA Excel assuming no previous coding experience. * Develops programs in Linear Analysis, Logic, Combinatorics, Probability, and Number Theory. * Contains over 90 fully tested and debugged programs. The code for these is as well as the exercises is available on the author's website. * Contains numerous examples that gradually introduce the reader to coding techniques. * Includes programs that solve systems of linear equations, linear programming problems, combinatorial problems, Venn diagram problems and programs that produce truth tables from logic statements and logic statements from switching and gate circuits, encrypt and decrypt messages and simulate probability experiments. Cover Half Title Series Page Title Page Copyright Page Dedication Contents Preface I. Essentials of VBA 1. Introduction 1.1. Modules, Subs, and Functions 1.2. Data Output and Input OutputExample, InputExample 1.3. Cell Characteristics CellAttributes 1.4. Number Formats NumberFormat 1.5. Passing Arguments SwitchIntegers 1.6. User-Defined Data Types 1.7. Command Buttons 1.8. Spin Buttons MixColors 1.9. Exercises 2. VBA Operators 2.1. Arithmetic Operators 2.2. Comparison Operators 2.3. Logical Operators 2.4. Exercises 3. Conditional Statements 3.1. The If Then Else Statement Grade 3.2. The Select Case Statement CycleEdges 3.3. Exercises 4. Loops 4.1. The For Next Statement 4.2. The Do While Loop ReduceFraction, NumberOfTerms 4.3. The Do Until Loop 4.4. Exit Statements 4.5. Finding the Zeros of a Function FindZero, FunctionVal 4.6. Exercises 5. Arrays 5.1. Declaring Arrays 5.2. First and Last Indices of an Array 5.3. Passing and Returning Arrays 5.4. Variants and the Array Function 5.5. Sorting Numeric Data NumericSort 5.6. Finding Nearest Numbers NearestNumbers 5.7. Stacks Push, Pop 5.8. Exercises 6. String Functions 6.1. The VBA Concatenation Operator 6.2. The VBA Extraction Function Mid 6.3. The VBA ASCII Functions Asc and Chr 6.4. VBA Data Conversion Functions CStr, CInt, CLng, CDbl 6.5. The VBA Function Replace 6.6. The VBA Function InStr 6.7. The VBA Operator Like 6.8. The VBA Functions Join and Split 6.9. Exercises 7. Grids 7.1. Setting up a Grid MakeGrid 7.2. The Grid as a Torus TorusPoint 7.3. Installing Coordinates in a Grid InstallCoord 7.4. Sieve of Erastothenes Sieve 7.5. A Changing Rectangle CollapseExpandRectangle, Delay 7.6. Table Sum Game TableSum 7.7. Finding the Nearest Cells NearestCells 7.8. A Growing Spiral Spiral 7.9. Billiard Ball BilliardBall 7.10. Exercises 8. Recursion 8.1. The Factorial Function FactRecursive 8.2. Binary Trees Binarytree 8.3. The Tower of Hanoi HanoiTower *8.4. A Complex Arithmetic Calculator ComplexCalc *8.5. A Polynomial Calculator PolyCalc 8.6. Exercises 9. Charts and Graphs 9.1. Frequency Charts LetterFreqency 9.2. Drawing Lines GraphPoly 9.3. Intersection of Two Lines LineIntersect 9.4. Projection of a Point onto a Line Point2Line 9.5. The Incenter of a Triangle Incenter 9.6. Function Graphs GraphFunction 9.7. Fitting a Line to Data Least Squares 9.8. Graphing Parametric Curves GraphCurve 9.9. A Fractal Game ChaosTriangleGame 9.10. Overlaying Graphs PredatorPrey 9.11. Bezier Curves Bezier 9.12. Exercises 10. Random Numbers 10.1. The VBA Function Rnd 10.2. A Nonsense Generator Nonsense 10.3. Area under a Curve AreaUnderCurve 10.4. A Simple Random Walk Random Walk 10.5. Spreading Disease SpreadOfDisease 10.6. Particle Swarm Optimization ParticleSwarmOpt 10.7. A Randomly Sprouting Plant SproutWither 10.8. Random Walk of a Rotating Pattern RotateAndMove 10.9. Random Tessellations RandomTess 10.10. Maxwell's Entropy Demon MaxwellsDemon 10.11. Multi-Random Walk RandomWalks 10.12. A Shedding Organism RandomWalkShed 10.13. A Splitting Organism RandomWalkSplit 10.14. Random Mazes Maze 10.15. Exercises II. Linear Analysis 11. Linear Equations 11.1. Matrix Arrays MatrixIn, MatrixOut 11.2. Systems of Linear Equations 11.3. The Gauss Jordan Method 11.4. Row Operations with VBA RowOperations 11.5. Row Echelon Form with VBA RowEchelon 11.6. Exercises 12. Linear Programming 12.1. Linear Inequalities and Feasible Regions 12.2. Formulation of the General LP Problem 12.3. Graphic Solution for Two Dimensions 12.4. The Simplex Method 12.5. Standard Max Problem with VBA Simplex 12.6. Duality and the Standard LP Min Problem 12.7. Solving Nonstandard LP Problems 12.8. Exercises 13. Matrix Algebra 13.1. Matrix Scalar Multiplication ScalarMult 13.2. Matrix Addition and Substraction AddSubMat 13.3. Matrix Multiplication MultMat 13.4. Inverse of a Matrix MatrixInversion 13.5. Matrix Powers PowerMat 13.6. Input-Output Models IOModel 13.7. Polynomial of Best Fit PolyFitData *13.8. The Barnsley Fern AffineIterations *13.9. A Matrix Calculator MatrixCalculator 13.10. Exercises 14. Determinants 14.1. Definition and Properties 14.2. Determinants Using VBA DetEchelon, DetRecursive 14.3. Cramer's Rule CramersRule 14.4. Collinear and Coplanar Points Using Determinants 14.5. Areas and Volumes Using Determinants 14.6. Circumscribing a Triangle Circumcenter 14.7. Exercises III. Logic 15. Propositional Logic 15.1. Compound Statements 15.2. Equivalent Statements and Laws of Logic 15.3. Truth Tables with VBA Stmt2TruthTable 15.4. Statement from a Truth Table TruthTable2DisjNormal 15.5. Valid Arguments 15.6. Exercises 16. Switching Circuits 16.1. Introduction 16.2. Series and Parallel Circuits 16.3. Equivalent Circuits 16.4. Circuit Expressions with VBA SwitchCircuitExpr 16.5. Exercises 17. Gates and Logic Circuits 17.1. The Gates NOT, AND, OR 17.2. The Gates XOR, NAND, NOR 17.3. Logic Circuit Expressions with VBA LogicCircuitExpr 17.4. Half Adders 17.5. VBA Simulation of a Half Adder 17.6. Full Adders 17.7. VBA Simulation of a 4-bit Adder FullAdder4 17.8. Exercises IV. Combinatorics 18. Sets 18.1. Introduction 18.2. The Union of Two Sets Union 18.3. The Intersection of Two Sets Intersection, Card 18.4. The Complement of a Set Complement 18.5. Extensions to Three or More Sets 18.6. Calculating Sets with VBA SetCalculator 18.7. Venn Diagram Components with VBA VennParts 18.8. Laws of Set Equality 18.9. Laws of Set Inclusion 18.10. Cartesian Products, Relations, and Functions 18.11. Exercises 19. Counting 19.1. The Addition Principle *19.2. Venn Solutions with VBA Venn3Solver 19.3. The Multiplication Principle 19.4. Permutations 19.5. Generating Permutations with VBA Permutations 19.6. Combinations 19.7. Generating Combinations with VBA Combinations 19.8. Traveling Salesman Problem TravelSales *19.9. Permutation Algebra MultPerm, InvPerm, PowerPerm *19.10. Permutation Cycles PermCycles 19.11. Exercises V. Probability 20. Probability 20.1. Sample Spaces, Probabilities, and Events 20.2. Throwing a Pair of Fair Dice DiceRelativFreq 20.3. Poker Hands PokerHands 20.4. Drawing Balls from an Urn 20.5. Simulation of the Binomial Distribution GaltonsBoard 20.6. Conditional Probability 20.7. Bayes' Theorem 20.8. Disease Testing TruePosTrueNeg 20.9. Independence 20.10. Exercises 21. Random Variables 21.1. Examples of Random Variables 21.2. Expected Value of a Random Variable 21.3. Properties of Expectation 21.4. Variance and Standard Deviation of a Random Variable 21.5. The Law of Large Numbers 21.6. Central Limit Theorem 21.7. Exercises 22. Markov Chains 22.1. Transition Probabilities 22.2. Higher Order Transition Probabilities 22.3. The Initial Distribution of a Markov Chain 22.4. The Steady State Vector 22.5. Position Dependent Random Walk PositionRandWalk 22.6. Polya Urn Model PolyaUrn 22.7. Ehrenfest Diffusion Model EhrenfestUrns 22.8. Stepping Stone Model SteppingStone 22.9. Exercises VI. Properties of Numbers 23. Divisibility and Prime Numbers 23.1. The Division Algorithm 23.2. Number Bases BaseToBase *23.3. Wolfram's Binary Rules WolframRules 23.4. Greatest Common Divisor GCD 23.5. Prime Divisibility Property 23.6. The Fundamental Theorem of Arithmetic 23.7. Prime Decomposition with VBA PrimeDecomposition 23.8. Exercises 24. Congruence 24.1. Definition and Basic Properties 24.2. Congruence Arithmetic 24.3. Fermat's Little Theorem 24.4. Remainder of a Product ProductRmdr 24.5. Remainder of a Power PowerRmdr 24.6. Solving Congruence Equations CongruenceSolver *24.7. Modular Arithmetic CongruenceTables 24.8. Exercises 25. Cryptography 25.1. Encoding the Alphabet 25.2. Caesar's Shift Cipher 25.3. Zigzag Cipher 25.4. Spiral Cipher SpiralCipher 25.5. Affine Cipher AffCipher 25.6. Permutation Cipher PermCipher 25.7. Vigenère Cipher VCipher 25.8. Four Square Cipher FourSquare 25.9. Matrix Cipher MatrixCipher 25.10. The RSA Algorithm RSACipher 25.11. Exercises 26. The Enigma Machine 26.1. Description 26.2. Implementation in VBA EnigmaCipher 26.3. A Closer Look at the Mathematics 27. Large Numbers 27.1. Arithmetic of Large Positive Integers 27.2. Arithmetic of Large Signed Integers 27.3. Arithmetic of Large Decimals *27.4. A Large Scale Calculator LargeCalc 27.5. Exercises Index This book, for a first undergraduate course in Discrete Mathematics, systematically exploits the relationship between discrete mathematics and computer programming. Unlike most discrete mathematics texts focusing on one of the other, the book explores the rich and important connection between these two disciplines and shows how each discipline reinforces and enhances the other.The mathematics in the book is self-contained, requiring only a good background in precalculus and some mathematical maturity. New mathematical topics are introduced as needed.The coding language used is VBA Excel. The language is easy to learn, has intuitive commands, and the reader can develop interesting programs from the outset. Additionally, the spreadsheet platform in Excel makes for convenient and transparent data input and output and provides a powerful venue for complex data manipulation. Manipulating data is greatly simplified using spreadsheet features and visualizing the data can make programming and debugging easier. The VBA language is seamlessly integrated into the spreadsheet environment with no other resources required. Furthermore, as some of the modules in the book show, intricate patterns, graphs, and animation in the form of moving cells is possible. Features Introduces coding in VBA Excel assuming no previous coding experience. Develops programs in Linear Analysis, Logic, Combinatorics, Probability, and Number Theory. Contains over 90 fully tested and debugged programs. The code for these is as well as the exercises is available on the author's website. Contains numerous examples that gradually introduce the reader to coding techniques. Includes programs that solve systems of linear equations, linear programming problems, combinatorial problems, Venn diagram problems and programs that produce truth tables from logic statements and logic statements from switching and gate circuits, encrypt and decrypt messages and simulate probability experiments. "The book is an attempt to integrate coding with discrete mathematics in the hopes that each discipline will complement the other and allow for a fuller treatment of concrete mathematical computations. Mathematics provides fertile ground for interesting, useful, and certainly nontrivial programs"-- Provided by publisher