Conveying ideas in a user-friendly style, this book has been designed for a course in Applied Algebra. The book covers graph algorithms, basic algebraic structures, coding theory and cryptography. It will be most suited for senior undergraduates and beginning graduate students in mathematics and computer science as also to
individuals who want to have a knowledge of the below-mentioned topics.
Provides a complete discussion on several graph algorithms such as Prims algorithm and Kruskals algorithm for sending a minimum cost spanning tree in a weighted graph, Dijkstras single source shortest path algorithm, Floyds algorithm, Warshalls algorithm, Kuhn-Munkres Algorithm. In addition to DFS and BFS search, several applications of DFS and BFS are also discussed. Presents a good introduction to the basic algebraic structures, namely, matrices, groups, rings, fields including finite fields as also a discussion on vector spaces and linear equations and their solutions. Provides an introduction to linear codes including cyclic codes.
Presents a description of private key cryptosystems as also a discussion on public key cryptosystems such as RSA, ElGamal and Miller-Rabin. Finally, the Agrawal-KayalSaxena algorithm (AKS Algorithm) for testing if a given
positive integer is prime or not in polynomial time is presented- the first time in a textbook.
Two distinguished features of the book are:
Illustrative examples have been presented throughout the book to make the readers appreciate the concepts described. Answers to all even-numbered exercises in all the chapters are given.
Author(s): Sriraman Sridharan; R. Balakrishnan
Publisher: CRC Press
Year: 2020
Language: English
Pages: xxvi+314
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
