An algorithm is a set of steps of operations to solve a problem performing calculation, data processing, and automated reasoning tasks. The important aspects of algorithm design include creating an efficient algorithm to solve a problem in an efficient way using minimum time and space.
The course introduces students to the design of computer algorithms, as well as analysis of algorithms. Algorithm design and analysis provide the theoretical backbone of computer science and are a must in the daily work of the successful programmer. The goal of this course is to provide a solid background in the design and analysis of the major classes of algorithms. At the end of the course students will be able to develop their own versions for a given computational task and to compare and contrast their performance.
After the completion of the course the student will be able to
CO1 :Analyze any given algorithm and express its time and space complexities in asymptotic notations. (Cognitive Level: Apply)
CO2: Derive recurrence equations and solve it using Iteration, Recurrence Tree, Substitution and Master’s Method to compute time complexity of algorithms. (Cognitive Level: Apply)
CO3: Illustrate Graph traversal algorithms & applications and Advanced Data structures like AVL trees and Disjoint set operations. (Cognitive Level: Apply)
CO4:Demonstrate Divide-and-conquer, Greedy Strategy, Dynamic programming, Branch-and Bound and Backtracking algorithm design techniques (Cognitive Level: Apply)
CO5: Classify a problem as computationally tractable or intractable, and discuss strategies to address intractability (Cognitive Level: Understand)
CO6: Identify the suitable design strategy to solve a given problem. (Cognitive Level: Analyze)
Curriculum
- 6 Sections
- 35 Lessons
- 10 Weeks
- Introduction6
- 1.1Syllabus
- 1.2Module-1 (Introduction to Algorithm Analysis) Characteristics of Algorithms, Criteria for Analysing Algorithms, Time and Space Complexity – Best, Worst and Average Case Complexities, Asymptotic Notations – Big-Oh (O), Big- Omega (Ω), Big-Theta (Θ), Little-oh (o) and Little- Omega (ω) and their properties. Classifying functions by their asymptotic growth rate, Time and Space Complexity Calculation of simple algorithms. Analysis of Recursive Algorithms: Recurrence Equations, Solving Recurrence Equations – Iteration Method, Recursion Tree Method, Substitution method and Master’s Theorem (Proof not required).
- 1.3Module–2 (Advanced Data Structures and Graph Algorithms) Self Balancing Tree – AVL Trees (Insertion and deletion operations with all rotations in detail, algorithms not expected); Disjoint Sets- Disjoint set operations, Union and find algorithms. DFS and BFS traversals – Analysis, Strongly Connected Components of a Directed graph, Topological Sorting.
- 1.4Module–3 (Divide & Conquer and Greedy Strategy) The Control Abstraction of Divide and Conquer- 2-way Merge sort, Strassen’s Algorithm for Matrix Multiplication-Analysis. The Control Abstraction of Greedy Strategy- Fractional Knapsack Problem, Minimum Cost Spanning Tree Computation- Kruskal’s Algorithms – Analysis, Single Source Shortest Path Algorithm – Dijkstra’s Algorithm-Analysis.
- 1.5Module-4 (Dynamic Programming, Back Tracking and Branch & Bound)) The Control Abstraction- The Optimality Principle- Matrix Chain Multiplication-Analysis, All Pairs Shortest Path Algorithm – Floyd-Warshall Algorithm-Analysis. The Control Abstraction of Back Tracking – The N Queen’s Problem. Branch and Bound Algorithm for Travelling Salesman Problem.10 Minutes0 Questions
- 1.6Module-5 (Introduction to Complexity Theory) Tractable and Intractable Problems, Complexity Classes – P, NP, NP- Hard and NP-Complete Classes- NP Completeness proof of Clique Problem and Vertex Cover Problem- Approximation algorithms- Bin Packing, Graph Coloring. Randomized Algorithms (Definitions of Monte Carlo and Las Vegas algorithms), Randomized version of Quick Sort algorithm with analysis.10 Minutes0 Questions
- Module 16
- 2.1Characteristics of Algorithms
- 2.2Criteria for Analysing Algorithms, Time and SpaceComplexity – Best, Worst and Average Case Complexities,
- 2.3Asymptotic Notations
- 2.4Analysis of Recursive Algorithms: Recurrence Equations-Recursion Tree Method
- 2.5Analysis of Recursive Algorithms: Recurrence Equations – Iteration Method.
- 2.6Analysis of Recursive Algorithms: Recurrence Equations -Master’s Theorem and its Illustration.
- Module 29
- 3.0Self Balancing Trees – Properties of AVL Trees
- 3.1Self Balancing Trees – Rotations of AVL Trees
- 3.2AVL Trees Insertion and Illustration
- 3.3AVL Trees Deletion and Illustration
- 3.4Disjoint set operations.
- 3.5Graph Algorithms: BFS traversal, Analysis.
- 3.6Graph Algorithms: DFS traversal, Analysis.
- 3.7Strongly connected components of a Directed graph.
- 3.8Topological Sorting.
- Module 38
- 4.0Divide and Conquer: The Control Abstraction.
- 4.12-way Merge Sort, Analysis.
- 4.2Strassen’s Algorithm for Matrix Multiplication, Analysis
- 4.3Greedy Strategy: The Control Abstraction.
- 4.4Fractional Knapsack Problem
- 4.5Minimum Cost Spanning Tree Computation- Kruskal’s Algorithm, Analysis.
- 4.6Single Source Shortest Path Algorithm – Dijkstra’s Algorithm
- 4.7Illustration of Dijkstra’s Algorithm-Analysis.
- Module 47
- 5.1Dynamic Programming-The Control Abstraction
- 5.2The Optimality Principle
- 5.3Matrix Chain Multiplication-Analysis
- 5.4Floyd-Warshall Algorithm-Analysis
- 5.5The Control Abstraction of Back Tracking
- 5.6The Control Abstraction of Back Tracking – The N Queen’s Problem
- 5.7Branch and Bound Algorithm for Travelling Salesman Problem.
- Module 59
- 6.0Tractable and Intractable Problems
- 6.1Complexity Classes – P, NP3 Days
- 6.2NP- Hard and NP- Complete Classes3 Days
- 6.3NP Completeness proof of Clique Problem3 Days
- 6.4NP Completeness proof of Vertex Cover Problem3 Days
- 6.5Approximation algorithms- Bin Packing3 Days
- 6.6Graph Coloring.3 Days
- 6.7Randomized Algorithms3 Days
- 6.8Randomized version of Quick Sort algorithm with analysis.3 Days
