This is a revision of the course CS2040

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 - 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

  1. Develop the ability to analyze the running time and prove the correctness of basic algorithms.

  2. To be able to design efficient algorithms for moderately difficult computational problems, using various algorithm design techniques taught in the course.

  3. To be able to prove the hardness of NP-Hard problems using simple reductions.

Textbooks

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

Reference

  1. The Design and Analysis of Algorithms by Dexter C Kozen. Texts and Monographs in Computer Science, Springer, 1992. ISBN:0-387-97687-6.

  2. 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.

  3. Algorithm Design by Jon Kleinberg and Eva Tardos. Pearson, 2015. ISBN:978-93-325-1864.