Algorithm and Flow Chart

Algorithm

• An algorithm (pronounced AL-go-rith-um) is a procedure or formula for solving a problem, based on conducting a sequence of specified actions. A computer program can be viewed as an elaborate algorithm. In mathematics and computer science, an algorithm usually means a small procedure that solves a recurrent problem.
• In mathematics and computer science, an algorithm is a finite sequence of well-defined, computer-implementable instructions, typically to solve a class of problems or to perform a computation.
• An algorithm is a step procedure to solve logical and mathematical problems.
• In other words An algorithm is a set of instructions for solving a problem or accomplishing a task.
• The word Algorithm means “a process or set of rules to be followed in calculations or other problem-solving operations”. Therefore Algorithm refers to a set of rules/instructions that step-by-step define how a work is to be executed upon in order to get the expected results
• Ex: A recipe is a good example of an algorithm because it says what must be done, step by step. It takes inputs (ingredients) and produces an output (the completed dish)

​

Steps involved in algorithm development

• An algorithm can be defined as “a complete, unambiguous, finite number of logical steps for solving a specific problem “
• Step1. Identification of input: For an algorithm, there are quantities to be supplied called input and these are fed externally. The input is to be indentified first for any specified problem.
• Step2: Identification of output: From an algorithm, at least one quantity is produced, called for any specified problem.
• Step3 : Identification the processing operations : All the calculations to be performed in order to lead to output from the input are to be identified in an orderly manner.
• Step4 : Processing Definiteness : The instructions composing the algorithm must be clear and there should not be any ambiguity in them.
• Step5 : Processing Finiteness : If we go through the algorithm, then for all cases, the algorithm should terminate after a finite number of steps.
• Step6 : Possessing Effectiveness : The instructions in the algorithm must be sufficiently basic and in practice they can be carries out easily.

Characteristics of Algo

• Clear and Unambiguous: Algorithm should be clear and unambiguous. Each of its steps should be clear in all aspects and must lead to only one meaning.
• Well-Defined Inputs: If an algorithm says to take inputs, it should be well-defined inputs.
• Well-Defined Outputs: The algorithm must clearly define what output will be yielded and it should be well-defined as well.
• Finite-ness: The algorithm must be finite, i.e. it should not end up in an infinite loops or similar.
• Feasible: The algorithm must be simple, generic and practical, such that it can be executed upon will the available resources. It must not contain some future technology, or anything.
• Language Independent: The Algorithm designed must be language-independent, i.e. it must be just plain instructions that can be implemented in any language, and yet the output will be same, as expected.
• �

Merits and De-merits

• Advantages of Algorithms:
• It is easy to understand.
• Algorithm is a step-wise representation of a solution to a given problem.
• In Algorithm the problem is broken down into smaller pieces or steps hence, it is easier for the programmer to convert it into an actual program.
• Disadvantages of Algorithms:
• Writing an algorithm takes a long time so it is time-consuming.
• Branching and Looping statements are difficult to show in Algorithms.

​

How to Design an Algorithm?

• In order to write an algorithm, following things are needed as a pre-requisite: � 
• The problem that is to be solved by this algorithm.
• The constraints of the problem that must be considered while solving the problem.
• The input to be taken to solve the problem.
• The output to be expected when the problem the is solved.
• The solution to this problem, in the given constraints.

Ex: add three numbers and print the sum.�

• Step 1: Fulfilling the pre-requisites �As discussed above, in order to write an algorithm, its pre-requisites must be fulfilled. 
• The problem that is to be solved by this algorithm: Add 3 numbers and print their sum.
• The constraints of the problem that must be considered while solving the problem: The numbers must contain only digits and no other characters.
• The input to be taken to solve the problem: The three numbers to be added.
• The output to be expected when the problem the is solved: The sum of the three numbers taken as the input.
• The solution to this problem, in the given constraints: The solution consists of adding the 3 numbers. It can be done with the help of ‘+’ operator, or bit-wise, or any other method.
• Step 2: Designing the algorithm�Now let’s design the algorithm with the help of above pre-requisites:�Algorithm to add 3 numbers and print their sum: 
• START
• Declare 3 integer variables num1, num2 and num3.
• Take the three numbers, to be added, as inputs in variables num1, num2, and num3 respectively.
• Declare an integer variable sum to store the resultant sum of the 3 numbers.
• Add the 3 numbers and store the result in the variable sum.
• Print the value of variable sum
• END
• Step 3: Testing the algorithm by implementing it.�In order to test the algorithm, let’s implement it in C language.

​

​

Analysis

• Priori Analysis: “Priori” means “before”. Hence Priori analysis means checking the algorithm before its implementation. In this, the algorithm is checked when it is written in the form of theoretical steps. This Efficiency of an algorithm is measured by assuming that all other factors, for example, processor speed, are constant and have no effect on the implementation. This is done usually by the algorithm designer. It is in this method, that the Algorithm Complexity is determined.
• Posterior Analysis: “Posterior” means “after”. Hence Posterior analysis means checking the algorithm after its implementation. In this, the algorithm is checked by implementing it in any programming language and executing it. This analysis helps to get the actual and real analysis report about correctness, space required, time consumed etc.
• Time Factor: Time is measured by counting the number of key operations such as comparisons in the sorting algorithm.
• Space Factor: Space is measured by counting the maximum memory space required by the algorithm.�

Analysis of Algorithms to find best

