Algorithms: Design and Analysis of is a textbook designed for the undergraduate and postgraduate students of computer science engineering, information technology, and computer applications. It helps the students to understand the fundamentals and applications of algorithms. The book has been divided into four sections: Algorithm Basics, Data Structures, Design Techniques and Advanced Topics. The first section explains the importance of algorithms, growth of functions, recursion and analysis of algorithms. The second section covers the data structures basics, trees, graphs, sorting in linear and quadratic time. Section three discusses the various design techniques namely, divide and conquer, greedy approach, dynamic approach, backtracking, branch and bound and randomized algorithms used for solving problems in separate chapters. The fourth section includes the advanced topics such as transform and conquer, decrease and conquer, number thoeretics, string matching, computational geometry, complexity classes, approximation algorithms, and parallel algorithms. Finally, the applications of algorithms in Machine Learning and Computational Biology areas are dealt with in the subsequent chapters. This section will be useful for those interested in advanced courses in algorithms. The book also has 10 appendixes which include topics like probability, matrix operations, Red-black tress, linear programming, DFT, scheduling, a reprise of sorting, searching and amortized analysis and problems based on writing algorithms. The concepts and algorithms in the book are explained with the help of examples which are solved using one or more methods for better understanding. The book includes variety of chapter-end pedagogical features such as point-wise summary, glossary, multiple choice questions with answers, review questions, application-based exercises to help readers test their understanding of the learnt concepts.

