Data Structures 2e

Home / Browse / Data Structures 2e

Data Structures 2e

ISBN 9789393665751

Publication Date Fri Jul 01 00:00:00 UTC 2016

- Twitter
- Facebook
- WhatsApp
- LinkedIn
- Copy URL

PAPERBACK

EBOOK (EPUB)

EBOOK (PDF)

Description

Table of contents

Biographical note

User Reviews

The study of Data Structures provides the base for many fields and areas in computer science and information technology courses world over. This book, in its second edition, continues to provide an in-depth introduction to Data Structures and has its emphasis on clear concepts.

Cover
Title Page
Copyright Page
Dedication
Contents
Preface
CHAPTER 1 INTRODUCTION TO DATA STRUCTURES
- Overview
  - Need for Data Structures
- Definitions
  - Types
  - Data Type
  - Abstract Data Type (ADT)
  - Advantages of ADT
  - Pre and Post Conditions
  - Data Structures
  - Types of Data Structures
  - Choice of Data Structures
  - Definitions Related to Data Structures
- Summary
- Solved Exercises
- Review Questions
- Exercises
CHAPTER 2 ALGORITHM ANALYSIS
- Overview
- Introduction
- Problem Solving
  - Categories of Problem Solving
  - Problem Solving Strategies
- Modular Design
  - Bottom-up Design
  - Top-down Design
- Implementation of Algorithms
  - Choice of Data Structure
  - Common Errors in Implementation
- Testing
  - Functional Testing
  - Performance Testing
- Verification
  - Loop Invariants
  - Program Verification – An example
  - Verification of Programs Using Arrays
- Algorithm Analysis
  - Operations Count
- Time Complexity Classes
- Asymptotic Analysis
  - Asymptotic Upper Bound–Big O
- Summary
- Review Questions
- Exercises
CHAPTER 3 ARRAYS
- Overview
- Introduction
- Range of an Array
  - Primitive Operations
  - Element Access in an Array
  - Addressing Function
- One-Dimensional Array
- Two-Dimensional Array
  - Storage Representation of 2D Arrays
- Multidimensional Arrays
  - Addressing Function of a 3D Array
- Special Types of Matrices
  - Lower Triangular Matrices
  - Upper Triangular Matrices
  - Tridiagonal Matrix
  - Sparse Matrices
- Strings
  - Variable Length Strings
  - String Operations
  - Substring
  - Records
  - Variant Records
- Summary
- Solved Exercise
- Exercises
- Programming Exercises
CHAPTER 4 LINKED LISTS
- Overview
- Introduction
- Memory Allocation
- Benefits of Linked Lists
- Limitations of Linked Lists
- Types
- Basic Operations in Linked List
  - ADT List
- Singly Linked Lists
  - C Program
  - Simple Algorithms on Linked Lists
  - Print the Elements in a List
  - Insert a Node in a Sorted List
  - Copy a List
  - Concatenation of Two Lists
  - Deletion of a Node
- Circular Linked Lists
  - Count the Number of Nodes in a Circularly Linked List
  - Print the Elements of a Circularly Linked List
- Doubly Linked Lists
  - Print the Elements in a DLL
  - Insertion in a DLL
  - Deletion in DLL
- Circular Doubly Linked List
  - Initialization of a Circular DLL
  - Header (or Sentinel Node)
  - Cursor Implementation of Linked Lists
  - Initialization of Cursor
  - Allocate a Node
  - Deallocation of Node from the List
  - Initialization of a List
  - Checking for Null List
  - C function to Check for Null List
  - Insert a Node at the Head of a List
  - Insert a Value After a Given Key
  - Deletion of a Value From a List
  - Print the Values of a List
  - Performance Comparison of Various Types of Lists
- Multiply Linked Lists
  - Sparse Matrix Representation
  - Applications of Linked Lists
  - Polynomial Representation
  - Polynomial Addition
  - Representation of Polynomials With Multi Variables
- Summary
- Review Questions
- Exercises
CHAPTER 5 STACKS
- Overview
- Introduction
- ADT Stack
  - Create (S)
  - Push (S, Element)
  - Pop (S)
  - ShowTop(S)
  - isEmpty(S)
- Implementation of Stack
  - Array Implementation of Stack
