Discrete Mathematics and Graph Theory: A Concise Study Companion and Guide (Undergraduate Topics in Computer Science)

Preface
Contents
Part I Fundamentals of Discrete  Mathematics
1 Logic
	1.1 Propositional Logic
		1.1.1 Compound Propositions
		1.1.2 Conditional Statements
		1.1.3 Biconditional Statements
		1.1.4 Tautologies and Contradictions
		1.1.5 Equivalences
		1.1.6 Laws of Logic
	1.2 Predicate Logic
		1.2.1 Quantifiers
		1.2.2 Propositional Functions with Two Variables
		1.2.3 Negation
		1.2.4 The Universal Conditional Statement
		1.2.5 The Existential Conditional Statements
	1.3 Review Questions
	1.4 Chapter Notes
2 Proofs
	2.1 Arguments
		2.1.1 Rules of Inference
		2.1.2 Definitions
	2.2 Direct Proof
	2.3 Contrapositive
	2.4 Proof by Contradiction
	2.5 Proving Biconditional Propositions
	2.6 Proofs Using Quantifiers
		2.6.1 Proving Universal Statements
		2.6.2 Proving Existential Statements
	2.7 Proof by Cases
	2.8 Review Questions
	2.9 Chapter Notes
3 Algorithms
	3.1 Basics
		3.1.1 Pseudocode Convention
		3.1.2 Assignment and Types of Variables
		3.1.3 Decision
		3.1.4 Loops
		3.1.5 Functions and Parameter Passing
	3.2 Basic Data Structures
	3.3 Sorting
		3.3.1 Bubble Sort
		3.3.2 Exchange Sort
	3.4 Analysis
	3.5 Design Methods
		3.5.1 Divide and Conquer
		3.5.2 Greedy Method
		3.5.3 Dynamic Programming
	3.6 Difficult Problems
	3.7 Review Questions
	3.8 Chapter Notes
4 Set Theory
	4.1 Definitions
		4.1.1 Equality of Sets
		4.1.2 Cardinality of a Set
	4.2 Subsets
	4.3 Venn Diagrams
	4.4 Set Operations
		4.4.1 Cartesian Product
		4.4.2 Set Partition
		4.4.3 Operation Precedence
	4.5 Laws of Set Theory
	4.6 Proving Set Equations
		4.6.1 The Element Method
		4.6.2 The Tabular Method
		4.6.3 The Algebraic Method
	4.7 Review Questions
	4.8 Chapter Notes
5 Relations and Functions
	5.1 Relations
		5.1.1 Representations
		5.1.2 Inverse of a Relation
		5.1.3 Union and Intersection of Relations
		5.1.4 Properties of Relations
		5.1.5 Equivalence Relations and Partitions
		5.1.6 Order
		5.1.7 Composite Relation
		5.1.8 n-Ary Relations
		5.1.9 Transitive Closure
		5.1.10 Database Applications
	5.2 Functions
		5.2.1 Composite Functions
		5.2.2 Injection, Surjection and Bijection
		5.2.3 Inverse of a Function
		5.2.4 Some Special Functions
	5.3 Review Questions
	5.4 Chapter Notes
6 Sequences, Induction and Recursion
	6.1 Sequences
		6.1.1 Summation
		6.1.2 Arithmetic Sequence and Series
		6.1.3 Geometric Sequence
		6.1.4 Product Notation
		6.1.5 Big Operators
	6.2 Induction
		6.2.1 Proving Inequalities
	6.3 Strong Induction
	6.4 Recursion
		6.4.1 Recurrence Relations
		6.4.2 Recursively Defined Functions
		6.4.3 Recursive Algorithms
		6.4.4 Recursively Defined Sets
	6.5 Structural Induction
	6.6 Review Questions
	6.7 Chapter Notes
7 Introduction to Number Theory
	7.1 Basics
	7.2 Division
	7.3 Greatest Common Divisor
		7.3.1 Euclid's Algorithm
		7.3.2 Least Common Multiple
	7.4 Prime Numbers
		7.4.1 Primality Test
		7.4.2 The Sieve of Eratosthenes
	7.5 Congruence
	7.6 Representation of Integers
		7.6.1 Binary System
		7.6.2 Hexadecimal System
	7.7 Introduction to Cryptography
		7.7.1 Diffie-Hellman Protocol
		7.7.2 RSA Protocol
	7.8 Review Questions
	7.9 Chapter Notes
8 Counting and Probability
	8.1 Basic Counting Methods
		8.1.1 Principle of Inclusion-Exclusion
		8.1.2 Additive Counting Principle
		8.1.3 Multiplicative Counting Principle
		8.1.4 The Pigeonhole Principle
		8.1.5 Permutations
		8.1.6 Combinations
	8.2 Discrete Probability
		8.2.1 Probability Measures
		8.2.2 Independent Events
		8.2.3 Conditional Probability
		8.2.4 Tree Diagrams
		8.2.5 Random Variables
		8.2.6 Stochastic Processes
	8.3 Review Questions
	8.4 Chapter Notes
