Syllabus Data Structures and Algorithms - 4330704 Total Credits (CI+T/2+P/2) Examination Scheme Theory Marks Practical Marks Total Marks C CA ESE CA ESE 5 30 70 25 25 150 Unit Unit Outcomes (UOs) Topics and Sub-topics Unit - I Basic Concepts of Data Structures 1a. Represent the data in relevant memory 1.1 Data Structure Basic Concepts 1.2 Types of data structures 1b. Differentiate primitive and non-primitive data structures 1.3 Primitive and non-primitive data structures 1c. List key features of an algorithm 1.4 Introduction to Algorithms 1.5 Key features of an algorithm 1d. Define time complexity and space complexity 1.6 Analysis Terms (for the definitions purpose only) : a. Time Complexity b. Space Complexity c. Asymptotic Notations : Big Oh Notation, Big Omega Notation, Big Theta Notation, Best case Time Complexity, Average case Time Complexity, Worst case Time Complexity 1e. Implement programs to represent array in row major and column major order 1.7 Array : i. Row Major Arrays ii. Column Major Arrays 1.8 Overview of different array operations. 1f. Design and Implement search algorithms 1.9 Searching an element into an array : i. Linear Search ii. Binary Search (Chapter - 1) Unit - II Strings 2a. Describe representation of a strings 2.1 String representation : Reading and Writing Strings 2b. Develop algorithms to implement various operations on string 2.2 String operations : Finding length of a string, Converting Characters of a string into upper case and lower case, Concatenation of two strings to form a new string, Appending, Reversing a string, Copying a string, Comparing strings, Insertion, Substring, Deletion. (Chapter - 2) Unit - III Stack and Queues 3a. Define linear and non- linear data structures 3.1 Linear and Non-Linear Data Structures 3b. Implement algorithms to push an element into stack, pop an element from the stack. 3.2 Stack : Array representation of Stack, PUSH- POP Operations on Stack, Implementation of Stack, Application of Stack, Infix, Prefix and Postfix Forms of Expressions, Recursive Functions (Factorial, greatest common divisor, Fibonacci series) 3c. Implement different operations on a Queue 3.3 Queue : Array representation of Queue Operations on a Queue (Add an element, delete an element, display all elements of a queue), Implementation of a Queue, Limitation of a Single Queue 3d. Differentiate circular and simple queue 3.4 Concepts of Circular Queue 3.5 Applications of a queue 3.6 Differentiate circular queue and simple queue (Chapter - 3) Unit - IV Linked List 4a. Define linked list 4.1 Pointers Revision 4.2 Revision of Structure 4.3 Revision of structure using pointers 4.4 Dynamic Memory Allocation 4.5 Linked list Presentation 4.6 Types of Linked List 4b. Implement algorithms to perform various operations on a singly linked list 4.7 Basic operations on singly linked list : Insertion of a new node in the beginning of the list, at the end of the list, after a given node, before a given node, in sorted linked list, Deleting the first and last node from a linked list, Searching a node in Linked List, Count the number of nodes in linked list 4c. Distinguish circular linked list and singly linked list 4.8 Concepts of circular linked list 4.9 Difference between circular linked list and singly linked list 4d. Distinguish Doubly linked list and singly linked list 4.10 Doubly linked list : Representation 4.11 Difference between Doubly linked list and singly linked list 4e. List applications of the linked list 4.12 Applications of the linked list (Chapter - 4) Unit - V Trees 5a. Define non-linear data structure 5.1 Non-linear data structures : Tree, Graph 5b. Define basic terms of a tree data structure 5.2 Basic Terms : General Tree, Forest, Binary trees, level number, degree, in-degree and out-degree, root node, leaf node, directed edge, path, depth 5c. Convert general tree to binary tree Binary tree: Complete Binary Tree, Strict Binary Tree, Conversion of General Tree to Binary Tree 5d. Implement basic operations on a binary tree 5.3 Binary Search Tree : Insertion of a node in binary tree, Deletion of a node in binary tree, Searching a node in binary tree 5e. Demonstrate the traversal of a binary tree 5.4 Binary Tree Traversal : Inorder, Preorder, Postorder 5f. List applications of tree 5.5 Applications of binary tree (Chapter - 5) Unit - VI Sorting and Hashing 6a. Arrange data in ascending and descending orders using appropriate sorting algorithm 6.1 Sorting Methods : a. Bubble Sort, b. Selection Sort, c. Quick Sort, d. Insertion Sort, e. Merge Sort, f. Radix Sort 6b. Apply various hashing techniques 6.2 Hashing Concepts 6.3 Hash functions : Division Method, Middle Square Method, Folding Method. (Chapter - 6)