Introduction to Algorithms - Geeks4Coding

Algorithms

 

Algorithms

 A process or set of rules to be followed in calculations or other problem-solving operations, especially by a computer.

Or

Set of rules defined to make any task complete, how to handle the data and store it and how easy the data can be access, manipulate, delete etc.

Analysis of Algorithms:

Asymptotic Analysis:

               Asymptotic Analysis using Asymptotic analysis we can find worst case, average case and best case performance of any algorithm.

Notation used to define algorithms:

1. Θ Notation (theta)
2. Big O Notation:
3. Ω Notation(Omega)

Amortized Analysis:

             The Amortized cost of n operations is the total cost of the operations divided by n. Analyzing the amortized cost, however, will often require some thought if we want to do it well.

For example:
The time complexity of above algorithm is O(n).

Space Complexity:

             Space Complexity gives the amount of space used by algorithms to carry out certain task.

Or

 Space Complexity of an algorithm is total space taken by the algorithm with respect to the input size.
Space complexity is the Auxiliary Space at many Algorithms.

Auxiliary Space is the extra space or temporary space used by an algorithm.

Space complexity includes both Auxiliary space and space used by input.

For example, if we want to compare sorting algorithms on the basis of space, then Auxiliary Space Merge Sort uses O(n) auxiliary space, Insertion sort and Heap Sort use O(1) auxiliary space. Space complexity of all these sorting algorithms is O(n).

Types of Algorithm:

Searching Algorithm: 

             Search data from given input. Some of the searching algorithms are Linear Search, Binary Search, Jump Search, Interpolation Search, Exponential Search, and Ternary Search

Sorting Algorithm:

              Sorting the given data in a required manner like ascending/increasing, descending/decreasing. Some of the sorting algorithms are Selection Sort, Bubble Sort, Counting Sort, Bucket Sort, Shell Sort, Insertion Sort, Quick sort, Radix Sort, Merge Sort, Heap Sort etc.

Greedy Algorithms:

              Greedy is an algorithm that solve problem always choosing between the next most optimum solution as immediate benefit. Greedy algorithms are used for optimization problems. A problem can be solved using Greedy if the problem has the property: At every step, we can make a choice that looks best at the moment, and we get the optimal solution of the complete problem.

If a Greedy Algorithm can solve a problem, then it generally becomes the best method to solve that problem as the Greedy algorithms. Examples Dijkstra’s Shortest Path Algorithm, Kruskal’s Minimum Spanning Tree Algorithm, Prim’s Minimum Spanning Tree Algorithm etc.

Backtracking:

              Backtracking is an algorithm that make use of different solutions until it finds a solution. These problems can only be solved by trying every possible configuration and each configuration is tried only once. Example rat in maze, queens algorithm etc.

Divide and Conquer: 

              Divide and Conquer algorithm break the given problem into sub problems of same type.Recursively solve these sub problems. Appropriately combine the answers example Binary search, merge sort etc.

We will cover all topics soon…