Introductory discrete mathematics
By: V.K. Balakrishnan.
Edition: Dover ed.
Series: Dover books on mathematics
Publisher: Dover Publications
Published: 1996
Place of publication: New York
Language: eng
Number of pages: 236
Subjects: Mathematics.; Computer science -- Mathematics.
Notes: Includes bibliographical references (p. 219-223) and index.
"An unabridged, corrected republication of the work first published by Prentice Hall, Englewood Cliffs, N.J., 1991"--T.p. verso.
Table of contents: title: Preface
pagenum: xiii; label: 0
title: Set Theory and Logic
pagenum: 1; label: 0.1
title: Introduction to Set Theory
pagenum: 1; label: 0.2
title: Functions and Relations
pagenum: 7; label: 0.3
title: Inductive Proofs and Recursive Definitions
pagenum: 17; label: 0.4
title: The Language of Logic
pagenum: 22; label: 0.5
title: Notes and References
pagenum: 25; label: 0.6
title: Exercises
pagenum: 26; label: 1
title: Combinatorics
pagenum: 35; label: 1.1
title: Two Basic Counting Rules
pagenum: 35; label: 1.2
title: Permutations
pagenum: 38; label: 1.3
title: Combinations
pagenum: 42; label: 1.4
title: More on Permutations and Combinations
pagenum: 48; label: 1.5
title: The Pigeonhole Principle
pagenum: 53; label: 1.6
title: The Inclusion-Exclusion Principle
pagenum: 59; label: 1.7
title: Summary of Results in Combinatorics
pagenum: 69; label: 1.8
title: Notes and References
pagenum: 71; label: 1.9
title: Exercises
pagenum: 72; label: 2
title: Generating Functions
pagenum: 80; label: 2.1
title: Introduction
pagenum: 80; label: 2.2
title: Ordinary Generating Functions
pagenum: 83; label: 2.3
title: Exponential Generating Functions
pagenum: 86; label: 2.4
title: Notes and References
pagenum: 90; label: 2.5
title: Exercises
pagenum: 90; label: 3
title: Recurrence Relations
pagenum: 94; label: 3.1
title: Introduction
pagenum: 94; label: 3.2
title: Homogeneous Recurrence Relations
pagenum: 97; label: 3.3
title: Inhomogeneous Recurrence Relations
pagenum: 102; label: 3.4
title: Recurrence Relations and Generating Functions
pagenum: 105; label: 3.5
title: Analysis of Algorithms
pagenum: 108; label: 3.6
title: Notes and References
pagenum: 116; label: 3.7
title: Exercises
pagenum: 116; label: 4
title: Graphs and Digraphs
pagenum: 120; label: 4.1
title: Introduction
pagenum: 120; label: 4.2
title: Adjacency Matrices and Incidence Matrices
pagenum: 125; label: 4.3
title: Joining in Graphs
pagenum: 129; label: 4.4
title: Reaching in Digraphs
pagenum: 132; label: 4.5
title: Testing Connectedness
pagenum: 133; label: 4.6
title: Strong Orientation of Graphs
pagenum: 135; label: 4.7
title: Notes and References
pagenum: 135; label: 4.8
title: Exercises
pagenum: 136; label: 5
title: More on Graphs and Digraphs
pagenum: 140; label: 5.1
title: Eulerian Paths and Eulerian Circuits
pagenum: 140; label: 5.2
title: Coding and de Bruijn Digraphs
pagenum: 144; label: 5.3
title: Hamiltonian Paths and Hamiltonian Cycles
pagenum: 149; label: 5.4
title: Applications of Hamiltonian Cycles
pagenum: 153; label: 5.5
title: Vertex Coloring and Planarity of Graphs
pagenum: 155; label: 5.6
title: Notes and References
pagenum: 161; label: 5.7
title: Exercises
pagenum: 162; label: 6
title: Trees and Their Applications
pagenum: 164; label: 6.1
title: Definitions and Properties
pagenum: 164; label: 6.2
title: Spanning Trees
pagenum: 167; label: 6.3
title: Binary Trees
pagenum: 170; label: 6.4
title: Notes and References
pagenum: 177; label: 6.5
title: Exercises
pagenum: 178; label: 7
title: Spanning Tree Problems
pagenum: 180; label: 7.1
title: More on Spanning Trees
pagenum: 180; label: 7.2
title: Kruskal's Greedy Algorithm
pagenum: 184; label: 7.3
title: Prim's Greedy Algorithm
pagenum: 187; label: 7.4
title: Comparison of the Two Algorithms
pagenum: 193; label: 7.5
title: Notes and References
pagenum: 193; label: 7.6
title: Exercises
pagenum: 193; label: 8
title: Shortest Path Problems
pagenum: 196; label: 8.1
title: Introduction
pagenum: 196; label: 8.2
title: Dijkstra's Algorithm
pagenum: 197; label: 8.3
title: Floyd-Warshall Algorithm
pagenum: 202; label: 8.4
title: Comparison of the Two Algorithms
pagenum: 204; label: 8.5
title: Notes and References
pagenum: 205; label: 8.6
title: Exercises
pagenum: 205; label: Appendix
title: What Is NP-Completeness?
pagenum: 207; label: A.1
title: Problems and Their Instances
pagenum: 207; label: A.2
title: The Size of an Instance
pagenum: 208; label: A.3
title: Algorithm to Solve a Problem
pagenum: 209; label: A.4
title: Complexity of an Algorithm
pagenum: 209; label: A.5
title: The "Big Oh" or the O(·) Notation
pagenum: 210; label: A.6
title: Easy Problems and Difficult Problems
pagenum: 211; label: A.7
title: The Class P and the Class NP
pagenum: 212; label: A.8
title: Polynomial Transformations and NP-Completeness
pagenum: 214; label: A.9
title: Coping with Hard Problems
pagenum: 217; title: Bibliography
pagenum: 219; title: Answers to Selected Exercises
pagenum: 224; title: Index
pagenum: 231