Mumbai University SE Computer syllabus

Mumbai University · Second Year Computer Engineering · NEP 2020

Analysis of Algorithms

2113113 · Semester III · 3 credits · Internal tests 40 + end-semester 60

End-semester paper (2 hours): Six questions of 20 marks; Q1 is compulsory and you answer three.

All notes for this subject
  1. Module 1: Introduction

    4 hours

    Space and time complexity; growth of functions; Big-O, Omega and Theta; the master method; analysis of selection and insertion sort.

    Examined in one of the two internal tests and in the 60-mark end-semester paper

    • Asymptotic notation: Big-O, Omega and Theta
    • Growth of functions
    • The master method
    • Analysis of selection and insertion sort
  2. Module 2: Divide and Conquer

    5 hours

    The general method; merge sort; quick sort; analysis of binary search.

    Examined in one of the two internal tests and in the 60-mark end-semester paper

    • Divide and conquer
    • Merge sort
    • Quick sort
    • Analysis of binary search
  3. Module 3: Greedy Method

    5 hours

    The general method; Dijkstra's single-source shortest paths; fractional knapsack; Kruskal's and Prim's minimum spanning trees.

    Examined in one of the two internal tests and in the 60-mark end-semester paper

    • The greedy method
    • Dijkstra's single-source shortest paths
    • Fractional knapsack
    • Kruskal's and Prim's minimum spanning trees
  4. Module 4: Dynamic Programming

    8 hours

    The general method; multistage graphs; Floyd–Warshall all-pairs shortest paths; 0/1 knapsack; travelling salesperson; longest common subsequence.

    Examined in one of the two internal tests and in the 60-mark end-semester paper

    • Dynamic programming
    • Multistage graphs
    • Floyd-Warshall all-pairs shortest paths
    • 0/1 knapsack
    • Travelling salesperson by dynamic programming
    • Longest common subsequence
  5. Module 5: Backtracking and Branch and Bound

    7 hours

    Backtracking: N-queens, sum of subsets and graph colouring; branch and bound: travelling salesperson and the 15-puzzle.

    Examined in one of the two internal tests and in the 60-mark end-semester paper

    • Backtracking
    • N-queens problem
    • Sum of subsets
    • Graph colouring by backtracking
    • Branch and bound
    • 15-puzzle and TSP by branch and bound
  6. Module 6: String Matching

    3 hours

    Naive string matching; Rabin–Karp; Knuth–Morris–Pratt.

    Examined in one of the two internal tests and in the 60-mark end-semester paper

    • Naive string matching
    • Rabin-Karp algorithm
    • Knuth-Morris-Pratt algorithm

Module contents are summarised from the official Mumbai University syllabus . AiCanCode.org is not affiliated with the University of Mumbai.