SGBAU · Third Year B.E. Computer Science and Engineering · NEP 2020
Design and Analysis of Algorithm
6CS232PC · 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
- Asymptotic notation: Big-O, Omega and Theta
- Growth of functions
- Recurrences: substitution, iteration and recursion tree
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
- The master method
- 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
- The greedy method
- Fractional knapsack
- Activity selection and job sequencing
- Kruskal's and Prim's minimum spanning trees
- Dijkstra's single-source shortest paths
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
- Dynamic programming
- Multistage graphs
- Travelling salesperson by dynamic programming
- Matrix chain multiplication
- Longest common subsequence
- Bellman-Ford algorithm
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
- N-queens problem
- Sum of subsets
- Graph colouring by backtracking
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
- Analysis of selection and insertion sort
- Amortised analysis
Unit contents are summarised from the official SGBAU syllabus . AiCanCode.org is not affiliated with Sant Gadge Baba Amravati University (SGBAU).