101 lessons: An Introduction to Algorithm and its bunch of characteristics

A process or set of rules to be followed in calculations is simply referred to as an Algorithm. In this way, Algorithm alludes to a defined bunch of rules or instructions that step-by-step characterize how a work is to be executed to get the expected outcomes.

Talking about subjects like mathematics, statistics, linguistics, and related domains, an algorithm is defined as a sequence of finite instructions, often used to perform computations and data processing. It is an effective methodology wherein a list of well-defined rules and steps for completing a task flow through a definite series of successive states-given an initial state and eventually conclude in an end-state. The transition from one state to the next is not always a straightforward process. For example, probabilistic algorithms consolidate randomness.

Algorithms may also include pseudo-code, which is written in human-readable form. This allows programmers to understand what each line does without having to read it directly into their computer's memory. Also, they are language-independent. That is, algorithms are basically outright guidelines that can be executed in any programming language, and yet the expected output will always be the same.

A program is said to have been compiled if its source code has been converted into machine-executable binary format. If no compilation takes place then the program is said to be interpreted. Interpreted programs run slower than those that have undergone compiler optimization because interpretation requires more time to execute.

Let's now proceed to discuss some properties and characteristics of algorithms.

What are the major characteristics of algorithms?

Unambiguous and clear: There needs to be a clear and unambiguous algorithm. Each of the steps or phases should be clear and have a single meaning

Input specified: An algorithm has zero or more inputs, that is the quantities that are given to it initially before the start of the algorithm. What kind of data, how much, and what form it should be are things that input precision requires.

Output specified: An algorithm should have 1 or more well-defined outputs and should match with the expected output. If there will be any output at all, you have to know what kind of data and how much it should be.

Finiteness: After a finite amount of steps, the algorithm must end, for example, it should not get trapped in infinite loops.

Feasibility: The algorithm needs to be simple, generic, and practical in order for it to be executed. It must not contain technology from the future and should be feasible with the available resources.

Independent of the language: The Algorithm should always be independent of the programming language. It only refers to definite guidelines that can be implemented in any language to result in the same expected output.

Flexible: The algorithm must allow for flexibility in order to adapt to different situations, such as when there are multiple possible outcomes from one step. For example, if you want to find all the words that start with "a" but don't end with "b", then it's not enough just to check whether each word starts with an 'a'. You also need to know what happens after the first letter is found (e.g., does the next character match?)

It should be able to handle a large number of steps without becoming too slow or memory-intensive. This means that it needs to have some kind of data structure that can store information about previous states and transitions between them efficiently.

Note: The inputs to an algorithm are not necessarily limited to data, but may also include other information such as a set of rules for solving problems. This is called 'input-output' in some contexts.

Algorithms can be classified into two categories: deterministic algorithms and non-deterministic algorithms.

Deterministic algorithms are those that always produce the same output for a given input, regardless of how many times they have been run on it. Nondeterministic algorithms may or may not give different outputs depending upon which order in which their subroutines are called.

What are the categories of an algorithm?

There are three main types of algorithms – sequential, parallel, and hybrid.

Sequential Algorithms

In order to solve a problem, some steps of instructions are performed in chronological order. Sequential algorithms process elements sequentially. They do so by performing operations on individual elements until the entire list/set/array is processed. These algorithms are usually used for processing lists, sets, arrays, etc. Examples of these algorithms are bubble sort, selection sort, insertion sort, merge sort, quick sort, heap sort, shell sort, radix sort, bucket sort, and others.

Parallel Algorithms

A parallel algorithm can execute several instructions at the same time on different processing devices and combine them to produce a final output. The problem statement is broken down into sub-problem sets and is executed parallelly to get individual yields. Later on, these individual outputs are consolidated together to get the final desired result.

It isn't difficult to partition a huge problem set into sub-categories. Data dependency is possible among the sub-problems. The problem has to be solved by the processors communicating with each other. In order to communicate with each other, more time is needed than the actual processing time. So, while designing any parallel algorithm, appropriate CPU usage ought to be considered to get a proficient algorithm.

