Balakrishnan V.K. Introductory Discrete Mathematics

London: Dover Publications, 2010. — 251 p.This concise text offers an introduction to discrete mathematics for undergraduate students in computer science and mathematics. Mathematics educators consider it vital that their students be exposed to a course in discrete methods that introduces them to combinatorial mathematics and to algebraic and logical structures focusing on the interplay between computer science and mathematics. The present volume emphasizes combinatorics, graph theory with applications to some stand network optimization problems, and algorithms to solve these problems.
Chapters 0–3 cover fundamental operations involving sets and the principle of mathematical induction, and standard combinatorial topics: basic counting principles, permutations, combinations, the inclusion-exclusion principle, generating functions, recurrence relations, and an introduction to the analysis of algorithms. Applications are emphasized wherever possible and more than 200 exercises at the ends of these chapters help students test their grasp of the material.
Chapters 4 and 5 survey graphs and digraphs, including their connectedness properties, applications of graph coloring, and more, with stress on applications to coding and other related problems. Two important problems in network optimization ? the minimal spanning tree problem and the shortest distance problem ? are covered in the last two chapters. A very brief nontechnical exposition of the theory of computational complexity and NP-completeness is outlined in the appendix.Introduction to Set Theory
Functions and Relations
Inductive Proofs and Recursive Definitions
The Language of Logic
Notes and References
ExercisesTwo Basic Counting Rules
Permutations
Combinations
More on Permutations and Combinations
The Pigeonhole Principle
The Inclusion-Exclusion Principle
Summary of Results in Combinatorics
Notes and References
ExercisesOrdinary Generating Functions
Exponential Generating Functions
ExercisesHomogeneous Recurrence Relations
Inhomogeneous Recurrence Relations
Recurrence Relations and Generating Functions
Analysis of Algorithms
ExercisesAdjacency Matrices and Incidence Matrices
Joining in Graphs
Reaching in Digraphs
Testing Connectedness
Notes and References
ExercisesEulerian Paths and Eulerian Circuits
Coding and de Bruijn Digraphs
Hamiltonian Paths and Hamiltonian Cycles
Applications of Hamiltonian Cycles
Vertex Coloring and Planarity of Graphs
Notes and References
ExercisesDefinitions and Properties
Spanning Trees
Binary Trees
Notes and References
ExercisesMore on Spanning Trees
Kruskal’s Greedy Algorithm
Prim’s Greedy Algorithm
ExercisesDijkstra’s Algorithm
Floyd-Warshall Algorithm
Comparison of the Two Algorithms
Exercisesl Problems and Their Instances
The Size of an Instance
Complexity of an Algorithm
The Big Oh’’ or the O(-) Notation\t
Easy Problems and Difficult Problems
The Class P and the Class NP
Polynomial Transformations and NP-Completeness
Coping with Hard ProblemsAnswers to Selected Exercises