ADVANCE DATA STRUCTURE AND ANALYSIS for MU NEP Semester 3 Degree in Information Technology | Dr Uttara Gogate | Nirali Prakashan

0. Prerequisite (01)
Overview of Data Structures: Revision of basic data structures (arrays, stacks, queues, linked lists, trees).
1. Introduction to Analysis of Algorithm (03)
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.
2. Advanced Data Structures (08)
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: learning Topics: learning Topics: Solve problems on AVL trees, B tree, B+ tree etc.
3. Greedy Algorithms and Applications (06)
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: learning Topics: learning Topics: Solve problems on Spanning Trees, Knapsack etc.
4. Backtracking and Maximum Flow Networks (07)
Backtracking Techniques: Backtracking Techniques: 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: learning Topics: learning Topics: Solve problems N-Queens, Hamiltonian cycles, Augmenting Paths Residual Network etc.
5. Dynamic Algorithms (08)
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: learning Topics: learning Topics: Solve problems on shortest path- Dijkstra’s Algorithm etc.
6. String Matching Algorithms (06)
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: learning Topics: learning Topics: Solve problems on DNA sequencing, and data compression.

Authors – Dr Uttara Gogate, Reena Deshmukh, Dr. Aboli Hemant Patil, Dr. Swati Bhavsar