Learning Objectives
This is an intermediate course on algorithm design. The first part of this course is intended to make students familiar with some basic graph algorithms and their efficiency analysis. The second part of this course will provide a detailed introduction to different algorithm design paradigms with illustrative problems. The third part of this course is looking at designing algorithms for the classical network flow problem. The last part of this course will deal with computationally hard problems and tackling them using approximation algorithms.
Learning Outcomes
- To develop the ability to analyze the running time and prove the correctness of basic algorithms.
- To be able to design efficient algorithms for moderately difficult computational problems, using various algorithm design techniques taught in the course.
- To be able to prove the hardness of NP-Hard problems using simple reductions.
- To be able to do performance analysis of simple approximation algorithms.
Syllabus
Module 1 (12 lectures) Review - asymptotic notation, graph search algorithms, topological sorting, computing shortest paths in unweighted graphs.
Graph Algorithms: minimum spanning tree algorithms - cut property, Kruskal’s algorithm using disjoint sets, Prim’s algorithm. Shortest path algorithms - Dijkstra’s algorithm, Bellman-Ford algorithm, Floyd-Warshall algorithm.
Module 2 (10 lectures) Design paradigms: greedy algorithms - greedy choice, fractional knapsack, Huffman coding. Dynamic programming - optimal substructure and overlapping sub-problems, coin changing, integral knapsack. Backtracking eight-queen's problem.
Module 3 (10 lectures) Network Flow: max-flow min-cut theorem, Ford Fulkerson algorithm, Edmond's shortest path heuristic, bipartite matching using max-flow.
Module 4 (8 lectures) Complexity: NP-completeness, polynomial time reductions, classes NP and P, NP-complete problems.
Approximation algorithms: vertex cover via maximum matching, greedy algorithm for set cover.
Textbook
- Introduction to Algorithms (3rd Edition) by Thomas H. Cormen, Charles E. Leiserson, Ronald L Rivest, Clifford Stein. PHI Learning, 2009. ISBN:978-81-203-4007-7.
- Algorithm Design by Jon Kleinberg and Eva Tardos. Pearson, 2015. ISBN:978-93-325-1864.
Reference
- The Design and Analysis of Algorithms by Dexter C Kozen. Texts and Monographs in Computer Science, Springer, 1992. ISBN:0-387-97687-6.
- Algorithms by Sanjoy Dasgupta, Christos H. Papadimitriou, Umesh Vazirani. McGraw- Hill Education, 2006. ISBN: 978-0073523408.
Past Offerings
- Offered in Jan-May, 2023 by Krithika Ramaswamy
- Offered in Jan-May, 2022 by Jasine Babu
- Offered in Jan-May, 2021 by Jasine
- Offered in Jan-May, 2020 by Krithika
- Offered in Jan-May, 2019 by Krithika
Course Metadata
| Item | Details |
|---|---|
| Course Title | Design and Analysis of Algorithms |
| Course Code | CS2040 |
| Course Credits | 3-1-0-4 |
| Course Category | PMT |
| Proposing Faculty | Jasine Babu |
| Approved on | Senate 6 of IIT Palakkad |
| Course prerequisites | CS2030 Data Structures & Algorithms |
| Course status | old |
| Course revision information | NOT GIVEN |