Introduction - Algorithms vs programs. Flow charts and pseudo code, Rate of
growth of functions. Asymptotic notation: motivation and types of notations.
Recurrence relations and methods to solve them: Recursion tree, substitution,
Master Method, Sorting: Bubble – Insertion – Selection – Bucket – Heap, Comparison
of sorting algorithms, Divide and Conquer: Quick sort – Merge sort – Binary search
– Long integer multiplication – Maximum sub array sum.
Greedy Algorithm - Introduction to the method, Fractional Knapsack problem, Task
Scheduling Problem, Dynamic Programming: Introduction to the method, Fibonacci
numbers, 0-1 Knapsack problem, Matrix chain multiplication problem. Backtracking,
Branch and Bound 0-1 Knapsack, N- Queen problem.
Graph Algorithms - Graph Traversal: Applications of BFS: distance, connectivity
and connected components and cycles in undirected graphs. Applications of DFS:
Topological sort, cycles in directed graphs, Biconnected Components and Strong
Connectivity. Path algorithms: Shortest path algorithms (along with analysis) SSSP:
Bellman Ford. APSP: Floyd Warshall’s. Minimum Spanning Tree (with analysis and
applications). Introduction to NP class: Definitions P, NP, NP complete, NP hard,
Examples of P and NP.