According to Wikipedia, the definition of the algorithm is as follows,
"In mathematics and computer science, an algorithm is a finite sequence of rigorous instructions, typically used to solve a class of specific problems or to perform a computation." - wikipediaTherefore the algorithm is a step-by-step approach to solving a mathematical problem.
Algorithms may be simple or complex depending on the task one should need to complete.
Phones, computers, laptops, calculators, and most of the equipment involve a digital approach to complete a task using algorithms. Algorithms are used every time you use your phone, computer, laptop, or calculator. Similarly, algorithms aid in the completion of a task in programming to provide the desired outcome.
The developed algorithms are language-independent, which means they are just plain instructions that may be implemented in any language and provide the same result.
Table of Contents
Characteristics of Algorithms
Clear and Unambiguous: The steps of the algorithms should be clear and not open to more than one interpretation.
Well-Defined Inputs: If an algorithm requires inputs, those inputs should be well-defined. It may or may not accept user input.
Language Independent: Algorithms can be implemented in any language but the result should be the same as plain instructions.
Feasible: The algorithm must be simple, generic, and practical enough to be run with the resources provided. It must not include any futuristic technologies or anything else.
Finite-ness: The algorithm program should finish its task after a specific time.
Properties of Algorithm
It should end after a certain amount of time.
It must generate at least one output.
It should accept 0 or more input.
It should be deterministic, which means it should provide the same result for every input instance.
Every step in the algorithm must be effective, which means that each step must perform some function.
Types of Algorithms
Brute Force Algorithm
When we encounter a problem, the first technique that comes to us is the brute force algorithm. It is the simplest solution to a problem. It is the same as iterating through every possible solution to the problem.
For example, a brute force algorithm for solving the traveling salesman problem would check all possible routes to find the shortest one.
Recursive Algorithm
Recursion is the foundation of a recursive algorithm. In this situation, an issue is divided into multiple sub-parts and the same function is called repeatedly.
A recursive algorithm to find the nth Fibonacci number would call itself twice with the input of n-1 and n-2 can be given as an example.
Backtracking Algorithm
Backtracking algorithms construct solutions by looking through all possible solutions. Using this approach, we continue to create the result based on the criteria. Whenever a solution fails, we trace back to the failure point and build on the next solution, repeating this process until the solution is found or all possible options are considered.
For example, a backtracking algorithm to solve the n-queens problem would place queens on a chessboard one by one and undo the last step if it leads to a conflict with previously placed queens.
Searching Algorithm
Searching algorithms are those that are used to find items or groups of elements in a certain data structure. They can be classified according to their technique or the data structure in which the element should be identified. Binary search and linear search are two common issues that can be handled with the Searching Algorithm.
For example, a linear search algorithm would check each item in an array one by one until it finds the item it is looking for, while a binary search algorithm would divide the array in half and check the middle value to narrow down the search.
Sorting Algorithm
The process of arranging a bunch of data in a certain order based on the requirements like ascending or descending for example is called sorting. Sorting algorithms are the algorithms that aid in the performance of this function. The sorting Algorithm can handle several issues, including bubble sort, insertion sort, merge sort, selection sort, and rapid sort.
A bubble sort algorithm would repeatedly go through an array and swap adjacent items if they are not in the correct order, while a quick sort algorithm would divide the array into smaller sub-arrays and repeatedly partition the data so that elements smaller than a pivot come before elements greater than a pivot is an example for sorting algorithm.
Hashing Algorithm
Hashing algorithms function similarly to searching algorithms. They do, however, have an index with a key ID that is a key-value pair. A key is assigned to specific data in hashing. password verification can be solved via a hashing algorithm.
A hash algorithm for a password database would take a plaintext password and map it to a unique, fixed-size hash value for storage.
Divide and Conquer Algorithm
The principle behind Divide and Conquer algorithms is to divide the issue into two sections, the first of which divides the problem into subproblems of the same type. The second step involves solving the smaller problems individually and then combining the results to arrive at the final solution to the problem. Some problems like Binary Search, Merge Sort, Quick Sort, and Strassen’s Matrix Multiplication can be solved using this algorithm.
For example, a divide and conquer algorithm for solving the closest pair of points problem would divide the set of points into two halves, solve each half recursively, and then combine the solutions.
Greedy Algorithm
The solution is created part by part in the Greedy Algorithm. The decision to go on to the next section is based on the fact that it provides an instant benefit. It never takes past decisions into account. The option that provides the most advantage will be picked for the upcoming section.
For example, a greedy algorithm for solving the knapsack problem would add the most valuable items to the knapsack until it is full, without regard for the overall value of the knapsack.
Dynamic Programming Algorithm
Dynamic Programming Algorithm is also known as the memoization technique since the objective is to store the previously calculated answer to prevent having to calculate it over and again. Divide the complicated issue into smaller overlapping subproblems and store the solution for further use in Dynamic Programming.
For example, a dynamic programming algorithm for solving the longest common subsequence problem would store the length of the longest common subsequence of all substrings of the two input strings in a table, so that it can be reused later.
Randomized Algorithm
We use a random integer in the randomized algorithm. It aids in determining the expected outcome. The choice to select a random number that provides an immediate advantage.
For example, a randomized algorithm for solving the traveling salesman problem would generate a large number of random routes and select the shortest one as the solution.
Advantages and Disadvantages of Algorithms
Advantages | Disadvantages |
It can be easily understood. | Writing an algorithm is a time-consuming procedure. |
A step-by-step representation of a solution to a given issue is what an algorithm is. | It is difficult to understand complex logic via algorithms. |
The problem is broken into smaller parts or steps in an algorithm, making it easier for the programmer to translate it into an actual program. | Algorithms make it difficult to demonstrate Branching and Looping statements. |
Designing an Algorithm
Identify the problem that has to be solved clearly.
Consider the limitations of the problem while solving it.
Consider the inputs required to solve the problem.
Consider the expected output when the problem is solved.
Make sure the solution to the problem is within the limitations.
Write the algorithm when you have decided on the above prerequisites program.
Analyzing an Algorithm
Priori Analysis
"Priori" is Latin for "before". As a result, priori analysis implies testing the method before implementing it. When the algorithm is stated in the form of theoretical stages, it is tested. The efficiency of an algorithm is calculated by assuming that all other variables, such as processor speed, are constant and have no influence on the implementation. This is normally done by the algorithm designer. This examination is unaffected by the compiler's hardware or language. It provides approximations for the program's complexity.
Posterior Analysis
"Posterior" means "after". As a result, posterior analysis refers to testing the method after it has been implemented. The algorithm is validated by implementing it in any programming language and running it. This analysis assists in obtaining an actual and real analysis report on correctness (whether or not each potential input/s shows/returns proper output), space required, time wasted, and so on. That is, it is determined by the compiler's language and the type of hardware used.
Algorithm Complexity
The quantity of Space and Time consumed by an algorithm determines its complexity. As a result, an algorithm's complexity relates to the amount of time it will take to run and generate the desired output, as well as the amount of storage it will require to store all of the data (input, temporary data, time-consuming, and output). As a result, these two factors define an algorithm's efficiency.
Hence the Algorithm complexity is two types.
Space Complexity
The amount of memory needed by an algorithm to store variables and obtain the result is referred to as its space complexity. This applies to inputs, temporary operations, and outputs.
Time Complexity
The time complexity of an algorithm relates to how long it takes the algorithm to run and return the result. This may be used for standard operations, conditional if-else statements, loop statements, and so on.
Express an Algorithm
Natural Language
Algorithms are explained here in plain English. It is very difficult to deduce the algorithm from Natural Language.
Flow Chat
The algorithm is expressed graphically/pictorially. It is simpler to grasp than Natural Language.
Pseudo Code
We represent the algorithm in the form of annotations and informative text written in plain English, which is very similar to genuine code, but since it lacks syntax, it cannot be compiled or interpreted by the computer. It is the greatest technique to explain an algorithm since it can be understood by anybody with basic programming experience.
Commentaires