Discrete Mathmatics
Publisher: Oxford University Press India
Published: 2015
Language: eng
Number of pages: 628
ISBN-13: 9780199452798
Subjects: Computer science, mathematics
Description: Discrete Mathematics is a textbook designed for the students of computer science engineering, information technology, and computer applications to help them develop the foundation of theoretical computer science.
Table of contents: title: Features of the Book
pagenum: iv; title: Preface
pagenum: vii; title: Brief Contents
pagenum: xiii; title: Detailed Contents
pagenum: xv; title: List of Symbols
pagenum: xxv; label: 1
title: Introduction to Discrete Mathematics and Propositional Logic
pagenum: 1; label: 1.1
title: Discrete Mathematics: A Brief Introduction
pagenum: 1; label: 1.2
title: Introduction to Propositional Logic
pagenum: 4; label: 1.3
title: Proposition
pagenum: 5; label: 1.4
title: Logical Operators
pagenum: 6; label: 1.4.1
title: Negation (~)
pagenum: 6; label: 1.4.2
title: Disjunction (OR/∨)
pagenum: 6; label: 1.4.3
title: Exclusive OR
pagenum: 7; label: 1.4.4
title: Conjunction (and/∧)
pagenum: 7; label: 1.4.5
title: Conditional (→)
pagenum: 8; label: 1.4.6
title: Biconditional (↔)
pagenum: 10; label: 1.4.7
title: NAND (↑)
pagenum: 10; label: 1.4.8
title: NOR (↓)
pagenum: 11; label: 1.4.9
title: Well-formed Formula
pagenum: 13; label: 1.4.10
title: Rules of Precedence
pagenum: 13; label: 1.5
title: Tautology
pagenum: 14; label: 1.6
title: Contradiction
pagenum: 14; label: 1.7
title: Logical Equivalence
pagenum: 14; label: 1.8
title: Tautological Implication
pagenum: 17; label: 1.9
title: Converse, Inverse, and Contrapositive
pagenum: 18; label: 1.10
title: Functionally Complete Set of Connectives
pagenum: 18; label: 1.11
title: Normal Forms
pagenum: 19; label: 1.11.1
title: Elementary Product
pagenum: 20; label: 1.11.2
title: Elementary Sum
pagenum: 20; label: 1.11.3
title: Disjunctive Normal Form
pagenum: 20; label: 1.11.4
title: Conjunctive Normal Form
pagenum: 21; label: 1.11.5
title: Principal Disjunctive Normal Form
pagenum: 21; label: 1.11.6
title: Principal Conjunctive Normal Form
pagenum: 22; label: 1.12
title: Argument
pagenum: 23; label: 1.12.1
title: Checking the Validity of an Argument by Constructing Truth Table
pagenum: 24; label: 1.12.2
title: Checking the Validity of an Argument Without Constructing Truth Table
pagenum: 26; label: 1.13
title: Predicates
pagenum: 27; label: 1.13.1
title: Quantifiers
pagenum: 27; label: 1.13.2
title: Free and Bound Variables
pagenum: 29; label: 1.13.3
title: Negation of Quantifiers
pagenum: 30; label: 1.13.4
title: Removing Quantifiers from Predicates
pagenum: 31; label: 1.14
title: Nested Quantifiers
pagenum: 32; label: 1.14.1
title: Effect of Order of Quantifiers
pagenum: 32; label: 1.15
title: Inference Theory of Predicate Calculus
pagenum: 34; label: 1.15.1
title: Universal Specification
pagenum: 35; label: 1.15.2
title: Existential Specification
pagenum: 35; label: 1.15.3
title: Universal Generalization
pagenum: 35; label: 1.15.4
title: Existential Generalization
pagenum: 36; label: 1.15.5
title: Substitution
pagenum: 37; label: 1.15.6
title: First-order and Second-order Logic
pagenum: 37; label: 1.16
title: Methods of Proof
pagenum: 38; label: 1.16.1
title: Trivial Proof
pagenum: 38; label: 1.16.2
title: Vacuous Proof
pagenum: 38; label: 1.16.3
title: Direct Proof
pagenum: 38; label: 1.16.4
title: Proof by Contradiction
pagenum: 39; label: 1.16.5
title: Proof by Contraposition
pagenum: 41; label: 1.16.6
title: Proof by Cases
pagenum: 42; label: 1.16.7
title: Exhaustive Proof
pagenum: 43; label: 1.16.8
title: Proof by Mathematical Induction
pagenum: 43; label: 1.16.9
title: Proof by Minimal Counter Example
pagenum: 48; label: 1.17
title: Satisfiability and Consistency
pagenum: 49; label: 1.18
title: Mechanization of Reasoning
pagenum: 49; label: 1.18.1
title: Russell's Paradox
pagenum: 50; label: 2
title: Set Theory
pagenum: 62; label: 2.1
title: Introduction
pagenum: 62; label: 2.2
title: Sets
pagenum: 63; label: 2.2.1
title: Roster Notation
pagenum: 63; label: 2.2.2
title: Set-builder Notation
pagenum: 63; label: 2.2.3
title: Cardinality of Sets
pagenum: 64; label: 2.3
title: Some Standard Sets
pagenum: 65; label: 2.3.1
title: Empty Set
pagenum: 65; label: 2.3.2
title: Singleton Set
pagenum: 65; label: 2.3.3
title: Finite and Infinite Sets
pagenum: 65; label: 2.3.4
title: Countable and Uncountable Sets
pagenum: 66; label: 2.3.5
title: Universal Set
pagenum: 66; label: 2.4
title: Subset and Proper Subset
pagenum: 66; label: 2.5
title: Equality of Sets
pagenum: 67; label: 2.6
title: Power Set
pagenum: 68; label: 2.7
title: Venn Diagrams
pagenum: 68; label: 2.8
title: Operations on Sets
pagenum: 69; label: 2.8.1
title: Union
pagenum: 69; label: 2.8.2
title: Intersection
pagenum: 69; label: 2.8.3
title: Difference of Two Sets
pagenum: 70; label: 2.8.4
title: Symmetric Difference of Two Sets
pagenum: 70; label: 2.8.5
title: Complement of a Set
pagenum: 71; label: 2.8.6
title: Generalized Union and Intersection
pagenum: 71; label: 2.9
title: Some Other Classes of Sets
pagenum: 74; label: 2.9.1
title: Disjoint Sets
pagenum: 74; label: 2.9.2
title: Partition
pagenum: 74; label: 2.9.3
title: Ordered Set
pagenum: 74; label: 2.9.4
title: Cartesian Product of Sets
pagenum: 75; label: 2.10
title: Algebra of Sets
pagenum: 75; label: 2.11
title: Multisets
pagenum: 81; label: 2.12
title: Fuzzy Sets
pagenum: 82; label: 2.12.1
title: Operations on Fuzzy Sets
pagenum: 83; label: 2.12.2
title: α-Cut and Strong α-Cut
pagenum: 84; label: 2.12.3
title: Support, Core, and Height of Fuzzy Sets
pagenum: 85; label: 3
title: Relations
pagenum: 91; label: 3.1
title: Introduction
pagenum: 91; label: 3.2
title: Relation
pagenum: 92; label: 3.2.1
title: Domain and Range
pagenum: 93; label: 3.2.2
title: Inverse of Relation
pagenum: 93; label: 3.3
title: Combining Relations
pagenum: 94; label: 3.3.1
title: Composition of Relations
pagenum: 95; label: 3.4
title: Different Types of Relations
pagenum: 96; label: 3.4.1
title: Reflexive Relation
pagenum: 96; label: 3.4.2
title: Symmetric Relation
pagenum: 97; label: 3.4.3
title: Transitive Relation
pagenum: 99; label: 3.4.4
title: Compatible Relation
pagenum: 101; label: 3.4.5
title: Equivalence Relation
pagenum: 101; label: 3.4.6
title: Irreflexive Relation
pagenum: 107; label: 3.4.7
title: Asymmetric Relation
pagenum: 108; label: 3.4.8
title: Anti-symmetric Relation
pagenum: 109; label: 3.4.9
title: Partial Order Relation
pagenum: 111; label: 3.5
title: Pictorial or Graphical Representation of Relations
pagenum: 112; label: 3.6
title: Matrix Representation of Relations
pagenum: 113; label: 3.7
title: Closure of Relations
pagenum: 114; label: 3.7.1
title: Reflexive Closure
pagenum: 114; label: 3.7.2
title: Symmetric Closure
pagenum: 114; label: 3.7.3
title: Transitive Closure
pagenum: 115; label: 3.8
title: Warshall's Algorithm
pagenum: 115; label: 3.9
title: n-Ary Relations
pagenum: 118; label: 4
title: Functions
pagenum: 126; label: 4.1
title: Introduction
pagenum: 126; label: 4.2
title: Definition of Function
pagenum: 127; label: 4.3
title: Relations vs Functions
pagenum: 128; label: 4.4
title: Types of Functions
pagenum: 130; label: 4.4.1
title: One-One Function
pagenum: 130; label: 4.4.2
title: Many-One Function
pagenum: 132; label: 4.4.3
title: Onto Function
pagenum: 133; label: 4.4.4
title: Identity Function
pagenum: 136; label: 4.4.5
title: Constant Function
pagenum: 136; label: 4.4.6
title: Invertible Function
pagenum: 136; label: 4.5
title: Composition of Functions
pagenum: 138; label: 4.6
title: Sum and Product of Functions
pagenum: 142; label: 4.7
title: Functions Used in Computer Science
pagenum: 143; label: 4.7.1
title: Floor Function
pagenum: 143; label: 4.7.2
title: Ceiling Function
pagenum: 144; label: 4.7.3
title: Remainder Function / Modular Arithmetic
pagenum: 146; label: 4.7.4
title: Characteristic Function
pagenum: 146; label: 4.7.5
title: Hash Function
pagenum: 146; label: 4.8
title: Collision Resolution
pagenum: 148; label: 4.8.1
title: Open Addressing
pagenum: 148; label: 4.8.2
title: Chaining
pagenum: 150; label: 4.9
title: Investigation of Functions
pagenum: 150; label: 5
title: Properties of Integers
pagenum: 158; label: 5.1
title: Introduction
pagenum: 158; label: 5.2
title: Basic Properties of Z
pagenum: 159; label: 5.3
title: Well-Ordering Principle
pagenum: 161; label: 5.4
title: Elementary Divisibility Properties
pagenum: 161; label: 5.5
title: Greatest Common Divisor
pagenum: 164; label: 5.6
title: Least Common Multiple
pagenum: 167; label: 5.7
title: Linear Diophantine Equation
pagenum: 168; label: 5.8
title: Fundamental Theorem of Arithmetic
pagenum: 170; label: 5.8.1
title: Primes and Composites
pagenum: 171; label: 5.8.2
title: Relatively Prime Integers
pagenum: 173; label: 5.9
title: Congruence Relation
pagenum: 173; label: 5.10
title: Residue Classes
pagenum: 175; label: 5.11
title: Linear Congruence
pagenum: 176; label: 6
title: Counting Techniques
pagenum: 185; label: 6.1
title: Introduction
pagenum: 185; label: 6.2
title: Basic Counting Principle
pagenum: 186; label: 6.2.1
title: Sum Rule
pagenum: 186; label: 6.2.2
title: Product Rule
pagenum: 186; label: 6.2.3
title: Inclusion-Exclusion Principle
pagenum: 189; label: 6.3
title: Permutations and Combinations
pagenum: 194; label: 6.3.1
title: Permutation
pagenum: 195; label: 6.3.2
title: Combination
pagenum: 198; label: 6.4
title: Generalized Permutation and Combination
pagenum: 201; label: 6.4.1
title: Permutation with Repetition
pagenum: 201; label: 6.4.2
title: Permutations with Identical Objects
pagenum: 202; label: 6.4.3
title: Combination with Repetition
pagenum: 203; label: 6.5
title: Binomial Coefficients
pagenum: 206; label: 6.6
title: Partition
pagenum: 208; label: 6.7
title: Pigeonhole Principle
pagenum: 211; label: 6.7.1
title: Generalized Pigeonhole Principle
pagenum: 212; label: 6.8
title: Arrangements with Forbidden Positions
pagenum: 213; label: 6.8.1
title: Rook Polynomial
pagenum: 217; label: 6.8.2
title: Derangement
pagenum: 218; label: 7
title: Fundamentals of Probability
pagenum: 226; label: 7.1
title: Introduction
pagenum: 226; label: 7.2
title: Random Experiment
pagenum: 227; label: 7.3
title: Sample Space
pagenum: 227; label: 7.4
title: Event
pagenum: 227; label: 7.4.1
title: Equally Likely Events
pagenum: 228; label: 7.4.2
title: Mutually Exclusive Events
pagenum: 229; label: 7.4.3
title: Exhaustive Events
pagenum: 229; label: 7.4.4
title: Independent Events
pagenum: 229; label: 7.4.5
title: Dependent Events
pagenum: 230; label: 7.4.6
title: Complementary Event
pagenum: 230; label: 7.5
title: Measurement of Probability
pagenum: 231; label: 7.5.1
title: Classical or a Priori Approach of Probability
pagenum: 231; label: 7.5.2
title: Relative Frequency Approach of Probability
pagenum: 231; label: 7.6
title: Axioms of Probability
pagenum: 234; label: 7.7
title: Conditional Probability
pagenum: 238; label: 7.8
title: Bayes' Theorem
pagenum: 247; label: 7.9
title: Discrete Probability Distributions
pagenum: 248; label: 7.9.1
title: Expectation of Random Variable
pagenum: 250; label: 7.9.2
title: Variance and Standard Deviation of Random Variables
pagenum: 251; label: 7.9.3
title: Binomial Distribution
pagenum: 251; label: 7.9.4
title: Poisson Distribution
pagenum: 254; label: 7.9.5
title: Negative Binomial Distribution
pagenum: 256; label: 7.9.6
title: Geometric Distribution
pagenum: 256; label: 8
title: Discrete Numeric Functions and Generating Functions
pagenum: 263; label: 8.1
title: Introduction
pagenum: 263; label: 8.2
title: Manipulation of Numeric Functions
pagenum: 264; label: 8.2.1
title: Sum and Product of Two Numeric Functions
pagenum: 264; label: 8.2.2
title: Multiplication with Scalar
pagenum: 265; label: 8.2.3
title: Modulus of Numeric Function
pagenum: 265; label: 8.2.4
title: \(S^i a_r\) and \(S^{-i} a_r\) of Numeric Function
pagenum: 265; label: 8.2.5
title: Forward and Backward Differences of Numeric Functions
pagenum: 267; label: 8.2.6
title: Accumulated Sum
pagenum: 268; label: 8.2.7
title: Convolution of Two Numeric Functions
pagenum: 269; label: 8.3
title: Generating Functions
pagenum: 274; label: 8.3.1
title: Properties of Generating Functions
pagenum: 276; label: 8.3.2
title: Solution of Combinatorial Problems Using Generating Functions
pagenum: 283; label: 9
title: Recurrence Relations
pagenum: 293; label: 9.1
title: Introduction
pagenum: 293; label: 9.2
title: Recursive Definition
pagenum: 294; label: 9.2.1
title: Recursively Defined Functions
pagenum: 295; label: 9.2.2
title: Recursively Defined Sets
pagenum: 295; label: 9.3
title: Recurrence Relation
pagenum: 296; label: 9.4
title: Solution of Recurrence Relations
pagenum: 298; label: 9.4.1
title: Iterative Method
pagenum: 298; label: 9.4.2
title: Recursive Method
pagenum: 301; label: 9.4.3
title: Generating Function
pagenum: 305; label: 9.5
title: Structural Induction
pagenum: 306; label: 9.6
title: Order and Degree of Recurrence Relations
pagenum: 306; label: 9.7
title: Linear Recurrence Relation with Constant Coefficients
pagenum: 307; label: 9.7.1
title: Linear Homogeneous Recurrence Relation with Constant Coefficients
pagenum: 307; label: 9.7.2
title: Linear Non-homogeneous Recurrence Relation with Constant Coefficients
pagenum: 310; label: 10
title: Algebraic Structures
pagenum: 322; label: 10.1
title: Introduction
pagenum: 322; label: 10.2
title: Binary Operations
pagenum: 322; label: 10.2.1
title: Semi-Group
pagenum: 324; label: 10.2.2
title: Monoid
pagenum: 325; label: 10.2.3
title: Group
pagenum: 326; label: 10.3
title: Addition and Multiplication Modulo m
pagenum: 330; label: 10.4
title: Subgroup
pagenum: 331; label: 10.4.1
title: Cosets
pagenum: 333; label: 10.5
title: Permutations and Symmetric Group
pagenum: 335; label: 10.5.1
title: Cyclic Permutation
pagenum: 336; label: 10.5.2
title: Stabilizer of an Element
pagenum: 337; label: 10.5.3
title: Orbit of an Element
pagenum: 337; label: 10.5.4
title: Invariant Elements under Permutation
pagenum: 337; label: 10.6
title: Cyclic Group
pagenum: 339; label: 10.7
title: Normal Subgroup
pagenum: 343; label: 10.8
title: Quotient Group
pagenum: 345; label: 10.9
title: Dihedral Group
pagenum: 345; label: 10.10
title: Homomorphism and Isomorphism
pagenum: 346; label: 10.10.1
title: Kernel of Homomorphism
pagenum: 347; label: 10.11
title: Ring
pagenum: 349; label: 10.11.1
title: Commutative Ring
pagenum: 350; label: 10.11.2
title: Ring with Unity
pagenum: 350; label: 10.11.3
title: Zero Divisor of a Ring
pagenum: 351; label: 10.11.4
title: Subrings
pagenum: 351; label: 10.11.5
title: Ring Homomorphism
pagenum: 351; label: 10.12
title: Integral Domain
pagenum: 351; label: 10.13
title: Division Ring or Skew Field
pagenum: 352; label: 10.14
title: Field
pagenum: 352; label: 10.15
title: Polynomial Ring
pagenum: 354; label: 10.16
title: Boolean Algebra
pagenum: 354; label: 10.16.1
title: Duality
pagenum: 356; label: 10.16.2
title: Boolean Functions
pagenum: 358; label: 10.16.3
title: Simplification of Boolean Functions
pagenum: 358; label: 10.16.4
title: Canonical Form
pagenum: 359; label: 10.16.5
title: Standard Form
pagenum: 361; label: 10.16.6
title: Other Logic Operations
pagenum: 362; label: 10.16.7
title: Karnaugh Map
pagenum: 362; label: 10.16.8
title: Quine–McCluskey Method
pagenum: 366; label: 10.16.9
title: Free Boolean Algebra
pagenum: 368; label: 11
title: Posets and Lattices
pagenum: 374; label: 11.1
title: Introduction
pagenum: 374; label: 11.2
title: Partially Ordered Set
pagenum: 375; label: 11.3
title: Diagrammatic Representation of Poset (Hasse Diagram)
pagenum: 375; label: 11.4
title: Elements in Posets
pagenum: 376; label: 11.4.1
title: Least and Greatest Elements
pagenum: 377; label: 11.4.2
title: Minimal and Maximal Elements
pagenum: 377; label: 11.4.3
title: Lower and Upper Bounds
pagenum: 377; label: 11.4.4
title: Greatest Lower Bound and Least Upper Bound
pagenum: 377; label: 11.5
title: Linearly Ordered Set
pagenum: 380; label: 11.6
title: Well-Ordered Set
pagenum: 380; label: 11.7
title: Product Order
pagenum: 381; label: 11.8
title: Lexicographic Order
pagenum: 382; label: 11.9
title: Topological Sorting and Consistent Enumeration
pagenum: 383; label: 11.10
title: Isomorphism
pagenum: 384; label: 11.11
title: Lattices
pagenum: 386; label: 11.12
title: Properties of Lattices
pagenum: 386; label: 11.12.1
title: Principle of Duality
pagenum: 387; label: 11.12.2
title: Sublattice
pagenum: 390; label: 11.13
title: Some Special Lattices
pagenum: 390; label: 11.13.1
title: Modular Lattice
pagenum: 390; label: 11.13.2
title: Distributive Lattice
pagenum: 391; label: 11.13.3
title: Bounded Lattice
pagenum: 392; label: 11.13.4
title: Complemented Lattice
pagenum: 395; label: 11.13.5
title: Complete Lattice
pagenum: 396; label: 11.14
title: Product of Lattices
pagenum: 396; label: 11.15
title: Lattice Homomorphism
pagenum: 396; label: 11.16
title: Boolean Algebra and Lattices
pagenum: 397; label: 11.17
title: Stone's Representation Theorem
pagenum: 399; label: 12
title: Formal Languages and Finite Automata
pagenum: 409; label: 12.1
title: Introduction
pagenum: 409; label: 12.2
title: Alphabet and Words
pagenum: 409; label: 12.3
title: Language
pagenum: 410; label: 12.4
title: Operations on Languages
pagenum: 410; label: 12.5
title: Finite Automata
pagenum: 411; label: 12.5.1
title: Deterministic Finite State Automata
pagenum: 412; label: 12.5.2
title: Non-Deterministic Finite Automata
pagenum: 416; label: 12.5.3
title: Conversion From Non-Deterministic Finite Automata to Deterministic Finite Automata
pagenum: 418; label: 12.5.4
title: Minimization of Finite Automata
pagenum: 421; label: 12.6
title: Finite Automata with Outputs
pagenum: 423; label: 12.6.1
title: Mealy Machine
pagenum: 423; label: 12.6.2
title: Moore Machine
pagenum: 425; label: 12.6.3
title: Equivalence of Mealy and Moore Machines
pagenum: 426; label: 12.6.4
title: Conversion From Mealy to Moore Machine
pagenum: 426; label: 12.6.5
title: Conversion From Moore to Mealy Machine
pagenum: 428; label: 12.7
title: Regular Expression
pagenum: 430; label: 12.8
title: Regular Expression and Finite Automata
pagenum: 432; label: 12.9
title: Generalized Transition Graph
pagenum: 439; label: 12.10
title: Grammar of Formal Languages
pagenum: 440; label: 12.10.1
title: Phrase Structure Grammar
pagenum: 440; label: 12.10.2
title: Chomsky Hierarchy
pagenum: 442; label: 12.11
title: Other Machines
pagenum: 443; label: 13
title: Graph Theory
pagenum: 453; label: 13.1
title: Introduction
pagenum: 453; label: 13.2
title: Graph and its Related Definitions
pagenum: 454; label: 13.3
title: Different Types of Graphs
pagenum: 457; label: 13.3.1
title: Simple Graph
pagenum: 457; label: 13.3.2
title: Multigraph, Trivial Graph, and Null Graph
pagenum: 457; label: 13.3.3
title: Complete Graph
pagenum: 457; label: 13.3.4
title: Regular Graph
pagenum: 457; label: 13.3.5
title: Bipartite Graph
pagenum: 458; label: 13.3.6
title: Weighted Graph
pagenum: 458; label: 13.4
title: Subgraphs
pagenum: 459; label: 13.5
title: Operations on Graphs
pagenum: 460; label: 13.5.1
title: Union of Two Graphs
pagenum: 460; label: 13.5.2
title: Intersection of Two Graphs
pagenum: 461; label: 13.5.3
title: Ring Sum of Two Graphs
pagenum: 461; label: 13.5.4
title: Decomposition of a Graph
pagenum: 461; label: 13.5.5
title: Deletion of a Vertex
pagenum: 461; label: 13.5.6
title: Deletion of an Edge
pagenum: 462; label: 13.5.7
title: Complement of a Graph
pagenum: 462; label: 13.6
title: Walk, Path, and Circuit
pagenum: 462; label: 13.6.1
title: Walk
pagenum: 463; label: 13.6.2
title: Path
pagenum: 463; label: 13.6.3
title: Circuit
pagenum: 463; label: 13.7
title: Connected Graph, Disconnected Graph, and Components
pagenum: 463; label: 13.8
title: Homomorphism and Isomorphism of Graphs
pagenum: 466; label: 13.9
title: Homeomorphic Graphs
pagenum: 467; label: 13.10
title: Euler and Hamiltonian Graphs
pagenum: 468; label: 13.10.1
title: Euler Line and Euler Graph
pagenum: 468; label: 13.10.2
title: Hamiltonian Path and Hamiltonian Circuit
pagenum: 469; label: 13.10.3
title: Travelling Salesman Problem
pagenum: 469; label: 13.11
title: Planar Graph
pagenum: 470; label: 13.11.1
title: Kuratowski's Two Graphs
pagenum: 470; label: 13.11.2
title: Region and its Degree
pagenum: 471; label: 13.11.3
title: Euler's Formula
pagenum: 471; label: 13.12
title: Tree
pagenum: 472; label: 13.12.1
title: Rooted Tree
pagenum: 473; label: 13.12.2
title: Binary Tree
pagenum: 473; label: 13.12.3
title: Height of Binary Tree
pagenum: 475; label: 13.12.4
title: Spanning Tree
pagenum: 476; label: 13.12.5
title: Branch and Chord
pagenum: 476; label: 13.12.6
title: Rank and Nullity
pagenum: 476; label: 13.12.7
title: Fundamental Circuits
pagenum: 477; label: 13.12.8
title: Finding All Spanning Trees of a Graph
pagenum: 477; label: 13.12.9
title: Spanning Trees in a Weighted Graph
pagenum: 477; label: 13.12.10
title: Kruskal's Algorithm
pagenum: 478; label: 13.12.11
title: Prim's Algorithm
pagenum: 479; label: 13.12.12
title: Dijkstra Algorithm
pagenum: 479; label: 13.12.13
title: Binary Search Tree
pagenum: 482; label: 13.13
title: Cut Set and Cut Vertex
pagenum: 482; label: 13.14
title: Colouring of Graphs
pagenum: 484; label: 13.14.1
title: Chromatic Number
pagenum: 484; label: 13.14.2
title: Chromatic Partitioning
pagenum: 485; label: 13.14.3
title: Independence Set and Maximal Independence Set
pagenum: 485; label: 13.14.4
title: Maximum Independence Set and Independence Number
pagenum: 485; label: 13.14.5
title: Clique and Maximal Clique
pagenum: 485; label: 13.14.6
title: Maximum Clique and Clique Number
pagenum: 486; label: 13.14.7
title: Perfect Graph
pagenum: 486; label: 13.14.8
title: Chromatic Polynomial
pagenum: 486; label: 13.14.9
title: Applications of Graph Colouring
pagenum: 488; label: 13.15
title: Matching
pagenum: 489; label: 13.15.1
title: Maximal Matching, Maximum Matching, and Matching Number
pagenum: 489; label: 13.15.2
title: Perfect Matching
pagenum: 489; label: 13.16
title: Matrix Representation of Graphs
pagenum: 490; label: 13.16.1
title: Incidence Matrix
pagenum: 490; label: 13.16.2
title: Circuit Matrix
pagenum: 491; label: 13.16.3
title: Cut Set Matrix
pagenum: 492; label: 13.16.4
title: Path Matrix
pagenum: 493; label: 13.16.5
title: Adjacency Matrix
pagenum: 494; label: 13.17
title: Traversal of Graphs
pagenum: 494; label: 13.17.1
title: Breadth-First Search
pagenum: 494; label: 13.17.2
title: Depth-First Search
pagenum: 496; label: 13.18
title: Traversing Binary Trees
pagenum: 498; label: 13.18.1
title: Pre-Order Traversal
pagenum: 498; label: 13.18.2
title: In-Order Traversal
pagenum: 498; label: 13.18.3
title: Post-Order Traversal
pagenum: 499; label: 13.19
title: Digraph or Directed Graph
pagenum: 499; label: 13.20
title: Network Flow
pagenum: 500; label: 13.20.1
title: Cut in a Transport Network
pagenum: 501; label: 13.20.2
title: Flow Augmenting Path
pagenum: 503; label: 13.21
title: Enumeration of Graphs
pagenum: 505; label: 14
title: Applications of Discrete Mathematical Structures
pagenum: 523; label: 14.1
title: Introduction
pagenum: 523; label: 14.2
title: Asymptotic Behaviour of Numeric Functions
pagenum: 524; label: 14.2.1
title: Big-Oh (O) Notation
pagenum: 524; label: 14.2.2
title: Omega (Ω) Notation
pagenum: 529; label: 14.2.3
title: Theta (Θ) Notation
pagenum: 529; label: 14.3
title: Analysis of Algorithms
pagenum: 530; label: 14.3.1
title: Space Complexity
pagenum: 530; label: 14.3.2
title: Time Complexity
pagenum: 531; label: 14.4
title: Analysis of Sorting Algorithms
pagenum: 534; label: 14.4.1
title: Insertion Sort
pagenum: 534; label: 14.4.2
title: Bubble Sort
pagenum: 537; label: 14.4.3
title: Selection Sort
pagenum: 539; label: 14.5
title: Divide-and-Conquer Approach
pagenum: 542; label: 14.5.1
title: Merge Sort
pagenum: 542; label: 14.5.2
title: Quick Sort
pagenum: 548; label: 14.6
title: Analysis of Searching Algorithms
pagenum: 552; label: 14.6.1
title: Linear Search
pagenum: 552; label: 14.6.2
title: Binary Search
pagenum: 553; label: 14.7
title: Tractable and Intractable Problems
pagenum: 555; label: 14.8
title: Logic Gates
pagenum: 556; label: 14.8.1
title: Switching Circuits and Logic Gates
pagenum: 557; label: 14.8.2
title: NAND and NOR Implementations
pagenum: 558; label: 14.9
title: Combinational Circuits
pagenum: 560; label: 14.9.1
title: Half Adder
pagenum: 561; label: 14.9.2
title: Full Adder
pagenum: 561; label: 14.9.3
title: Half Subtractor
pagenum: 563; label: 14.9.4
title: Full Subtractor
pagenum: 563; label: 14.10
title: Information and Coding Theory
pagenum: 565; label: 14.10.1
title: Discrete Information Sources
pagenum: 565; label: 14.10.2
title: Entropy
pagenum: 566; label: 14.10.3
title: Mutual Information
pagenum: 567; label: 14.10.4
title: Coding Theory
pagenum: 567; label: 14.10.5
title: Hamming Distance
pagenum: 567; label: 14.10.6
title: Error-Detecting and Error-Correcting Codes
pagenum: 568; label: 14.10.7
title: Group Codes
pagenum: 573; label: 14.10.8
title: Generator Matrices
pagenum: 575; label: 14.10.9
title: Parity Check Matrices
pagenum: 576; label: 14.10.10
title: Coset Decoding
pagenum: 578; label: 14.10.11
title: Prefix Codes
pagenum: 578; label: 14.10.12
title: Cyclic Code
pagenum: 579; title: Appendices
pagenum: 585; title: Bibliography
pagenum: 593; title: Index
pagenum: 594; title: About the Authors
pagenum: 601