Unit - I Introduction to Data Structures 1.1 Concept and need of DS, Abstract Data Type 1.2 Types of Data Structures : (i) Linear Data Structures (ii) Non - Linear Data Structures 1.3 Algorithm Complexity : (i) Time (ii) Space 1.4 Operations on Data Structures : (i) Traversing, (ii) Searching, (iii) Insertion, (iv) Deletion, (v) Sorting. Unit - II Searching and Sorting 2.1 Searching : Searching an item in a data set using following methods : i) Linear Search ii) Binary Search 2.2 Sorting : Sorting of data set in an order using following methods : i) Bubble Sort ii) Selection Sort iii) Insertion Sort iv) Quick Sort v) Radix Sort Unit - III Stacks and Queues 3.1 Introduction to Stack - Stack representation in memory using array. - Stack as an ADT - Stack Operations - PUSH, POP - Stack Operations Conditions - Stack Full/Stack Overflow, Stack Empty/ Stack Underflow. - Applications of Stack Reversing a list Polish notations 3.2 Conversion of infix to postfix expression, Evaluation of postfix expression, Converting an infix into prefix expression, Evaluation of prefix expression, Recursion, Tower of Hanoi 3.3 Introduction to Queue - Queue representation in memory using array - Queue as an ADT - Types of Queues : Linear Queue, Circular Queue, Concept of Priority Queue - Queue Operations - INSERT, DELETE - Queue Operations Conditions - Queue Full, Queue Empty - Applications of Queue Unit - IV Linked List 4.1 Introduction to Linked List Terminologies : Node, Address, Pointer, Information field/Data field, Next pointer, null pointer, Empty list. 4.2 Type of lists : Linear list, Circular list 4.3 Operations on a singly linked list : Traversing a singly linked list, Searching a key in linked list, Inserting a new node in a linked list, Deleting a node from a linked list. Unit - V Trees and Graphs Introduction to Trees 5.1 Terminologies : Tree, degree of a node, degree of a tree, level of a node, leaf node, Depth/Height of a tree, In-degree and Out-degree, Path, Ancestor and descendant nodes. 5.2 Tree Types and Traversal methods Types of Trees : General tree, Binary tree, Binary search tree (BST) Binary tree traversal : In order traversal, Preorder traversal, Post order traversal 5.3 Expression tree 5.4 Introduction to Graph terminologies : graph, node (Vertices), arcs (edge), directed graph, undirected graph, in-degree, out-degree, adjacent, successor, predecessor, relation, path, sink, articulation point. 5.5 Adjacency List, Adjacency Matrix of directed/undirected graph.
