This article is about Algorithm Definition that describes some terms related to algorithms such as Infix, Postfix, characteristics, etc.
Let’s see another article DSA.
Table of Contents
Algorithm
An Algorithm is a set of instructions that are provided to the computer to perform some tasks. It is the set of procedures given to the input to return the output. An algorithm is a sequence of instructions that converts input to output.
It can also be considered as a tool for solving computational problems. The algorithm describes the specific steps to be followed by the problem statement to result in the input/output.
Steps to follow the algorithm
- Parenthesize the Infix expression according to the operator’s high precedence value.
- Start solving the expression from left to right and move each operator to its right parentheses.
- Remove all parentheses.
E.g., Conversion of Infix equation to Postfix.
Expression: A + B * C + D
Step 1: ([A + B] * [C + D]) #write infix expressions into parentheses as per precedence value.
Step 2: ([A B +] * [C D +]) #Move the operator to its right parentheses.
Step 3: AB + C D + * #Remove the brackets.
Features of an algorithm
- Well-defined inputs and outputs: An algorithm should have clearly defined inputs and outputs. It should specify what data or information is required as input and what results or outcomes are expected as output.
- Finiteness: An algorithm should terminate after a finite number of steps. It should have a clear stopping criterion, ensuring that it will complete its execution and produce the output.
- Well-defined steps: An algorithm should be composed of a well-defined set of instructions or steps. Each step should be clearly defined, specifying what operation needs to be performed.
- Determinism: An algorithm should be deterministic, meaning that for a given input, it should produce the same output every time it is executed. The steps and computations in the algorithm should be fully determined and predictable.
- Effective and efficient: An algorithm should be designed to solve a problem effectively and efficiently. It should provide a correct solution to the problem and do so in a manner that optimizes resources such as time, memory, or computational power.
Types of Algorithms
- Brute Force Algorithm: A Brute Force Algorithm is the most basic type of algorithm that tries all possible solutions/chances to return the output. E.g., If there is a lock of a 3-digit PIN, then the algorithm will try to break the PIN from all combinations of available chances starting from 000, 001, 002, 003, and so on. In the worst-case scenario, it can take a lot of time to solve the problem.
- Recursive Algorithm: Recursive algorithm is based on recursion in which the problem is broken into sub-problems and repeated in the same condition to solve the problem with the help of the base condition.
- Divide and conquer: Divide and conquer based on the rule of breaking the problem into two sections. The first section is used to divide the main problem into small multiple problems and the second section solved those problems independently and finally, combines the solutions to get the final result.
- Dynamic Programming Algorithm: Dynamic Programming Algorithm is also called the memoization technique because it stores the previously calculated result to avoid calculating it over and again in the next steps. In Dynamic Programming, divide the problem into subproblems and store the result for the future.
- Greedy Algorithm: Greedy Algorithm is used to find the solution step by step. The decision of choosing the next step is based on the immediate result it gives. Also, it keeps ignoring the solutions for the selection again it had already taken.
- Backtracking Algorithm: Backtracking Algorithm is considered to build the solution by incrementing procedure. It is a technique to solve the problem recursively by trying to build the solution incrementally, one after another, removing those solutions that fail to meet the problem’s requirements.
Efficiency of Algorithms
An algorithm’s efficiency can be evaluated at two separate levels, before and after implementation. These are the following −
A Priori Analysis: This is an algorithm theoretical analysis. An algorithm’s efficiency is calculated by assuming that all other variables are constant and have no effect on the implementation, such as processor speed.
A Posterior Analysis: This is an algorithm’s empirical analysis. A programming language is used to implement the chosen algorithm. This is executed on the target computer machine afterward. In this analysis, actual statistics are collected, such as the necessary running time and space.
Complexity of Algorithms
If X is an algorithm and n is the input data size, the time and space used by the X algorithm are the two key factors that determine X’s performance.
Time Factor: Time is calculated by counting the number of main operations in the sorting algorithm, such as comparisons.
Space Factor: Space is determined by counting the algorithm’s maximum memory space available.
The complexity of an algorithm f(n) gives the algorithm’s necessary runtime and/or storage space in terms of n as the input data size.
Complexity in Space
The algorithm’s space complexity reflects the amount of memory space needed by the algorithm throughout its life cycle. The space needed by an algorithm is equal to the sum of the two components that follow,
A fixed component is a space needed to store some information and variables that are independent of the problem’s size. Easy variables and constants, for instance, used program size, etc.
A part of a variable is the space needed by variables, the size of which depends on the problem’s size. For instance, allocating dynamic memory, recursion stack space, etc.
Complexity in space Of any algorithm, S(P) P is S(P) = C + SP(I), where C is the fixed part and S(I) is the algorithm’s variable part, which depends on the characteristic of the instance I.
The following is a brief example that helps to illustrate the theory.
SUM: algorithm (A, B)
Phase 1 – Beginning
Phase 2 – C > A + B + 10
Phase 3 – Avoiding
We have three variables here, namely A, B, and C, and one constant. Therefore, S(P)= 1 + 3. Now, space depends on and will be multiplied accordingly by data types of given variables and constant types.
Analysis Method – Asymptotic Analysis
An algorithm’s asymptotic analysis refers to the concept of its run-time performance’s mathematical foundation/framing. We can very well infer the best-case, average-case, and worst-case scenarios of an algorithm using asymptotic analysis.
Asymptotic analysis is bound by input, i.e. it is concluded to operate in a constant time if there is no input to the algorithm. All other variables are considered stable, other than the input.
In mathematical units of computation, asymptotic analysis refers to calculating the running time of any operation. E.g., one operation’s running time is computed as f(n), while another operation’s running time is computed as g. (n2). This means that as n increases, the first operation’s running time will increase linearly, while the second operation’s running time will increase exponentially. Similarly, if n is substantially small, the runtime of both operations would be almost the same.
An algorithm’s time requirement typically falls into one of three groups –
- In the best-case scenario, the program execution time is as short as possible.
- Average Case Average time needed for execution of the program.
- Bad Case-Maximum time needed for implementation of the program
Conclusion
The article provides a comprehensive understanding of algorithms, their definition, and their key characteristics. It emphasizes that algorithms are step-by-step procedures designed to solve problems or perform specific tasks. It highlights the essential features of algorithms, which include well-defined inputs and outputs, finiteness, well-defined steps, and determinism, etc.,
It emphasizes the importance of these characteristics in designing and evaluating algorithms. It explains that algorithms should have clear instructions, ensuring that they can be executed in a finite number of steps and produce consistent and predictable results. It also highlights the significance of algorithm efficiency, both in terms of time and resource utilization.
