Analysis And Design of Algorithms

• Brute force: Brute force is a straightforward approach to solving

problems by systematically checking all possible solutions. While it
is often simple to implement, it can be inefficient for large problem
sizes due to its exhaustive nature.

Consider a password-cracking program that tries all possible

combinations of characters until it finds the correct password. This
program exhaustively searches through the entire space of
possible passwords until it finds the correct one.

Eg: Traveling Salesman Problem and Knapsack Problem

• Divide and Conquer: Divide and Conquer is a problem-solving
technique where a problem is divided into smaller subproblems
that are solved recursively. The solutions to the subproblems are
then combined to solve the original problem.

Divide and Rule: British in India

It is commonly used in other algorithms like Merge Sort and Quick

Sort.
• Decrease and Conquer: Decrease and Conquer is a problem-
solving technique where a problem is reduced to a simpler
instance of the same problem, which is then solved recursively.
The solution to the simpler instance is then used to solve the
original problem.

Consider a scenario where you have a dictionary of words sorted

in alphabetical order. To find the definition of a particular word,
you could use

Eg: Binary Search

• Transform and Conquer: Transform and Conquer is a problem-
solving technique where a problem is transformed into a different
form that is easier to solve. Once the transformed problem is
solved, the solution is converted back to the original problem's
solution.

Consider the problem of finding the shortest path between two

locations on a map. By transforming the map into a graph
representation and applying graph algorithms.

Eg: Matrix Multiplication

• Dynamic Programming: Dynamic Programming is a method for
solving complex problems by breaking them down into simpler
subproblems and solving each subproblem only once. The
solutions to subproblems are stored in a table and reused to solve
larger subproblems, which leads to improved efficiency.

Eg: Warshall’s and Floyd’s Algorithm

• Greedy Method: The Greedy Method is a problem-solving
technique where a solution is built piece by piece by selecting the
best possible choice at each step. It makes locally optimal choices
with the hope of finding a global optimum solution. However, it
may not always lead to the optimal solution.
Eg: Coin Change Problem

• Backtracking: Backtracking is a systematic way of generating all

possible solutions to a problem by building candidates
incrementally and abandoning a candidate as soon as it is
determined that it cannot lead to a valid solution. It is commonly
used in problems with constraints or conditions that must be
satisfied.
Eg: N-Queens Problem
INTRODUCTION: What is an Algorithm?, Fundamentals of
Algorithmic Problem Solving.

FUNDAMENTALS OF THE ANALYSIS OF ALGORITHM

EFFICIENCY: Analysis Framework, Asymptotic Notations and
Basic Efficiency Classes, Mathematical Analysis of Non recursive
Algorithms, Mathematical Analysis of Recursive Algorithms.

BRUTE FORCE APPROACHES: Selection Sort and Bubble Sort,

Sequential Search and Brute Force String Matching.
 Introduction to Algorithms
Why do you need to study algorithms?
 If we want to be a good computer professional, we should know how
to design the algorithms. So let us understand standard algorithms
and then learn how to design new algorithms to solve various
problems.
 Computer programs would not exist without algorithms.
 Another reason for studying algorithms is their usefulness in
developing analytical skills.
 An algorithm is defined as finite sequence of unambiguous
instructions followed to accomplish a given task.
Sequential Search
Binary Search
Bubble Sort
An algorithm is defined as finite sequence of unambiguous
instructions followed to accomplish a given task.
 What Is an Algorithm?
Definition - 1
An algorithm is a sequence of unambiguous instructions for solving a
problem, i.e., for obtaining a required output for any legitimate input in
a finite amount of time.

Figure : The notion of the algorithm.

You need to understand several important points:
1. The non-ambiguity requirement for each step of an algorithm
cannot be compromised.

2. The range of inputs for which an algorithm works has to be

specified carefully.

3. The same algorithm can be represented in several different ways.

4. There may exist several algorithms for solving the same problem.

5. Algorithms for the same problem can be based on very different

ideas and can solve the problem with dramatically different speeds.
What Is an Algorithm?
Definition - 2
An algorithm is a finite set of instructions that are followed to
accomplish a particular task.
In addition, all algorithms must satisfy the following criteria:
1. Input: Zero or more inputs are externally supplied.
2. Output: At least one output is produced.
3. Definiteness: Each instruction is clear and unambiguous.
4. Finiteness: If we trace out the instructions of an algorithm, then for
all cases, the algorithm terminates after a finite number of steps.
5. Effectiveness: Every instruction must be very basic so that it can be
carried out, it also must be feasible.
Important and active areas of study to design and
analysis of algorithms

