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
| Course Status : | Ongoing |
| Course Type : | Not Applicable |
| Language for course content : | English |
| Duration : | 12 weeks |
| Category : |
|
| Credit Points : | 4 |
| Level : | Postgraduate |
| Start Date : | 01 Jan 2025 |
| End Date : | 30 Apr 2025 |
| Enrollment Ends : | 28 Feb 2025 |
| Exam Date : | 24 May 2025 IST |
| NCrF Level : | 6.5 |
| Exam Shift : | Shift-I |
Note: This exam date is subject to change based on seat availability. You can check final exam date on your hall ticket.
DOWNLOAD APP
FOLLOW US