9 Boolean Algebras and Combinational Circuits
	9.1 Boolean Algebras
		9.1.1 Principle of Duality
		9.1.2 Boolean Functions
		9.1.3 Sum-of-Products Form
		9.1.4 Product-of-Sums Form
		9.1.5 Conversions
		9.1.6 Minimization
	9.2 Combinational Circuits
		9.2.1 Gates
		9.2.2 Designing Combinational Circuits
		9.2.3 Arithmetic Circuits
	9.3 Review Questions
	9.4 Chapter Notes
10 Introduction to the Theory of Computation
	10.1 Languages
	10.2 Finite State Machines
	10.3 Finite State Automata
		10.3.1 Analysis
		10.3.2 Designing Finite State Automata
	10.4 The Relationship Between Languages and Automata
	10.5 Nondeterministic Finite State Automata
	10.6 Regular Expressions
	10.7 Turing Machines
	10.8 Complexity Theory
		10.8.1 Reductions
		10.8.2 NP-Completeness
		10.8.3 Coping with NP-Completeness
	10.9 Review Questions
	10.10 Chapter Notes
Part II Graph Theory
11 Introduction to Graphs
	11.1 Terminology
	11.2 Vertex Degree
		11.2.1 Degree Sequence
	11.3 Directed Graph
	11.4 Representation of a Graph
		11.4.1 Adjacency List
		11.4.2 Adjacency Matrix
		11.4.3 Incidence Matrix
	11.5 Subgraphs
	11.6 Types of Graphs
		11.6.1 Complete Graph
		11.6.2 Weighted Graphs
		11.6.3 Bipartite Graphs
		11.6.4 Regular Graphs
		11.6.5 Line Graphs
	11.7 Graph Operations
		11.7.1 Graph Union
		11.7.2 Graph Intersection
		11.7.3 Graph Join
		11.7.4 Cartesian Product
	11.8 Connectivity
		11.8.1 Definitions
		11.8.2 Connectedness
	11.9 Graph Isomorphism
	11.10 Review Questions
	11.11 Chapter Notes
12 Trees and Traversals
	12.1 Definitions and Properties
	12.2 Traversal Algorithms
		12.2.1 Preorder Traversal
		12.2.2 Postorder Traversal
	12.3 Binary Trees
	12.4 Binary Search Trees
	12.5 Depth-First-Search
	12.6 Breadth-First Search
	12.7 Spanning Trees
		12.7.1 Unweighted Spanning Trees
		12.7.2 Minimum Spanning Trees
	12.8 Review Questions
	12.9 Chapter Notes
13 Subgraphs
	13.1 Cliques
	13.2 Matching
		13.2.1 Unweighted Matching
		13.2.2 Weighted Matching
		13.2.3 Bipartite Graph Matching
	13.3 Independent Sets
		13.3.1 Algorithm
	13.4 Dominating Sets
		13.4.1 Algorithm
	13.5 Coloring
		13.5.1 Vertex Coloring
		13.5.2 Edge Coloring
	13.6 Vertex Cover
		13.6.1 Unweighted Vertex Cover
		13.6.2 Weighted Vertex Cover
	13.7 Review Questions
	13.8 Chapter Notes
14 Connectivity, Network Flows and Shortest Paths
	14.1 Basics
		14.1.1 Menger's Theorems
	14.2 Connectivity Test
	14.3 Digraph Connectivity
		14.3.1 Strong Connectivity Check
		14.3.2 Finding Strongly Connected Components
	14.4 Network Flows
		14.4.1 A Greedy Algorithm
		14.4.2 Residual Graphs
		14.4.3 Ford–Fulkerson Algorithm
		14.4.4 Bipartite Graph Matching
	14.5 Algebraic Connectivity
		14.5.1 The Laplacian Matrix
		14.5.2 Normalized Laplacian
		14.5.3 Eigenvalues
	14.6 Shortest Paths
	14.7 Chapter Notes
15 Graph Applications
	15.1 Analysis of Large Graphs
		15.1.1 Degree Distribution
		15.1.2 Clustering
		15.1.3 Matching Index
		15.1.4 Centrality
		15.1.5 Network Models
	15.2 The Web
		15.2.1 The Web Graph
		15.2.2 Page Rank Algorithm
	15.3 Ad hoc Wireless Networks
		15.3.1 Routing in ad hoc Networks
		15.3.2 Clustering and Spanning Tree Construction in a WSN
	15.4 Biological Networks
		15.4.1 Network Motifs
		15.4.2 Network Alignment
	15.5 Social Networks
		15.5.1 Relationships
		15.5.2 Structural Balance
	15.6 Review Questions
	15.7 Chapter Notes
A Pseudocode Conventions
	A.1 Introduction
	A.2 Data Structures
	A.3 Control Structures
Index