Analysis and Design of Algorithms (IT-3002)
rgpv bhopal, diploma, rgpv syllabus, rgpv time table, how to get transcript from rgpv, rgpvonline,rgpv question paper, rgpv online question paper, rgpv admit card, rgpv papers, rgpv scheme
RGPV notes CBGS Bachelor of engineering
Course 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.
NOTES
- Unit 1
- Unit 2
- Unit 3
- Unit 4
- Unit 5
Course 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.
Reference Books:
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++.
