An Algorithm is a sequence of steps to solve a problem. Design and Analysis of Algorithm is very important for designing algorithm to solve different types of problems in the branch of computer science and information technology. This tutorial introduces the fundamental concepts of Designing Strategies, Complexity analysis of Algorithms, followed by problems on Graph Theory and Sorting methods. This tutorial also includes the basic concepts on Complexity theory.
Note: Click on the topic to watch video
UNIT-I
2. Performance Analysis -Space complexity
3. Performance Analysis -Time complexity
4. Asymptotic Notations (Big-oh notation).
5. Asymptotic Notations (Omega notation).
6. Asymptotic Notations (Theta notation).
UNIT-II (Divide and Conquer)
2. Binary search
2.1. Binary search Iterative Method
2.2. Binary search Recursive Method
3. Merge sort
3.1. Merge sort Example
3.2. Merge sort Time Complexity
4. Quick sort
4.1. Quick sort Example
4.2. Quick sort Time Complexity
5. Strassen’s matrix multiplication.
5.1. Introduction to Strassen’s matrix multiplication.
5.2. Example of Strassen’s matrix multiplication.
Note: Algorithm, example, and Time Complexity are important while writing Exam.
UNIT-III (Greedy method)
3. Job sequencing with deadlines
4. Minimum cost spanning trees
4.1. Prim's Algorithm
4.1.1. Prim's Algorithm Time Complexity
4.2. Kruskals Algorithm
4.2.1.Kruskals Algorithm Time Complexity
5. Single source shortest paths
UNIT-IV(Dynamic Programming)
2. All pairs shortest path problem Example
2.1. All pairs shortest path problem Algorithm Analysis
6. The Travelling sales person problem
7. Matrix-chain multiplication
UNIT-V
Backtracking:
Branch and Bound:
Travelling sales person problem.
Differences between different methodologies
1. Difference between divide and conquer Vs Greedy Method
2. Difference between divide and conquer Vs Dynamic Programming