There are four distinct areas of study:

1.How to devise algorithms

2.How to validate algorithms
3.How to analyze algorithms (time and space)
4.How to test a program (debugging, profiling)
Important and active areas of study to design and
analysis of algorithms

How to devise algorithms

 Creating an algorithm is an art which may never be fully automated.
 There are different techniques to design good algorithms.
How to validate algorithms
 Once an algorithm is devised, it is necessary to show that it
computes the correct answer for all possible legal inputs.
 This process is referred to as algorithm validation.
 Once the algorithm validation is completed, algorithm can be
converted into program.
How to analyze algorithms
 This field of study is called analysis of algorithms.
 Analysis of an algorithm is a task of determining how much
computing time and storage an algorithm requires.
 This is a challenging area which sometimes requires great
mathematical skills.
How to test a program
Testing a program consists of two phases:
1. Debugging
Debugging is the process of executing programs on sample data sets to determine
whether faulty results occur and, if so, to correct them.
2. Profiling
Profiling is the process of executing a correct program on data sets and measuring
the time and space it takes to compute the results.
Algorithm Specification
We can describe/specify algorithms in many ways:
1. Using natural language
2. Using pseudo code convention
3. Using flowcharts

Algorithm using natural language

 We can use natural language like English.
 Since we can clearly understand the English language, its easy to
specify algorithm.
Drawback: it has no imposed structure like pseudo code and flowcharts,
it may lead to ambiguity.
Example : find the greatest common divisor of two
nonnegative, not-both-zero integers m and n.
Euclid’s algorithm for computing gcd(m, n)
Step 1: If n = 0, return the value of m as the answer and stop;
otherwise, proceed to Step 2.
Step 2: Divide m by n and assign the value of the remainder to r.
Step 3: Assign the value of n to m and assign the value of r to n. Go to
Step 1.

Consecutive integer checking algorithm for computing gcd(m, n)

Step 1: Assign the value of min{m, n} to t.
Step 2: Divide m by t. If the remainder of this division is 0, go to Step
3; otherwise, go to Step 4.
Step 3: Divide n by t. If the remainder of this division is 0, return the
value of t as the answer and stop; otherwise, proceed to Step 4.
Step 4: Decrease the value of t by 1. Go to Step 2.
Algorithm using pseudo code convention
 Pseudo code is a mix of the natural language and mathematics
 Pseudo code represents an algorithm to solve a problem using
natural and mathematical notations.
Example:
 Consecutive Integer Checking (CIC) algorithm
for computing gcd(m,n)
//Computes gcd(m, n) by Consecutive Integer Checking algorithm
//Input: Two nonnegative, not-both-zero integers m and n
//Output: GCD of m and n
t  min(m,n)
while t > 0
rem  m % t
if rem == 0 then
rem  n % t
if rem == 0 then
return t
else
tt–1
end if
end while
end
Algorithm for generating consecutive primes for given integer n > 1
as input.
ALGORITHM Sieve(n)
//Implements the sieve algorithm
//Input: A positive integer n > 1
//Output: Array L of all prime numbers less than or equal to n
Consider the application of the above algorithm to finding the list of
primes not exceeding n = 25
Fundamentals of Algorithmic
Problem Solving

“We can consider algorithms to be procedural

solutions to problems. These solutions are not
answers to the problems, but specific
instructions for getting answers”.
Figure: Algorithm design and analysis process.
The sequence of steps involved in designing and analyzing an
algorithm:
1) Understanding the Problem
 The first thing you need to do before designing an
algorithm is to understand completely the problem given.
 An input to an algorithm specifies an instance of the
problem the algorithm solves.
 It is very important to specify exactly the set of instances
the algorithm needs to handle.
 If you fail to specify problem instance exactly, your algorithm
may work correctly for a majority of inputs but crash
on some “boundary” value.
 Remember that a correct algorithm is not one that works most
of the time, but one that works correctly for all legitimate inputs.

2) Decide on:
 Computational means,
 Exact vs. Approximate solving,
 Algorithm design technique.
Computational means
Once you completely understand a problem, you need to find out
the capabilities of the computational device that you are
using for running the algorithm.
Exact vs. Approximate solving
 The next important decision is to choose between solving the
problem exactly or solving it approximately.
 Why would one opt for an approximation algorithm?
