META TAGS:-RGPV IT 4TH SEM ADA SYLLABUS I DOWNLOAD RGPV 4TH SEM ANALYSIS AND ALGORITHM DESIGN SYLLABUS I RGTU ADA SYLLABUS I RGPV ADA PAPERS I RGPV ADA PAPERS I IT-404 ADA SYLLABUS I IT 4TH SEM ADA SYLLABUS I ADA SYLLABUS FOR IT 4TH SEM I RGTU ANALYSIS AND ALGORITHM DESIGN SYLLABUS I RGTU IT 4TH SEM SYLLABUS I RGPV BHOPAL IT 4TH SEM SYLLABUS
RGPV / RGTU ANALYSIS & ALGORITHM DESIGN IT-404
Branch : Information Technology, IV Semester
Course :Analysis And Algorithm Design
Course :Analysis And Algorithm Design
UNIT I
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 II
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, etc.
UNIT III
Concept of dynamic programming:problems based on this approach such as 0/1 knapsack, multistage graph,reliability design, Floyd-Warshall algorithm, etc.
UNIT IV
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 V
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.
REFERENCE BOOKS:
- 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
List of Experiments( expandable):
- 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 minimum spanning trees using Kruskal’s algorithm.
- Write a program for minimum spanning trees using Prim’s algorithm.
- Write a program for single sources shortest path algorithm.
- Write a program for Floye-Warshal algorithm.
- Write a program for traveling salesman problem.
- Write a program for Hamiltonian cycle problem.
0 comments