| |
| |
| Preface | |
| |
| |
| Acknowledgements | |
| |
| |
| Features of the Book | |
| |
| |
| |
| Fundamental Concepts | |
| |
| |
| |
| Introduction to Programming | |
| |
| |
| |
| Object-oriented Programming | |
| |
| |
| |
| Introduction to Data Structures | |
| |
| |
| |
| Data | |
| |
| |
| |
| Data type | |
| |
| |
| |
| Data object | |
| |
| |
| |
| Data structure | |
| |
| |
| |
| Abstract data type | |
| |
| |
| |
| Types of Data Structures | |
| |
| |
| |
| Primitive and non-primitive data structures | |
| |
| |
| |
| Linear and non-linear data structures | |
| |
| |
| |
| Static and dynamic data structures | |
| |
| |
| |
| Persistent and ephemeral data structures | |
| |
| |
| |
| Sequential access and direct access data structures | |
| |
| |
| |
| Introduction to Algorithms | |
| |
| |
| |
| Characteristics of algorithms | |
| |
| |
| |
| Algorithmics | |
| |
| |
| |
| Algorithm design tools: Pseudocode and flowchart | |
| |
| |
| |
| Pseudocode | |
| |
| |
| |
| Pseudocode notations | |
| |
| |
| |
| Algorithm header | |
| |
| |
| |
| Purpose | |
| |
| |
| |
| Condition and return statements | |
| |
| |
| |
| Statement numbers | |
| |
| |
| |
| Variables | |
| |
| |
| |
| Statement constructs | |
| |
| |
| |
| Subalgorithms | |
| |
| |
| |
| Relationship among data, data structures, and algorithms | |
| |
| |
| |
| Implementation of data structures | |
| |
| |
| |
| Flowcharts | |
| |
| |
| |
| Analysis of Algorithms | |
| |
| |
| |
| Complexity of algorithms | |
| |
| |
| |
| Space complexity | |
| |
| |
| |
| Time complexity | |
| |
| |
| |
| Computing time complexity of an algorithm | |
| |
| |
| |
| Big-O notation | |
| |
| |
| |
| From Problem to Program | |
| |
| |
| |
| Software Engineering | |
| |
| |
| |
| Analysis phase | |
| |
| |
| |
| Design phase | |
| |
| |
| |
| Implementation phase | |
| |
| |
| |
| Testing phase | |
| |
| |
| |
| Verification phase | |
| |
| |
| |
| Linear Data Structure Using Arrays | |
| |
| |
| |
| Sequential Organization | |
| |
| |
| |
| Linear Data Structure Using Sequential Organization: Arrays | |
| |
| |
| |
| Array as an Abstract Data Type | |
| |
| |
| |
| Memory Representation and Address Calculation | |
| |
| |
| |
| Class Array | |
| |
| |
| |
| Inserting an element into an array | |
| |
| |
| |
| Deleting an element | |
| |
| |
| |
| Arrays Using Template | |
| |
| |
| |
| Multidimensional Arrays | |
| |
| |
| |
| Two-dimensional arrays | |
| |
| |
| |
| n-dimensional arrays | |
| |
| |
| |
| Concept of Ordered List | |
| |
| |
| |
| Single Variable Polynomial | |
| |
| |
| |
| Representation using arrays | |
| |
| |
| |
| Polynomial as array of structure | |
| |
| |
| |
| Polynomial evaluation | |
| |
| |
| |
| Polynomial addition | |
| |
| |
| |
| Polynomial multiplication | |
| |
| |
| |
| Array for Frequency Count | |
| |
| |
| |
| Sparse Matrix | |
| |
| |
| |
| Sparse matrix representation | |
| |
| |
| |
| Sparse matrix addition | |
| |
| |
| |
| Transpose of sparse matrix | |
| |
| |
| |
| String Manipulation Using Array | |
| |
| |
| |
| Pros and Cons of Arrays | |
| |
| |
| |
| Characteristics | |
| |
| |
| |
| Advantages | |
| |
| |
| |
| Disadvantages | |
| |
| |
| |
| Applications of arrays | |
| |
| |
| |
| Stacks | |
| |
| |
| |
| Concept of Stacks and Queues | |
| |
| |
| |
| Stacks | |
| |
| |
| |
| Primitive operations | |
| |
| |
| |
| Stack Abstract Data Type | |
| |
| |
| |
| Representation of Stacks Using Sequential Organization (Arrays) | |
| |
| |
| |
| Create | |
| |
| |
| |
| Empty | |
| |
| |
| |
| Get Top | |
| |
| |
| |
| Push | |
| |
| |
| |
| Pop | |
| |
| |
| |
| Stacks Using Template | |
| |
| |
| |
| Multiple Stacks | |
| |
| |
| |
| Applications of Stack | |
| |
| |
| |
| Expression Evaluation and Conversion | |
| |
| |
| |
| Polish notation and expression conversion | |
| |
| |
| |
| Need for prefix and postfix expressions | |
| |
| |
| |
| Postfix expression evaluation | |
| |
| |
| |
| Processing of Function Calls | |
| |
| |
| |
| Reversing a String with a Stack | |
| |
| |
| |
| Checking Correctness of Well-formed Parentheses | |
| |
| |
| |
| Recursion | |
| |
| |
| |
| Parsing Computer Programs | |
| |
| |
| |
| Backtracking Algorithms | |
| |
| |
| |
| Converting Decimal Numbers to Binary | |
| |
| |
| |
| Recursion | |
| |
| |
| |
| Introduction | |
| |
| |
| |
| Recurrence | |
| |
| |
| |
| Use of Stack in Recursion | |
| |
| |
| |
| Variants of Recursion | |
| |
| |
| |
| Direct recursion | |
| |
| |
| |
| Indirect recursion | |
| |
| |
| |
| Tail recursion | |
| |
| |
| |
| Linear recursion | |
| |
| |
| |
| Tree recursion | |
| |
| |
| |
| Execution of Recursive Calls | |
| |
| |
| |
| Recursive Functions | |
| |
| |
| |
| Writing recursive code | |
| |
| |
| |
| Tower of Hanoi: An example of recursion | |
| |
| |
| |
| Checking for correctness | |
| |
| |
| |
| Things to remember | |
| |
| |
| |
| Iteration Versus Recursion | |
| |
| |
| |
| Demerits of recursive algorithms | |
| |
| |
| |
| Demerits of iterative methods | |
| |
| |
| |
| Simulating Recursion Using Stack (Eliminating Recursion) | |
| |
| |
| |
| Applications of Recursion | |
| |
| |
| |
| Queues | |
| |
| |
| |
| Concept of Queues | |
| |
| |
| |
| Queue as Abstract Data Type | |
| |
| |
| |
| Realization of Queues Using Arrays | |
| |
| |
| |
| Circular Queue | |
| |
| |
| |
| Advantages of using circular queues | |
| |
| |
| |
| Multi-queues | |
| |
| |
| |
| Deque | |
| |
| |
| |
| Priority Queue | |
| |
| |
| |
| Array implementation of priority queue | |
| |
| |
| |
| Applications of Queues | |
| |
| |
| |
| Josephus problem | |
| |
| |
| |
| Job scheduling | |
| |
| |
| |
| Simulation | |
| |
| |
| |
| Queues Using Template | |
| |
| |
| |
| Linked Lists | |
| |
| |
| |
| Introduction | |
| |
| |
| |
| Linked List | |
| |
| |
| |
| Comparison of sequential and linked organizations | |
| |
| |
| |
| Linked list terminology | |
| |
| |
| |
| Primitive operations | |
| |
| |
| |
| Realization of Linked Lists | |
| |
| |
| |
| Realization of linked list using arrays | |
| |
| |
| |
| Linked list using dynamic memory management | |
| |
| |
| |
| Dynamic Memory Management | |
| |
| |
| |
| Dynamic memory management in C++ with new and delete operators | |
| |
| |
| |
| Linked List Abstract Data Type | |
| |
| |
| |
| Data structure of node | |
| |
| |
| |
| Insertion of a node | |
| |
| |
| |
| Linked list traversal | |
| |
| |
| |
| Deletion of a node | |
| |
| |
| |
| Linked List Variants | |
| |
| |
| |
| Head pointer and header node | |
| |
| |
| |
| Types of linked list | |
| |
| |
| |
| Linear and circular linked lists | |
| |
| |
| |
| Doubly Linked List | |
| |
| |
| |
| Creation of doubly linked list | |
| |
| |
| |
| Deletion of a node from a doubly linked list | |
| |
| |
| |
| Insertion of a node in a doubly linked list | |
| |
| |
| |
| Traversal of DLL | |
| |
| |
| |
| Circular Linked List | |
| |
| |
| |
| Singly circular linked list | |
| |
| |
| |
| Circular linked list with header node | |
| |
| |
| |
| Doubly circular linked list | |
| |
| |
| |
| Polynomial Manipulations | |
| |
| |
| |
| Polynomial evaluation | |
| |
| |
| |
| Polynomial addition | |
| |
| |
| |
| Polynomial multiplication | |
| |
| |
| |
| Representation of Sparse Matrix Using Linked List | |
| |
| |
| |
| Linked Stack | |
| |
| |
| |
| Class for linked stack | |
| |
| |
| |
| Operations on linked stack | |
| |
| |
| |
| Linked Queue | |
| |
| |
| |
| Erasing a linked queue | |
| |
| |
| |
| Generalized Linked List | |
| |
| |
| |
| Definition | |
| |
| |
| |
| Applications | |
| |
| |
| |
| Representation of polynomials using generalized linked list | |
| |
| |
| |
| Representation of sets using generalized linked list | |
| |
| |
| |
| More on Linked Lists | |
| |
| |
| |
| Copying a linked list | |
| |
| |
| |
| Computing the length of a linked list | |
| |
| |
| |
| Reversing singly linked list without temporary storage | |
| |
| |
| |
| Concatenating two linked lists | |
| |
| |
| |
| Erasing the linked list | |
| |
| |
| |
| Application of Linked List-Garbage Collection | |
| |
| |
| |
| Trees | |
| |
| |
| |
| Introduction | |
| |
| |
| |
| Basic terminology | |
| |
| |
| |
| General tree | |
| |
| |
| |
| Representation of a general tree | |
| |
| |
| |
| Types of Trees | |
| |
| |
| |
| Binary Tree | |
| |
| |
| |
| Properties of a binary tree | |
| |
| |
| |
| Binary Tree Abstract Data Type | |
| |
| |
| |
| Realization of a Binary Tree | |
| |
| |
| |
| Array implementation of binary trees | |
| |
| |
| |
| Linked implementation of binary trees | |
| |
| |
| |
| Insertion of a Node in Binary Tree | |
| |
| |
| |
| Binary Tree Traversal | |
| |
| |
| |
| Preorder traversal | |
| |
| |
| |
| Inorder traversal | |
| |
| |
| |
| Postorder traversal | |
| |
| |
| |
| Non-recursive implementation of traversals | |
| |
| |
| |
| Formation of binary tree from its traversals | |
| |
| |
| |
| Breadth- and depth-first traversals | |
| |
| |
| |
| Other Tree Operations | |
| |
| |
| |
| Counting nodes | |
| |
| |
| |
| Counting leaf nodes | |
| |
| |
| |
| Computing height of binary tree | |
| |
| |
| |
| Getting mirror, replica, or tree interchange of binary tree | |
| |
| |
| |
| Copying binary tree | |
| |
| |
| |
| Equality test | |
| |
| |
| |
| Conversion of General Tree to Binary Tree | |
| |
| |
| |
| Binary Search Tree | |
| |
| |
| |
| Inserting a node | |
| |
| |
| |
| Searching for a key | |
| |
| |
| |
| Deleting a node | |
| |
| |
| |
| Binary tree and binary search tree | |
| |
| |
| |
| Threaded Binary Tree | |
| |
| |
| |
| Threading a binary tree | |
| |
| |
| |
| Right-threaded binary tree | |
| |
| |
| |
| Inorder traversal | |
| |
| |
| |
| Preorder traversal | |
| |
| |
| |
| Insert to right of a node | |
| |
| |
| |
| Deleting anode | |
| |
| |
| |
| Pros and cons | |
| |
| |
| |
| Applications of Binary Trees | |
| |
| |
| |
| Expression tree | |
| |
| |
| |
| Decision tree | |
| |
| |
| |
| Huffman's coding | |
| |
| |
| |
| Game trees | |
| |
| |
| |
| Graphs | |
| |
| |
| |
| Introduction | |
| |
| |
| |
| Graph Abstract Data Type | |
| |
| |
| |
| Representation of Graphs | |
| |
| |
| |
| Adjacency matrix | |
| |
| |
| |
| Adjacency list | |
| |
| |
| |
| Adjacency multilist | |
| |
| |
| |
| Inverse adjacency list | |
| |
| |
| |
| Comparison of sequential and linked representations | |
| |
| |
| |
| Graph Traversal | |
| |
| |
| |
| Depth-first search | |
| |
| |
| |
| Breadth-first search | |
| |
| |
| |
| Spanning Tree | |
| |
| |
| |
| Connected components | |
| |
| |
| |
| Prim's algorithm | |
| |
| |
| |
| Kruskal's algorithm | |
| |
| |
| |
| Biconnected components | |
| |
| |
| |
| Disjoint set operations | |
| |
| |
| |
| Shortest Path Algorithm | |
| |
| |
| |
| Searching and Sorting | |
| |
| |
| |
| Searching | |
| |
| |
| |
| Search Techniques | |
| |
| |
| |
| Sequential search | |
| |
| |
| |
| Binary search | |
| |
| |
| |
| Fibonacci search | |
| |
| |
| |
| Indexed sequential search | |
| |
| |
| |
| Hashed search | |
| |
| |
| |
| Sorting | |
| |
| |
| |
| Types of sorting | |
| |
| |
| |
| General sort concepts | |
| |
| |
| |
| Bubble sort | |
| |
| |
| |
| Insertion sort | |
| |
| |
| |
| Selection sort | |
| |
| |
| |
| Quick sort | |
| |
| |
| |
| Heap sort | |
| |
| |
| |
| Shell sort | |
| |
| |
| |
| Bucket sort | |
| |
| |
| |
| Radix sort | |
| |
| |
| |
| File sort | |
| |
| |
| |
| Merge sort | |
| |
| |
| |
| Multiway Merge and Polyphase Merge | |
| |
| |
| |
| Comparison of ordinary merge sort and polyphase sort | |
| |
| |
| |
| Comparison of M/Sorting Methods | |
| |
| |
| |
| Search Trees | |
| |
| |
| |
| Symbol Table | |
| |
| |
| |
| Representation of symbol table | |
| |
| |
| |
| Optimal Binary Search Tree | |
| |
| |
| |
| AVL Tree (Height-balanced Tree) | |
| |
| |
| |
| Implementation of AVL technique | |
| |
| |
| |
| Insertions and deletions in AVL tree | |
| |
| |
| |
| Hashing | |
| |
| |
| |
| Introduction | |
| |
| |
| |
| Key Terms and Issues | |
| |
| |
| |
| Hash Functions | |
| |
| |
| |
| Good hash function | |
| |
| |
| |
| Division method | |
| |
| |
| |
| Multiplication method | |
| |
| |
| |
| Extraction method | |
| |
| |
| |
| Mid-square hashing | |
| |
| |
| |
| Folding technique | |
| |
| |
| |
| Rotation | |
| |
| |
| |
| Universal hashing | |
| |
| |
| |
| Collision Resolution Strategies | |
| |
| |
| |
| Open addressing | |
| |
| |
| |
| Chaining | |
| |
| |
| |
| Hash Table Overflow | |
| |
| |
| |
| Open addressing for overflow handling | |
| |
| |
| |
| Overflow handling by chaining | |
| |
| |
| |
| Extendible Hashing | |
| |
| |
| |
| Dictionary | |
| |
| |
| |
| Skip List | |
| |
| |
| |
| Comparison of Hashing and Skip Lists | |
| |
| |
| |
| Heaps | |
| |
| |
| |
| Basic Concepts | |
| |
| |
| |
| Min-heap and max-heap | |
| |
| |
| |
| Implementation of Heap | |
| |
| |
| |
| Heap as Abstract Data Type | |
| |
| |
| |
| Operations on heaps | |
| |
| |
| |
| Heap Applications | |
| |
| |
| |
| Heap Sort | |
| |
| |
| |
| Binomial Trees and Heaps | |
| |
| |
| |
| Binomial trees | |
| |
| |
| |
| Binomial heap | |
| |
| |
| |
| Representation of binomial heap | |
| |
| |
| |
| Operations on binomial heaps | |
| |
| |
| |
| Fibonacci Heap | |
| |
| |
| |
| Representation of Fibonacci heap | |
| |
| |
| |
| Operations on Fibonacci heaps | |
| |
| |
| |
| Indexing and Multiway Trees | |
| |
| |
| |
| Introduction | |
| |
| |
| |
| Indexing | |
| |
| |
| |
| Indexing techniques | |
| |
| |
| |
| Types of Search Trees | |
| |
| |
| |
| Multiway search tree | |
| |
| |
| |
| B-tree | |
| |
| |
| |
| B+tree | |
| |
| |
| |
| Trie tree | |
| |
| |
| |
| Splay tree | |
| |
| |
| |
| Red-black tree | |
| |
| |
| |
| Z-dimensional tree | |
| |
| |
| |
| AA Tree | |
| |
| |
| |
| Files | |
| |
| |
| |
| Introduction | |
| |
| |
| |
| External Storage Devices | |
| |
| |
| |
| Magnetic tape | |
| |
| |
| |
| Magnetic drum | |
| |
| |
| |
| Magnetic disk | |
| |
| |
| |
| File Organization | |
| |
| |
| |
| Schemes of file organization | |
| |
| |
| |
| Factors affecting file organization | |
| |
| |
| |
| Factors involved in selecting file organization | |
| |
| |
| |
| Files Using C++ | |
| |
| |
| |
| File I/O classes | |
| |
| |
| |
| Primitive functions | |
| |
| |
| |
| Binary and text files | |
| |
| |
| |
| Sequential File Organization | |
| |
| |
| |
| Primitive operations | |
| |
| |
| |
| Advantages | |
| |
| |
| |
| Drawbacks | |
| |
| |
| |
| Direct Access File Organization | |
| |
| |
| |
| Primitive operations | |
| |
| |
| |
| Indexed Sequential File Organization | |
| |
| |
| |
| Types of indices | |
| |
| |
| |
| Structure of indexed sequential file | |
| |
| |
| |
| Characteristics of indexed sequential file | |
| |
| |
| |
| Linked Organization | |
| |
| |
| |
| Multilist files | |
| |
| |
| |
| Coral rings | |
| |
| |
| |
| Inverted files | |
| |
| |
| |
| Cellular partitions | |
| |
| |
| |
| Standard Template Library | |
| |
| |
| |
| Abstract Data Type | |
| |
| |
| |
| Abstract data type and data structures | |
| |
| |
| |
| Creating abstract data types | |
| |
| |
| |
| Stack abstract data type | |
| |
| |
| |
| Survey of Programming Techniques | |
| |
| |
| |
| Standard Template Library | |
| |
| |
| |
| Containers | |
| |
| |
| |
| Algorithms | |
| |
| |
| |
| Iterators | |
| |
| |
| |
| Function Objects | |
| |
| |
| |
| Algorithm Analysis and Design | |
| |
| |
| |
| Introduction | |
| |
| |
| |
| Algorithm analysis | |
| |
| |
| |
| Asymptotic notations (�, �,O) | |
| |
| |
| |
| Divide-and-Conquer | |
| |
| |
| |
| Unique characteristics and use | |
| |
| |
| |
| General method | |
| |
| |
| |
| Binary search | |
| |
| |
| |
| Merge sort | |
| |
| |
| |
| Quick sort | |
| |
| |
| |
| Strassen's algorithm for matrix multiplication | |
| |
| |
| |
| Greedy Method | |
| |
| |
| |
| General greedy method | |
| |
| |
| |
| Knapsack problem | |
| |
| |
| |
| Dynamic Programming | |
| |
| |
| |
| General method of dynamic programming | |
| |
| |
| |
| Elements of dynamic programming | |
| |
| |
| |
| Principle of optimality | |
| |
| |
| |
| Limitations of dynamic programming | |
| |
| |
| |
| Knapsack problem | |
| |
| |
| |
| Pattern Matching | |
| |
| |
| |
| Brute-force approach | |
| |
| |
| |
| Boyer-Moore algorithm | |
| |
| |
| |
| Knuth-Morris-Pratt algorithm | |
| |
| |
| |
| Tries | |
| |
| |
| |
| Standard tries | |
| |
| |
| |
| Compressed tries | |
| |
| |
| |
| Suffix tries | |
| |
| |
| Appendix: Overview of C++ Programming | |
| |
| |
| Index | |