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.
Module 1: Introduction
4 hoursSpace 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
Module 2: Divide and Conquer
5 hoursThe 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
Module 3: Greedy Method
5 hoursThe 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
Module 4: Dynamic Programming
8 hoursThe 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
Module 5: Backtracking and Branch and Bound
7 hoursBacktracking: 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
Module 6: String Matching
3 hoursNaive 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.