A Practical Approach to Data Structures and Algorithms

✍ Scribed by Pahuja, Sanjay

• Publisher: New Academic Science
• Year: 2009
• Tongue: English
• Leaves: 573
• Category: Library

✦ Table of Contents

Cover......Page 1
Preface......Page 6
Contents......Page 8
1.1 Introduction to data representation......Page 12
1.2 Review of data structures—Array, Pointer, Structure, Lists, Trees and Graphs......Page 13
1.3 What is an Algorithm? ......Page 15
1.4 Designing Algorithms......Page 17
1.5 Analyzing Algorithms......Page 20
1.6 Mathematical Notation and Functions......Page 23
1.7 Asymptotic Notation (O,θ,Ω)......Page 27
1.8 Performance Measurement......Page 28
2.3 Functions......Page 29
2.4 Structures and Unions......Page 37
2.5 Pointers......Page 38
2.6 Memory Management in 'C'......Page 40
3.1 One Dimensional Arrays......Page 41
3.2 Two-Dimensional Arrays......Page 52
3.3 Multidimensional Arrays......Page 61
3.4 Ordered Arrays......Page 66
3.5 Sparse Matrix......Page 73
4.1 Linear Linked List and Operations......Page 77
4.2 Circular Linked Linear Lists and Operations......Page 111
4.3 Doubly Linear Linked Lists and Operations......Page 127
4.4.1 Polynomial Manipulation......Page 148
4.4.2 Multiple–Precision Arithmetic......Page 172
4.5 Set Operation on Linked List......Page 177
5.1 Representation: Using Array and Linked List......Page 185
5.2 Push and Pop Operations......Page 188
5.3 Representation of expression: Infix, Postfix and Prefix......Page 193
5.4 Evaluation of the Postfix expression......Page 195
5.5 Transforming Infix Expression into Postfix Expression......Page 200
5.6 Recursion......Page 207
6.1 Representation: Using Array and Linked List......Page 219
6.2 Insertion and Deletion Operations......Page 221
6.3 Circular Queue......Page 227
6.4 Double Ended Queues (DEQues)......Page 232
6.5 Priority Queue......Page 237
6.6 Multiple Queues......Page 242
7.1 General Concept......Page 245
7.2 Binary Tree......Page 247
7.3 Sequential and Linked List Representation of Binary Tree......Page 249
7.4 Binary Tree Traversal Algorithm: Recursive and Non-recursive......Page 251
7.5 Threaded Binary Tree Traversal......Page 266
7.6 General Tree and Its Conversion......Page 272
7.7 Binary Search Tree (BST)......Page 282
7.8 Height Balanced Trees: AVL......Page 303
7.9 B-Trees......Page 321
7.10 Applications of Trees......Page 326
8.1 Properties of Graphs......Page 330
8.2 Representation of Graphs......Page 332
8.3 Traversal Algorithms—Depth First Search, Breadth First Search......Page 334
8.4 Minimum Cost Spanning Tree......Page 346
8.5 Biconnectivity......Page 358
8.6 Strong Connectivity......Page 363
8.7 Transitive Closure Algorithm......Page 366
8.8 Shortest Path Algorithms......Page 368
8.9 Applications of Graph......Page 378
9.1 Internal and External Sorting......Page 380
9.2 Sorting Problem......Page 381
9.2.1 Bubble Sort......Page 383
9.2.2 Selection Sort......Page 387
9.2.3 Insertion Sort......Page 393
9.2.4 Shell Sort......Page 396
9.2.6 Radix Sort......Page 401
9.2.7 Merge Sort......Page 406
9.2.8 Quick Sort......Page 413
9.2.9 Heap Sort......Page 420
10.2 Binary Search......Page 444
10.3 Hashing......Page 445
10.3.1 Hash Functions......Page 447
10.3.2 Collision Resolution Techniques......Page 449
10.4 Dynamic Memory Allocation......Page 462
11.1 Definition and Concept......Page 472
11.2 File Organization......Page 473
11.3 Files in 'C'......Page 476
Appendix: Conceptual Problem Solutions......Page 484
Index......Page 564
CD–Index......Page 570