Data Structures

PART-A

UNIT 1: Introduction to Data Structures

1. Concepts and definitions of basic data structure

2. Top Down and Bottom up Approaches

3.  Big “O” Notations

4. Time and Space Complexity of algorithms

5. Types of data Structures

6. Concept of Garbage Collection and Memory Allocation

7. Array: Representation of one and multidimensional arrays in memory

8. Array Operations

9. Sparse matrices: representation 

10.  Searching Techniques: Linear  Search; Binary search

11.  Sorting Techniques: Internal and External Sorting Techniques. 

Unit 2: Stacks and Queues

2.1 Stacks: Representation

2.2 Operations of Stack

2.3 Applications of Stack (Tower of hanoi algorithm and evaluation of arithmetic expression)

2.4 Queues: Representation

2.5 Operations of queue

2.6 Types of Queue

2.7 Applications of Queue  

Unit 3: Introduction to Linked List

3.1 Linked List: Representation

3.2 Operations of Linear Linked List

3.3 Applications of Linear Linked List

3.4 Circular Linked List and its operations

3.5 Double Linked List and operations

PART-B

Unit 4: Trees

4.1 Trees Terminology 

4.2 Representing a general tree

4.3 Types of Tree

4.4 Binary Tree: Memory representation

4.5 Binary tree Construction

4.6 Traversing of Binary Tree

4.7 Convert general tree into binary tree

4.8 Threaded Binary tree

4.9 Binary Search Tree: Searching and inserting in BST; Deleting in a BST; Applications of BST

4.10 B tree and its operations

4.11 B+ trees

4.12 AVL trees and its operations

Unit 5: Graph Theory

5.1 Graphs: Terms related with Graphs

5.2Types of Graphs

5.3 Sequential and Linked Representation of Graphs

5.4 Traversing a Graph: BFS; DFS

5.5 Minimum Spanning Tree

5.6 Graph Operations

5.7 Shortest path Algorithms: Dijkstra’s and Warshall’s Algorithm

Unit 6: File Organization

6.1 Introduction to File Organization

6.2 File attributes and operations

6.3 Fixed and Variable Length Record

6.4 Hashing Techniques

6.5 Collision Resolution Techniques