Unit Eleven

Algorithms
Introduction
• Algorithm is a step-by-step procedure, which defines a set of instructions to be
executed in a certain order to get the desired output. Algorithms are generally
created independent of underlying languages, i.e. an algorithm can be
implemented in more than one programming language.
• From the data structure point of view, following are some important categories of
algorithms −
• Search − Algorithm to search an item in a data structure.
• Sort − Algorithm to sort items in a certain order.
• Insert − Algorithm to insert item in a data structure.
• Update − Algorithm to update an existing item in a data structure.
• Delete − Algorithm to delete an existing item from a data structure.
Characteristics of an Algorithm
Not all procedures can be called an algorithm. An algorithm should have the following
characteristics −
• Unambiguous − Algorithm should be clear and unambiguous. Each of its steps (or phases),
and their inputs/outputs should be clear and must lead to only one meaning.
• Input − An algorithm should have 0 or more well-defined inputs.
• Output − An algorithm should have 1 or more well-defined outputs, and should match the
desired output.
• Finiteness − Algorithms must terminate after a finite number of steps.
• Feasibility − Should be feasible with the available resources.
• Independent − An algorithm should have step-by-step directions, which should be
independent of any programming code.
Analysis of an Algorithm
For a standard algorithm to be good, it must be efficient. Hence the efficiency of an algorithm
must be checked and maintained. It can be in two stages:
1. 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. This analysis is independent of the type of hardware
and language of the compiler. It gives the approximate answers for the complexity of the
program.
2. 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(for every possible input/s if it shows/returns correct output or not), space
required, time consumed, etc. That is, it is dependent on the language of the compiler and the
type of hardware used.
Complexity of an Algorithm
• An algorithm is defined as complex based on the amount of Space and Time it consumes.
Hence the Complexity of an algorithm refers to the measure of the time that it will need to
execute and get the expected output, and the Space it will need to store all the data (input,
temporary data, and output). Hence these two factors define the efficiency of an algorithm.
The two factors of Algorithm Complexity are:
• 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 to run/execute.
Therefore the complexity of an algorithm can be divided into two types:
1. Time Complexity
2. Space Complexity
1. Time Complexity
The time complexity of an algorithm refers to the amount of time required by the algorithm 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 the following 2
components:
Constant time part: Any instruction that is executed just once comes in this part. For example,
input, output, if-else, switch, arithmetic operations, etc.
Variable Time Part: Any instruction that is executed more than once, say n times, comes in this
part. For example, loops, recursion, etc.
Therefore Time complexity T(P) of any algorithm P is T(P) = C + TP(I), where C is the
constant time part and TP(I) is the variable part of the algorithm, which depends on the
instance characteristic I.
Determined in terms of 3 types of time:
1. Worst-case running time: The worst-case running time of an algorithm is an upper bound
on the running time for any input.
Therefore, having the knowledge of worst-case running time gives us an assurance that the
algorithm will never go beyond this time limit.
2. Average-case running time: The average-case running time of an algorithm is an estimate
of the running time for an `average' input.
It specifies the expected behaviour of the algorithm when the input is randomly drawn
from a given distribution. Average-case running time assumes that all inputs of a given size
are equally likely.
3. Best-case running time: The term 'best-case performance' is used to analyse an algorithm
under optimal conditions.
For example, the best case for a simple linear search on an array occurs when the desired
element is the first in the list.
=>It is always recommended to improve the average performance and the worst-case
performance of an algorithm.
2. Space Complexity
The space complexity of an algorithm refers to the amount of memory required by the
algorithm to store the variables 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 the following 2
components:
Fixed Part: This refers to the space that is 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.
Therefore Space complexity S(P) of any algorithm P is S(P) = C + SP(I), where C is the fixed
part and S(I) is the variable part of the algorithm, which depends on instance characteristic I.
Deterministic and Non Deterministic Algorithms
• A deterministic algorithm is a type of algorithm in which the result of every algorithm is
uniquely defined. Hence, a deterministic algorithm performs fixed number of steps and
always get finished with accept or reject state with the same result. The target machine
executes the same instruction and gives the same results that does not depend upon the way
or process in which the instruction gets executed.
• Deterministic algorithms can solve a problem in polynomial time. A deterministic algorithm
always has a single outcome, i.e. the input given to it always results the same output. A
mathematical function is a common example of the deterministic algorithm.
• A non-deterministic algorithm is one in which the output of every algorithm is not uniquely
defined and thus the result could be random. Hence, the non-deterministic algorithms have
multiple outcomes.
• Non-deterministic algorithms take multiple execution paths, thus it is quite difficult to
determine the next state of the machine. Unlike deterministic algorithms, a non-deterministic
algorithm cannot solve problems in polynomial time. Random functions are examples of
nondeterministic algorithms.
Assignment
Write down the differences between Deterministic and Non Deterministic Algorithm.
Asymptotic Notations
• Asymptotic notations are the mathematical notations used to describe the running time of an
algorithm when the input tends towards a particular value or a limiting value.
• For example: In bubble sort, when the input array is already sorted, the time taken by the
algorithm is linear i.e. the best case.
• But, when the input array is in reverse condition, the algorithm takes the maximum time
(quadratic) to sort the elements i.e. the worst case.
• When the input array is neither sorted nor in reverse order, then it takes average time. These
durations are denoted using asymptotic notations.
• There are mainly three asymptotic notations:
• Big-O notation
• Omega notation
• Theta notation
Big-O Notation (O-notation)
• Big-O notation represents the upper bound of the running time of an algorithm. Thus, it gives
the worst-case complexity of an algorithm.
Omega Notation (Ω-notation)
• Omega notation represents the lower bound of the running time of an algorithm. Thus, it
provides the best case complexity of an algorithm.
Theta Notation (Θ-notation)
• Theta notation encloses the function from above and below. Since it represents the upper and
the lower bound of the running time of an algorithm, it is used for analyzing the average-
case complexity of an algorithm.
Series and Parallel Algorithm

● Depending on the architecture of computers, we have two types of algorithms −

○ Sequential Algorithm − An algorithm in which some consecutive steps of instructions
are executed in a chronological order to solve a problem.
○ Parallel Algorithm − The problem is divided into sub-problems and are executed in
parallel to get individual outputs. Later on, these individual outputs are combined
together to get the final desired output.
● It is not easy to divide a large problem into sub-problems. Sub-problems may have data
dependency among them. Therefore, the processors have to communicate with each other
to solve the problem.
● It has been found that the time needed by the processors in communicating with each other
is more than the actual processing time. So, while designing a parallel algorithm, proper
CPU utilization should be considered to get an efficient algorithm.
Approximation Algorithm

● An approximation algorithm is a way of dealing with NP-completeness for an optimization

problem. This technique does not guarantee the best solution.
● The goal of the approximation algorithm is to come as close as possible to the optimal
solution in polynomial time.
● Such algorithms are called approximation algorithms or heuristic algorithms.

Features of Approximation Algorithm :

● An approximation algorithm guarantees to run in polynomial time though it does not
guarantee the most effective solution.
● An approximation algorithm guarantees to seek out high accuracy and top quality
solution(say within 1% of optimum)
● Approximation algorithms are used to get an answer near the (optimal) solution of an
optimization problem in polynomial time.
Heuristic Algorithm

● A heuristic algorithm is one that is designed to solve a problem in a faster and more
efficient fashion than traditional methods by sacrificing optimality, accuracy, precision, or
completeness for speed.
● Heuristic algorithms often times used to solve NP-complete problems, a class of decision
problems.
● In these problems, there is no known efficient way to find a solution quickly and accurately
although solutions can be verified when given.
● Heuristics can produce a solution individually or be used to provide a good baseline and
are supplemented with optimization algorithms.
● Heuristic algorithms are most often employed when approximate solutions are sufficient
and exact solutions are necessarily computationally expensive.
Algorithm Design

● A given problem can be solved in various different approaches and some approaches
deliver much more efficient results than others.
● Algorithm analysis is a technique used to measure the effectiveness and performance of the
algorithms.
● It helps to determine the quality of an algorithm based on several parameters such as user-
friendliness, maintainability, security, space usage and usage of other resources.
● Selecting a proper algorithm design is critical for the performance & success of the
application.
● Some of the algorithm designs are:
1. Brute-Force Or Exhaustive Search
2. Divide And Conquer
3. Greedy Algorithms
4. Dynamic Programming
5. Branch And Bound Algorithm
6. Randomized Algorithm
7. Backtracking
Brute-Force or Exhaustive Search

● Brute Force algorithm is a typical problem-solving technique where the possible solution
for a problem is uncovered by checking each answer one by one, by determining whether
the result satisfies the statement of a problem or not.
● It is used when the problem size is limited since its various tries are equally proportional to
a solution's candidates.
● In Computer Science, Brute Force is a trial and error methodology, which is used by
attackers to break into any website's data or systems.
● They try to steal information by generating every possible combination of the password-
protected information.
● Brute Force relies on the computational power of the machine to try every possible
combination to achieve the target.
Example: Finding optimal Visit sequence of factories for a businessman.
Greeding Algorithm

● As the name implies, this is a simple approach which tries to find the best solution at every
step.
● Thus, it aims to find the local optimal solution at every step so as to find the global optimal
solution for the entire problem.
● Consider that there is an objective function that has to be optimized (maximized/
minimized).
● This approach makes greedy choices at each step and makes sure that the objective
function is optimized.
● The greedy algorithm has only one chance to compute the optimal solution and thus,
cannot go back and look at other alternate solutions.
● However, in many problems, this strategy fails to produce a global optimal solution.
● Let's consider the following binary tree to understand how a basic greedy algorithm
To find the path with largest sum. Since we need to maximize the objective function, Greedy
approach can be used.
Following steps are followed to find the solution:
Step 1: Initialize sum = 0
Step 2: Select the root node, so its value will be added to sum, sum = 0+8 = 8
Step 3: The algorithm compares nodes at next level, selects the largest node which is 12,
making the sum = 20.
Step 4: The algorithm compares nodes at the next level, selects the largest node which is 10,
making the sum = 30.
Thus, using the greedy algorithm, we get 8-12-10 as the path. But this is not the optimal
solution, since the path 8-2-89 has the largest sum i.e. 99. This happens because the algorithm
makes decision based on the information available at each step without considering the overall
problem.