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