BAMU · Third Year B.E./B.Tech Computer Science and Engineering · NEP 2020
Design and Analysis of Algorithms
PCCT-3 · Semester V · 3 credits · CIA 40 + SEE 60
Module 1: Introduction to Algorithms; Analysis Framework
15 hoursWhat makes a good algorithm, space and time complexity, Big-O, Omega and Theta, worst, best and average case (linear versus binary search); analysing non-recursive and recursive algorithms and solving recurrences by substitution and recursion trees.
Examined in the 60-mark end-semester paper
- Asymptotic notation: Big-O, Omega and Theta
- Growth of functions
- Analysis of binary search
- Recurrences: substitution, iteration and recursion tree
Module 2: Divide-and-Conquer and Greedy Techniques; Dynamic Programming
15 hoursDivide and conquer, the master recurrence, merge sort, quick sort and Strassen's multiplication; the greedy method, fractional knapsack, Huffman coding and Prim's and Kruskal's MSTs; the principle of optimality, memoisation versus tabulation, 0/1 knapsack, LCS, matrix-chain multiplication, Bellman–Ford, Floyd–Warshall and optimal BSTs.
Examined in the 60-mark end-semester paper
- Divide and conquer
- Merge sort
- Quick sort
- Strassen's matrix multiplication
- Fractional knapsack
- Optimal merge patterns and Huffman coding
- Dynamic programming
- Optimal binary search trees
Module 3: Graph Algorithms and Advanced Search Techniques
15 hoursBFS and DFS with their complexity, topological sorting and Dijkstra's algorithm with priority queues; backtracking with state-space trees, N-queens, sum of subsets, graph colouring and Hamiltonian cycles; branch and bound, FIFO and least-cost search, and TSP.
Examined in the 60-mark end-semester paper
- Dijkstra's single-source shortest paths
- Backtracking
- N-queens problem
- Sum of subsets
- Graph colouring by backtracking
- Hamiltonian cycles by backtracking
- Branch and bound
- 15-puzzle and TSP by branch and bound
Module contents are summarised from the official BAMU syllabus . AiCanCode.org is not affiliated with Dr. Babasaheb Ambedkar Marathwada University (BAMU).