DESIGN AND ANALYSIS OF ALGORITHM
 

 
  KHALLIKOTE AUTONOMOUS COLLEGE,BERHAMPUR  
M.Sc Computer Science
 
   ABOUT  FACILITY ADMISSION  FACULTY    SYLLABUS   EXAMS  STUDENT OTHER..
 
                                                                                                                 FAQ | CONTACT US

DESIGN AND ANALYSIS OF ALGORITHMS

Unit-I

Concepts in algorithm analysis, Asymptotic Notations(Theta,Omega,Sigma),Recurrence relation.  

Unit-II

Devide and conquer:Control abstraction, Analysis of binary search ,Finding maximum and minimum, Merge sort, Quick sort, Finding smallest element (selection), Strassen's matrix multiplication.

Unit-III

The Greedy Method: Control abstraction, optimal storage on tapes, Knapsack problem, Optimal merge patterns, Huffman codes, MST (Minimum Spanning Trees), Prim's algorithm, Kruskal's algorithm.

Unit-IV

Dynamic Programming and Traversal Technique : General method, Multistage graphs, Shortest path (-ve weights), OBST (Optimal Binary Search Tree),0/1 Knapsack, TSP(Travelling Sales Person Problem), Graph Traversal ( BFS and DFS )

Unit-V

Backtracking & Lower Bound Theory: General algorithm (non recursive & recursive), n-Queens problem, Sum of subsets problem, Graph coloring, Hamiltonian cycles, Lower bound on searching, Lower bound on sorting, Lower bound on finding Max & Min.

Books

  • Fundamentals of Computer Algorithm by Ellies Horowity Sartaj sahni & S.Rajasekaran.Galgotia Publication Pvt Ltd,1999

  • Algoriths by Thomas H.Cormen Charles E.Leiserson Ronald L.Rivest,PHI