First, there are important problems that simply cannot be solved
exactly for most of their instances; examples include extracting
square roots, solving nonlinear equations, and evaluating definite
integrals.
Second, available algorithms for solving a problem exactly can be
unacceptably slow because of the problem’s intrinsic complexity.
Algorithm design technique
An algorithm design technique (or “strategy” or “paradigm”) is a
general approach to solving problems algorithmically that is applicable
to a variety of problems from different areas of computing.
Designing an Algorithm and Data Structures
 After choosing algorithm design technique, one should pay close
attention to choosing data structures appropriate for the operations
performed by the algorithm.
 Example: selected data structure array for solving the problem of
finding consecutive prime numbers.
Algorithms + Data Structures = Programs
Next task is to specify the algorithm either using natural language or
pseudo code convention.
4) Proving an Algorithm’s Correctness
 Once an algorithm has been specified, you have to prove its
correctness.
 That is, you have to prove that the algorithm yields a required result
for every legitimate input in a finite amount of time.
 For example: the correctness of Euclid’s algorithm for gcd(m,n)
the simple observation that the second integer gets smaller on every
iteration of the algorithm, and the fact that the algorithm stops when
the second integer becomes 0.
 If incorrect, think about redesigning the algorithm or
choose different data structures and redesign.
5) Analysing an Algorithm
 After correctness, it’s time to analyse the algorithm for its efficiency.
 Time efficiency, indicating how fast the algorithm runs,
 Space efficiency, indicating how much memory it uses.
 Also check for other two desirable characteristics of an algorithm is
simplicity and generality.
 If you are not satisfied with the algorithm’s efficiency, simplicity, or
generality, you must return to the drawing board and redesign the
algorithm.
6) Coding an Algorithm
 Convert algorithms into computer programs.
 But unless the correctness of a computer program is proven with full
mathematical rigor, the program cannot be considered correct.
 Testing of computer programs is an art rather than a science.
“As a rule, a good algorithm is a result of repeated effort and
rework”.
The Analysis Framework
 General framework for analyzing the efficiency of algorithms

There are two kinds of efficiency:

 Time efficiency, also called time complexity, indicates how fast an
algorithm in runs.
 Space efficiency, also called space complexity, refers to the amount
of memory units required by the algorithm in addition to the space
needed for its input and output.
Efficiency of an algorithm depends on:
- Space Efficiency
- Time Efficiency

Space Efficiency of an algorithm depends on:

- Program Space
- Data Space
- Stack Space
Time Efficiency of an algorithm depends on:
- Speed of computer
- Choice of Programming Language
- Compiler used
- Choice of the algorithm *
- Number (size) of inputs/outputs *
Measuring an Input’s Size
 The obvious observation is that almost all algorithms run longer on
larger inputs.
For example, it takes longer to sort larger arrays, multiply larger
matrices, and so on.
 Therefore, it is logical to investigate an algorithm’s efficiency as a
function of some parameter n indicating the algorithm’s input size.

For example, how should we measure an input’s size for a spell-

checking algorithm? If the algorithm examines individual
characters of its input, we should measure the size by the number of
characters; if it works by processing words, we should count
number of words in the input.
 For example, measuring input size for algorithms solving problems
such as checking primality of a positive integer n. Here, the input is
just one number.
 In such situations, it is preferable to measure input size by the
number b of bits in the n’s binary representation:

Units for Measuring Running Time

 We can simply use some standard unit of time measurement a
second, or mili second, or nano second.
 Measuring the running time of a program depends on the speed of a
particular computer, depends on the quality of a program
implementing the algorithm and depends on the speed of the
compiler used in generating the machine code.
 The first thing to do is to identify the most important operation of
the algorithm, called the basic operation, the operation
contributing the most to the total running time, and compute the
number of times the basic operation is executed.
 Basic operation is the statement that executes maximum number of
times in a function. The number of times basic operation is executed
depends of size of the input.
 For example, most sorting algorithms work by comparing
elements (keys) of a list being sorted with each other; for such
algorithms, the basic operation is a key comparison.
 Time efficiency of an algorithm is analyzed by determining the
number of times the basic operation is executed on inputs of size n.

 Let cop be the execution time of an algorithm’s basic operation on a

particular computer
 Let C(n) be the number of times this operation needs to be executed
for this algorithm.
 Then we can estimate the running time T(n) of a program
implementing this algorithm on that computer by the formula:

 Note: The count C(n) does not contain any information about
