Algorithm Design Techniques

1. Divide and Conquer Approach:

 Divide the original problem into a set of 7. Randomized Algorithm:
sub problems.
 Solve every sub problem individually, - A randomized algorithm uses a
recursively.
random number at least once during
 Combine the solution of the sub problems the computation make a decision.
(top level) into a solution of the whole
original problem.
Asymptotic notation:
2. Greedy Technique: - Means approaching a value or curve
arbitrarily closely (i.e., as some sort
 Greedy Algorithm always makes the of limit is taken).
choice (greedy criteria) looks best at the
moment, to optimize a given objective. - Used to write fastest and slowest
possible running time for an
 The greedy algorithm doesn't always
algorithm. These are also referred to
guarantee the optimal solution however it
as 'best case' and 'worst case'
generally produces a solution that is very
scenarios respectively.
close in value to the optimal.

3. Dynamic Programming: Asymptotic analysis

- It is a technique of representing
- Dynamic Programming is a bottom- limiting behavior. The methodology
up approach we solve all possible has the applications across science.
small problems and then combine It can be used to analyze the
them to obtain solutions for bigger performance of an algorithm for
problems. some large data set.

4. Branch and Bound: Asymptotic Notation Importance:

- a given subproblem, which cannot
1. They give simple characteristics of an
be bounded, has to be divided into at
algorithm's efficiency.
least two new restricted
subproblems. Branch and Bound
algorithm are methods for global 2. They allow the comparisons of the
optimization in non-convex performances of various algorithms.
problems.
1. Big-oh notation
5. Randomized Algorithms: (upperbound): Big-oh is the formal
method of expressing the upper bound
- A randomized algorithm is defined as of an algorithm's running time. It is the
an algorithm that is allowed to
access a source of independent, measure of the longest amount of
unbiased random bits, and it is then time. [f (n) = O (g (n))]
allowed to use these random bits to
influence its computation. 2. Omega () Notation (mean): The
function f (n) = Ω (g (n))
6. Backtracking Algorithm:

- Backtracking Algorithm tries each 3. Theta (θ) (lowerbound) : The

possibility until they find the right function f (n) = θ (g (n)) [read as "f is
one. It is a depth-first search of the the theta of g of n"]
set of possible solution. During the
search, if an alternative doesn't
work, then backtrack to the choice Typical Complexities of an
point, the place which presented Algorithm
different alternatives, and tries the 1. Constant Complexity: It imposes a
next alternative. complexity of O(1). It undergoes an
execution of a constant number of steps like
1, 5, 10, etc. for solving a given problem.
2. Logarithmic Complexity: It imposes a o Output: It results in at least one
complexity of O(log(N)). It undergoes the quantity.
execution of the order of log(N) steps. To o Definiteness: Each instruction should
perform operations on N elements, it often be clear and ambiguous.
takes the logarithmic base as 2. o Finiteness: An algorithm should
terminate after executing a finite
number of steps.
o Effectiveness: Every instruction
3. Linear Complexity:
should be fundamental to be carried out,
in principle, by a person using only pen
 It imposes a complexity of O(N). It and paper.
encompasses the same number of steps as o Feasible: It must be feasible enough to
that of the total number of elements to produce each instruction.
implement an operation on N elements. o Flexibility: It must be flexible enough
 It also imposes a run time of O(n*log(n)). to carry out desired changes with no
It undergoes the execution of the order efforts.
N*log(N) on N number of elements to o Efficient: The term efficiency is
solve the given problem. measured in terms of time and space
required by an algorithm to implement.
Thus, an algorithm must ensure that it
4. Quadratic Complexity: It imposes a
takes little time and less memory space
complexity of O(n2). For N input data size, meeting the acceptable limit of
it undergoes the order of N2 count of development time.
operations on N number of elements for o Independent: An algorithm must be
solving a given problem. language independent, which means
that it should mainly focus on the input
5. Cubic Complexity: It imposes a and the procedure required to derive
complexity of O(n3). For N input data size, the output instead of depending upon
it executes the order of N3 steps on N the language.
elements to solve a given problem.
Advantages of an Algorithm
6. Exponential Complexity: It imposes a
complexity of O(2n), O(N!), O(nk), …. For
o Effective Communication: Since it
N elements, it will execute the order of
is written in a natural language like
count of operations that is exponentially
English, it becomes easy to understand
dependable on the input data size.
the step-by-step delineation of a solution
to any particular problem.
o Easy Debugging: A well-designed
How to approximate the time taken algorithm facilitates easy debugging to
by the Algorithm? detect the logical errors that occurred
inside the program.
o Easy and Efficient Coding: An
1. Iterative Algorithm: In the iterative algorithm is nothing but a blueprint of a
program that helps develop a program.
approach, the function repeatedly runs until
o Independent of Programming
the condition is met or it fails. It involves Language: Since it is a language-
the looping construct. independent, it can be easily coded by
incorporating any high-level language.
2. Recursive Algorithm: In the recursive
approach, the function calls itself until the
Disadvantages of an Algorithm

condition is met. It integrates the branching

o Developing algorithms for complex
structure. problems would be time-consuming and
difficult to understand.
Characteristics of Algorithms o It is a challenging task to understand
complex logic through algorithms.

o Input: It should externally supply zero

or more quantities.
Pseudocode 2. To find an approach to solve the problem.

Pseudocode refers to an informal high-level 3. To improve the efficiency of existing

description of the operating principle of a techniques.
computer program or other algorithm. It uses
structural conventions of a standard 4. To understand the basic principles of
programming language intended for human designing the algorithms.
reading rather than the machine reading.
5. To compare the performance of the
Advantages of Pseudocode algorithm with respect to other techniques.

o Since it is similar to a programming 6.It is the best method of description without

language, it can be quickly transformed describing the implementation detail.
into the actual programming language
than a flowchart. 7. The Algorithm gives a clear description of
requirements and goal of the problem to the
o The layman can easily understand it.
designer.
o Easily modifiable as compared to the
flowcharts. 8. A good design can produce a good solution.
o Its implementation is beneficial for
structured, designed elements. 9. To understand the flow of the problem.
o It can easily detect an error before
transforming it into a code. 10. To measure the behavior (or performance)
of the methods in all cases (best cases, worst
Disadvantages of Pseudocode cases, average cases)

11. With the help of an algorithm, we can also

o Since it does not incorporate any
identify the resources (memory, input-output)
standardized style or format, it can vary
cycles required by the algorithm.
from one company to another.
o Error possibility is higher while
12. With the help of algorithm, we convert art
transforming into a code. into a science.
o It may require a tool for extracting out
the Pseudocode and facilitate drawing 13. To understand the principle of designing.
flowcharts.
o It does not depict the design. 14. We can measure and analyze the
complexity (time and space) of the problems
Analysis of algorithm concerning input size without implementing
and running it; it will reduce the cost of design.
The analysis is a process of estimating the
efficiency of an algorithm. There are two
fundamental parameters based on which we
can analysis the algorithm:

o Space Complexity: The space

complexity can be understood as the
amount of space required by an
algorithm to run to completion.

o Time Complexity: Time complexity is

a function of input size n that refers to
the amount of time needed by an
algorithm to run to completion.

Need of Algorithm

1. To understand the basic idea of the problem.