Mumbai University SE IT syllabus

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.

All notes for this subject
  1. Module 1: Introduction to Analysis of Algorithms

    3 hours

    Time 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
  2. Module 2: Advanced Data Structures

    8 hours

    AVL 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
  3. Module 3: Greedy Algorithms

    6 hours

    Properties 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
  4. Module 4: Backtracking and Flow Networks

    7 hours

    N-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
  5. Module 5: Dynamic Algorithms

    8 hours

    Greedy 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
  6. Module 6: String Matching Algorithms

    6 hours

    Naive, 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.