Analysis and Design of Algorithm With Sample Question Papers: Analysis and Design of Algorithm For Computer Science Engineering
- Length: 115 pages
- Edition: 1
- Language: English
- Publication Date: 2021-04-06
- ISBN-10: B091ZKQT77
An Algorithm is a sequence of steps to solve a problem. Design and Analysis of Algorithm is very important for designing algorithm to solve different types of problems in the branch of computer science and information technology.
UNIT – I – Introduction
1.1 Introduction
1.2 Fundamentals of Analysis of Algorithm
1.2.1 Analysis of Framework
1.2.2 Measuring an input size
1.2.3 Units for measuring runtime
1.2.4 Worst case, Best case and Average case
1.2.5 Asymptotic Notations
1.3 An Example
1.4 Analysis of Linear Search
Questions
UNIT – II – Divide and Conquer, Greedy Method
2.1 Divide and Conquer
2.2 General Method – Divide and Conquer
2.2.1 Master theorem
2.2.2 Efficiency of Merge sort
2.3 Binary Search
2.3.1 Efficiency of Binary Search
2.4 Greedy Techniques
2.5 General Method – Greedy Method
2.5.1 Prim‘s Algorithm
2.6 Container Loading
2.6.1 Algorithm for Container Loading
2.7 Knapsack Problem
Questions
UNIT – III – Dynamic Programming
3.1 Introduction
3.2 General Method – Dynamic Programming
3.2.1 Pseudo code for Binomial Coefficient
3.3 Multistage Graphs
3.3.1 Pseudo code for Floyd‘s Algorithm
3.4 Optimal Binary Search trees
3.5 0/1 Knapsack Problem
3.6 Traveling Salesman Problem
Questions
UNIT – IV – Backtracking
4.1 Backtracking
4.1.1 General Method – Backtracking
State-Space tree
4.2 N-queens Problem
4.3 Subset- Sum problem
4.3.1 Pseudo code for Backtracking Algorithms
4.4 Graph Coloring
4.5 Hamiltonian circuit problem
4.6 Knapsack Problem
Questions
UNIT – V – Traversals, Branch & Bound
5.1 Graph Traversals, BFS
5.1.1 BFS Forest
5.1.2 Efficiency
5.1.3 Ordering of Vertices
5.1.4 Application of BFS
5.2 DFS
5.2.1 DFS Forest
5.2.2 DFS Algorithm
5.1.3 Application of DFS
5.3 Connected Component
5.3.1 Biconnected Components
5.4 Spanning Trees
5.4.1 Prim‘s Algorithm
5.4.2 Kruskal‘s Algorithm
5.5 Branch & Bound
5.6 General Methods – FIFO & LC
5.7 Knapsack Problem
5.8 NP Hard & NP Completeness
Questions
