Prerequisite (if any) : Data Structures and Algorithms
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]
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.
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.
- Algorithms by Sanjoy Dasgupta, Christos H. Papadimitriou, Umesh Vazirani. McGraw- Hill Education, 2006. ISBN: 978-0073523408.
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.