Module
No.
Description     PDF
             0 Turing Machines and Input Representation
In this module, we shall explore computing models such as Turing machines, RAM, etc. We shall also discuss input representation and time complexity analysis for different encodings.
    
             1 Average Case Analysis
In this module, average case analysis of classical search and sorting problems are discussed in detail.
    
             2 Order Statistics
This module discusses algorithms for finding simultaneous minimum and maximum, minimum and second minimum, and K-th minimum efficiently.
    
             3 Min-Max Heap and Deap
This module discusses two advanced data structures using which we can find min and max efficiently.
    
             4 Binomial Heap
Binomial heap is a data structure that supports MERGE operation efficiently. Other operations include insert, extract min, decrease key and delete.
    
             5 Amortized Analysis
A variant of classical asymptotic analysis where we focus on average time in worst case for a sequence of operations. Case studies such as stack and binary counter are discussed in detail with respect to aggregate analysis, accounting method and potential function method.
    
             6 Amortized Analysis - Dynamic Tables
We shall discuss dynamic tables with supporting operations in detail. The importance of choosing the right potential function will also be highlighted.
    
             7 Fibonacci Heap
Fibonacci heap is a variant of binomial heap and has a relation to Fibonacci series. We shall explore Fibonacci heap and its associated operations from the perspective of amortized analysis.
    
             8 Greedy Algorithms
Case studies such as interval scheduling and minimum weight spanning tree along with a proof of correctness are discussed.
    
             9 More on NP and Reductions
This module considers some more reductions for classical problems and its variants. Solving optimization problem using decision as a black box is also explored for various case studies..