AOAD

Subject : Analysis of Algorithm & Design

Module :

1 Introduction to analysis of algorithm
 •  Design and analysis fundamentals.

•  Performance analysis ,space  and  time complexity.

•  Growth of function – Big-Oh, Omega, theta notation.

•  Mathematical background for algorithm analysis.

•  Randomized and recursive algorithm.

2  Divide and Conquer

•  Genaral method , Binary search, finding the min and max.

•  Merge sort analysis.

•  Quick sort,  performance measurement.

•  Randomized version of quick sort and analysis.

•  Partitioned algorithm selection sort, radix sort, efficiency

  considerations.

•  Strassen’s matrix multiplication.

3  Greedy Method

•  General mehod.

•  Knapsack problem.

•  Minimum cost spanning tree- kruskal and primal algo,

   performanance analysis.

•  Single source shorted path .

•  Job sequencing with deadlines.

•  Optimal storage on tapes.

4  Dynamic Programming

•  The general method

•  Multistage graphs, all pair shortest paths, single source

   shortest paths

•  Optimal BST ,0/1 knapsack

•  TSP, flow shop scheduling

5  Backtracking
•  The general method.

•  8 queen problem ,sum of subsets.

•  Graph coloring,hamltonian cycles.

•  Knapsack problem.

6  Branch and Bound

•  The method, LC search.

•  15 puzzle:An example.

•  Bounding and FIFO branch and bound .

•  LC branch and bound .

•  0/1 knapsack problem.

•  TP efficiency considerations.

7  Internet algorithm
•  Strings and patterns matching algorithm .

•  Tries.

•  Text compression.

•  Text similarity testing.

Notes :

1) Analysis of Algorithms-SE (Vidyalankar).pdf

http://www.mediafire.com/?i3zthh374pgznht

2) AOAD part1 (Sem-IV) Comp. Prof.R.V..Sadguru's.pdf

http://www.mediafire.com/?cwvo2tad073rd6i