CHHATTISGARH SWAMI VIVEKANAND TECHNICAL UNIVERSITY, BHILAI (C.G.)
Semester – V Branch-Computer Science & Engineering.
Subject: Analysis & Design Of Algorithms
UNIT-I INTRODUCTION & ANALYSIS: –
Analyzing algorithms, Algorithm types, Recurrence Equations, Growth function:
Asymptotic notation, Standard notation & common functions, Recurrence relation, different
methods of solution of recurrence equations with examples.
UNIT-II-DYNAMIC PROGRAMMING & GREEDY PARADIGM: –
The basic dynamic programming paradigm, Dynamic programming solution to the optimal
matrix chain multiplication and the longest common subsequence problems, Top down
recursive algorithms, Greedy Paradigm: The basic greedy strategy & computing minimum
spanning trees, Algorithms of Kruskal and Prim, Union to Find Algorithm & their
applications, Disjoint Set, The relationship in Dijkstra’s and Prim’s algorithms, Use of
greedy strategy in algorithms for the Knapsack problem and Huffman trees.
UNIT-III-DIVIDE AND CONQUER & BACKTRACKING PARADIGM: –
Introduction to Divide and Conquer paradigm, Quick and merge sorting techniques, Linear
time selection algorithm, the basic divide and conquer algorithm for matrix multiplication,
Backtracking & Recursive backtracking, Applications of backtracking paradigm. heaps and
introduction to 2-3 trees, Algorithms for manipulating 2-3 trees, Representation of heaps
using 2-3 trees, Red Black tree, Binary Search tree , heap sort, shell & bucket sort,
Amortized Analysis.
UNIT-IV-GRAPH ALGORITHMS & STRING MATCHING ALGORITHMS: –
Representational issues in graphs, Depth first search & Breath first search on graphs,
Computation of biconnected components and strongly connected components using DFS,
Topological sorting of nodes of an acyclic graph & applications, Shortest Path Algorithms
on Graphs: Bellman-Ford algorithm, Dijkstra’s algorithm & Analysis of Dijkstra’s algorithm
using heaps, Floyd-Warshall’s all pairs shortest path algorithm and its refinement for
computing the transitive closure of a graph. The general string problem as a finite
automata, Knuth Morris and Pratt algorithms, Linear time analysis of the KMP algorithm,
The Boyer-Moore algorithm.
UNIT-V-NP-COMPLETE PROBLEMS:-
Solvable problems, Types of problems, The notion of a non deterministic algorithm and its
basic relationship to backtracking. Polynomial time non deterministic algorithms for
problems like satisfiability, clique problem, Hamiltonian path problems etc., The definition
of NP-hardness and NP-completeness, The statement of Cook’s theorem and a
discussion of its implications, The notion of polynomial transformation and reductions,
Reductions to show that the clique problem, vertex cover, subset sum and Hamiltonian
cycle problems are NP-complete, Other models for computations.
Text Books:
1. Introduction to Algorithms (Second Edition); Cormen, Lelserson, Rivert; PHI.
2. Fundamentals of Algorithms, Sahni & Horowitz; Galgotia.
Reference Books:
1. The Design & Analysis of Computer Algorithms, Hopcroft – Aho – Ullman, AWL.
2. Handbook of Algorithms & Data Structures, G.H.Gonnet, AWL.
3. Introduction to Design & Analysis of Algorithms, Levitin, PE-LPE.