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 - union-find 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, Bellman-Ford algorithm, all-pairs shortest algorithms and Floyd-Warshall algorithm. [8 lectures + 3 tutorial hours]

Iterative Improvement - Networks and flows, Max-flow min-cut theorem, Ford-Fulkerson algorithm, Edmonds-Karp algorithm. Matching in bipartite graphs using flows. [7 lectures + 1 tutorial hour]

Computational Complexity

Polynomial time reductions, classes NP, co-NP and P, NP-complete 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 NP-Hard problems using simple reductions.

Textbooks

Algorithms by Sanjoy Dasgupta, Christos H. Papadimitriou, Umesh Vazirani. McGraw- Hill Education, 2006. ISBN: 978-0073523408.

Reference

The Design and Analysis of Algorithms by Dexter C Kozen. Texts and Monographs in Computer Science, Springer, 1992. ISBN:0-387-97687-6.
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.

Past Offerings

(Note: Past offerings could be under a different course number.)

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	CS3070
Course Credits	3-1-0-4
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 pre-revision code	CS2040