Syllabus Advance Data Structure & Analysis - (2343112) Theory Term work Pract / Oral Total Internal Assessment End Sem Exam Exam Duration (in Hrs) IAT - I IAT - II IAT - I + IAT - II 20 20 40 60 02 - - 100 Sr. No. Name of Module Detailed Content 0 Prerequisite Overview of Data Structures : Revision of basic data structures (arrays, stacks, queues, linked lists, trees). I Introduction to Analysis of Algorithms Fundamentals of the analysis of algorithms : Time and Space complexity, Asymptotic notation, Recurrence Relations : Methods to solve recurrence relations in algorithms (Substitution, Recursion tree, Master theorem). Self-learning Topics : Solve problems on analysis of algorithms. (Chapter - 1) II Advanced Data Structures Introduction. AVL trees, B tree, B tree operations, B+ tree, Red-Black Trees, tries data structures, time complexity analysis of all problems. Graphs, Representation, Graph Traversals : Breadth First Search, Depth First Search. Self-learning Topics : Solve problems on AVL trees, B tree, B+ tree etc. (Chapter - 2) III Greedy algorithms and Applications Introduction and properties of greedy algorithms, Fractional Knapsack problem, Minimum Spanning Trees (Prim’s and Kruskal’s algorithms), Job sequencing with deadlines, Optimal storage on tapes, Analysis of All problems. Self-learning Topics : Solve problems on Spanning Trees, Knapsack etc. (Chapter - 3) IV Backtracking and Maximum flow Networks Backtracking Techniques : Introduction, N-Queens problem, sum of subsets problem, graph coloring, Hamiltonian cycles. Introduction to flow networks, Augmenting Paths Residual Network, Ford Fulkerson method, Applications of Flow Networks in real-world problems. Self-learning Topics : Solve problems N-Queens, Hamiltonian cycles, Augmenting Paths Residual Network etc. (Chapter - 4) V Dynamic Algorithms Introduction Dynamic algorithms, Greedy vs. Dynamic algorithms, Single source shortest path-Dijkstra's Algorithm, Bellman Ford Algorithm, All pair shortest path- Floyd Warshall Algorithm, 0/1 knapsack problem, Travelling salesman problem, Analysis of All problems. Self-learning Topics : Solve problems on shortest path- Dijkstra's Algorithm etc. (Chapter - 5) VI String Matching Algorithms Introduction. Naïve string matching algorithm, Rabin-Karp algorithm, Knuth-Morris-Pratt (KMP) algorithm, Longest common subsequence(LCS), Analysis of All problems, Applications : Text searching, DNA sequencing, and data compression. Self-learning Topics : Solve problems on DNA sequencing and data compression. (Chapter - 6) Note : No questions will be asked in the end-semester exam from self-study topics. However, students are encouraged to explore these topics for a better understanding of the subject.
