ALGORITHMIC PROBLEM SOLVING
Definition
“Algorithmic-problem solving”; this
means solving problems that require the
formulation of an algorithm for their solution.
The formulation of algorithms has always
been an important element of problem-
solving .
An algorithm is a plan for solving a
problem.
Different ways in which algorithm solves Problem
A computer is a tool that can be used to implement
a plan for solving a problem.
A computer program is a set of instructions for a
computer. These instructions describe the steps
that the computer must follow to implement a
plan.
An algorithm is a plan for solving a problem. A
person must design an algorithm.
A person must translate an algorithm into a
computer program
Fundamentals of Algorithmic Problem
Solving
Understanding the problem :
An input to an algorithm specifies an instance
of the problem the algorithm solves.
It’s also important to specify exactly the range
of instances the algorithm needs to handle
Ascertaining the capabilities of a computational Device:
The second step is to ascertain the capabilities of a
machine.
The essence of von-Neumann machines
architecture is captured by RAM, Here the instructions
are executed one after another, one operation at a time,
Algorithms designed to be executed on such machines
are called sequential algorithms.
An algorithm which has the capability of executing
the operations concurrently is called parallel algorithms.
Choosing between exact and approximate
problem solving:
The next decision is to choose
between solving the problem exactly or solving
it approximately.
Based on this, the algorithms are
classified as exact and approximation
algorithms.
Deciding on data structures:
• Data structures play a vital role in designing
and analysing the algorithms.
• Some of the algorithm design techniques also
depend on the structuring data specifying a
problem’s instance.
Algorithm + Data structure = Programs
Algorithm Design Techniques:
• An algorithm design technique is a general
approach to solving problems algorithmically
that is applicable to a variety of problems from
different areas of computing.
Methods of specifying an Algorithm:
A Pseudocode , which is a mixture of a natural
language and programming language like
constructs.
Its usage is similar to algorithm descriptions
for writing psuedocode there are some
dialects which omits declarations of variables,
use indentation to show the scope of the
statements such as if, for and while
Proving an Algorithm’s correctness:
Correctness has to be proved for every algorithm.
To prove that the algorithm gives the required result
for every legitimate input in a finite amount of time.
For some algorithms, a proof of correctness is quite
easy; for others it can be quite complex.
A technique used for proving correctness s by
mathematical induction because an algorithm’s
iterations provide a natural sequence of steps
needed for such proofs
• Analysing an algorithm:
• There are two kinds of algorithm efficiency:
time and space efficiency.
• Time efficiency indicates how fast the
algorithm runs
• space efficiency indicates how much extra
memory the algorithm needs.
Coding an algorithm:
• Programming the algorithm by using some programming
language.
• Formal verification is done for small programs.
• Validity is done thru testing and debugging.
• Inputs should fall within a range and hence require no
verification.
• Some compilers allow code optimization which can speed
up a program by a constant factor whereas a better
algorithm can make a difference in their running time.