What is an algorithm? Design and performance analysis of algorithms, time complexity, space
complexity.
Asymptotic notations (O, Ω, Ө) to measure growth of a function and application to measure
complexity of algorithms.
Analysis of sequential search, bubble sort, selection sort, insertion sort, matrix multiplication.
Recursion: Basic concept. Analysis of recursive algorithms, Master’s theorem.

The Divide & Conquer Design Technique:
The general concept. Binary search, finding the maximum and minimum, merge sort, quick
sort. Best and worst case analysis for the mentioned algorithms. Strassen’s matrix
multiplication.
Lower bound for comparison-based sorting.

The Greedy Design Technique:
The general concept. Applications to general Knapsack problem, finding minimum weight
spanning trees: Prim’s and Kruskal’s algorithms, Dijkstra’s algorithm for finding single source
shortest paths problem.

The Dynamic Programming Design Technique:
The general concept. Computation of Fibonacci series and Binomial coefficients, all pair
shortest paths problem (Floyd-Warshall’s algorithm), 0/1 Knapsack problem.
Algorithms on Graphs:
Finding connected components, topological sorting.