 |
| Design and Analysis of Algorithms (DAA) Question Paper |
21CS42 Design and Analysis of Algorithms (DAA) | Syllabus
- Module-1
- Introduction: What is an Algorithm? It’s Properties. Algorithm Specification-using natural language, using Pseudo code convention, Fundamentals of Algorithmic Problem solving, Analysis FrameworkTime efficiency and space efficiency, Worst-case, Best-case and Average case efficiency.
- Performance Analysis: Estimating Space complexity and Time complexity of algorithms.
- Asymptotic Notations: Big-Oh notation (O), Omega notation (Ω), Theta notation ( ) with examples, Basic efficiency classes, Mathematical analysis of Non-Recursive and Recursive Algorithms with Examples.
- Brute force design technique: Selection sort, sequential search, string matching algorithm with complexity Analysis.
- Module-2
- Divide and Conquer: General method, Recurrence equation for divide and conquer, solving it using Master’s theorem. , Divide and Conquer algorithms and complexity Analysis of Finding the maximum & minimum, Binary search, Merge sort, Quick sort.
- Decrease and Conquer Approach: Introduction, Insertion sort, Graph searching algorithms, Topological Sorting. It’s efficiency analysis.
- Module-3
- Greedy Method: General method, Coin Change Problem, Knapsack Problem, solving Job sequencing with deadlines Problems.
- Minimum cost spanning trees: Prim’s Algorithm, Kruskal’s Algorithm with performance analysis. Single source shortest paths: Dijkstra's Algorithm.
- Optimal Tree problem: Huffman Trees and Codes.
- Transform and Conquer Approach: Introduction, Heaps and Heap Sort.
- Module-4
- Dynamic Programming: General method with Examples, Multistage Graphs.
- Transitive Closure: Warshall’s Algorithm.
- All Pairs Shortest Paths: Floyd's Algorithm, Knapsack problem, Bellman-Ford Algorithm, Travelling Sales Person problem.
- Space-Time Tradeoffs: Introduction, Sorting by Counting, Input Enhancement in String MatchingHarspool’s algorithm.
- Module-5
- Backtracking: General method, solution using back tracking to N-Queens problem, Sum of subsets problem, Graph coloring, Hamiltonian cycles Problems.
- Branch and Bound: Assignment Problem, Travelling Sales Person problem, 0/1 Knapsack problem
- NP-Complete and NP-Hard problems: Basic concepts, non- deterministic algorithms, P, NP, NPComplete, and NP-Hard classes.
Download Your Question Paper from Below
Keywords & Tags:
- 21cs42 vtu,
- 21cs42 notes,
- 21cs42 pdf,
- 21cs42 algorithm,
- 21cs42 vtu pdf,
- 21cs42 notes pdf,
- 21cs42 syllabus,
- 21cs42 question paper,
- Daa 4th sem pdf free download,
- Daa 4th sem pdf,
- Daa 4th sem example,
- daa 4th sem question papers,
- daa 4th sem notes 21 scheme,
- daa 4th sem notes vtu,
- design and analysis of algorithms handwritten notes pdf,
- 21cs42 notes pdf,