PAHSU · Third Year B.Tech. Computer Science and Engineering · NEP 2020
Design and Analysis of Algorithms
CSEPCC-07 · Semester V · 3 credits · ISE 30 + ESE 70
Unit 1: Introduction
8 hoursAlgorithm specification and pseudocode conventions; recursive algorithms; performance analysis: space and time complexity, worst-, best- and average-case complexity, asymptotic notations and performance measurement.
Examined in the 70-mark end-semester paper
- Asymptotic notation: Big-O, Omega and Theta
- Growth of functions
- Recurrences: substitution, iteration and recursion tree
- Asymptotic notation and the step-count method
Unit 2: Divide and Conquer
7 hoursThe general method; binary search; finding the maximum and minimum; quick sort, selection sort and merge sort.
Examined in the 70-mark end-semester paper
- Divide and conquer
- Analysis of binary search
- Finding maximum and minimum by divide and conquer
- Quick sort
- Merge sort
- Analysis of selection and insertion sort
Unit 3: The Greedy Method
8 hoursThe general method; the knapsack problem; job sequencing with deadlines; Prim's and Kruskal's minimum-cost spanning trees; optimal storage on tapes; optimal merge patterns; single-source shortest paths.
Examined in the 70-mark end-semester paper
- The greedy method
- Fractional knapsack
- Activity selection and job sequencing
- Kruskal's and Prim's minimum spanning trees
- Optimal storage on tapes
- Optimal merge patterns and Huffman coding
- Dijkstra's single-source shortest paths
Unit 4: Dynamic Programming
8 hoursThe general method; multistage graphs; all-pairs shortest paths; optimal binary search trees; 0/1 knapsack; reliability design; the travelling salesperson problem; flow shop scheduling.
Examined in the 70-mark end-semester paper
- Dynamic programming
- Multistage graphs
- Floyd-Warshall all-pairs shortest paths
- Optimal binary search trees
- 0/1 knapsack
- Reliability design
- Travelling salesperson by dynamic programming
- Flow shop scheduling: Johnson's rule
Unit 5: Backtracking
7 hoursThe general method; the 8-queens problem; sum of subsets; the knapsack problem; Hamiltonian cycles; graph colouring.
Examined in the 70-mark end-semester paper
- Backtracking
- N-queens problem
- Sum of subsets
- Hamiltonian cycles by backtracking
- Graph colouring by backtracking
Unit 6: NP-Hard and NP-Complete Problems
7 hoursTractable and intractable problems; computability and the halting problem; the classes P and NP, NP-complete and NP-hard; standard NP-complete problems and basic NP-hard problems.
Examined in the 70-mark end-semester paper
- P, NP and NP-complete problems
- Decidability and the halting problem
- NP-completeness reductions: vertex cover, 3-CNF SAT, clique and Hamiltonian cycle
Unit contents are summarised from the official PAHSU syllabus . AiCanCode.org is not affiliated with Punyashlok Ahilyadevi Holkar Solapur University (PAHSU).