Course Details
Subject {L-T-P / C} : CS2005 : Data Structures and Algorithms { 3-0-0 / 3}
Subject Nature : Theory
Coordinator : Sambit Bakshi
Syllabus
Part A. Defining data, data types, data structure classification of data structures (linear and non-linear) understanding data structure and storage structure
Part B. Defining an algorithm, its properties growth of a function complexityasymptotic analysis asymptotic notations for complexity analysis comparing standard growth rates
Part C. Linear array: its representation in memory, traversal, and operations on it 2D array: its representation in memory, traversal, and operations on it Generalized representation of multi-dimensional array on memory.
Part D. Linked List: Node structure, traversal, insertion and deletion from a linked list circular linked list two way linked list.
Part E: Sparse matrix, representation using triplet array, chain representations (single chain, row chain, orthogonal list)
Part F: Stack (operations on stack, array and linked list representation, application in conversion of expression from infix to postfix, and in evaluation of postfix notation)
Part G: Queue (operations on queue, array and linked list representation, deque, priority queue)
Part H: Searching algorithms (linear search, binary search, Fibonacci search)
Part I: Sorting algorithms (bubble sort, selection sort, insertion sort, merge sort, quick sort)
Part J: Tree (Terminologies, representation, binary tree and its traversal)
Part K: Binary search tree and operations on it, properties of BST, binary expression tree
Part L: AVL tree and operations on it
Part M: m-way search tree and B-tree
Part N: Heap (min-heap and max-heap)
Part O: Graphs (terminologies, storage, Dijkstra's shortest path algorithm, traversal: DFS, BFS, generalized shortest path problems, Bellman-Ford algorithm, Floyd-Warshall Algorithm)
Part P: Spanning tree, Minimum spanning tree, Prim's and Kruskal's algorithms
Course Objectives
- To develop students’ knowledge in data structures and the associated algorithms.
- To introduce the concepts and techniques of structuring and operating on abstract Data Types in problem solving
- To discuss common sorting, searching algorithms. Also the complexity and comparisons among these various techniques
Course Outcomes
At the end of the course, students shall be equipped with the knowledge to:
CO1: follow the operations for maintaining common data structures and recognize the associated algorithms’ complexity.
CO2: design appropriate data structures for solving computing problems.
CO3: develop and analyse algorithms which can be implemented in programming languages.
Essential Reading
- M.A. Weiss, Data Structures and Algorithm Analysis in C, Pearson Education , ISBN:9798178081679
- E. Horowitz, S. Sahni and S. Anderson-Freed, Fundamentals of Data Structures, Computer Science Press , ISBN: 978-0716780427
Supplementary Reading
- A.V. Aho, J.E. Hopcroft, and J.D. Ullman, Data Structures & Algorithms, Pearson Education India , ISBN: 9788178081021
- T.H. Cormen, C.E. Leiserson, R.L. Rivest, and C. Stein, Introduction to Algorithms, The MIT Press , ISBN: 978-0262033848