Course Details
Subject {L-T-P / C} : CS2061 : Data Structure Applications and Algorithms { 3-0-0 / 3}
Subject Nature : Theory
Coordinator : Prof. 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 make students aware of efficient storage and systematic operations on data using data structure
- To make students aware of applications of data structure
Course Outcomes
The students gather generalized knowledge on representing, storing, and operating on data in a systematic manner.
Essential Reading
- S. Lipschutz, Data Structures, Tata McGraw-Hill , ISBN: 9780070601680
- E. Horowitz, S. Sahni and S. Anderson-Freed, Fundamentals of Data Structures, Computer Science Press , ISBN: 9780716780427
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: 9780262033848
Journal and Conferences
- ACM Transactions on Computer Systems