This is a foundational and mandatory course that aims to build students' ability to apply various algorithmic design methods to provide an optimal solution to computational problems.
This course starts with time and space complexity analysis of divide and conquer algorithms using recursion-tree-based methods and Master’s theorem. Students would also learn about amortized time and space complexity analysis for randomized/probabilistic algorithms. Various algorithmic design strategies would be introduced via real-world examples and problems.
Students would learn when, where, and how to optimally use Divide and Conquer, Dynamic programming (top-down and button-up), Greedy, Backtracking, and Randomization strategies with examples. The module uses various practical examples from Array manipulations, Sorting, Searching, String manipulations, Tree & Graphs traversals, Graph path-finding, Spanning Trees, etc., to introduce the above algorithmic strategies in action. Students would implement many of the above algorithmic design methods from scratch as part of the assignments. The module also introduces how some of these popular algorithms are readily available via popular libraries in various programming languages.