Please enable JavaScript.
Coggle requires JavaScript to display documents.
Algorithms and Pseudocode (Problem solution steps (1. Problem definition…
Algorithms and Pseudocode
A problem is specified by
The givens
The query
Problem solution steps
1. Problem definition
Clear understanding of the problem is required before formulating a solution.
2. Problem analysis
Develop mathematical formulation, define inputs, outputs and their relationships, state any assumptions.
3.Algorithm design
Formulate a series of step by step instructions for solving the problem (pseudocode or flow charts)
4.Program development
Conversion of the algorithm into the desired programming language.
5. Testing and verification
Does the program perform its intended function, debugging, verification.
6. Documentation
Internal and external documentation.
7.Maintenance and modification
Correcting errors and enhancing features.
What is an algorithm
Algorithm is a step by step procedure for solving a problem in a finite amount of time.
Input
: An algorithm has input values from a specified set.
Output:
From each set of input values an algorithm produces output values from a specified set. The output values are the solution to the problem.
Definiteness
: The steps of an algorithm must be defined precisely.
Correctness:
An algorithm should always produce the correct output values for each set of input values.
Completeness:
always gives a solution when one exists.
Properties of algorithm
Finiteness:
An algorithm should produce the desired output after a finite number of steps for any input in the set.
Effectiveness:
It must be possible each step of an algorithm exactly and in finite amount of time.
Generality:
The procedure should be applicable for all problems of the desired form, not just for a particular set of input values.
Efficient=
runs in polynomial time.
Method of designing algorithms
Top-Down-
Breaking large problems into smaller, manageable ones.
Involves two techniques:
Decomposition
and
stepwise refinement.
1.Define the problem statement in general.
2.Decompose the original problem into sub problems.
Refine each of the general steps in greater detail- this is iterative step with each one adding more detail.
Advantages of Top-Down
Produces well designed modular programs.
Helps reduce complexity since decisions are posponed until appropriate level in the development.
Algorithms are usually presented using
pseudocode
or
flow charts.
Pseudocode
- is an English like presentation of algorithms.
Good Pseudocode
Is a balance between clarity and detail.
Abstracts the algorithm
Makes good use of mathematical notation.
Is easy to read and write.
Language independent
Bad Pseudocode
Gives too many details.
Is too implementation specific.
Verbose
Used to write the algorithm once the data structure is fully understood.
Instruction is written on a separate line from top to bottom with one entry and one exit.