Syllabus
Course Code: MCA-20-25(ii) Course Name: Design and Analysis of Algorithms |
||
MODULE NO / UNIT | COURSE SYLLABUS CONTENTS OF MODULE | NOTES |
---|---|---|
1 | Introduction: Algorithms, Role of algorithms in computing, Analysing algorithms, Designing algorithms,
Asymptotic notations. Divide and Conquer: Solving recurrence equations: Back substitution method, Recursion tree method, Masters theorem. Probabilistic Analysis and Randomized Algorithms: The hiring problem, Indicator random variables, Randomized algorithms, Probabilistic analysis and further uses of indicator random variables |
|
2 | Trees: Red-black trees and Splay trees.
Dynamic Programming (DP): Elements of DP, Matrix chain multiplication, Longest common subsequence,
optimal binary search trees. Greedy Techniques (GT): Elements of GT, Activity selection problem, Huffman codes, Knapsack Problem |
|
3 | Graph Algorithms: Topological sort, Strongly connected components, Single source shortest path: Analysis of
Dijkstra’s Algorithm, Limitations of Dijkstra’s Algorithm, Negative weight cycle, Bellman-Ford algorithm. All
Pairs Shortest Path: Relation of Shortest path and matrix multiplication, Analysis of Floyd Warshall algorithm.
Maximum Flow: Flow network, Ford-Fulkerson method. Strings: Storage of strings, Naive string-matching algorithm, Rabin-Karp algorithm, String matching with finite automata, Knuth-Morris-Pratt algorithm |
|
4 | Computational Geometry: Line-segment properties, Convex hull, Closest pair of points. Computational complexity: Notion of Polynomial time algorithms, Complexity classes: P, NP, NP-Hard and NP-Complete, Polynomial time verification, Reducibility, NP-Completeness, Examples of NP-Complete and NP-Hard problems: Traveling Salesman Problem, Knapsack, Bin Packing, Satisfiability, Vertex Cover, Clique, Independent Set. |