Module 1 Introduction to Problems, Algorithms and Computation, Basic Abstract Data Types (list or dynamic multi set, stack, queue) and Data Structures (array, linked list)
Module 2 Basic Algorithm Design & Analysis: RAM model of computation, notion of efficiency, asymptotic analysis, sorting arrays using iterative algorithms (selection sort, insertion sort) and recursive algorithms (merge sort, quick sort)
Module 3 Priority Queue, Expressions & Dictionary: Heap (for priority queue), hash table (for dictionary), binary search tree (for both dictionary & priority queue), expression trees (for arithmetic expressions)
Module 4 Graphs & Algorithms on Graphs: Representing graphs using list and matrix, depth-first search, topological orderings, strongly connected components, breadth-first search and shortest paths
Module 1 Algorithms with numbers - arithmetic on integers, modular arithmetic, GCD (Euclid’s algorithm). Factoring and primality testing. Iterative and recursive algorithms - multiplication and division algorithms, Towers of Hanoi. Divide and Conquer - multiplication. Solving recurrences using induction, recursion tree, Master Theorem. Estimates of factorials and binomials.
Module 2 Sorting (comparison model and exchange model) and searching lower bounds (sorted and unsorted lists). Find Max, Find Max-Min, Find Second Max upper and lower bounds.
Module 3 Graph algorithms using greedy, dynamic programming and iterative improvement - single source shortest path (in uniform weighted (di)graphs, arbitrary weighted DAGs, non-negative weights digraphs, arbitrary weighted digraphs), all pairs shortest path, minimum spanning trees, maximum flow, maximum bipartite matching.
Module 4 Theory of NP-completeness - polynomial-time reductions, classes NP, co-NP and P, NP-complete problems.
Discrete Mathematics
Part 1 Logic and Set Theory
Introduction to proofs. Well ordering principle. Logical formulas - propositional and predicate. Sets, relations, equivalences and partial orders. Induction. Recursive definitions. Infinite Sets: Cantor’s theorem, diagonalization argument, halting problem. Logic of sets.
Part 2 Graph Theory
Graphs, degree. Common graphs. Walks, paths, connectivity, cycles, trees, forests. Cliques, Independent sets. Graph Isomorphism, bipartite graphs and matchings. Coloring. Planar graphs: Euler’s formula, 6-coloring of planar graphs.
Part 3 Combinatorics
Product rule, division rule, counting subsets, sequences with repetitions - binomial and multinomial theorems. Pigeonhole principle. Inclusion-exclusion. Combinatorial proofs. Twelvefold way. Recurrence relations - Fibonacci numbers and Towers of Hanoi puzzle.
Part 4 Discrete Probability
Events and probability spaces. Set theory and probability. Conditional probability, law of total probability. Independence. Probability versus confidence. Random variables: independence. distribution functions, expectations. Linearity of Expectation.
Graph Theory and Combinatorics
Matching, Hall's Theorem, Kőnig's Theorem, Connectivity, Coloring, Planar Graphs, Eulerian Graphs, Hamiltonian cycles, Dirac's Theorem, Ore’s Theorem.
Introduction to Ramsey Theory and Extremal Graph Theory.
Ordinary, Exponential and other special Generating Functions, Formal Power Series.
Linear Algebraic Arguments like Dimensionality, Orthogonality and Rank arguments. Introduction to Spectral Graph Theory.
Basic Toolkit: branching, kernelization, iterative compression, LP techniques, crown decomposition, sunflower lemma
Randomized Techniques: color coding, chromatic coding, random separation, derandomization
Algebraic Techniques: principle of inclusion-exclusion, polynomial identity testing, representative sets
Treewidth: dynamic programming over tree decomposition, computing/approximating treewidth
Hardness: fixed-parameter intractability, kernelization lower bounds, ETH-based lower bounds
Combinatorial Optimization
Introduction: Network Flows, Ford-Fulkerson Method, Edmonds-Karp Algorithm, Linear Programming (LP), LP Formulation for Flows, LP Duality, Weak Duality Theorem, Complementary Slackness, Farkas’ Lemma
Linear Programming based Optimization: Minimum Spanning Trees, Shortest Paths, Totally Unimodular Matrices from Bipartite Graphs, Maximum Matching and Minimum Vertex Cover on Bipartite Graphs
Polyhedral Techniques: Polyhedra and Polytopes of Linear Programs, The Matching and Perfect Matching Polytopes for General Graphs, The Independent Set Polytope, Polyhedral Characterization of Bipartite Graphs and Perfect Graphs
Advanced Topics: Semidefinite programming based algorithms and Matroid based algorithms