Prerequisite (if any) : Data Structures and Algorithms
Course Content
Review of Basic Concepts
Asymptotic analysis of efficiency of algorithms, amortized analysis with an example (binary counter or stack with multipop), lower bounds for searching, finding maximum and sorting [6 lectures + 1 tutorial hour]
Graph Search Algorithms: DFS and BFS with applications to connectivity in undirected graphs, topological sorting and strongly connected components in directed graphs, shortest paths in unweighted graphs. [6 lectures + 3 tutorial hours]
Algorithm Design Paradigms
Overview of design paradigms  greedy strategy, dynamic programming, divide and conquer, iterative improvement.
Greedy Algorithms  optimal substructure and greedy choice, shortest paths in directed acyclic graphs, Dijkstra's algorithm, minimum spanning trees, cut property and cycle property theorems, Prim's algorithm, Kruskal's algorithm  unionfind data structure and amortized analysis of path compression heuristic. [10 lectures + 3 tutorial hours]
Dynamic Programming  optimal substructure, overlapping subproblems, ordering of subproblems and memoization, revisiting shortest paths in directed acyclic graphs, BellmanFord algorithm, allpairs shortest algorithms and FloydWarshall algorithm. [8 lectures + 3 tutorial hours]
Iterative Improvement  Networks and flows, Maxflow mincut theorem, FordFulkerson algorithm, EdmondsKarp algorithm. Matching in bipartite graphs using flows. [7 lectures + 1 tutorial hour]
Computational Complexity
Polynomial time reductions, classes NP, coNP and P, NPcomplete problems. [7 lectures + 1 tutorial hour]
Remarks: The tutorials sessions will typically be utilized for discussing problem sets and/or evaluating programming assignments. Course contents overlap with MCaM core course CS5009 Algorithms, however, CS5009 is not an elective for UG.
Learning Outcomes

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 NPHard problems using simple reductions.
Textbooks
 Algorithms by Sanjoy Dasgupta, Christos H. Papadimitriou, Umesh Vazirani. McGraw Hill Education, 2006. ISBN: 9780073523408.
Reference

The Design and Analysis of Algorithms by Dexter C Kozen. Texts and Monographs in Computer Science, Springer, 1992. ISBN:0387976876.

Introduction to Algorithms (3rd Edition) by Thomas H. Cormen, Charles E. Leiserson, Ronald L Rivest, Clifford Stein. PHI Learning, 2009. ISBN:9788120340077.

Algorithm Design by Jon Kleinberg and Eva Tardos. Pearson, 2015. ISBN:978933251864.
Past Offerings
(Note: Past offerings could be under a different course number.) Offered in JanMay, 2023 by Krithika Ramaswamy
 Offered in JanMay, 2022 by Jasine Babu
 Offered in JanMay, 2021 by Jasine
 Offered in JanMay, 2020 by Krithika
 Offered in JanMay, 2019 by Krithika
Course Metadata
Item  Details 

Course Title  Design and Analysis of Algorithms 
Course Code  CS3070 
Course Credits  3104 
Course Category  PMC 
Proposing Faculty  Jasine Babu & Krithika Ramaswamy 
Approved on  Senate 20 of IIT Palakkad 
Course prerequisites  Data Structures & Algorithms 
Course status  NEW 
Course revision information  Minor revision of CS2040 Design & Analysis of Algorithms Course 
Course prerevision code  CS2040 