Analysis and Design of Algorithms (IT-3002)
Objectives
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.
Syllabus
UNIT 1:Introduction of Algorithms, Analysis of algorithms: Space Complexity, Time Complexity, recurrence relation and Asymptotic Notation, Divide and Conquer: General Methods, Analysis and Design, Binary Search, Quick sort, Merge sort, Strassen’s matrix multiplication.
UNIT 2: Greedy Strategy: Introduction, examples of greedy method like optimal merge pattern, Huffman coding, Minimum spanning trees, knapsack problem, job sequencing with dead lines single source shortest path algorithms.
UNIT 3: Dynamic Programming: Introduction, Problem based on this approach such as 0/1 Knapsack Multistage graph, reliability design, Floyd-warshall algorithms.
UNIT 4: Backtracking Concept and its example like 8 Queen’s problem, Hamiltonian cycle, Graph coloring problem, 15 Puzzle problem, Least Cost Search
UNIT 5: Introduction to branch & bound method, examples of branch & bound methods like traveling sales man problem, meaning of lower bound theory and its use in solving algebraic problem. NPcompleteness & NP hard problems. Basic Concept of non deterministic algorithms. NP hard and NP complete classes.
Chameli Devi Group Of Institutions [NOTES]
Outcomes
1. Students will be able to understand fundamentals of algorithms.
2. Understanding various design methods for graphs.
3. Learning different concepts of backtracking including puzzle problem and graph coloring.
4. Getting familiar with non-deterministic algorithms and techniques of branch and bound.
References
1. Horowitz, Sahani,Rajasekaran “ Fundamentals of Computer Algorithms”, Universities Press.
2. Thomas H. Cormen, “Introduction to Algorithms”, PHI.
3. Harsh Bhasin “Algorithms Design and Analysis” Oxford.
4. I.Chandra Mohan “ Design and Analysis of Algorithms” PHI
List of Experiments
1. Implement Binary Search using C++.
2. Implement Quick sort using C++.
3. Implement Strassen Matrix multiplication on the given matrix.
4. Implement Merge sort on the given list of elements.
5. Implement Job sequencing problem using C++.
6. Implement Floyd warshall algorithm using C++.
7. Implement 8 – queens problem using backtracking.
8. Implement graph coloring problem using C++.
9. Implement 0/1 knapsack using branch and bound.
10. Implement travelling salesman problem using C++.
Comments
Post a Comment