operations that are not basic, and, in fact, the count itself is often
computed only approximately.
Order of Growth:
We expect the algorithms to work faster for all values of n. Some
algorithms execute faster for small values of n. But, as the value
of n increases, they tend to be very slow. So, the behaviour of
some algorithm changes with increase in value of n. This change
in behaviour of the algorithm and its efficiency can be analysed
by considering the highest order of n. The order of growth is
normally determined for larger values of n.

If the order of growth of one algorithm is linear and the order of

growth of second algorithm to solve the same problem is
quadratic, then it clearly means that running time of first
algorithm is less and it is more efficient. So, while analysing the
time efficiency of an algorithm, the order of growth of n is
important.
 We can ask a question that, how much longer will the algorithm run
if we double its input size?
 Assuming that C(n) = for problem size n.

 Algorithm will run 4 times longer when input size doubled.

 From the above equation we can observe that cop is neatly cancelled
out in the ratio.
 Also note that 1/2 , the multiplicative constant in the formula for the
count C(n), was also cancelled out.
 This is a reason that the efficiency analysis framework ignores
multiplicative constants and concentrates on the count’s order of
growth to within a constant multiple for large-size inputs.
Orders of Growth
 A difference in running times on small inputs is not really
distinguishes efficient algorithms from inefficient ones.
 For large values of n, it is the function’s order of growth that counts:
observe the table given below, which contains values of a few
functions particularly important for analysis of algorithms.
 The function growing the slowest among these is the logarithmic
function.
 It grows so slowly, in fact, that we should expect a program
implementing an algorithm with a logarithmic basic-operation count
to run practically instantaneously on inputs of all realistic sizes.
 On the other end the exponential function 2n and the factorial
function n! both these functions grow so fast that their values
become astronomically large even for rather small values of n.

“Algorithms that require an exponential number of operations are

practical for solving only problems of very small sizes”.

1 < log n < n < n log n < n2 < n3 < 2n < n!

Worst-Case, Best-Case, and Average-Case Efficiencies
 There are many algorithms for which running time depends not only
on an input size but also on the specifics of a particular input.
 In such cases it is required to express algorithm’s efficiency as
worst-case, best-case and average case.
 Consider sequential search as an example,
 Algorithm searches for a given item (some search key K) in a list of
n elements by checking successive elements of the list until either a
match with the search key is found or the list is exhausted.
 Assuming that the second condition A[i] != K will not be checked if
the first condition i < n fails(which checks that the array’s index does
not exceed its upper bound).
 A list is implemented as an array.
Worst-Case, Best-Case, and Average-Case Efficiencies
Worst-Case, Best-Case, and Average-Case Efficiencies
Analysis:
 In the worst case, when there are no matching elements in the list or
the first matching element happens to be the last one on the list, the
algorithm makes the largest number of key comparisons among all
possible inputs of size n:
Cworst(n) = n

 The best-case efficiency of an algorithm is its efficiency for input of

size n, which is an input (or inputs) of size n for which the algorithm
runs the fastest among all possible inputs of that size.
 Means smallest number of key comparisons among all possible
inputs of size n
Worst-Case, Best-Case, and Average-Case Efficiencies
For example, the best-case inputs for sequential search are lists of size
n with their first element equal to a search key;
Cbest(n) = 1
Average-case efficiency
 To analyze the algorithm’s average-case efficiency, we must make
some assumptions about possible inputs of size n.
1. The probability of a successful search is equal to p (0 ≤ p ≤ 1)
2. The probability of the first match occurring in the ith position of the
list is the same for every i.
 In the case of a successful search, the probability of the first match
occurring in the ith position of the list is p/n for every i, and the
number of comparisons made by the algorithm in such a situation is
obviously i.
Worst-Case, Best-Case, and Average-Case Efficiencies
 In the case of an unsuccessful search, the number of comparisons
will be n with the probability of such a search being (1 − p).
Therefore,

 if p = 1 (the search must be successful), the average number of key

comparisons made by sequential search is (n + 1)/2;
 If p = 0 (the search must be unsuccessful), the average number of
key comparisons will be n because the algorithm will inspect all n
elements on all such inputs.
Summary
1. Time efficiency is measured by counting the number of times the
algorithm’s basic operation is executed.
2. Space efficiency is measured by counting the number of extra
memory units consumed by the algorithm.
3. The efficiencies of some algorithms may differ significantly for
inputs of the same size.
4. For such algorithms, we need to distinguish between the worst-case,
average-case, and best-case efficiencies.
5. The framework’s primary interest lies in the order of growth of the
algorithm’s running time (extra memory units consumed) as its
input size goes to infinity.