Mumbai University · Second Year Information Technology · NEP 2020
Advance Data Structure & Analysis
2343112 · Semester III · 3 credits · Internal tests 40 + end-semester 60
End-semester paper (2 hours): Six questions of 15 marks; Q1 is compulsory and you answer four.
Module 1: Introduction to Analysis of Algorithms
3 hoursTime and space complexity; asymptotic notation; solving recurrences by substitution, recursion tree and the master theorem.
Examined in one of the two internal tests and in the 60-mark end-semester paper
- Time and space complexity, asymptotic notation
- Recurrence relations and the master theorem
Module 2: Advanced Data Structures
8 hoursAVL trees; B-trees and their operations; B+ trees; red–black trees; tries; graph representation; BFS and DFS.
Examined in one of the two internal tests and in the 60-mark end-semester paper
- AVL and 2-3 trees
- B-trees and B+ trees
- Red-black trees
- Tries
- Graph representation, BFS and DFS
Module 3: Greedy Algorithms
6 hoursProperties of greedy algorithms; fractional knapsack; Prim's and Kruskal's minimum spanning trees; job sequencing with deadlines; optimal storage on tapes.
Examined in one of the two internal tests and in the 60-mark end-semester paper
- Greedy: activity selection and fractional knapsack
- Minimum spanning trees: Prim's and Kruskal's
- Job sequencing with deadlines
- Optimal storage on tapes
Module 4: Backtracking and Flow Networks
7 hoursN-queens; sum of subsets; graph colouring; Hamiltonian cycles; flow networks, augmenting paths and residual networks; the Ford–Fulkerson method.
Examined in one of the two internal tests and in the 60-mark end-semester paper
- Backtracking: N-queens and sum of subsets
- Graph colouring and Hamiltonian cycles
- Flow networks and the Ford-Fulkerson method
Module 5: Dynamic Algorithms
8 hoursGreedy versus dynamic programming; Dijkstra's and Bellman–Ford single-source shortest paths; Floyd–Warshall all pairs; 0/1 knapsack; travelling salesman.
Examined in one of the two internal tests and in the 60-mark end-semester paper
- Shortest path algorithms
- Bellman-Ford algorithm
- Floyd–Warshall algorithm
- Dynamic programming: 0/1 knapsack
- Travelling salesman by dynamic programming
Module 6: String Matching Algorithms
6 hoursNaive, Rabin–Karp and KMP string matching; longest common subsequence; applications in text search, DNA sequencing and compression.
Examined in one of the two internal tests and in the 60-mark end-semester paper
- Naïve string matching
- Rabin–Karp algorithm
- Knuth–Morris–Pratt algorithm
- Longest common subsequence
Module contents are summarised from the official Mumbai University syllabus . AiCanCode.org is not affiliated with the University of Mumbai.