• The analysis of algorithm is to compare the various algorithms to solve a same problem. This is done to analyze which algorithm takes less resources such as time, effort and memory to solve a particular problem.
• To analyze a particular algorithm, we need to understand for which input the algorithm takes less time and for which input it takes more time. Based on this, we divide the inputs in three cases:
• Best Case: In which we analyze the performance of an algorithm for the input, for which the algorithm takes less time or space.
• Worst Case: In which we analyze the performance of an algorithm for the input, for which the algorithm takes long time or space.
• Average Case: In which we analyze the performance of an algorithm for the input, for which the algorithm takes time or space that lies between best and worst case.

​

Complexity of an algorithm.

• Hence let us look over them in detail:
• Space Complexity: 
• It is also known as memory requirement. The space complexity of an algorithm is the amount of memory it needs to run to completion. We would usually want our algorithm to take the least possible memory for operation, however in more powerful machines more resources are usually allocated for the operation in order to reduce the time taken.
• Space Complexity: Space complexity of an algorithm refers to the amount of memory that this algorithm requires to execute and get the result. This can be for inputs, temporary operations, or outputs.�How to calculate Space Complexity?�The space complexity of an algorithm is calculated by determining following 2 components: 
• Fixed Part: This refers to the space that is definitely required by the algorithm. For example, input variables, output variables, program size, etc.
• Variable Part: This refers to the space that can be different based on the implementation of the algorithm. For example, temporary variables, dynamic memory allocation, recursion stack space, etc.
• Time Complexity:
•  It is also known as performance requirement. Time Complexity is calculated of referred in instances when we may be interested to know in advance whether the program will provide a satisfactory real time response or not. There may be several possible solutions to a problem with different time requirements or with different time complexity. Time complexity is heavily taken care of in cases when an algorithm needs to be modeled to be run on even the least powerful machines.
• Time Complexity: Time complexity of an algorithm refers to the amount of time that this algorithm requires to execute and get the result. This can be for normal operations, conditional if-else statements, loop statements, etc.�How to calculate Time Complexity?�The time complexity of an algorithm is also calculated by determining following 2 components: 
• Constant time part: Any instruction that is executed just once comes in this part. For example, input, output, if-else, switch, etc.
• Variable Time Part: Any instruction that is executed more than once, say n times, comes in this part. For example, loops, recursion, etc.

​

Time-Space Trade-Off in Algorithms

•  A tradeoff is a situation where one thing increases and another thing decreases. It is a way to solve a problem in:
• Either in less time and by using more space, or
• In very little space by spending a long amount of time.
• The best Algorithm is that which helps to solve a problem that requires less space in memory and also takes less time to generate the output. But in general, it is not always possible to achieve both of these conditions at the same time. The most common condition is an algorithm using a lookup table. This means that the answers to some questions for every possible value can be written down. One way of solving this problem is to write down the entire lookup table, which will let you find answers very quickly but will use a lot of space. Another way is to calculate the answers without writing down anything, which uses very little space, but might take a long time. Therefore, the more time-efficient algorithms you have, that would be less space-efficient.

​

Types of Space-Time Trade-off

• Compressed or Uncompressed data
• Re Rendering or Stored images
• Smaller code or loop unrolling
• Lookup tables or Recalculation
• Compressed or Uncompressed data: A space-time trade-off can be applied to the problem of data storage. If data stored is uncompressed, it takes more space but less time. But if the data is stored compressed, it takes less space but more time to run the decompression algorithm. There are many instances where it is possible to directly work with compressed data. In that case of compressed bitmap indices, where it is faster to work with compression than without compression.
• Re-Rendering or Stored images: In this case, storing only the source and rendering it as an image would take more space but less time i.e., storing an image in the cache is faster than re-rendering but requires more space in memory.
• Smaller code or Loop Unrolling: Smaller code occupies less space in memory but it requires high computation time that is required for jumping back to the beginning of the loop at the end of each iteration. Loop unrolling can optimize execution speed at the cost of increased binary size. It occupies more space in memory but requires less computation time.
• Lookup tables or Recalculation: In a lookup table, an implementation can include the entire table which reduces computing time but increases the amount of memory needed. It can recalculate i.e., compute table entries as needed, increasing computing time but reducing memory requirements.

Space complexity

• Algo1_exchange (a, b)
• Step 1: tmp = a
• Step 2: a = b
• Step 3: b = tmp

​

• Algo2_exchange (a, b)
• Step 1: a = a + b
• Step 2: b = a - b
• Step 3: a = a - b

Space complexity

• Algo1_exchange (a, b)
• Step 1: tmp = a
• Step 2: a = b
• Step 3: b = tmp

​

• Algo2_exchange (a, b)
• Step 1: a = a + b
• Step 2: b = a - b
• Step 3: a = a - b

Time complexity

• Algo_add (a,b)
• Step 1. C = a + b;
• Step 2. return C;

​

• Algo_addeven (n)
• Step 1. i = 2;
• Step 2. sum = 0;
• Step 3. while i <= 2*n
• Step 4. sum = sum + i
• Step 5. i = i + 2;
• Step 6. end while;
• Step 7. return sum;

Types of Data Structure Asymptotic Notation

• Asymptotic Notations are the expressions that are used to represent the complexity of an algorithm.
• Big-O Notation (Ο) – Big O notation specifically describes worst case scenario.

​

2. Omega Notation (Ω) – Omega(Ω) notation specifically describes best case scenario.

​

• Theta Notation (θ) – This notation represents the average complexity of an algorithm.