DAA (B-TECH computer science engineering 5th)

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