Data Structures and Algorithms
Table Of Contents UNIT I 1.0 1.1 1.2 Introduction Objective Content 1.2.1 Data Structure 1.2.2 Stack 1.2.3 Queues 6 1.2.4 Linked list 1.2.5 Trees 1.2.6 Sets and disjoints set unions 1.2.7 Huffman Algorithm 1.2.8 Graphs 1.2.9 Graph Traversal 1.2.10 Searching Techniques Revision Points Intext Questions Summary Terminal Exercises Supplementary Materials Assignments Suggested Reading Learning Activities Keywords Page No. 1 1 1 1 2 9 12 15 17 21 26 30 33 33 34 34 35 35 35 35 36
1.3 1.4 1.5 1.6 1.7 1.8 1.9 1.10 1.11
UNIT II 2.0 2.1 2.2 Introduction Objective Content 2.2.1 The General Method [Divide and Conquer] 2.2.2 Binary Search 2.2.3 Finding the Maximum and Minimum 2.2.4 Merge Sort 2.2.5 Quick Sort 2.2.6 Heap Sort 2.2.7 Strassens Matrix Multiplication 2.2.8 The General Method 2.2.9 Knapsack Problem 2.2.10 Minimum-Cost Spanning Trees 2.2.11 Optimal Storage on Tapes 2.2.12 Single Source Shortest Paths Revision Points Intext Questions 37 37 37 37 38 40 42 44 46 53 55 56 59 70 72 79 79
2.3 2.4
2.5 2.6 2.7 2.8 2.9 2.10 2.11
Summary Terminal Exercises Supplementary Materials Assignments Suggested Reading Learning Activities Keywords
80 81 81 81 81 81 82
UNIT III 3.0 3.1 3.2 Introduction Objective Content 3.2.1 The General Method 3.2.2 Principle of Optimality 3.2.3 3.2.4 Multistage Graphs 83 83 83 83 84 84 90
3.3 3.4 3.5 3.6 3.7 3.8 3.9 3.10 3.11
All-Pairs Shortest Paths 3.2.5 0/1 Knapsack 93 3.2.6 The Traveling Salesperson Problem 96 3.2.7 Introduction to Searching 3.2.8 Basic Search Techniques 98 3.2.9 Sequential Search 99 3.2.10 Binary Search 3.2.11 Basic Traversal Techniques 3.2.12 Optimization 3.2.13 AND/OR Graphs 3.2.14 Bi-directional Components 110 3.2.15 Depth First Search and Traversal 111 Revision Points Intext Questions Summary Terminal Exercises Supplementary Materials Assignments Suggested Reading Learning Activities Keywords
98
100 104 105 107
113 113 114 115 115 115 115 115 116
UNIT IV 4.0 4.1 4.2 Introduction Objective Content 117 117 117
4.3 4.4 4.5 4.6 4.7 4.8 4.9 4.10 4.11
4.2.1 The General Method 4.2.2 The 8-Queens Problem 4.2.3 Sum of Subsets 4.2.4 Graph Coloring 4.2.5 Hamiltonian Cycles 4.2.6 Knapsack Problem 4.2.7 The Branch-and-Bound Method 4.2.8 0/1 Knapsack Problem 4.2.9 Traveling Salesperson 4.2.10 Efficiency Considerations Revision Points Intext Questions Summary Terminal Exercises Supplementary Materials Assignments Suggested Reading Learning Activities Keywords
118 123 126 127 131 133 136 143 147 155 157 157 158 159 159 159 160 160 160
UNIT V 5.0 5.1 5.2 Introduction Objective Content 5.2.1 Basic Concepts 5.2.2 NP-Hard Graph Problems 5.2.3 5.2.4 5.2.5 5.3 5.4 5.5 5.6 5.7 5.8 5.9 5.10 5.11 NP-Hard Scheduling Problems NP-Hard Code Generation Problems 161 161 162 162 167 170 174 178 180 180 180 181 181 181 182 182 182
Introduction to Approximate Algorithms for NP-Hard Problems Revision Points Intext Questions Summary Terminal Exercises Supplementary Materials Assignments Suggested Reading Learning Activities Keywords
