Algorithms: Design and Analysis

by Sushil C. Dimri, Preeti Malik, Mangey Ram

Overview

Algorithms play a central role both in the theory and in the practice of computing. The goal of the authors was to write a textbook that would not trivialize the subject but would still be readable by most students on their own. The book contains over 120 exercises. Some of them are drills; others make important points about the material covered in the text or introduce new algorithms not covered there. The book also provides programming projects.

From the Table of Contents:

Chapter 1: Basic knowledge of Mathematics, Relations, Recurrence relation and Solution techniques, Function and Growth of functions.

Chapter 2: Different Sorting Techniques and their analysis.

Chapter 3: Greedy approach, Dynamic Programming, Branch and Bound techniques, Backtracking and Problems, Amortized analysis, and Order Statics.

Chapter 4: Graph algorithms, BFS, DFS, Spanning Tree, Flow Maximization Algorithms. Shortest Path Algorithms.

Chapter 5: Binary search tree, Red black Tree, Binomial heap, B-Tree and Fibonacci Heap.

Chapter 6: Approximation Algorithms, Sorting Networks, Matrix operations, Fast Fourier Transformation, Number theoretic Algorithm, Computational geometry Randomized Algorithms, String matching, NP-Hard, NP-Completeness, Cooks theorem.

Product Details

ISBN-13:	9783110693751
Publisher:	De Gruyter
Publication date:	03/08/2021
Series:	De Gruyter Textbook
Sold by:	Barnes & Noble
Format:	eBook
Pages:	178
File size:	5 MB
Age Range:	18 Years

About the Author

Dr. Mangey Ram received the Ph.D. degree major in Mathematics and minor in Computer Science from G. B. Pant University of Agriculture and Technology, Pantnagar, India. He has been a Faculty Member for around ten years and has taught several core courses in pure and applied mathematics at undergraduate, postgraduate, and doctorate levels. He is currently a Professor at Graphic Era (Deemed to be University), Dehradun, India.
He is the Editor of the De Gruyter Series of Applications of Mathematical Engineering (AMEIS)

Dr. Sushil Chandra Dimri is presently working as Professor in the department of Computer Science at the Graphic Era University, Dehradun

Dr. Preeti Malik has received her Ph. D. Degree in 2017 from Gurukul Kangri University, INDIA. She has three years of teaching experience in Graphic Era University, INDIA. Currently, she is working as an Assistant Professor in the same university.

Table of Contents

Preface v

Chapter 1 Introduction 1

1.1 Algorithm 1

1.2 Another definition 1

1.3 Analyzing the performance of algorithms 1

1.4 Growth of the functions 2

1.5 Asymptotic notations 2

1.5.1 The O (big oh) notation 3

1.5.2 The ω notation 4

1.5.3 The θ notation 5

1.6 Recurrence relation 8

1.6.1 Linear recurrence relation 8

1.6.2 Solution of homogeneous recurrence relation 8

1.6.3 Solution to nonhomogeneous linear recurrence relation 10

1.7 Divide and conquer relations 12

1.7.1 Solution to DAC recurrence relation 12

1.7.2 The recursion tree method 13

1.7.3 The substitution method 14

1.7.4 Change of variable method 17

1.8 Master's theorem 17

Problem set 20

Chapter 2 Sorting techniques 23

2.1 Sorting 23

2.2 Insertion sort 23

2.2.1 Analysis of insertion sort 24

2.3 Quick sort 25

2.3.1 DAC approach 26

2.3.2 Analysis of quick sort 28

2.4 Merge sort 29

2.4.1 Analysis of merge sort 31

2.5 Heap sort 32

2.5.1 Analysis of Heapify 35

2.5.2 Heap sort 35

2.5.3 Analysis of heap sort 35

2.6 Sorting in linear time 35

2.7 Counting sort 36

2.7.1 Analysis of counting sort 37

2.8 Radix sort 38

2.8.1 Analysis of radix sort 38

2.9 Bucket sort 38

2.9.1 Analysis of bucket sort 39

2.9.2 Binomial distribution 40

Problem set 41

Chapter 3 Algorithm design techniques 43

3.1 Greedy approach 43

3.1.1 Traveling salesman problem 43

3.1.2 Fractional knapsack problem 44

3.2 Backtracking 46

3.2.1 Hamiltonian cycle 47

3.2.2 8-queen problem 48

3.3 Dynamic programming 51

3.3.1 0/1 knapsack problem 52

3.3.2 The traveling salesman problem 53

3.3.3 Chain matrix multiplication 55

3.3.4 Optimal binary search tree 57

3.4 Branch-and-bound technique 59

3.4.1 Assignment problem 60

3.4.2 Knapsack problem 61

3.5 Amortized analysis 62

3.5.1 Aggregate method 62

3.5.2 The potential method 63

3.6 Order statistics 65

Problem set 67

Chapter 4 Advanced graph algorithm 69

4.1 Introduction 69

4.1.1 Terminology 69

4.2 The graph search techniques 70

4.2.1 Breadth first search 70

4.2.2 Depth first search 72

4.3 Spanning tree 74

4.3.1 Kruskal's algorithm 75

4.3.2 Prim's algorithm 76

4.4 Shortest path algorithm 77

4.4.1 Warhsall's algorithm 77

4.4.2 Floyd Warshall's algorithm 80

4.4.3 Dijkstra algorithm 82

4.4.4 Bellman-Ford algorithm 83

4.5 Maximum flow 89

4.5.1 Maximum flow and minimum cut 90

4.5.2 Ford Fulkerson method 91

Problem set 94

Chapter 5 Number theory, classification of problems, and random algorithms 97

5.1 Division theorem 97

5.1.1 Common divisor and greatest common divisor 97

5.2 Chinese remainder theorem 98

5.3 Matrix operations 100

5.3.1 Strassen's matrix multiplication 100

5.3.2 Divide and conquer for matrix multiplication 101

5.3.3 Strassen's multiplication 102

5.4 Pattern matching 103

5.4.1 The Naive algorithm 103

5.4.2 The Rabin-Karp algorithm 104

5.5 P and NP class problem 107

5.5.1 Reducibility 107

5.5.2 NP complete problem 107

5.6 Approximation algorithms 108

5.6.1 Relative error 108

5.6.2 Approximation algorithm for TSP 108

5.6.3 The vertex cover problem 109

5.7 Deterministic and randomized algorithm 111

5.7.1 The nut and bolt problem 112

5.8 Computational geometry 112

5.9 The convex hull 113

5.9.1 Counterclockwise and clockwise 114

5.9.2 Finding whether two line segments intersect 114

5.10 Class P problems 116

5.10.1 NP (nondeterministic Polynomial Time) Problems 116

5.10.2 Any problem in P is also in NP 116

5.10.3 NP Hard Problems 116

5.10.4 NP Complete 117

5.10.5 Halting Problem for Deterministic Algorithms 117

5.10.6 The satisfiability problem 117

5.11 Clique 118

5.11.1 Clique Decision Problem 118

5.11.2 Non-Deterministic Algorithm for Clique Decision Algorithm 118

Problem set 120

Chapter 6 Tree and heaps 121

6.1 Red-Black Tree 121

6.2 Operations on RBT 122

6.2.1 Rotation 122

6.2.2 Insertion 123

6.2.3 Deletion 126

6.3 B-tree 127

6.3.1 Searching key k in B-tree 128

6.4 Binomial heap 130

6.4.1 Binomial heap 131

6.5 Fibonacci heap 135

6.5.1 Operation on Fibonacci heap 136

Problem set 138

Chapter 7 Lab session 141

Appendices 141

Further reading 165

Index 167