Course Details
Subject {L-T-P / C} : CS2006 : Design and Analysis of Algorithms { 3-0-0 / 3}
Subject Nature : Theory
Coordinator : Prof. Ramesh Kumar Mohapatra
Syllabus
Review of Data Structures. Notion of an Algorithm – Fundamentals of Algorithmic Problem Solving – Important Problem Types – Fundamentals of the Analysis of Algorithm Efficiency – Analysis Framework – Asymptotic Notations and its properties – Mathematical analysis for Recursive and Non-recursive algorithms. Algorithmic Techniques: Algorithm design strategies, divide and conquer, merge sort, quick sort and its performance analysis, randomized quick sort, Strassen’s matrix multiplication Greedy method and its applications, knapsack problem Dynamic programming and its performance analysis, optimal binary search trees, 0/1 knapsack problem Traveling salesman problem Backtracking, n-queens problem, graph coloring, Hamiltonian cycles, knapsack problem Branch and bound examples, 15-puzzle problem, 0/1 knapsack, traveling salesman. Graph Algorithms: DFS and BFS, spanning trees, biconnectivity Minimum cost spanning trees: Kruskal’s, Prim’s and Sollin’s algorithms Path finding and shortest path algorithms Topological sorting Bipartite graphs. Infeasibility: P and NP-classes, NP-hard problems, reduction. Other Algorithms: Number theoretic algorithms, string matching algorithms, approximation algorithms, randomized algorithms.
Course Objectives
- Analyze the performance of recursive and non recursive algorithms. Measure the time and space complexity of any algorithm.
- Become familiar with the different algorithm design techniques.
- Understand the limitations of Algorithm power.
Course Outcomes
Design algorithms for various computing problems and analyze the time and space complexity of algorithms. Ability to Understand, Analyze the performance of recursive and non recursive algorithms and use of asymptotic notations to measure the performance of algorithms. Solve problems by applying appropriate algorithm design techniques and analyze the <br />efficiency of various algorithms including parallel algorithms. Understand the necessary mathematical abstraction to solve problems and come up with analysis of efficiency and proofs of correctness. Comprehend and select algorithm design approaches in a problem specific manner and also modify existing algorithms to improve efficiency. Ability to understand the limitations of Algorithm power and identify algorithm design techniques to cope up with the limitations.
Essential Reading
- Thomas H.Cormen, Charles E.Leiserson, Ronald L. Rivest and Clifford Stein, Introduction to Algorithms, PHI Learning Private Limited , Third Edition, 2012
- Horowitz, Ellis, and Sartaj Sahni, Fundamentals of computer algorithms, Computer Science Press , 1978
Supplementary Reading
- Anany Levitin, Introduction to the Design and Analysis of Algorithms, Pearson Education , 2012
- J. Klienberg and E. Tardos, Algorithm Design, Pearson Education Limited , 2014