CSVTU, B.E. V Semester, Computer Science Engineering, Analysis & Design Of Algorithms Syllabus

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.