Design Analysis and Algorithm

Syllabus
Unit-1 Basic Concepts of Analysis and Design of Algorithms
Introduction; Characteristics of iterative algorithms; Efficiency of
algorithms; Estimating and specifying execution time; Order notation:
Big-Oh, Theta, Omega, Small-Oh, Small-Omega notations; Algorithm
strategies

Unit-2 Algorithms Using Divide-and-Conquer Strategy
Introduction; Examples: x**n; Multiplication algorithm and its analysis;
Binary search and its analysis; Closest pair; Merge sort and its analysis;
Limitations of Divide-and-Conquer strategy; Decrease-and-Conquer
approach: Permutation generation


Unit-3 Greedy Methods
Introduction; Knapsack problem; Job sequencing with deadlines;
Minimum spanning trees: Prim's algorithm, and Kruskal's algorithm;
Shortest path, Dijkstra's shortest path algorithm, Optimal merge patterns

Unit-4 Dynamic Programming
Introduction; Examples: Coin exchange problem; Principle of Optimality;
Rod cutting problem, Multistage graphs, Traveling salesman problem,
Matrix multiplication, Longest common sub-sequence, Maximum flow
problem

Unit-5 Backtracking, Branch and Bound Algorithms
Combinatorial search; Search and traversal: Breadth First Search (BFS),
Depth First Search (DFS); 8-Queen problem; M-Coloring problem;
Hamiltonian circuits; Branch-and-Bound algorithms, Examples: Shortest
path; 16-Puzzle and 8-Puzzle; Scale balancing, 0/1 Knapsack problem,
Traveling salesman problem; Limitations of Branch-and-Bound

Unit-6 Efficiency of Algorithms; Complexity Calculation and Categorization
Polynomial-time and Non-polynomial-time algorithms; Worst and average
case behavior, Probabilistic average case analysis; Time analysis of
algorithms; Examples: Matrix multiplication; Efficiency of recursion;
Complexity: Notion of complexity, Profiling, Suppressing multiplicative
constants, Counting dominant operations, Growth rate, Upper bounds,
Asymptotic growth rate; The 'O' notation; Simplified definition of 'O'; 'O'
notation rules
Examples of Complexity Calculation: Sorting examples: Bucket sort,
Radix sort, Simple Insertion sort, Quick sort, Heap sort, Merge sort,
Counting Sort; Binary, Binomial and Fibonacci Heaps; Binomial Heap;
Dijkstra's shortest path algorithm;
Complexity Categorization of Problems: Introduction: P, NP, NPC,
NPH; Upper and lower bounds; Four levels of algorithmic behavior;
summary