DBATU · Second Year B.Tech Information Technology · NEP 2020
Analysis of Algorithms
25AF1246PC401 · Semester IV · 3 credits · Continuous assessment 20 + mid-semester 20 + end-semester 60
Unit 1: Introduction
7 hoursInstruction counts and growth functions; why time and space are analysed; O, Θ and Ω notation; solving recurrences by substitution, the master theorem and recursion trees.
Examined in the 60-mark end-semester paper, and in the mid-semester exam if it is taught by then
- Time and space complexity, asymptotic notation
- Step-count method and analysing loops
- Recurrence relations and the master theorem
Unit 2: Divide and Conquer and Greedy Algorithms
7 hoursBinary search, finding maximum and minimum, merge sort, quick sort and Strassen's multiplication; greedy knapsack, job sequencing, optimal storage on tapes, optimal merge patterns and single-source shortest paths.
Examined in the 60-mark end-semester paper, and in the mid-semester exam if it is taught by then
- Finding maximum and minimum by divide and conquer
- Divide and conquer: merge sort and quick sort
- Divide and conquer matrix multiplication
- Greedy: activity selection and fractional knapsack
- Job sequencing with deadlines
- Optimal storage on tapes
- Optimal merge patterns
- Shortest path algorithms
Unit 3: Dynamic Programming
7 hoursMultistage graphs; all-pairs shortest paths; 0/1 knapsack; the travelling salesperson problem; longest common subsequence.
Examined in the 60-mark end-semester paper, and in the mid-semester exam if it is taught by then
- Multistage graphs
- Floyd–Warshall algorithm
- Dynamic programming: 0/1 knapsack
- Travelling salesman by dynamic programming
- Longest common subsequence
Unit 4: Graph Algorithms
7 hoursDFS, BFS and topological sort; minimum spanning trees with Kruskal's and Prim's algorithms.
Examined in the 60-mark end-semester paper, and in the mid-semester exam if it is taught by then
- Graph representation, BFS and DFS
- Topological sort
- Minimum spanning trees: Prim's and Kruskal's
Unit 5: Backtracking, Branch and Bound, and NP Theory
7 hoursN-queens, sum of subsets and graph colouring; the branch-and-bound strategy; P, NP, NP-hard and NP-complete problems and reduction.
Examined in the 60-mark end-semester paper, and in the mid-semester exam if it is taught by then
- Backtracking: N-queens and sum of subsets
- Graph colouring and Hamiltonian cycles
- Branch and bound
- P, NP, NP-hard 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).