GUG · Third Year B.Tech. Computer Science and Engineering · NEP 2020
Design and Analysis of Algorithms
STPCCCSE503 · Semester V · 4 credits · IE 10 + mid-semester 10 + ESE 80
4 credits with its lab.
Unit 1: Introduction
9 hoursAlgorithms and pseudocode; performance analysis: space and time complexity; asymptotic notation: big-O, omega and theta; recurrences; iterative sorting and searching algorithms.
Examined in the 80-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
- Analysis of selection and insertion sort
Unit 2: Divide and Conquer and the Greedy Method
9 hoursDivide and conquer: the general method and the analysis of binary search, quick sort and merge sort. The greedy method: job sequencing with deadlines, the fractional knapsack, minimum-cost spanning trees, single-source shortest paths and Huffman codes.
Examined in the 80-mark end-semester paper, and in the mid-semester exam if it is taught by then
- Divide and conquer
- Analysis of binary search
- Quick sort
- Merge sort
- The greedy method
- Activity selection and job sequencing
- Fractional knapsack
- Kruskal's and Prim's minimum spanning trees
- Dijkstra's single-source shortest paths
- Optimal merge patterns and Huffman coding
Unit 3: Dynamic Programming
9 hoursThe general method; longest common subsequence, matrix chain multiplication, optimal binary search trees, the 0/1 knapsack, all-pairs shortest paths and the travelling salesperson problem.
Examined in the 80-mark end-semester paper, and in the mid-semester exam if it is taught by then
- Dynamic programming
- Longest common subsequence
- Matrix chain multiplication
- Optimal binary search trees
- 0/1 knapsack
- Floyd-Warshall all-pairs shortest paths
- Travelling salesperson by dynamic programming
Unit 4: Backtracking and Branch and Bound
9 hoursBacktracking: the n-queens problem, sum of subsets, graph colouring and Hamiltonian cycles. Branch and bound: the travelling salesperson problem and the 0/1 knapsack by LC and FIFO branch and bound.
Examined in the 80-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
- 0/1 knapsack by LC and FIFO branch and bound
Unit 5: NP-Hard and NP-Complete Problems
9 hoursBasic concepts; non-deterministic algorithms; the NP-hard and NP-complete classes; Cook's theorem.
Examined in the 80-mark end-semester paper, and in the mid-semester exam if it is taught by then
- Non-deterministic algorithms and Cook's theorem
- P, NP and NP-complete problems
- NP-completeness reductions: vertex cover, 3-CNF SAT, clique and Hamiltonian cycle
Unit contents are summarised from the official GUG syllabus . AiCanCode.org is not affiliated with Gondwana University, Gadchiroli.