CBCGS [2017 - current]

CBGS [2013 - 2016]

Old [2000 - 2012]

## University of Mumbai Semester 4 (SE Second Year) Analysis of Algorithm Revised Syllabus

University of Mumbai Semester 4 (SE Second Year) Analysis of Algorithm and their Unit wise marks distribution

### Units and Topics

# | Unit/Topic | Marks |
---|---|---|

100 | Introduction to Analysis of Algorithm | - |

200 | Divide and Conquer | - |

300 | Greedy Method | - |

400 | Dynamic Programming | - |

500 | Backtracking | - |

600 | String Matching Algorithms | - |

700 | Branch and Bound | - |

Total | - |

## Syllabus

100 Introduction to Analysis of Algorithm

- Decision and analysis fundamentals
- Performance analysis , space and time complexity
- Growth of function – Big –Oh ,Omega , Theta notation
- Mathematical background for algorithm analysis
- Analysis of selection sort , insertion sort
- Randomized algorithms
- Recursive algorithms
- The substitution method
- Recursion tree method
- Master method

200 Divide and Conquer

- General method
- Binary search
- Finding minimum and maximum
- Merge sort analysis
- Quick sort analysis
- Strassen’s matrix multiplication
- The problem of multiplying long integers
- Constructing Tennis tournament

300 Greedy Method

- General Method
- Knapsack problem
- Job sequencing with deadlines
- Minimum cost spanning trees-Kruskal and prim’s algorithm
- Optimal storage on tapes
- Single source shortest path

400 Dynamic Programming

- General Method
- Multistage graphs
- All pair shortest path
- Single source shortest path
- Optimal binary search tree
- 0/1 knapsack
- Travelling salesman problem
- Flow shop scheduling

500 Backtracking

- General Method
- 8 queen problem (N-queen problem)
- Sum of subsets
- Graph coloring

600 String Matching Algorithms

- The naïve string matching Algorithms
- The Rabin Karp algorithm
- String matching with finite automata
- The knuth-Morris-Pratt algorithm
- Longest common subsequence algorithm

700 Branch and Bound

- General method
- 15 puzzle problem
- Travelling salesman problem

Advertisement Remove all ads

Advertisement Remove all ads