UNIT-I

Introduction to Data Structure: Data, Entity, Information, Difference between Data and Information, Data type, Built-in data type, Abstract data type, Definition of data structures, Types of data structures — Linear and Non-Linear data structure. Introduction to Algorithms: Definition, Difference between algorithm and programs, properties of algorithm, Algorithm design techniques, Performance analysis of algorithms, Complexity of algorithms, Asymptotic Notations — Big O Notation.

UNIT-II

Arrays: Definition, Single and Multidimensional arrays, Representation of arrays — Row Major Order and Column Major Order, Derivation of index formulae for 1-D, 2-D arrays. Sparse Matrices and their representations. Linked lists: Array and Pointer implementation of singly linked list, Operations on a linked list — insertion, deletion, traversal and searching. Doubly linked list. Circularly linked list.

UNIT-III

Stacks: Introduction, Primitive stack operations — push & pop, Array and linked implementation of stack, Applications of stack — conversion of infix to prefix and postfix expressions, Evaluation of prefix & postfix expression. Queues: Introduction, Queue operations — create, add, delete, is-full and is-empty. Circular Queue. Array and linked implementation of queues, Dequeue and Priority Queue.

UNIT-IV

Trees: Basic terminology used with tree, Binary trees, Binary tree representation — Array representation and Pointer (Linked list) representation. Binary Search Tree. Recursive algorithms of tree traversals — Inorder, Preorder and Postorder. Operation of insertion, deletion, searching & modification of data in a Binary Search Tree.

UNIT-V

Graphs: Terminology used with graph, Data structure for graph representations — Adjacency Matrices. Graph traversals — Depth First Search (DFS) and Breadth First Search (BFS).

Text and Reference Books:

1.     Fundamentals of Data Structures in C, €. Horowitz and S. Sahani, Universities Press, 2“ Edition, 2008.