21CS42-Design And Analysis Of Algorithms 2021 scheme VTU University notes on 4th SEM Computer science and Engineerings notes 2022 scheme notes 2024 VTU University 21CS42 notes, study materials notes, and previous year question paper on easenotes 2024
Design And Analysis Of Algorithms 2021 scheme VTU University 4th SEM Computer science and Engineerings notes, We are offering the best quality online 4th SEM Computer science and Engineerings VTU University notes to help you learn, and have a better knowledge and also we are offering 2022 scheme Notes, study materials, question paper
Introduction: What is an Algorithm? It’s Properties. Algorithm Specification-using natural language, using Pseudo code convention, Fundamentals of Algorithmic Problem solving, Analysis Framework- Time 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. Textbook 1: Chapter 1 (Sections 1.1,1.2), Chapter 2(Sections 2.1,2.2,2.3,2.4), Chapter 3(Section3.1,3.2)Textbook 2: Chapter 1(section 1.1,1.2,1.3)
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. Textbook 2: Chapter 3(Sections 3.1,3.3,3.4,3.5,3.6) Textbook 1: Chapter 4 (Sections 4.1,4.2,4.3), Chapter 5(Section 5.1,5.2,5.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. Textbook 2: Chapter 4(Sections 4.1,4.3,4.5) Textbook 1: Chapter 9(Section 9.1,9.2,9.3,9.4), Chapter 6( section 6.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 Matching- Harspool’s algorithm. Textbook 2: Chapter 5 (Sections 5.1,5.2,5.4,5.9) Textbook 1: Chapter 8(Sections 8.2,8.4), Chapter 7 (Sections 7.1,7.2)
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, NP- Complete, and NP-Hard classes. Textbook 1: Chapter 12 (Sections 12.1,12.2) Chapter 11(11.3) Textbook 2: Chapter 7 (Sections 7.1,7.2,7.3,7.4,7.5) Chapter 11 (Section 11.1)