...

An algorithm is composed of a finite set of

Design and Analysis of
•
steps, each of which may require one or
Algorithm more operations.
• The possibility of a computer carrying out
these operations necessitates that certain
constraints be placed on the type of
Dr. Yatendra Sahu operations an algorithm can include.
• Concept of algorithm is fundamental to
computer science.

Algorithm Specification
Classroom Etiquette
• An algorithm is a finite sequence of instructions
that if followed, accomplishes a particular task.
• Criteria for algorithm
• No pagers and cell phones – switch off in a. Input – there are zero or more quantities that are
classroom. externally supplied.
b. Output – at least one quantity is produced.
• Latecomers should enter QUIETLY. c. Definiteness – each instruction is clear and
unambiguous.
d. Finiteness – for all cases, algorithm terminates after a
• No loud talking during lectures. finite number of steps.
e. Effectiveness – every instruction must be basis
enough to be carried out. (feasible)
• But please ask questions and provide feedback. • Algorithm and program
a. program doesn’t need to satisfy finiteness.

WHAT IS AN ALGORITHM?
• The word algorithm comes from the name of a • In computational theory, we distinguish between an
Persian author, Abu Ja'far Mohammed ibn Musa algorithm and a program.
al Khowarizmi (c. 825 A.D.), who wrote a – Program does not have to satisfy the finiteness condition.
– For example, we can think of an operating system that
textbook on mathematics. continues in a "wait" loop until more jobs are entered.
• This word has taken on a special significance in – Such a program does not terminate unless the system
computer science, where "algorithm" has come crashes.
– Since our programs always terminate, we use
to refer to a method that can be used by a "algorithm" and "program" interchangeably in this text.
computer for the solution of a problem. • We can describe an algorithm in many ways.
• This is what makes algorithm different from – Graphic representations called flowcharts are another
possibility, but they work well only if the algorithm is
words such as process, technique, or method. small and simple.
 ...

The Study of Algorithms includes many important and

active areas of research.
• How to device algorithm: Artistic work, by
using various designs techniques device new
and useful algorithms.
• How to validate algorithm: correctness of
output for all possible legal input.
• How to analyse algorithm: space complexity
and time complexity.
• How to test a program: after coding,
• perform debugging (determining faulty result
occur, if so, correct them) and
• profiling (performance measurement using space
and time requirement.

Classification of algorithms

Implementation Method Design Method Other Classifications

1. Recursion or
Iteration 1. Divide and 1. Classification by
Conquer Research Area
2. Procedural or
Declarative 2. Greedy Method 2. Classification by
(non- 3. Dynamic Complexity
Procedural) Programming
3. Serial or Parallel 4. Linear 3. Branch and Bound
or Distributed Programming & Backtracking
4. Deterministic or 5. Transform and 4. Randomized
Non- Conquer
Deterministic Algorithms

5. Exact or
Approximate
 ...

Recursion or Iteration
Deterministic or Non-Deterministic
• A recursive algorithm is one that calls itself • Deterministic Algorithms:
repeatedly until a base condition is satisfied. • Produce the same output for a given input every time they are
• It is a common method used in functional executed.
programming languages like C,C++, etc. • Follow a predictable path and have defined behavior at every
step.
• Iterative algorithms use constructs like loops and • Examples include binary search, quicksort, and Shortest path
sometimes other data structures like stacks and Dijkstra's algorithm.
queues to solve the problems. • Non-Deterministic Algorithms:
• Some problems are suited for recursive and others • May produce different outputs for the same input depending on
are suited for iterative. internal choices or randomness.
• Can explore multiple paths simultaneously or randomly choose
• For example, the Towers of Hanoi problem can be paths.
easily understood in recursive implementation. • Used in theoretical computer science to describe problems in
• Every recursive version has an iterative version, and complexity classes like NP (Non-deterministic Polynomial time).
vice versa. • Examples include non-deterministic Turing machines and
randomized algorithms.

Procedural or Declarative (non-Procedural Exact or Approximate

• In declarative programming languages, we say what • As we have seen, for many problems we are not able
we want without having to say how to do it. to find the optimal solutions.
• With procedural programming, we have to specify the • That means, the algorithms for which we are able to
exact steps to get the result. find the optimal solutions are called exact algorithms.
• Examples of procedural languages include: C, PHP, • In computer science, if we do not have the optimal
and PERL. solution, we give approximation algorithms.
• For example, SQL is more declarative than • Approximation algorithms are generally associated
procedural, because the queries don't specify the with NP-hard problems.
steps to produce the result.

Serial or Parallel or Distributed Divide and Conquer

• In general, while discussing the algorithms we assume • The D & C strategy solves a problem by:
that computers execute one instruction at a time.
• These are called serial algorithms. 1) Divide: Breaking the problem into sub problems that
•
• Parallel algorithms take advantage of computer are themselves smaller instances of the same type of
architectures to process several instructions at a time. problem
• They divide the problem into sub problems and • 2) Recursion: Recursively solving these sub problems.
serve them to several processors or threads.
• 3) Conquer: Appropriately combining their answers.
• Iterative algorithms are generally parallelizable.
• If the parallel algorithms are distributed on to different
machines then we call such algorithms distributed • Examples: merge sort and binary search algorithms.
algorithms.
 ...

