Analysis & Design of Algorithm (CS-4004)
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
Objective:
Student will be able to learn algorithm designing,various problem solving strategies like divide and conquer approach,Greedy strategy,Dynamic Programming,Backtracking etc.
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:
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
UNIT 3:
Concept of dynamic programming, problems based on this approach such as 0/1 knapsack,
multistage graph, reliability design, Floyd-Warshall algorithm
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
References:
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
- ES-3001 - Energy, Environment, Ecology & Society
- CS-4002 - Computer System Organization
- CS-4003 - Analog & Digital communication
- CS-4005 - Theory of computation
- CS-4006 - Computer Programming-II [Dot Net Technology]
- CS-4006 - Computer Programming-II [Python]
- CS-4006 - Computer Programming-II [MATLAB]
- CS-4007 - Programming Tools(Internal Assessment)
- CS-4008 - Professional Ethics (Internal Assessment)
