DBATU · Second Year B.Tech Computer Engineering · NEP 2020
Design and Analysis of Algorithms
25AF1245PC401 · Semester IV · 3 credits · Continuous assessment 20 + mid-semester 20 + end-semester 60
Unit 1: Introduction to Algorithms
7 hoursProperties and expression of algorithms; performance analysis and order of growth; asymptotic notation; recurrences by substitution, iteration, recursion tree and the master theorem; heap sort.
Examined in the 60-mark end-semester paper, and in the mid-semester exam if it is taught by then
- Asymptotic notation: Big-O, Omega and Theta
- Growth of functions
- Recurrences: substitution, iteration and recursion tree
- The master method
- Heap sort
Unit 2: Divide and Conquer
7 hoursBinary search, merge sort, quick sort and Strassen's matrix multiplication.
Examined in the 60-mark end-semester paper, and in the mid-semester exam if it is taught by then
- Divide and conquer
- Analysis of binary search
- Merge sort
- Quick sort
- Strassen's matrix multiplication
Unit 3: Backtracking and Branch and Bound
7 hoursN-queens, Hamiltonian cycles, sum of subsets and graph colouring by backtracking; travelling salesperson and the 15-puzzle by branch and bound; the two compared.
Examined in the 60-mark end-semester paper, and in the mid-semester exam if it is taught by then
- 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
Unit 4: Greedy Algorithms
7 hoursThe greedy method; optimal merge patterns and Huffman coding; knapsack; activity selection; job sequencing with deadlines; minimum spanning trees; single-source shortest paths.
Examined in the 60-mark end-semester paper, and in the mid-semester exam if it is taught by then
- The greedy method
- Optimal merge patterns and Huffman coding
- Fractional knapsack
- Activity selection and job sequencing
- Kruskal's and Prim's minimum spanning trees
- Dijkstra's single-source shortest paths
Unit 5: Dynamic Programming and NP-Completeness
7 hoursCharacteristics of dynamic programming versus divide and conquer; longest common subsequence; matrix-chain multiplication; Bellman–Ford and Floyd–Warshall; the classes P, NP and NP-complete and polynomial-time reduction.
Examined in the 60-mark end-semester paper, and in the mid-semester exam if it is taught by then
- Dynamic programming
- Longest common subsequence
- Matrix chain multiplication
- Bellman-Ford algorithm
- Floyd-Warshall all-pairs shortest paths
- P, NP and NP-complete problems
Unit contents are summarised from the official DBATU syllabus . AiCanCode.org is not affiliated with Dr. Babasaheb Ambedkar Technological University (DBATU).