{{{credits}}}
| L | T | P | C |
| 3 | 0 | 0 | 3 |
- To understand the use of algorithms in computing.
- To learn develop algorithms using hierarchical data structures.
- To select and use data structures and algorithms appropriate to the problems.
- To study about NP hard and NP completeness of problems.
{{{unit}}}
| Unit I | Role of Algorithms in Computing | 9 |
Algorithms – Analyzing algorithms – Designing algorithms – Growth of functions: Asymptotic notation – Standard notations and common functions; Recurrences: The substitution method – The recursion-tree method – The master method for solving recurrences.
{{{unit}}}
| Unit II | Hierarchical Data Structures | 9 |
Binary search trees: Basics – Query, Insertion and Deletion; Red-black trees: Properties of Red-black trees – Rotations – Insertion – Deletion; B-Trees: Basic operations on B-Trees; Fibonacci heaps: Structure – Mergeable-heap operations – Decreasing a key and deleting a node; Disjoint-set operations – Disjoint-set forests.
{{{unit}}}
| Unit III | Graphs | 9 |
Elementary graph algorithms: Representations of graphs – Breadth-first search – Depth-first search – Topological sort – Strongly connected components; Single-source shortest paths: Bellman-Ford algorithm; Single-source shortest paths in directed acyclic graphs: Dijkstra’s algorithm; All-pairs shortest paths: Floyd-Warshall algorithm
{{{unit}}}
| Unit IV | Algorithm Design Techniques | 10 |
Greedy Algorithms: The job/event scheduling problem – Minimum-spanning-tree problem; Recursive backtracking: Developing recursive backtracking algorithm – Pruning branches – N-queens problem; Developing dynamic programming algorithms – Subtle points – Decreasing time and space – Longest common subsequence problem, Weighted job/Event Scheduling Problem
{{{unit}}}
| Unit V | NP Complete and NP Hard | 8 |
Reductions and NP – Completeness – Satisfiability – Proving NP-Completeness – 3-Coloring – Bipartite Matching.
\hfill Total: 45
After the completion of this course, students will be able to:
- Apply asymptotic notations and methods to find the time complexity of linear and recursive algorithms. (K3)
- Develop optimal algorithms using tree data structures (K3)
- Develop optimal algorithms using graph data structures. (K3)
- Solve problems using suitable design techniques (K4)
- Explain NP type problems and their reductions (K2)
- Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein, “Introduction to Algorithms”, Third Edition, Prentice-Hall, 2012
- Jeff Edmonds, “How to Think about Algorithms”, Cambridge University Press, 2008
- Alfred V. Aho, John E. Hopcroft, Jeffrey D. Ullman, “Data Structures and Algorithms”, Pearson Education, Reprint 2006.
- Robert Sedgewick and Kevin Wayne, “Algorithms”, Fourth Edition, Pearson Education, 2012
- S. Sridhar, “Design and Analysis of Algorithms”, First Edition, Oxford University Press, 2014
| PO1 | PO2 | PO3 | PO4 | PO5 | PO6 | PO7 | PO8 | PO9 | PO10 | PO11 | ||
| K3 | K6 | K6 | K6 | K6 | ||||||||
| CO1 | K3 | 3 | 2 | |||||||||
| CO2 | K3 | 3 | 2 | 2 | ||||||||
| CO3 | K3 | 3 | 2 | 2 | ||||||||
| CO4 | K4 | 3 | 2 | 2 | 2 | |||||||
| CO5 | K2 | 2 | ||||||||||
| Score | 14 | 8 | 6 | 2 | ||||||||
| Course Mapping | 3 | 2 | 2 | 2 |