Table of Contents:
CHAPTER 1 Introduction to Algorithms; 1.1 Introduction; 1.2 Importance of Algorithms; 1.3 History of Algorithm; 1.4 Algorithm: Definition; 1.5 Ways of Writing an Algorithm; 1.5.1 English-Like Algorithm; 1.5.2 Flowchart; 1.5.3 Pseudocode; 1.6 Design and Analysis vs. Analysis and Design; 1.7 Present and Future; 1.8 Flow of the Book; CHAPTER 2 Growth of Functions; 2.1 Introduction; 2.2 Basic Mathematical Concepts; 2.2.1 Logarithms; 2.2.2 Arithmetic Progression; 2.2.3 Geometric Progression; 2.3 Asymptotic Notation; 2.3.1 O Notation: Big Oh Notation; 2.3.2 ??Notation: Omega Notation; 2.3.3 ??Notation: Theta Notation; 2.3.4 ? Notation: Small Omega Notation; 2.3.5 O Notation: Small Oh Notation; 2.3.6 Comparison of Functions; 2.4 Properties of Asymptotic Comparisons; 2.5 Theorems Related To Asymptotic Notations; CHAPTER 3 Recursion; 3.1 Introduction; 3.2 Rabbit Problem; 3.3 Deriving an Explicit Formula from Recurrence Formula; 3.3.1 Substitution Method; 3.4 Solving a Recurrence Equation; 3.5 Solving a Non-Linear Recurrence Equation; 3.6 Generating Functions; CHAPTER 4 Analysis of Algorithms; 4.1 Introduction; 4.2 Complexity of Recursive Algorithms; 4.3 Finding Complexity by Tree Method; 4.4 Proving Techniques; 4.4.1 Proof by Contradiction; 4.4.2 Proof by Mathematical Induction; 4.5 Amortized Analysis; 4.6 Probabilistic Analysis; 4.6.1 V iva Problem; 4.6.2 Marriage Problem; 4.6.3 Application to Algorithms; 4.7 Tail Recursion; CHAPTER 5 Basic Data Structures; 5.1 Introduction; 5.2 Abstract Data Types; 5.3 Arrays; 5.3.1 Linear Search; 5.3.2 Reversing the Order of Elements of a Given Array; 5.3.3 Sorting; 5.3.4 2D Array; 5.3.5 Sparse Matrix; 5.4 Linked List; 5.4.1 Advantages of a Linked List; 5.4.2 Creation of a linked list; 5.4.4 Insertion at End; 5.4.5 Inserting an Element in the Middle; 5.4.6 Deleting a Node from the Beginning; 5.4.7 Deleting a Node from the End; 5.4.8 Deletion from a Particular Point; 5.4.9 Doubly Linked List; 5.5 Stack; 5.5.1 Static Implementation of Stack; 5.5.2 Dynamic Implementation; 5.5.3 Applications of Stack; 5.5.4 Evaluation of a Postfix Expression; 5.5.5 Infix to Postfix; 5.5.6 Infix to prefix; 5.6 Queue; 5.6.1 Static Implementation; 5.6.2 Problems with the Above Implementation; 5.6.3 Circular Queue; 5.6.4 Applications of a Queue; CHAPTER 6 Trees; 6.1 Introduction; 6.2 Binary Trees; 6.3 Representation of trees; 6.4 Applications of Trees; 6.5 Tree Traversal; 6.6 To Draw a Tree When Pre-order and In-order Traversals Are Given; 6.7 Binary Search Tree; 6.8 B-Tree; 6.9 Heap; 6.10 Creation of a heap; 6.11 Deletion from a Heap; 6.12 Heapsort; 6.13 Binomial and Fibonacci Heap; 6.14 Balanced Trees; CHAPTER 7 Graphs; 7.1 Introduction; 7.2 Concept of Graph; 7.3 Representation of a Graph; 7.4 Cyclic Graphs: Hamiltonian And Eulerian Cycles; 7.5 Isomorphic and Planar Graphs; 7.6 Graph Traversals; 7.6.1 Breadth First Search; 7.6.2 Depth First Search; 7.7 Connected Components; 7.8 Topological Sorting; 7.9 Spanning Tree; CHAPTER 8 Sorting in Linear and Quadratic Time; 8.1 Introduction; 8.2 Sorting; 8.3 Classification; 8.3.1 Classification Based On the Number of Comparisons; 8.3.2 Classification Based On the Number of Swaps; 8.3.3 Classification Based On Memory; 8.3.4 Use of Recursion; 8.3.5 Adaptability; 8.3.6 Stable Sort; 8.4 Selection Sort; 8.5 Bubble Sort; 8.6 Insertion Sort; 8.7 Diminishing Incremental Sort; 8.8 Counting Sort; 8.9 Radix Sort; 8.10 Bucket Sort; CHAPTER 9 Divide and Conquer; 9.1 Introduction; 9.2 Concept of Divide And Conquer; 9.3 Master Theorem; 9.3.1 Proof of Master Theorem; 9.4 Quick Sort; 9.5 Merge Sort; 9.6 Selection; 9.7 Convex Hull; 9.8 Strassens Matrix Multiplication; 9.9 Minimum Distance between N Points; 9.10 Miscellaneous Problems; 9.10.1 Multiplying numbers using divide and conquer; 9.10.2 Defective chessboard problem; CHAPTER 10 Greedy Algorithms; 10.1 Introduction; 10.2 Concept of Greedy Approach; 10.3 0/1 Knapsack Problem; 10.4 Job Sequencing; 10.5 Kruskals Algorithm; 10.6 Prims Algorithm; 10.7 Coin Changing; 10.8 Huffman Codes; 10.9 Single-Source Shortest Path; 10.10 Miscellaneous Problems; 10.10.1 Container Loading Problem; 10.10.2 Subset Cover Problem; 10.10.3 Optimal Storage; 10.11 Analysis and Design for Greedy Approach; CHAPTER 11 Dynamic Programming; 11.1 Introduction; 11.2 Concept of Dynamic Programming; 11.2.1 Implementing the dynamic approach; 11.3 Longest Common Subsequence; 11.4 Matrix Chain Multiplication; 11.5 Travelling Salesman Problem; 11.6 Optimal Substructure Lemma; 11.7 The Optimal Binary Search Tree Problem; 11.8 Floyd s Algorithm; 11.9 Miscellaneous Problems; 11.9.1 Coin changing problem; 11.9.2 Calculating binomial coefficients; CHAPTER 12 Backtracking; 12.1 Introduction; 12.2 Concept of Backtracking; 12.3 Subset Sum Problem; 12.4 N-Queens Problem; 12.5 m -Colouring Problem; 12.6 Hamiltonian Cycle; 12.6.1 Solution of Hamiltonion Cycle using Backtracking; 12.7 Miscellaneous Problems; 12.7.1 Knapsack Problem; 12.7.2 Other Problems; 12.8 Conclusion; CHAPTER 13 Branch and Bound; 13.1 Introduction; 13.2 Concept of Branch and Bound; 13.2.1 FIFO Search; 13.2.2 LIFO Search; 13.2.3 Example of Branch and Bound: 0/1 Knapsack; 13.3 Travelling Salesman Problem; 13.4 Knapsack Problem; 13.5 Solution of the 8-Puzzle Problems; 13.6 Efficiency Considerations; 13.7 Optimization and Relaxation; 13.7.1 Optimization; 13.7.2 Relaxation; CHAPTER 14 An Introduction to Randomized Algorithms; 14.1 Introduction; 14.2 Randomization; 14.3 Monte Carlo vs Las Vegas Algorithms; 14.4 Use of Randomized Algorithms; 14.5 Complexity Classes of Randomized Algorithms; 14.6 Applications of Randomized Algorithms; 14.6.1 The Book Problem; 14.6.2 Load Balancing; 14.6.3 Quick Sort; 14.6.4 Equality of Polynomials; CHAPTER 15 Transform and Conquer; 15.1 Introduction; 15.2 Presorting; 15.3 Gauss Elimination Method; 15.4 The LU Decomposition; 15.5 Horners Method; 15.6 Lowest Common Multiple; 15.7 NP Hard Problems; CHAPTER 16 Decrease and Conquer; 16.1 Introduction; 16.2 Finding the Power Set of a Given Set; 16.3 Breadth First Search and Depth First Search; 16.4 Permutation Generation; 16.5 Decrease and Conquer: Variable Decrease; CHAPTER 17 Number Theoretic Algorithms; 17.1 Introduction; 17.2 GCD of Two Numbers; 17.3 Euclid Theorem; 17.4 Extended Euclid Theorem; 17.5 Modular Linear Equations; 17.6 The Chinese Remainder Theorem; 17.6.1 Applications; 17.7 Cryptography; 17.7.1 Digital Signatures; 17.8 RSA Algorithm; CHAPTER 18 String Matching; 18.1 Introduction; 18.2 String MatchingMeaning and Applications; 18.2.1 Applications; 18.2.2 Algorithms and Data Structures; 18.3 Naive String-Matching Algorithm; 18.4 The RabinKarp Algorithm; 18.5 Deterministic Finite Automata; 18.5.1 Non-Deterministic Finite Automata; 18.6 The KnuthMorrisPratt Automata; 18.7 Tries; 18.8 The Suffix Tree; CHAPTER 19 Complexity Classes; 19.1 Introduction; 19.2 The Concept of P and NP; 19.3 Important Problems and Their Classes; 19.4 Cooks Theorem; 19.5 Reducibility; 19.5.1 How to Convert A CNF into And-Or Graph; 19.5.2 Maximum Clique from Sat3; 19.5.3 Independent Set; 19.5.4 Vertex Cover; 19.6 A Note about Problems That Are NP Hard but Not NP Complete; CHAPTER 20 An Introduction to PSpace; 20.1 Introduction; 20.2 Quantified Satisfiability; 20.3 Planning Problems; 20.3.1 N-Puzzle Problem; 20.3.2 Solution; 20.4 Regular Expressions; 20.5 Conclusion; CHAPTER 21 Approximation Algorithms; 21.1 Introduction; 21.2 Taxonomy; 21.3 Approximation Algorithm for Load Balancing; 21.4 Vertex Cover Problem; 21.5 Set Cover Problem; 21.5.1 Greedy Approach For Approximate Set Cover; 21.5.2 Subset Cover (Sets With Weights Associated With Them); 21.6 ??Approximation Algorithms; 21.6.1 Load Balancing Problem Using 2-Approximation Algorithm; 21.6.2 Travelling Salesman Problem; 21.7 Use of Linear Programming In Approximation Algorithms; CHAPTER 22 Parallel Algorithms; 22.1 Introduction; 22.2 Generations of Computers; 22.3 Parallel Computers; 22.4 Basics; 22.5 Parallel Random Access Machine; 22.6 Finding Maximum; 22.6.1 Using CRCW; 22.6.2 Using EREW; 22.7 Prefix Computation; 22.8 Merge; 22.9 Hypercube Algorithms; 22.9.1 Broadcasting; 22.9.2 Prefix Computation Using Hypercube Algorithm; CHAPTER 23 An Introduction to Machine Learning Approaches; 23.1 Introduction; 23.2 Artificial Intelligence; 23.3 Machine Learning; 23.3.1 Learning; 23.4 Neural Networks; 23.5 Genetic Algorithms; 23.5.1 Crossover; 23.5.2 Mutation; 23.5.3 Selection; 23.5.4 The Process; 23.6 Knapsack Problem; 23.7 Subset Sum Using GA; 23.7.1 Problems in the Brute Force Method; 23.7.2 Use of Gas to Solve Subset Sum Problem; 23.8 Travelling Salesman Problem; 23.8.1 GA Approach to Solve Travelling Salesman Problem; 23.9 Vertex Cover Problem; 23.9.1 Approximation Algorithm; 23.9.2 Solution of Vertex Cover via Gas; 23.10 Maximum Clique Problem; 23.10.1 Solution of Maximum Clique via Gas; CHAPTER 24 Computational Biology and Bioinformatics; 24.1 Introduction; 24.2 Basics of Computational Biology and Bioinformatics; 24.3 Basics of Life Sciences; 24.3.1 The Cell; 24.3.2 DNA and RNA; 24.3.3 Genome; 24.3.4 Amino Acids; 24.4 Sequencing and Problems Therein; 24.4.1 Folding Problem; 24.5 Algorithms; APPENDIX A1 Amortized Analysis Revisited; A1.1 Introduction; A1.2 Aggregate Analysis; A1.3 Dynamic Tables: Aggregation, Accounting, and Potential Amortized Analysis; A1.4 Conclusion; APPENDIX A2 2-3-4 and RedBlack Trees; A2.1 Introduction; A2.2 2-3-4 Tree; A2.3 RedBlack Trees; A2.4 Conclusion; APPENDIX A3 Matrix Operations; A3.1 Basics; A3.2 Operations on Matrices; A3.2.1 Equality of Matrices; A3.2.2 Addition of Matrices; A3.2.3 Subtraction of Matrices; A3.2.4 Scalar Multiplication; A3.2.5 Transpose of a Matrix; A3.2.6 Symmetric Matrix; A3.2.7 Skew-Symmetric Matrix; A3.2.8 Multiplication of Matrices; A3.2.9 Determinant of a Matrix; A3.2.10 Minor and Cofactor of an Element; A3.2.11 Inverse of a Matrix; A3.3 Solving System of Linear Equations: Cramers Rule; A3.4 Solving System of Linear Equations: Inverse Method; A3.5 Elementary Row Operations; A3.6 Conclusion; APPENDIX A4 Linear Programming; A4.1 Introduction; A4.2 Graphical Method; A4.3 Simplex Method; A4.4 Finding Dual and An Introduction To The Dual Simplex Method; A4.5 Conclusion; APPENDIX A5 Complex Numbers and Introduction to DFT; A5.1 Introduction; A5.2 Complex Numbers; A5.2.1 Complex Number: The Cartesian And Polar Form; A5.2.2 Power and Root Of A Complex Number; A5.2.3 Finding Powers and Roots Of A Complex Number Using The Polar Form; A5.2.4 Root of a Complex Number; A5.2.5 Cube Roots Of Unity; A5.2.6 Nth Roots of Unity; A5.3 Discrete Fourier Transform; A5.4 Use of Divide and Conquer In DFT; A5.5 Conclusion; APPENDIX A6 Probability; A6.1 Introduction; A6.2 Basics; A6.2.1 Taxonomy; A6.2.2 Pigeonhole Principle; A6.3 Independent Events; A6.3.1 Bays Theorem; A6.4 Probability Distribution; A6.4.1 Mean and Variance of A Probability Distribution; A6.5 Binomial Distribution; A6.5.1 Recurrence Formula for Binomial Distribution; A6.6 Poisson distribution; A6.7 Normal Distribution; A6.8 Conclusion; APPENDIX A7 Scheduling; A7.1 Introduction; A7.2 Definitions and Discussions; A7.3 How to Handle Scheduling Problems; A7.4 Tools; A7.5 Conclusion; APPENDIX A8 Searching Reprise; A8.1 Introduction; A8.2 Binary Search Tree Revisited; A8.3 Deletion in A BST; A8.4 Problem with BST and AVL Trees; A8.5 Conclusion; APPENDIX A9 Analysis of Sorting Algorithms; A9.1 Introduction; A9.2 Lab 1: Quick Sort; A9.3 Lab 2: Selection Sort; A9.4 Lab 3: Insertion Sort; A9.5 Lab 4: Bubble Sort; A9.6 Problems Based On Sorting; APPENDIX A10 Problems; A10.1 Introduction; A10.2 Problems; A10.2.1 To Design an O(n) Algorithm to Find the nth Fibonacci Term; A10.2.2 To Find Whether a Strictly Binary Tree is a Heap; A10.3 TO DEVELOP AN O(N) Algorithm To Sort Numbers Between 0 to (n - 1); A10.4 Division of a List into Two Parts Whose Sum Has Minimum Difference; A10.5 Complexity-Related Questions; A10.6 Algorithm to Store Subsets Having Two Elements; A10.7 Divide and Conquer; A10.7.1 Non-Recursive Binary Search; A10.7.2 Binary Search in a 2-Dimensional Array; A10.7.3 Complexity of Divide and Conquer; A10.8 Applications of Dynamic Programming