Discrete Mathematics: Graph Algorithms, Algebraic Structures, Coding Theory, and Cryptography

Cover
Half Title
Title Page
Copyright Page
Dedication
Contents
List of Figures
List of Tables
Preface
Acknowledgment
Authors
1. Graph Algorithms I
	1.1 Representation of Graphs
	1.2 Minimum Spanning Tree Algorithms
		1.2.1 Prim\'s minimum spanning tree algorithm
		1.2.2 Kruskal\'s minimum spanning tree algorithm
		1.2.3 Rooted ordered trees and traversal of trees
	1.3 Shortest Path Algorithms
		1.3.1 Single-source shortest path algorithm
	1.4 Dijkstra\'s Algorithm for Negative Weighted Arcs
	1.5 All-Pairs Shortest Path Algorithm
		1.5.1 An application of Floyd\'s algorithm
	1.6 Transitive Closure of a Directed Graph
	1.7 An O(n3) Transitive Closure Algorithm Due to Warshall
	1.8 Navigation in Graphs
	1.9 Applications of Depth-First Search
		1.9.1 Application 1: Finding connected components
		1.9.2 Application 2: Testing acyclic graph
		1.9.3 Application 3: Finding biconnected components of a connected multigraph
	1.10 Depth-First Search for Directed Graphs
	1.11 Applications of Depth-First Search for Directed Graphs
		1.11.1 Application 1: Finding the roots of a directed graph
		1.11.2 Application 2: Testing if a digraph is without circuits
		1.11.3 Application 3: Topological sort
			1.11.3.1 An application of topological sort: PERT
		1.11.4 Application 4: Strongly connected components algorithm
	1.12 Traveling Salesman Problem
		1.12.1 Approximate algorithms for traveling salesman problem
	1.13 Exercises
2. Graph Algorithms II
	2.1 Breadth-First Search
	2.2 Applications of bfs Algorithm
	2.3 Matchings in Graphs
		2.3.1 An application: (k-1)-regular subgraphs of k-regular graphs
	2.4 Matrices and Bipartite Graphs
		2.4.1 Personnel assignment problem or weighted matching in a bipartite graph
	2.5 Exercises
3. Algebraic Structures I (Matrices, Groups, Rings, and Fields)
	3.1 Introduction
	3.2 Matrices
	3.3 Operations on Matrices: Addition, Scalar Multiplication, and Multiplication of Matrices
		3.3.1 Block multiplication of matrices
		3.3.2 Transpose of a matrix
		3.3.3 Inverse of a matrix
		3.3.4 Symmetric and skew-symmetric matrices
		3.3.5 Hermitian and skew-Hermitian matrices
		3.3.6 Orthogonal and unitary matrices
		3.3.7 Exercises
	3.4 Groups
		3.4.1 Abelian and non-Abelian groups
		3.4.2 Examples of Abelian groups
		3.4.3 Examples of non-Abelian groups
		3.4.4 Group tables
	3.5 A Group of Congruent Transformations (Also called Symmetries)
	3.6 Another Group of Congruent Transformations
	3.7 Subgroups
		3.7.1 Examples of subgroups
		3.7.2 Subgroup generated by a subset of a group
	3.8 Cyclic Groups
		3.8.1 Examples of cyclic groups
	3.9 Lagrange\'s Theorem for Finite Groups
	3.10 Homomorphisms and Isomorphisms of Groups
	3.11 Properties of Homomorphisms of Groups
	3.12 Automorphism of Groups
	3.13 Normal Subgroups
	3.14 Quotient Groups (or Factor Groups)
	3.15 Basic Isomorphism Theorem for Groups
		3.15.1 Examples of factor groups
	3.16 Exercises
	3.17 Rings
		3.17.1 Rings, definitions and examples
			3.17.1.1 Unity element of a ring
		3.17.2 Units of a ring
			3.17.2.1 Units of the ring Zn
			3.17.2.2 Zero divisors
	3.18 Integral Domains
	3.19 Exercises
	3.20 Ideals
	3.21 Principal Ideals
	3.22 Fields
		3.22.1 Examples of fields
	3.23 Characteristic of a Field
4. Algebraic Structures II (Vector Spaces and Finite Fields)
	4.1 Vector Spaces
		4.1.1 Examples of vector spaces
	4.2 Subspaces
		4.2.1 An example of a subspace
	4.3 Spanning Sets
	4.4 Linear Independence of Vectors
	4.5 Bases of a Vector Space
	4.6 Dimension of a Vector Space
	4.7 Solutions of Linear Equations and Rank of a Matrix
	4.8 Exercises
	4.9 Solutions of Linear Equations
	4.10 Solutions of Non-Homogeneous Linear Equations
	4.11 LUP Decomposition
		4.11.1 Computing an LU decomposition
	4.12 Exercises
	4.13 Finite Fields
	4.14 Factorization of Polynomials Over Finite Fields
	4.15 Exercises
	4.16 Mutually Orthogonal Latin Squares
5. Introduction to Coding Theory
	5.1 Introduction
	5.2 Binary Symmetric Channels
	5.3 Linear Codes
	5.4 Minimum Distance of a Code
	5.5 Hamming Codes
	5.6 Standard Array Decoding
	5.7 Sphere Packings
	5.8 Extended Codes
	5.9 Syndrome Decoding
	5.10 Error Detection
	5.11 Sphere Packing Bound or Hamming Bound
	5.12 Exercises
	5.13 Cyclic Codes
	5.14 Dual Codes
	5.15 Exercises
6. Cryptography
	6.1 Introduction
	6.2 Some Classical Cryptosystems
		6.2.1 Caesar cryptosystem
		6.2.2 Affine cryptosystem
		6.2.3 Private key cryptosystems
		6.2.4 Hacking an affine cryptosystem
	6.3 Encryption Using Matrices
	6.4 Exercises
	6.5 Other Private Key Cryptosystems
		6.5.1 Vigenere cipher
		6.5.2 The one-time pad
	6.6 Public Key Cryptography
		6.6.1 Working of public key cryptosystems
			6.6.1.1 Transmission of messages
			6.6.1.2 Digital signature
		6.6.2 RSA public key cryptosystem
			6.6.2.1 Description of RSA
		6.6.3 The ElGamal public key cryptosystem
		6.6.4 Description of ElGamal system
	6.7 Primality Testing
		6.7.1 Non-trivial square roots (mod n)
		6.7.2 Prime Number Theorem
		6.7.3 Pseudo-primality testing
			6.7.3.1 Base-2 Pseudo-prime test
		6.7.4 Miller-Rabin Algorithm
		6.7.5 Horner\'s method to evaluate a polynomial
		6.7.6 Modular exponentiation algorithm based on repeated squaring
	6.8 The Agrawal-Kayal-Saxena (AKS) Primality Testing Algorithm
		6.8.1 Introduction
		6.8.2 The basis of AKS algorithm
		6.8.3 Notation and preliminaries
		6.8.4 The AKS algorithm
Appendix A: Answers to Chapter 1–Graph Algorithms I
Appendix B: Answers to Chapter 2–Graph Algorithms II
Appendix C: Answers to Chapter 3–Algebraic Structures I
Appendix D: Answers to Chapter 4–Algebraic Structures II
Appendix E: Answers to Chapter 5–Introduction to Coding Theory
Appendix F: Answers to Chapter 6–Cryptography
Bibliography
Index