SGBAU · Third Year B.E. Computer Science and Engineering (Data Science) · NEP 2020
Design and Analysis of Algorithm
6DS232PC · Semester VI · 3 credits · IE 40 + ESE 60
Unit 1: Algorithm Analysis and Iterative Design
6 hoursAlgorithms and loops, efficiency, estimating and specifying execution time, Big-O, Big-Ω and Big-Θ, an overview of strategies, and design using recursion.
Examined in the 60-mark end-semester paper
- What makes a good algorithm
- Space and time complexity
- Asymptotic notations: big-O, omega and theta
- Analysing non-recursive algorithms
- Recurrences: substitution and recursion-tree methods
Unit 2: Divide and Conquer
6 hoursThe divide-and-conquer strategy, multiplication algorithms and their analysis, the triangulation and convex-hull problems, the drawbacks of divide and conquer, and timing analysis.
Examined in the 60-mark end-semester paper
- Divide and conquer and the master theorem
- Strassen's matrix multiplication
- Convex hull and large-integer multiplication by divide and conquer
Unit 3: Greedy Methods
6 hoursThe greedy strategy, the knapsack problem, job sequencing with deadlines, minimum spanning trees by Prim's and Kruskal's algorithms, and Dijkstra's shortest paths.
Examined in the 60-mark end-semester paper
- Greedy method: fractional knapsack and Huffman coding
- Job sequencing with deadlines
- Minimum spanning trees: Prim's and Kruskal's
- Dijkstra's algorithm with priority queues
Unit 4: Dynamic Programming
6 hoursDynamic programming, multistage graphs, the travelling-salesman problem, matrix-chain multiplication, the longest common subsequence, optimal polygon triangulation and single-source shortest paths.
Examined in the 60-mark end-semester paper
- Multistage graphs
- Travelling salesperson by dynamic programming
- Matrix chain multiplication and optimal BSTs
- Dynamic programming: 0/1 knapsack and LCS
- Shortest paths: Bellman-Ford and Floyd-Warshall
Unit 5: Backtracking
6 hoursCombinatorial search, search and traversal methods, the backtracking strategy and framework, and typical state-space trees and their applications.
Examined in the 60-mark end-semester paper
- Backtracking and state-space trees
- N-queens and sum of subsets
- Graph colouring and Hamiltonian cycles
Unit 6: Algorithm Efficiency and Complexity Classes
6 hoursPolynomial and non-polynomial algorithms, worst- and average-case analysis, the efficiency of recursion, the complexity of sorting algorithms, and time–space trade-offs.
Examined in the 60-mark end-semester paper
- P, NP and NP-complete problems
- Best, worst and average-case analysis
- Merge sort and quick sort analysis
Unit contents are summarised from the official SGBAU syllabus . AiCanCode.org is not affiliated with Sant Gadge Baba Amravati University (SGBAU).