The course is one of the courses of Master of Computer Applications programme of IGNOU. Algorithms are the central part of computing and Design and Analysis of algorithms course is the core of the study of Computer Science discipline. This course helps you design and analyse algorithms. The topics included in the course are: 1. Introduction to Algorithms Basics of an Algorithm and its properties: Basics building blocks of Algorithms, A survey of common running time, Analysis & Complexity of Algorithm. Some pre-requisites and Asymptotic Bounds: Some Useful Mathematical Functions & Notations (Functions &Notations, Modular Arithmetic/Mod Function, Mathematical Expectation, Principle of Mathematical Induction). Analysis of Simple Algorithm: Complexity analysis of Algorithms, Euclid Algorithm for GCD, Polynomial Evaluation Algorithm, Exponent Evaluation, Sorting Algorithm Solving Recurrences: Substitution Methods, Iteration Methods, Recursive Tree Methods, Master Methods 2. Design Techniques-I Greedy Technique, Some Examples to understand Greedy Techniques, Formalization of Greedy Techniques, An overview of local and global optima, Fractional Knapsack problem, Huffman Codes, A task scheduling algorithm Divide & Conquer Technique: General Issues in Divide and Conquer Technique, Binary Search Algorithm, Sorting Algorithm (Merge Sort Quick Sort), Matrix Multiplication Algorithm Graph Algorithm –I: Basic Definition and terminologies, Graph Representation (Adjacency Matrix, Adjacency List), (Graph Traversal Algorithms (Depth First Search, Breadth First Search), Topological Sort, Strongly Connected Components) 3. Design Techniques – II Graph Algorithms- II: Minimum Cost Spanning Tree problems, (Kruskal’s Algorithm, Prim’s Algorithm), Single Source Shortest Path Problems (Bellman Ford Algorithm, Dijkstra’s Algorithm), Maximum Bipartite Matching Problem Dynamic Programming Technique: The Principle of Optimality, Chained Matrix Multiplication, Matrix Multiplication Using Dynamic Programming, Optimal binary search trees problems, Binomial coefficient computation, Floyd Warshall algorithm String Matching Techniques: The naïve String-Matching Algorithm, The Rabin Karp Algorithm, Knuth –Morris Pratt Algorithm 4. NP-Completeness and Approximation Algorithm NP-Completeness: Concepts of Class-P, NP-Completeness, NP-Hard, Unsolvable problems, Polynomial-time, Polynomial-time Reductions, Class P with Examples, Knapsack and TSP problems NP-Completeness and NP-Hard Problems: Polynomial Time verification, Techniques to show NP- Hardness, NP-Complete problems and P Vs NP problems? Handling Intractability: Approximation algorithms for Vertex Cover problem and minimizing make span as parallel machines (Graham’s algorithm), Parameterized algorithm for Vertex Cover problem, Meta-heuristic Algorithms
Overview
Syllabus
Week(s)
Unit (S)
Title of the Video Session
Block and Unit of the Course
Week-1
Block 1
Unit -1: Basics of an Algorithm and its Properties
Unit -2: Asymptotic Bounds
1. Algorithm Basics
Block 1 and Unit 1
2. Complexity of Algorithms
Block 1 and Unit 1
3. Useful Mathematical Functions & Notations
Block 1 and Unit 2
4. Asymptotic Notations of Algorithm Complexity
Block 1 and Unit 2
Week-2
Block 1
Unit -3: Complexity Analysis of Simple Algorithms
5. Analysis of Simple Algorithm
Block 1 and Unit 3
6. Analysis of Exponent Evaluation
Block 1 and Unit 3
7. Analysis of a Sorting Algorithm
Block 1 and Unit 3
Week-3
Block 1
Unit 4: Solving Recurrences
8. Introduction to Recurrence Relation
Block 1 and Unit 4
9. Solving Recurrence Relation: Substitution Recursion Tree Method
Block 1 and Unit 4
10. Master Method of Solving Recurrence
Block 1 and Unit 4
Week-4
Block 2
Unit 1: Greedy Technique
11. Greedy Techniques and Fractional Knapsack Problem and Task Scheduling Problem
Block 2 and Unit 1
12. Huffman Codes
Block 2 and Unit 1
Week-5
Block 2
Unit 2: Divide & Conquer Technique
13. Divide & Conquer Techniques : Merge Sort
Block 2 and Unit 2
14. Quick Sort
Block 2 and Unit 2
15. Integer Multiplication
Block 2 and Unit 2
16. Matrix Multiplication
Block 2 and Unit 2
Week-6
Block 2
Unit 3: Graph Algorithm-1
17. Graph Representation and Traversal
Block 2 and Unit 3
18. Topological Ordering
Block 2 and Unit 3
19. Strongly Connected Components
Block 2 and Unit 3
Week-7
Block 3
Unit 1: Graph Algorithms-II
20. Minimum Cost Spanning Tree: Kruskal’s Algorithm
Block 3 and Unit 1
21. Minimum Cost Spanning Tree: Prim’s Algorithm
Block 3 and Unit 1
22. Shortest Path” Dijkstra’s Algorithm
Block 3 and Unit 1
23. Shortest Path: Bellman – Ford Algorithm
Block 3 and Unit 1
24. Maximum Bipartite Matching
Block 3 and Unit 1
Week-8
Block 3
Unit 2: Dynamic Programming Technique
25. Principle of Optimality and Matrix Chain Multiplication – I
Block 3 and Unit 2
26. Matrix Chain Multiplication – II
Block 3 and Unit 2
27. Optimal Binary Search Tree - I
Block 3 and Unit 2
Week-9
Block 3
Unit 2: Dynamic Programming Technique
28. Optimal Binary Search Tree - II
Block 3 and Unit 2
29. Binomial Coefficient Computation
Block 3 and Unit 2
30. All Pair Shortest Path: Floyd Warshall Algorithm
Block 3 and Unit 2
Week-10
Block 3
Unit 3: String Matching Algorithms
31. String Matching Algorithm
Block 3 and Unit 3
32. Knuth-Morris-Pratt Algorithm
Block 3 and Unit 3
Week-11
Block 4
Unit 1: Introduction to Complexity Classes
&
Unit 2: NP-Completeness and NP-Hard Problems
33. P and NP Class of Problem
Block 4 and Unit 1
34. NP Complete Problem
Block 4 and Unit 1
35. Some NP Complete Problem Definitions
Block 4 and Unit 2
36. Proving NP Completeness
Block 4 and Unit 2
37. Some NP Complete Decision Problem
Block 4 and Unit 2
Week-12
Block 4
Unit 3: Handling Intractability
38. Backtracking Problem
Block 4 and Unit 3
39. Branch and Bound Problem
Block 4 and Unit 3
40. Approximation Algorithms
Block 4 and Unit 3
Taught by
Dr Akshay Kumar