Greedy Method Reduction [Transform and Conquer]

• Greedy algorithms work in stages. • In this method we solve a difficult problem by

• In each stage, a decision is made that is good at that transforming it into a known problem for which we
point, without bothering about the future have asymptotically optimal algorithms.
consequences. • Transform and Conquer is a fundamental algorithmic
• Generally, this means that some local best is chosen. paradigm that involves transforming a problem into a
simpler or different version that is easier to solve.
• It assumes that the local best selection also makes for
the global optimal solution. • This paradigm is widely used in various algorithmic
strategies, including reduction, where a problem is
reduced to another problem for which a solution is
already known.

Dynamic Programming
Classification by Area
• Dynamic programming (DP) and memoization work
together.
• The difference between DP and divide and conquer is • In computer science each field has its own problems
that in the case of the latter there is no dependency and needs efficient algorithms.
among the sab problems, whereas in DP there will be • Examples:
an overlap of sub-problems. • search algorithms, sorting algorithms, merge
• By using memoization [maintaining a table for already algorithms,
solved sub problems), DP reduces the exponential • numerical algorithms, graph algorithms, string
complexity to polynomial complexity (O(m²), (m³), etc.) algorithms,
for many problems. • geometric algorithms, combinatorial algorithms,
• machine learning, cryptography,
• The difference between dynamic programming and
• parallel algorithms,
recursion is in the memoization of recursive calls.
• data compression algorithms, parsing techniques,
• When sub problems are independent and if there is no and more
repetition, memoization does not help, hence dynamic
programming is not a solution for all problems.

Linear Programming Classification by Complexity

• In linear programming, there are inequalities in terms • In this classification, algorithms are classified by the
of inputs and maximizing (or minimizing) some linear time they take to find a solution based on their input
function of the inputs. size.
• Many problems (example: maximum flow for directed • Some algorithms take linear time complexity (O(n))
graphs) can be discussed using linear programming, and others take exponential time, and some never
halt.
• Note that some problems may have multiple
algorithms with different complexities.
 ...

Branch and Bound and Backtracking

• These were used in Artificial Intelligence.
• Branch and Bound is an algorithm design paradigm for discrete
and combinatorial optimization problems.
• It systematically enumerates candidate solutions by means of
a state space search tree.
• The goal is to find the optimal solution by pruning branches
of the tree that cannot yield better solutions than already
known ones.
• Backtracking is a general algorithm for finding all (or some)
solutions to some computational problems, particularly constraint
satisfaction problems.
• It incrementally builds candidates to the solutions, and
abandons a candidate ("backtracks") as soon as it
determines that the candidate cannot possibly be completed
to a valid solution.

Randomized Algorithms

• A few algorithms make choices randomly. For some

problems, the fastest solutions must involve
• randomness. Example: Quick Sort.