Unit - IIntroduction to Data Structures 1a. Classify the given type of Data structures based on their characteristics.1b. Explain complexity of the given algorithm in terms of time and space.1c. Explain the given operations to be performed on the given type of data structures. 1.1 Concept and need of DS, Abstract Data Type1.2 Types of Data Structures : (i) Linear Data Structures (ii) Non - Linear Data Structures1.3 Algorithm Complexity : (i) Time (ii) Space1.4 Operations on Data Structures : (i) Traversing, (ii) Searching, (iii) Insertion, (iv) Deletion, (v) Sorting.
Unit - IISearching and Sorting 2a. Explain working of the given search method with an example.2b. Write an algorithm to search the given key using binary Search method.2c. Write an Algorithm to sort data using a specified sorting method.2d. Explain the working of given sorting method step-by-step with an example and small data set. 2.1 Searching : Searching an item in a data set using following methods : i) Linear Search ii) Binary Search2.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 - IIIStacks and Queues 3a. Develop an algorithm to perform PUSH and POP operations for the given item in a Stack.3b. Convert the given expression from Infix to Prefix/Postfix using Stack.3c. Write steps to evaluate the given expression using the stack.3d. Develop a program to perform the given operation on a linear Queue.3e. Write Algorithm to perform the given operations on circular queue. 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 notations3.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 - IVLinked List 4a. Create relevant structure to represent a node using linked list.4b. Develop algorithm to insert the given item in linear linked list.4c. Develop algorithm to delete the given item from linear linked list.4d. Develop algorithm to traverse a circular 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 list4.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 - VTrees and Graphs 5a. Draw Binary Search Tree for the given data set.5b. Write algorithms to traverse the tree using the given method.5c. Construct Expression tree for the given data.5d. Represent the given Graph using adjacency matrix and adjacency list. Introduction to Trees5.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 traversal5.3 Expression tree5.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.