BAMU · Third Year B.E./B.Tech Information Technology · NEP 2020
Design and Analysis of Algorithms
PCCT-3 · Semester V · 3 credits · CIA 40 + SEE 60
Module 1: Introduction; Analysis Framework
15 hoursWhat makes a good algorithm; space and time complexity; Big-O, Omega and Theta; worst, best and average cases (linear versus binary search); analysing non-recursive algorithms, setting up recurrences, and the substitution and recursion-tree methods.
Examined in the 60-mark end-semester paper
- Time and space complexity, asymptotic notation
- Step-count method and analysing loops
- Recurrence relations and the master theorem
- Linear and binary search
Module 2: Divide-and-Conquer and Greedy Techniques; Dynamic Programming
15 hoursDivide and conquer with merge sort, quick sort and Strassen's multiplication; the greedy method with fractional knapsack, Huffman coding and Prim's and Kruskal's MSTs; dynamic programming with memoisation and 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 and quick sort
- Divide and conquer matrix multiplication
- Greedy: activity selection and fractional knapsack
- Huffman coding
- Dynamic programming: 0/1 knapsack
- Longest common subsequence
- Matrix chain multiplication
- Bellman-Ford algorithm
Module 3: Graph Algorithms and Advanced Search Techniques; Backtracking and Branch and Bound
15 hoursBFS and DFS, topological sorting and Dijkstra's algorithm with priority queues; backtracking for N-queens, sum of subsets, graph colouring and Hamiltonian cycles; branch and bound, FIFO versus least-cost search, and the travelling salesperson problem.
Examined in the 60-mark end-semester paper
- Graph representation, BFS and DFS
- Topological sort
- Shortest path algorithms
- Backtracking: N-queens and sum of subsets
- Graph colouring and Hamiltonian cycles
- Branch and bound
Module contents are summarised from the official BAMU syllabus . AiCanCode.org is not affiliated with Dr. Babasaheb Ambedkar Marathwada University (BAMU).