DAA Syllabus(639401)

Unit-I

Basic Concepts of Analysis and Design of Algorithms in Computing and Growth of Functions:

Algorithms, Algorithms as a technology, Analyzing algorithms, Designing algorithms, Asymptotic notation, Standard notations and common functions.

Unit-II

Algorithms Using Divide-and-Conquer, Probabilistic Analysis and Randomized Algorithms:

The maximum-subarray problem, Strassen’s algorithm for matrix multiplication, The substitution method for solving recurrences, The recursion-tree method for solving recurrences, The master method for solving recurrences,

The hiring problem, Indicator random variables, Randomized algorithms.

Unit-III

Dynamic Programming:      

 Rod cutting, Matrix-chain   multiplication, Elements of dynamic programming, Longest

common subsequence, Optimal binary search trees.

Unit-IV

Greedy Algorithms and Amortized Analysis

An activity-selection problem, Elements of the greedy strategy, Huffman codes. Aggregate analysis, The accounting method, The potential method and Dynamic tables.

Unit-V

Minimum Spanning Trees and Single-Source Shortest Paths: 

Growing a minimum spanning tree, The algorithms of Kruskal and Prim, The Bellman-Ford algorithm, Single- source shortest paths in directed acyclic graphs, Dijkstra’s algorithm, Difference constraints and shortest paths, Proofs

of shortest-paths properties.