Hybrid Algorithms

A hybrid algorithm is a combination of two or more algorithms that are designed to provide better performance. Depending on the data, these are used to choose one or switch between them in a programming language, mainly C++. It is done to combine desired features of each component so that the overall formula is better than individual components.

Analysis of an Algorithm

Designing an efficient algorithm involves analyzing its characteristics like space requirement, speed, error handling, etc., before actually coding it. There are various ways to analyze an algorithm. Some of them are listed below:

Time Complexity Analysis

The Time complexity of an algorithm refers to its execution time. An algorithm's time complexity depends on both the size of the input and the amount of work required to perform all the necessary computations.

For example, sorting a list requires O, where n represents the total number of items being sorted. If we assume that there are only 2 items in our array then this would mean that the time taken to complete the operation will be equal to O. This means that if you double the length of your array then the time taken to finish the task increases linearly.

Space Complexity Analysis

Space complexity measures the space needed to store information about the inputs as well as the results produced during the course of executing the program. A simple way to measure space complexity is to count how many bytes are occupied by variables, constants, and memory locations. Memory location includes stack frames, registers, global variables, static local variables, dynamic local variables, and pointers.

Data Structure Design

Designing a good data structure involves choosing the right type of container and deciding whether it should use recursion or iteration. Choosing the best data structures also involves understanding what kind of access patterns they support.

Algorithm Optimization

Optimizing an existing algorithm may involve changing the code itself, reordering the code, replacing expensive functions with faster alternatives, removing unnecessary calculations, and combining similar tasks.

Code Review

Reviewing source codes helps programmers identify potential problems such as bugs, poor coding practices, inefficient implementations, and design flaws.

Error handling analysis

There are two different types of errors when writing a programming code. A syntax error is simply a mistake made in the structure of a statement. For example, in languages like C/C++. Writing a statement and forgetting the colon is incorrect. When you first start learning a language, there are more Syntax errors.

A logic error is when a program executes but gives the wrong result. This can be a result of an error in the underlying algorithm or translation. Sometimes logic errors can lead to very bad situations such as trying to divide by zero or access an item that is outside the bounds of a list. The program ends when the logic error leads to a runtime error. These types of runtime errors are typically called exceptions.

How to write good Algorithms?

The following points need to be kept in mind when we design our own algorithms:

1) We must consider all aspects of the problem at hand. For example, if we want to find out whether there exists a palindrome number within a certain range then we should first decide what exactly constitutes a palindrome number. This will help us determine the type of search required.

2) If we know the size of the array beforehand, we could use dynamic memory allocation techniques to allocate enough storage space for storing the numbers. However, this would require additional effort from the programmer's end.

3) In PHP, a simple way to check whether a given string contains only lowercase letters, is to convert it to upper case using strtoupper function. Similarly, converting a string to lower case is achieved through strtolower.

4) When dealing with strings, we have to keep in mind that they may contain special characters such as '\n' which denotes a new line character. To avoid this issue, we can replace \n with a blank space.

5) Another important thing to remember is that whenever we perform arithmetic operations on integers, we always round off towards negative infinity. Therefore, we cannot directly compare floating-point values without rounding them off.

6) Finally, we also have to take care about how many times we iterate over the same element.

There are a number of things that need to be done before you can write an algorithm:

The problem that is required to be solved by this algorithm.
It is necessary to consider the constraints of the problem while resolving it.
To solve the problem, the input will be taken.
When the problem is solved, the output must be expected.
The solution to this problem can be found in the given constraints.

After all the above steps, the algorithm is written such that it solves the problem keeping the space and time complexities in mind. You first fulfill the above-mentioned pre-requisites, then you proceed to design the algorithm, and finally, you test it by dry-running all the possible test cases. After this, you proceed to optimize the algorithm if there's a scope of improvisation. Storage space, computational time, running time, size of input data, and basic code conducts - everything should be optimized for an efficient algorithm!