Analysis Design Of Algorithm ( IT-403 )

( IT- 4th Sem )

analysis design of algorithm

Objective

Data structure includes analyzing various algorithms along with time and space complexities. It also helps students to design new algorithms through mathematical analysis and programming.


Course Outcomes

After Completion of this Course students can:

  • Understand how to Implement sorting and searching algorithm.
  • Experiment with techniques for obtaining maximum output with minnium efforts.
  • Make use of dynamic programming for finding.
  • Distinguish between NP hard and NP complete problems and develop their solutions.
  • Solve 8 queen’s problem and others of the kind for application in real world scenarios.

Course Content

Main Contents of this course which students needs to learn are:

  • Algorithms, Designing algorithms, analyzing algorithms, asymptotic notations, heap and heap sort. Introduction to divide and conquer technique, analysis, design and comparison of various algorithms based on this technique, example binary search, merge sort, quick sort, strassen’s matrix multiplication.
  • Backtracking concept and its examples like 8 queen’s problem, Hamiltonian cycle, Graph coloring problem etc. Introduction to branch & bound method, examples of branch and bound method like traveling salesman problem etc. Meaning of low.
  • Study of Greedy strategy, examples of greedy method like optimal merge patterns, Huffman coding, minimum spanning trees, knapsack problem, job sequencing with deadlines, single source shortest path algorithm.
  • Concept of dynamic programming, problems based on this approach such as 0/1 knapsack, multistage graph, reliability design, Floyd-Warshall algorithm.
  • Binary search trees, height balanced trees, 2-3 trees, B-trees, basic search and traversal techniques for trees and graphs (In order, preorder, postorder, DFS, BFS), NP-completeness.

Book References

Some books which will help you to learn this course:

  • Coremen Thomas, Leiserson CE, Rivest RL; Introduction to Algorithms; PHI.
  • Horowitz & Sahani; Analysis & Design of Algorithm.
  • Dasgupta; algorithms; TMH.
  • Ullmann; Analysis & Design of Algorithm.
  • Michael T Goodrich, Robarto Tamassia, Algorithm Design, Wiely India.
  • Rajesh K Shukla: Analysis and Design of Algorithms: A Beginner's Approach; Wiley.

Some Programs List

Here are some program list to practice:

  • Write a program for Iterative and Recursive Binary Search.
  • Write a program for Merge Sort.
  • Write a program for Quick Sort.
  • Write a program for Strassen’s Matrix Multiplication.
  • Write a program for optimal merge patterns.
  • Write a program for Huffman coding.
  • Write a program for Hamiltonian cycle problem.
  • Write a program for Floye-Warshal algorithm.
  • Write a program for traveling salesman problem.
  • Write a program for minimum spanning trees using Prim’s algorithm.

Cousre Notes

For "Course Notes" you can refer our Notes Section for 2nd Year( Click Here )

  • TAGS:


    • Satyam College Academy
    Author- Satyam
    ( Core Member )