- Linked List Implementation of Stack
  - Definition of a Stack Using Linked Lists
  - Reversing a List
  - Palindrome Checking
- Applications of Stack
  - Well Formedness of Parenthesis
  - Syntax Checking using Stacks
  - Infix, Prefix and Postfix Forms of Expressions
  - Conversion of Infix Expression to Postfix Form
  - Steps in Conversion of Infix Expression to Postfix Notation
  - Evaluation of Postfix Expressions
  - Algorithm to Evaluate Postfix Expression
  - Evaluation of Recursive Functions
  - Solving Tower of Hanoi Problem
  - Recurrence Relation for Tower of Hanoi Problem
  - Solving Maze Problem
- Solved Exercises
- Exercises
- Programming Exercises
CHAPTER 6 QUEUES
- Overview
- Introduction
- Implementation of Queues
  - Basic Operations on Queues
- Implementation of Basic Operations on Array-Based Implementation ofQueues
  - Creation
  - Insertion
  - Deletion
- Implementations of basic operations on linked list-based implementation of queues
  - Creation
  - Insertion
  - Deletion
- Implementation of Queue Operations Using Stacks
  - Enqueue Operation
  - Dequeue Operation
  - Round Robin Algorithm
  - Priority Queue
  - Limitations of Linear Array-Based Queues
- Circular Queues
- Dequeue
  - Input Restricted Dequeue
  - Output Restricted Dequeue
  - Applications of Queues
- Summary
- Review Questions
- Exercises
CHAPTER 7 TREES
- Overview
- Introduction
- Binary Trees
- Types of Binary Trees
  - Strictly Binary Tree
  - Complete Binary Tree
  - Almost Complete Binary Tree
  - Skew Trees
- Number of Nodes in Binary Trees
  - Strictly Binary Tree
  - Complete Binary Tree
  - Almost Complete Binary Tree
  - Skew Trees
  - Binary Trees
  - Operations on Binary Trees
  - Inorder Traversal
  - Pre Order Traversal
  - Post Order Traversal
  - Breadth First Traversal
- Representation of Binary Trees
  - Linear Representation
  - Linked Representation
  - Node Representation of Binary Trees
  - C Function to Create a Binary Tree Node
  - Construction of a Simple Binary Tree
  - Function to Count the Number of Nodes in a Binary Tree
  - Function to Determine the Depth of the Tree
  - Identical Trees
  - Binary Tree Traversal in C
  - Inorder Traversal
  - Non-Recursive Algorithm for Preorder Traversal
  - Applications of Binary Trees
  - Huffman Coding
  - Decoding
  - Heap
  - Properties of Heap
  - Representation of Heap
  - Operations on a Heap
  - Deletion
  - Threaded Binary Trees
  - Inorder Traversal of Threaded Binary Trees
  - Representation of Right In–Threaded Trees
  - Expression Trees
  - Evaluating an Expression Tree
  - Representing General Trees Using Binary Trees
- Solved Exercises
- Exercises
- Programming Assignments
CHAPTER 8 BINARY SEARCH TREES
- Overview
- Introduction
  - Creation of a BST
  - Searching an Element in BST
  - Complexity of Searching in BST
  - Ordering Elements in BST
  - Minimum Element in a BST
  - Maximum Element in a BST
  - Deletion of an Element in a BST
  - Predecessor of a Node in a BST
  - Successor of a Node
  - Application of BST
  - BST with Duplicates
  - Bin-Packing Problem
  - Indexed Binary Search Trees
  - Indexed Search in Indexed BST
- Summary
- Solved Exercises
- Exercises
- Programming Exercises
CHAPTER 9 BALANCED SEARCH TREES
- Overview
- Adelson Velskii Landis (Avl) Trees
  - Height of AVL Tree
  - Operations in AVL Tree
  - Single Right Rotation (SRR)
  - Single Left Rotation (SLR)
  - Double Left Right Rotation (DLR)
  - Double Right Left Rotation
  - Deletion of Node
  - Illustration of Balancing of Nodes in an AVL Tree
  - Illustration of Deletion on AVL Trees
  - Multiway Search Tree
  - B Trees
- Operations on B-Tree
  - Searching
  - Insertion
  - Deletion
- B+ Tree
  - Search operation
  - Insertion
  - Deletion
  - Situation 1:
  - Situation 2:
  - Trie
  - Searching
