| |

| |

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 | |