BAMU · Third Year B.E./B.Tech Artificial Intelligence and Data Science · 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, best, worst and average cases; analysing loops and conditionals; setting up recurrences and solving them by substitution and recursion trees.
Examined in the 60-mark end-semester paper
- What makes a good algorithm
- Space and time complexity
- Asymptotic notations: big-O, omega and theta
- Best, worst and average-case analysis
- Analysing non-recursive algorithms
- Recurrences: substitution and recursion-tree methods
Module 2: Divide and Conquer and Greedy Techniques; Dynamic Programming
15 hoursDivide and conquer and its master recurrence, merge sort, quick sort and Strassen's multiplication; the greedy method, fractional knapsack, Huffman coding and minimum spanning trees; dynamic programming — 0/1 knapsack, LCS, matrix chain multiplication, Bellman–Ford, Floyd–Warshall and optimal BSTs — compared with greedy.
Examined in the 60-mark end-semester paper
- Divide and conquer and the master theorem
- Merge sort and quick sort analysis
- Strassen's matrix multiplication
- Greedy method: fractional knapsack and Huffman coding
- Minimum spanning trees: Prim's and Kruskal's
- Dynamic programming: 0/1 knapsack and LCS
- Matrix chain multiplication and optimal BSTs
- Shortest paths: Bellman-Ford and Floyd-Warshall
Module 3: Graph Algorithms and Advanced Search Techniques
15 hoursBFS, DFS and topological sorting; Dijkstra's algorithm with priority queues; backtracking and state-space trees for N-queens, sum of subsets, graph colouring and Hamiltonian cycles; branch and bound, FIFO and least-cost search, and the travelling salesperson problem.
Examined in the 60-mark end-semester paper
- BFS, DFS and topological sorting
- Dijkstra's algorithm with priority queues
- Backtracking and state-space trees
- N-queens and sum of subsets
- Graph colouring and Hamiltonian cycles
- Branch and bound: FIFO and least-cost search
- Travelling salesperson 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).