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.