- Summary
- Review Questions
- Exercises
CHAPTER 10 HASHING
- Overview
- Introduction
- Hash Functions
  - Direct Method
  - Division-Reminder Method
  - Multiplicative Hashing
  - Mid-Square Method
  - Digit Analysis Method
  - Length Dependent Method
  - Folding Method
- Collision Resolution Techniques
  - Linear Probing
  - Double Hashing
  - Chaining
  - Overflow Area
- Hashing
  - Open Addressing
  - Quadratic probing
  - Separate Chaining
  - Extendible Hashing
  - Find Operation
  - Insertion
- Performance of Hashing
- Theoretical Estimates of Collision Resolution Techniques
- Limitations of Hashing
- Summary
- Review Questions
- Exercises
CHAPTER 11 SORTING AND SEARCHING
- Overview
- Sorting
  - General Background of Sorting
- Classification of Sorting Algorithms
  - Classification Based on Structure of the Algorithm
  - Classification Based on Computational Complexity
  - Classification Based on Stability of Sorting
  - Classification Based on Memory Usage
  - Selection of Sorting Method
  - Complexity Analysis
  - Selection Sort
  - Binary Tree Sort
  - Heap Sort
  - Heap Sort Procedure
  - Complexity
  - Simple Insertion
  - Shell Sort
  - Counting Sort
  - Complexity of Counting Sort
  - Merge Sort
  - Radix Sort
  - Complexity of Radix Sort
  - Bucket Sort
  - Complexity of Bucket Sort
  - Sorting Using Binary Search Tree
  - Sorting on Tapes
  - Polyphase Sorting
  - Sorting on Disks Using Merging
  - Searching
  - Complexity of Sequential Search
  - Binary Search
  - Complexity of Binary Search
  - Searching Using BST
  - Complexity of Searching in BST
- Summary
- Solved Exercises
- Review Questions
- Exercises
- Programming Assignments
CHAPTER 12 GRAPHS
- Overview
- Introduction
  - Representation of Graphs
  - Adjacency Matrix
  - Adjacency Lists
  - Operations on Graphs
  - Insertion
  - Deletion
  - Traversal
  - Breadth First Search (BFS)
  - Data Structures Used in BFS Algorithm
  - BFS on Adjacency Matrix Representation of a Graph
  - BFS on Adjacency List Representation of a Graph
  - Complexity
  - BFS Tree
  - Depth First Search (DFS)
  - DFS (G)
  - DFS_VERTEX(u)
  - Complexity
  - Shortest Path Algorithm
  - Shortest Path in an Unweighted Graph
  - Shortest Path on a Weighted Graph
  - Dijkstra’s Algorithm
  - Implementation of Dijkstra’s Algorithm
  - Complexity Analysis
  - All Pairs Shortest Path
  - Minimum Spanning Tree
  - Kruskal’s Algorithm
  - Prim’s Algorithm
  - Kruskal’s Algorithm
  - Data Structures for Implementation of Kruskal’s Algorithm
  - Complexity of Algorithm
  - Prim’s Algorithm
  - Topological Sort
  - Complexity of Algorithm
  - Biconnected Components
  - Euler Circuit
  - Hamilton Circuits
- Solved Exercises
- Review Questions
- Exercises
CHAPTER 13 INTRODUCTION TO NP COMPLETE PROBLEMS
- Overview
- Introduction
  - Decidability
  - Complexity Class of Problems
- Examples of Problems
  - Simple Path in a Graph
  - Halting Problem
  - NP Complete Problems
  - Solving NP Complete Problems
  - Approximation
  - Probabilistic
  - Heuristic
  - Special Algorithm
  - Polynomial Reduction
  - Polynomial Transformation
  - NP Completeness
  - Is P = NP?
  - P ⊆ NP
  - Cooks Theorem
  - Clique Problem is NP Complete
- Summary
- Review Questions
- Exercises
Index

Dr. A. Chitra is Professor and Head, Department of Computer Applications, PSG College of Technology, Coimbatore. She holds a Ph.D. in Computer Science and is actively involved in teaching and research.

Mr. P T Rajan is an IT Consultant with a broad range of successful experiences in IT project planning, implementation, management and support. Mr. Rajan has a strong background in the infrastructure service and solution industry.

Comments should not be blank

Rating