Mathematical structures for computer science
Subtitle: discrete mathematics and its applications
By: Judith L. Gersting, Indiana University-Purdue University at Indianapolis
Edition: 7th edition.
Publisher: W.H. Freeman and Company, a Macmillian Higher Education Company
Published: 2014
Place of publication: New York, NY
Language: eng
Number of pages: 969
ISBN-13: 9781429215107
Subjects: Mathematics; Mathematical models; Computer science
Notes: Includes index.
Table of contents: label: Chapter 1
title: Formal Logic
pagenum: 1; label: 1.1
title: Statements, Symbolic Representation, and Tautologies
pagenum: 2; title: Connectives and Truth Values
pagenum: 2; title: Tautologies
pagenum: 8; title: Logical Connectives in the Real World
pagenum: 10; title: An Algorithm
pagenum: 12; title: Special Interest Page: Can "And" Ever Be "Or"?
pagenum: 15; title: Section 1.1 Review
pagenum: 16; title: Exercises 1.1
pagenum: 16; label: 1.2
title: Propositional Logic
pagenum: 25; title: Valid Arguments
pagenum: 25; title: Derivation Rules for Propositional Logic
pagenum: 28; title: Deduction Method and Other Rules
pagenum: 32; title: Verbal Arguments
pagenum: 33; title: Section 1.2 Review
pagenum: 35; title: Exercises 1.2
pagenum: 35; label: 1.3
title: Quantifiers, Predicates, and Validity
pagenum: 39; title: Quantifiers and Predicates
pagenum: 39; title: Translation
pagenum: 42; title: Validity
pagenum: 48; title: Section 1.3 Review
pagenum: 50; title: Exercises 1.3
pagenum: 50; label: 1.4
title: Predicate Logic
pagenum: 58; title: Derivation Rules for Predicate Logic
pagenum: 58; title: Universal Instantiation
pagenum: 59; title: Existential Instantiation
pagenum: 60; title: Universal Generalization
pagenum: 61; title: Existential Generalization
pagenum: 62; title: More Work with Rules
pagenum: 62; title: Verbal Arguments
pagenum: 67; title: Conclusion
pagenum: 68; title: Section 1.4 Review
pagenum: 69; title: Exercises 1.4
pagenum: 69; label: 1.5
title: Logic Programming
pagenum: 73; title: Prolog
pagenum: 73; title: Horn Clauses and Resolution
pagenum: 75; title: Recursion
pagenum: 79; title: Expert Systems
pagenum: 81; title: Section 1.5 Review
pagenum: 82; title: Exercises 1.5
pagenum: 82; label: 1.6
title: Proof of Correctness
pagenum: 84; title: Assertions
pagenum: 85; title: Assignment Rule
pagenum: 87; title: Conditional Rule
pagenum: 90; title: Section 1.6 Review
pagenum: 92; title: Exercises 1.6
pagenum: 92; title: Chapter 1 Review
pagenum: 95; title: On the Computer
pagenum: 96; label: Chapter 2
title: Proofs, Induction, and Number Theory
pagenum: 97; label: 2.1
title: Proof Techniques
pagenum: 98; title: Theorems and Informal Proofs
pagenum: 98; title: To Prove or Not to Prove
pagenum: 99; title: Exhaustive Proof
pagenum: 100; title: Direct Proof
pagenum: 101; title: Contraposition
pagenum: 103; title: Contradiction
pagenum: 104; title: Serendipity
pagenum: 106; title: Common Definitions
pagenum: 107; title: Section 2.1 Review
pagenum: 107; title: Exercises 2.1
pagenum: 107; label: 2.2
title: Induction
pagenum: 110; title: First Principle of Induction
pagenum: 110; title: Proofs by Mathematical Induction
pagenum: 112; title: Second Principle of Induction
pagenum: 118; title: Section 2.2 Review
pagenum: 122; title: Exercises 2.2
pagenum: 122; label: 2.3
title: More on Proof of Correctness
pagenum: 129; title: Loop Rule
pagenum: 129; title: Euclidean Algorithm
pagenum: 133; title: Special Interest Page: Making Safer Software
pagenum: 136; title: Section 2.3 Review
pagenum: 137; title: Exercises 2.3
pagenum: 137; label: 2.4
title: Number Theory
pagenum: 143; title: The Fundamental Theorem of Arithmetic
pagenum: 144; title: More on Prime Numbers
pagenum: 148; title: Euler Phi Function
pagenum: 149; title: Section 2.4 Review
pagenum: 152; title: Exercises 2.4
pagenum: 152; title: Chapter 2 Review
pagenum: 155; title: On the Computer
pagenum: 156; label: Chapter 3
title: Recursion, Recurrence Relations, and Analysis of Algorithms
pagenum: 157; label: 3.1
title: Recursive Definitions
pagenum: 158; title: Recursively Defined Sequences
pagenum: 158; title: Recursively Defined Sets
pagenum: 162; title: Recursively Defined Operations
pagenum: 165; title: Recursively Defined Algorithms
pagenum: 166; title: Section 3.1 Review
pagenum: 171; title: Exercises 3.1
pagenum: 171; label: 3.2
title: Recurrence Relations
pagenum: 180; title: Linear First-Order Recurrence Relations
pagenum: 180; title: Expand, Guess, and Verify
pagenum: 180; title: A Solution Formula
pagenum: 182; title: Linear Second-Order Recurrence Relations
pagenum: 188; title: Divide-and-Conquer Recurrence Relations
pagenum: 193; title: Section 3.2 Review
pagenum: 197; title: Exercises 3.2
pagenum: 197; label: 3.3
title: Analysis of Algorithms
pagenum: 203; title: The General Idea
pagenum: 203; title: Analysis Using Recurrence Relations
pagenum: 206; title: Upper Bound (Euclidean Algorithm)
pagenum: 210; title: Special Interest Page: Of Trees ... and Pancakes
pagenum: 211; title: Section 3.3 Review
pagenum: 212; title: Exercises 3.3
pagenum: 212; title: Chapter 3 Review
pagenum: 217; title: On the Computer
pagenum: 218; label: Chapter 4
title: Sets, Combinatorics, and Probability
pagenum: 221; label: 4.1
title: Sets
pagenum: 222; title: Notation
pagenum: 222; title: Relationships Between Sets
pagenum: 224; title: Sets of Sets
pagenum: 227; title: Binary and Unary Operations
pagenum: 228; title: Operations on Sets
pagenum: 230; title: Set Identities
pagenum: 233; title: Countable and Uncountable Sets
pagenum: 236; title: Section 4.1 Review
pagenum: 239; title: Exercises 4.1
pagenum: 239; label: 4.2
title: Counting
pagenum: 252; title: Multiplication Principle
pagenum: 252; title: Addition Principle
pagenum: 254; title: Using the Principles Together
pagenum: 255; title: Decision Trees
pagenum: 257; title: Section 4.2 Review
pagenum: 258; title: Exercises 4.2
pagenum: 259; label: 4.3
title: Principle of Inclusion and Exclusion; Pigeonhole Principle
pagenum: 263; title: Principle of Inclusion and Exclusion
pagenum: 264; title: Pigeonhole Principle
pagenum: 269; title: Section 4.3 Review
pagenum: 269; title: Exercises 4.3
pagenum: 270; label: 4.4
title: Permutations and Combinations
pagenum: 272; title: Permutations
pagenum: 272; title: Combinations
pagenum: 274; title: Eliminating Duplicates
pagenum: 277; title: Permutations and Combinations with Repetitions
pagenum: 279; title: Generating Permutations and Combinations
pagenum: 280; title: Special Interest Page: Archimedes and the Stomachion
pagenum: 286; title: Section 4.4 Review
pagenum: 288; title: Exercises 4.4
pagenum: 288; label: 4.5
title: Binomial Theorem
pagenum: 294; title: Pascal's Triangle
pagenum: 294; title: Binomial Theorem and Its Proof
pagenum: 296; title: Applying the Binomial Theorem
pagenum: 298; title: Section 4.5 Review
pagenum: 299; title: Exercises 4.5
pagenum: 299; label: 4.6
title: Probability
pagenum: 301; title: Introduction to Finite Probability
pagenum: 301; title: Probability Distributions
pagenum: 304; title: Conditional Probability
pagenum: 306; title: Bayes' Theorem
pagenum: 308; title: Expected Value
pagenum: 310; title: Binomial Distributions
pagenum: 313; title: Average Case Analysis of Algorithms
pagenum: 314; title: Section 4.6 Review
pagenum: 315; title: Exercises 4.6
pagenum: 315; title: Chapter 4 Review
pagenum: 323; title: On the Computer
pagenum: 324; label: Chapter 5
title: Relations, Functions, and Matrices
pagenum: 327; label: 5.1
title: Relations
pagenum: 328; title: Binary Relations
pagenum: 328; title: Properties of Relations
pagenum: 332; title: Closures of Relations
pagenum: 334; title: Partial Orderings
pagenum: 336; title: Equivalence Relations
pagenum: 339; title: Section 5.1 Review
pagenum: 344; title: Exercises 5.1
pagenum: 345; label: 5.2
title: Topological Sorting
pagenum: 356; title: Section 5.2 Review
pagenum: 361; title: Exercises 5.2
pagenum: 362; label: 5.3
title: Relations and Databases
pagenum: 365; title: Entity-Relationship Model
pagenum: 365; title: Relational Model
pagenum: 366; title: Operations on Relations
pagenum: 369; title: Null Values and Three-valued Logic
pagenum: 373; title: Database Integrity
pagenum: 375; title: Section 5.3 Review
pagenum: 376; title: Exercises 5.3
pagenum: 381; label: 5.4
title: Functions
pagenum: 381; title: Definition
pagenum: 381; title: Properties of Functions
pagenum: 388; title: Onto Functions
pagenum: 388; title: One-to-One Functions
pagenum: 389; title: Bijections
pagenum: 390; title: Composition of Functions
pagenum: 390; title: Inverse Functions
pagenum: 392; title: Permutation Functions
pagenum: 394; title: How Many Functions
pagenum: 397; title: Equivalent Sets
pagenum: 401; title: Section 5.4 Review
pagenum: 402; title: Exercises 5.4
pagenum: 402; label: 5.5
title: Order of Magnitude
pagenum: 412; title: Function Growth
pagenum: 412; title: More on Analysis of Algorithms
pagenum: 415; title: The Master Theorem
pagenum: 417; title: Proof of the Master Theorem
pagenum: 419; title: Section 5.5 Review
pagenum: 421; title: Exercises 5.5
pagenum: 421; label: 5.6
title: The Mighty Mod Function
pagenum: 423; title: Hashing
pagenum: 424; title: Computer Security
pagenum: 427; title: Cryptography
pagenum: 427; title: Hashing for Password Encryption
pagenum: 433; title: Miscellaneous Applications
pagenum: 435; title: Identification Codes
pagenum: 435; title: Generating and Decomposing Integers
pagenum: 437; title: Modular Arithmetic Designs
pagenum: 438; title: Section 5.6 Review
pagenum: 440; title: Exercises 5.6
pagenum: 440; label: 5.7
title: Matrices
pagenum: 446; title: Terminology
pagenum: 446; title: Matrix Operations
pagenum: 448; title: Gaussian Elimination
pagenum: 453; title: Boolean Matrices
pagenum: 458; title: Special Interest Page: Solve Millions of Equations, Faster than Gauss
pagenum: 460; title: Section 5.7 Review
pagenum: 461; title: Exercises 5.7
pagenum: 461; title: Chapter 5 Review
pagenum: 470; title: On the Computer
pagenum: 472; label: Chapter 6
title: Graphs and Trees
pagenum: 475; label: 6.1
title: Graphs and Their Representations
pagenum: 476; title: Definitions of a Graph
pagenum: 476; title: Applications of Graphs
pagenum: 479; title: Graph Terminology
pagenum: 481; title: Isomorphic Graphs
pagenum: 484; title: Planar Graphs
pagenum: 487; title: Computer Representation of Graphs
pagenum: 492; title: Adjacency Matrix
pagenum: 492; title: Adjacency List
pagenum: 494; title: Special Interest Page: Isomorphic Protein Graphs
pagenum: 497; title: Section 6.1 Review
pagenum: 498; title: Exercises 6.1
pagenum: 498; label: 6.2
title: Trees and Their Representations
pagenum: 509; title: Tree Terminology
pagenum: 509; title: Applications of Trees
pagenum: 511; title: Binary Tree Representation
pagenum: 513; title: Tree Traversal Algorithms
pagenum: 514; title: Results about Trees
pagenum: 519; title: Section 6.2 Review
pagenum: 521; title: Exercises 6.2
pagenum: 521; label: 6.3
title: Decision Trees
pagenum: 529; title: Searching
pagenum: 529; title: Lower Bounds on Searching
pagenum: 532; title: Binary Tree Search
pagenum: 533; title: Sorting
pagenum: 535; title: Section 6.3 Review
pagenum: 536; title: Exercises 6.3
pagenum: 536; label: 6.4
title: Huffman Codes
pagenum: 539; title: Problem and Trial Solution
pagenum: 539; title: Huffman Encoding Algorithm
pagenum: 542; title: Justification
pagenum: 544; title: Application of Huffman Codes
pagenum: 546; title: Section 6.4 Review
pagenum: 547; title: Exercises 6.4
pagenum: 548; title: Chapter 6 Review
pagenum: 551; title: On the Computer
pagenum: 552; label: Chapter 7
title: Graph Algorithms
pagenum: 553; label: 7.1
title: Directed Graphs and Binary Relations; Warshall's Algorithm
pagenum: 554; title: Directed Graphs and Binary Relations
pagenum: 555; title: Reachability
pagenum: 557; title: Warshall's Algorithm
pagenum: 562; title: Section 7.1 Review
pagenum: 566; title: Exercises 7.1
pagenum: 566; label: 7.2
title: Euler Path and Hamiltonian Circuit
pagenum: 571; title: Euler Path Problem
pagenum: 571; title: Hamiltonian Circuit Problem
pagenum: 576; title: Section 7.2 Review
pagenum: 577; title: Exercises 7.2
pagenum: 577; label: 7.3
title: Shortest Path and Minimal Spanning Tree
pagenum: 581; title: Shortest-Path Problem
pagenum: 581; title: Minimal Spanning Tree Problem
pagenum: 587; title: Special Interest Page: Pathfinding
pagenum: 589; title: Section 7.3 Review
pagenum: 591; title: Exercises 7.3
pagenum: 591; label: 7.4
title: Traversal Algorithms
pagenum: 596; title: Depth-First Search
pagenum: 596; title: Breadth-First Search
pagenum: 598; title: Analysis
pagenum: 601; title: Applications
pagenum: 601; title: Section 7.4 Review
pagenum: 604; title: Exercises 7.4
pagenum: 604; label: 7.5
title: Articulation Points and Computer Networks
pagenum: 607; title: The Problem Statement
pagenum: 607; title: The Idea behind the Algorithm
pagenum: 608; title: The Algorithm Itself
pagenum: 610; title: Section 7.5 Review
pagenum: 612; title: Exercises 7.5
pagenum: 612; title: Chapter 7 Review
pagenum: 614; title: On the Computer
pagenum: 615; label: Chapter 8
title: Boolean Algebra and Computer Logic
pagenum: 617; label: 8.1
title: Boolean Algebra Structure
pagenum: 618; title: Models or Abstractions
pagenum: 619; title: Definition and Properties
pagenum: 620; title: Isomorphic Boolean Algebras
pagenum: 626; title: What is Isomorphism?
pagenum: 626; title: Isomorphism as Applied to Boolean Algebra
pagenum: 628; title: Section 8.1 Review
pagenum: 631; title: Exercises 8.1
pagenum: 631; label: 8.2
title: Logic Networks
pagenum: 638; title: Combinational Networks
pagenum: 638; title: Basic Logic Elements
pagenum: 638; title: Boolean Expressions
pagenum: 639; title: Truth Functions
pagenum: 640; title: Networks and Expressions
pagenum: 641; title: Canonical Form
pagenum: 642; title: Minimization
pagenum: 645; title: Programmable Logic Devices
pagenum: 647; title: A Useful Network
pagenum: 648; title: Other Logic Elements
pagenum: 650; title: Constructing Truth Functions
pagenum: 652; label: Special Interest
title: Pruning Chips and Programs
pagenum: 654; title: Section 8.2 Review
pagenum: 655; title: Exercises 8.2
pagenum: 655; label: 8.3
title: Minimization
pagenum: 663; title: Minimization Process
pagenum: 663; title: Karnaugh Map
pagenum: 665; title: Maps for Three and Four Variables
pagenum: 666; title: Using the Karnaugh Map
pagenum: 668; title: Quine-McCluskey Procedure
pagenum: 673; title: Section 8.3 Review
pagenum: 677; title: Exercises 8.3
pagenum: 678; title: Chapter 8 Review
pagenum: 683; title: On the Computer
pagenum: 684; label: Chapter 9
title: Modeling Arithmetic, Computation, and Languages
pagenum: 685; label: 9.1
title: Algebraic Structures
pagenum: 686; title: Definitions and Examples
pagenum: 686; title: Basic Results about Groups
pagenum: 695; title: Subgroups
pagenum: 698; title: Isomorphic Groups
pagenum: 702; title: Section 9.1 Review
pagenum: 708; title: Exercises 9.1; label: 9.2
title: Coding Theory
pagenum: 714; title: Introduction
pagenum: 714; title: Background: Homomorphisms and Cosets
pagenum: 715; title: Generating Group Codes
pagenum: 717; title: Decoding Group Codes
pagenum: 723; title: Section 9.2 Review
pagenum: 727; title: Exercises 9.2
pagenum: 727; label: 9.3
title: Finite-State Machines
pagenum: 728; title: Definition
pagenum: 729; title: Examples of Finite-State Machines
pagenum: 729; title: Recognition
pagenum: 733; title: Regular Sets and Kleene's Theorem
pagenum: 735; title: Machine Minimization
pagenum: 737; title: Unreachable States
pagenum: 737; title: Minimization Procedure
pagenum: 739; title: Sequential Networks and Finite-State Machines
pagenum: 744; label: Special Interest
title: FSMs Behind the Game
pagenum: 749; title: Section 9.3 Review
pagenum: 750; title: Exercises 9.3
pagenum: 750; label: 9.4
title: Turing Machines
pagenum: 759; title: Definition
pagenum: 760; title: Turing Machines as Set Recognizers
pagenum: 764; title: Turing Machines as Function Computers
pagenum: 767; title: Church-Turing Thesis
pagenum: 769; title: Decision Problems and Uncomputability
pagenum: 771; title: Examples of Decision Problems
pagenum: 772; title: Halting Problem
pagenum: 773; title: Computational Complexity
pagenum: 776; title: Section 9.4 Review
pagenum: 778; title: Exercises 9.4
pagenum: 779; label: 9.5
title: Formal Languages
pagenum: 782; title: Classes of Grammars
pagenum: 789; title: Formal Languages and Computational Devices
pagenum: 792; title: Context-Free Grammars
pagenum: 793; title: Section 9.5 Review
pagenum: 795; title: Exercises 9.5
pagenum: 795; title: Chapter 9 Review
pagenum: 799; title: On the Computer
pagenum: 800; label: Appendix A
title: Derivation Rules for Propositional and Predicate Logic
pagenum: 803; label: Appendix B
title: Summation and Product Notation
pagenum: 805; label: Appendix C
title: The Logarithm Function
pagenum: 809; title: Answers to Practice Problems
pagenum: 813; title: Answers to Odd-Numbered Exercises
pagenum: 851; title: Answers to Self-Tests
pagenum: 949; title: Index
pagenum: 959