Foundation of Algorithm Analysis
Algorithm properties, RAM model, time & space complexity, detailed algorithm analysis, aggregate analysis, asymptotic notations.
Design and Analysis of Algorithms Chapters
B.Sc. CSIT - Fifth Semester
Iterative Algorithms
GCD and Fibonacci algorithms, sequential search, binary search, time and space complexity analysis.
Divide and Conquer Algorithms
Binary search, Min-Max finding, merge sort, quick sort, best/worst/average case analysis.
Greedy Algorithms
Optimization problems, greedy strategy, fractional knapsack, job sequencing, Huffman coding.
Dynamic Programming
Greedy vs DP, recursion vs DP, matrix chain multiplication, string editing, zero-one knapsack.
Backtracking
Concepts of backtracking; subset-sum; zero-one knapsack; N-queen problem and analysis.
Number Theoretic Algorithms
Euclid’s and extended Euclid algorithms; modular linear equations; Chinese remainder theorem; primality tests.
NP Completeness
Tractable vs intractable problems; P, NP, NP-Hard, NP-Complete; polynomial reductions.