|
Module No. |
Description | |
PDF |
|
0 |
Introduction to Computer Science We shall discuss the notion 'computation/computing' and its history. | |
|
|
1 |
Asymptotic Analysis This module introduces algorithm design, analysis using step count method, asymptotic analysis using order notation. Further, properties of asymptotic notation are discussed in detail. | |
|
|
2 |
Recurrence Relations We shall explore techniques for solving recurrence relations, in particular recurrence tree method and master theorem will be discussed in detail. | |
|
|
3 |
Sorting Classical sorting algorithms such as bubble sort, insertion sort, merge sort, heap sort, and quick sort are discussed in detail. Further, lower bound theory arguments for search and sorting algorithms are presented. | |
|
|
4 |
Dynamic Programming Five case studies; Assembly line scheduling, Matrix chain multiplication, 0-1 knapsack, Traveling salesman problem and Optimal binary search trees are discussed in detail. | |
|
|
5 |
Greedy Algorithms We shall discuss knapsack problem and its variants in detail. The importance of proof of correctness is also highlighted. | |
|
|
6 |
Graph Algorithms This module uncovers BFS and DFS and their applications in detail. Algorithms for articulation points, bridges, topological sorting and strongly connected components are discussed.
| |
|
|
7 |
Theory of NP-completeness The notion non-determinism is introduced in this lecture. Beyond polynomial-time algorithms and reductions between combinatorial problems are explored in detail. | |
|