Design & Analysis of Algorithm

Any mathematical problem which is to be solved using computers requires a specific algorithm designed for it. And once algorithm is ready it can be then converted to any of the programming language to make it workable on computer system. The most important property for any algorithm is to produce a correct output with in a feasible time and this time is always dependent on the input size of the problem. Higher the number of inputs to be processed, higher the execution time will be taken to produce an answer.

So in this subject we are going to read about what are the different factors that effect design of the algorithm, how to avoid the performance lag, how to define the limits for any input size, which techniques are used to solve the real world problems in terms of computer programs, and how to optimize the existing algorithm for certain problems.

Following are the topics which we are going to cover:

1. Introduction
   1. What is an algorithm
   2. Performance Analysis - Time and space complexity of an algorithm
   3. Asymptotic notations
   4. Polynomial vs. Exponential running time
2. Basic Algorithm Techniques
   1. Divide and Conquer Technique
   2. Greedy Technique
   3. Randomization Techniques
   4. Dynamic Programming Technique
3. Graph Algorithms
   1. Introduction to graphs
   2. Breadth First Search & its Applications
   3. Depth First Search & its Applications
   4. Topological Sort
   5. Minimum Spanning Tree
   6. Dijkstra Algorithm
   7. Bellman ford Algorithm
4. Sorting and Searching
   1. Linear Search
   2. Binary Search
   3. Bubble Sort
   4. Quick Sort
   5. Merge Sort
   6. Heap Sort
   7. Radix Sort
   8. Lower Bounds of Sorting
   9. Median and Order Statistics
5. NP-completeness
   1. Introduction to problem classes
   2. 3SAT of NP-Complete
   3. Proving a problem to be NP-complete using polynomial-time reduction.
   4. Examples of NP-complete problems
   5. Approximation algorithms for various NP-complete problems
6. Misc Topics
   1. Knuth_Monis-Pratt algorithm
   2. Convex hulls and its applications
   3. Fast Fourier Transform (FFT) and its applications
   4. Integer and polynomial arithmetic
   5. Strassen's algorithm

References

• Leiserson, Charles E., Ronald L. Rivest, and Clifford Stein. Introduction to algorithms. Ed. Thomas H. Cormen. The MIT press, 2001.