Introduction. What is an algorithm ? Time and space complexity of an algorithm. Comparing the
performance of different algorithms for the same problem. Different orders of growth. Asymptotic notation.
Polynomial vs. Exponential running time.
Basic Algorithm Design Techniques. Divide-and-conquer, greedy, randomization, and dynamic
programming. Example problems and algorithms illustrating the use of these techniques.
Graph Algorithms. Graph traversal: breadth-first search (BFS) and depth-first search (DFS). Applications
of BFS and DFS. Topological sort. Shortest paths in graphs: Dijkstra and Bellman-Ford. Minimum spanning
trees.
Sorting and searching. Binary search in an ordered array. Sorting algorithms such as Merge sort, Quick
sort, Heap sort, Radix Sort, and Bubble sort with analysis of their running times. Lower bound on sorting.
Median and order statistics.
NP-completeness. Definition of class NP. NP-hard and NP-complete problems. 3SAT is NP-complete.
Proving a problem to be NP-complete using polynomial-time reductions. Examples of NP-complete
problems.
Coping with NP-completeness. Approximation algorithms for various NP-complete problems.
Advanced topics. Pattern matching algorithms : Knuth-Morris-Pratt algorithm. Algorithms in Computational
Geometry : Convex hulls. Fast Fourier Transform (FFT) and its applications. Integer and polynomial
arithmetic. Matrix multiplication : Strassen's algorithm