CO1: Understanding the fundamental concepts of abstract data types, data structures, algorithms and time complexity analysis of algorithms.
CO2: Implementation of different abstract data types (array, linked list, stack, queue, tree, graph).
CO3: Implementation of different sorting and searching techniques along with their performance evaluation.
CO4: Analysis of the suitability/compatibility of different data structures based on the types of applications.
CO5: Design and development of algorithms for real-life applications.
Introduction: Abstract Data Type (ADT), Data Structures, Concept of static and dynamic memory allocation, Algorithm, Analysis of time and space complexity of algorithms, Asymptotic notations: Big Oh, Big Omega and Big Theta notations, Impact of data structure on the performance of an algorithm. (6L)
Array: Array as an ADT, Single and multi-dimensional array, Memory representation (row major and column major) of array, Address calculation for array elements. Sparse Matrix, Manipulation of the Sparse Matrix like Addition, Subtraction, Transpose and Multiplication, Time Complexity Analysis (2L)
Linked list: Linked list as an ADT, Memory allocation and deallocation for a linked list, Linked list versus array, Types of linked lists: singly linked list, doubly linked list and circular linked list, Operations on linked list: creation, display, insertion and deletion (in different positions), Concatenation, Searching, Adding & Multiplications of two polynomials using Linked List, Sorting, Applications of linked list: Representations and operations on polynomials, sparse matrices, etc., Array vs. Linked List. 6L)
Stack: Stack as an ADT, Push and pop operations on stacks, Array implementation of stack, Linked list implementation of stack, Applications of stack: Recursion, Function call, Evaluation of postfix expression using stack, Conversion of infix to postfix using stack. (5L)
Queue: Queue as an ADT, Enqueue and dequeue operations, Array implementation of queue, Limitation of array implementation, Circular queue, Linked list implementation of queue, Priority queue. (4L)
Binary Tree: Binary Tree, Definition and properties, Representation of binary tree in memory: linked representation, array representation, Binary tree traversal (Preorder, Inorder and Postorder), Binary search tree, Heap. (8L)
Searching Algorithms: Linear search and binary search. (2L)
Sorting Algorithms: Selection sort, Insertion sort, Quick sort, and Merge sort. (5L)
Graphs Algorithms: Graph representation using Adjacency matrix and Adjacency list, Breadth First Search and Depth First Search algorithms. (4L)
Miscellaneous (6 Hours)
Linked List: Sorting using Linked List and Time,Space Complexity Analysis
Graph (Minimum Spanning Tree): Prim's and Kruskal's Algorithm and Time, Space Complexity Analysis, Celebrity Finding Problem
Graph (Shortest Path Algoithm): Dijkstra Algorithm and Time,Space Complexity Analysis
Sorting: Heap Sort
Topological Sorting