Analysis and Design of Algorithm (IT-403)
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.
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
B.Tech RGPV notes AICTE flexible curricula Bachelor of technology
Syllabus
UNIT 1:
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
UNIT 2:
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
UNIT 3:
Concept of dynamic programming, problems based on this approach such as 0/1
knapsack, multistage graph, reliability design, Floyd-Warshall algorithm, etc.
UNIT 4:
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 lower bound theory and its use in
solving algebraic problem, introduction to parallel algorithms.
UNIT 5:
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.
NOTES
- Unit 1
- Unit 2
- Unit 3
- Unit 4
- Unit 5
Course Outcomes:
At the end of the course student will be able to :
1 Implement sorting and searching algorithm
2 Experiment with techniques for obtaining maximum output with minnium efforts
3 Make use of dynamic programming for finding
4 Solve 8 queen’s problem and others of the kind for application in real world scenarios .
5 Distinguish between NP hard and NP complete problems and develop their solutions
Books Recommended
1. Coremen Thomas, Leiserson CE, Rivest RL; Introduction to Algorithms; PHI.
2. Horowitz & Sahani; Analysis & Design of Algorithm
3. Dasgupta; algorithms; TMH
4. Ullmann; Analysis & Design of Algorithm;
5. Michael T Goodrich, Robarto Tamassia, Algorithm Design, Wiely India
List of Experiments:
1. Write a program for Iterative and Recursive Binary Search.
2. Write a program for Merge Sort.
3. Write a program for Quick Sort.
4. Write a program for Strassen’s Matrix Multiplication.
5. Write a program for optimal merge patterns.
6. Write a program for Huffman coding.
7. Write a program for minimum spanning trees using Kruskal’s algorithm.
8. Write a program for minimum spanning trees using Prim’s algorithm.
9. Write a program for single sources shortest path algorithm.
10. Write a program for Floye-Warshal algorithm.
11. Write a program for traveling salesman problem.
12. Write a program for Hamiltonian cycle problem.
You May Also Like
- BT-401 - Mathematics- III
- IT-402 - Computer Architecture
- IT-404 - Analog & Digital Communication
- IT-405 - Data base Management System
- IT-406 - Introduction to MATLAB, Scilab/Web Design
- IT-407 - Dot Net
- BT-408 - 90 hrs Internship based on using various software’s –Internship -II
- BT-409 - Cyber Security