WHAT IS ALGORITHAM
An algorithm (pronounced AL-go-rith-um) is a procedure or formula for solving a problem. The word derives from the name of the mathematician, Mohammed ibn-Musa al-Khwarizmi, who was part of the royal court in Baghdad and who lived from about 780 to 850. Al-Khwarizmi's work is the likely source for the word algebra as well.
A computer program can be viewed as an elaborate algorithm. In mathematics and computer science, an algorithm usually means:
1. A step-by-step method of solving a problem or making decisions, as in making a diagnosis.
2. An established mechanical procedure for solving certain mathematical problems.
3. " a sequence of instructions for achieving a goal "
Definition:
“ An ordered sequence of unambiguous and well-defined instructions that performs some task and halts in finite time “
Let's examine the four parts of this definition more closely
- An ordered sequence means that you can number the steps (its socks then shoes!)
- unambiguous and well-defined instructions means that each instruction is clear, do-able, and can be done without difficulty
- performs some task
- Halts in finite time (algorithms terminate!)
Algorithms can be executed by a computing agent which is not necessarily a computer.
Properties of the algorithm:
1) Finiteness: - an algorithm terminates after a finite numbers of steps.
2) Definiteness: - each step in algorithm is unambiguous. This means that the action specified by the step cannot be interpreted (explain the meaning of) in multiple ways & can be performed without any confusion.
3) Input: - an algorithm accepts zero or more inputs
4) Output: - it produces at least one output.
5) Effectiveness: - it consists of basic instructions that are realizable. This means that the instructions can be performed by using the given inputs in a finite amount of time.
1) Finiteness: - an algorithm terminates after a finite numbers of steps.
2) Definiteness: - each step in algorithm is unambiguous. This means that the action specified by the step cannot be interpreted (explain the meaning of) in multiple ways & can be performed without any confusion.
3) Input: - an algorithm accepts zero or more inputs
4) Output: - it produces at least one output.
5) Effectiveness: - it consists of basic instructions that are realizable. This means that the instructions can be performed by using the given inputs in a finite amount of time.
Categories of Algorithms:
Algorithmic operations are ordered in that there is a first instruction, a second instruction etc. However, this is not enough. An algorithm must have the ability to alter the order of its instructions. An instruction that alters the order of an algorithm is called a control structure
Categories (Operations based):
- sequential operations - instructions are executed in order
- conditional ("question asking") operations - a control structure that asks a true/false question and then selects the next instruction based on the answer
- iterative operations (loops) - a control structure that repeats the execution of a block of instructions
Categories (output based):
Unfortunately not every problem or task has a "good" algorithmic solution. There are
- unsolvable problems - no algorithm can exist to solve the problem (Halting Problem)
- "Hard" (intractable) problems - algorithm takes too long to solve the problem (Traveling Salesman Problem)
- problems with no known algorithmic solution
Representation of Algorithms:
1. Use natural languages
- too verbose
- too "context-sensitive"- relies on experience of reader
- Use formal programming languages
- too low level
- requires us to deal with complicated syntax of programming language
- Pseudo-Code - natural language constructs modeled to look like statements available in many programming languages
Advantages of Algorithms:
1. Algorithms are the foundation of computer Science, it is telling the computer to do the task in the most efficient matter.
2. An algorithm is particularly important in optimizing a computer program; the efficiency of the algorithm usually determines the efficiency of the program as a whole.
Pseudo code
Definition:
“An outline of a program, written in a form that can be easily converted into real programming statements”.
Characteristics:
· It has no real formatting or syntax rules.
· It can be written in any formal language.
Why is pseudocode necessary?
The programming process is a complicated one. You must first understand the program specifications, of course, and then you need to organize your thoughts and create the program. This is a difficult task when the program is not trivial (i.e. easy). You must break the main tasks that must be accomplished into smaller ones in order to be able to eventually write fully developed code. Writing pseudo code WILL save you time later during the construction & testing phase of a program's development.
Purpose
The purpose of using pseudo code is that it is easier for humans to understand than conventional programming language code, and that it is an efficient and environment-independent description of the key principles of an algorithm. It is commonly used in textbooks and scientific publications that are documenting various algorithms, and also in planning of computer program development, for sketching out the structure of the program before the actual coding takes place.
Common Action Keywords:
· Several keywords are often used to indicate common input, output, and processing operations.
· Input: READ, OBTAIN, GET
· Output: PRINT, DISPLAY, SHOW
· Compute: COMPUTE, CALCULATE, DETERMINE
· Initialize: SET, INIT
· Add one: INCREMENT, BUMP
Rules and constraints:
One Statement Per Line:
Each statement in pseudo code should express just one action for the computer. If the task list is properly drawn, then in most cases each task will correspond to one line of pseudocode.
Capitalize Initial Keyword:
In the example below note the words: READ and WRITE. These are just a few of the keywords to use, others include:
READ, WRITE, IF, ELSE, ENDIF, WHILE, ENDWHILE
Indent to Show Hierarchy Sequence:
Keep statements in sequence all starting in the same column
End Multiline Structures
See the IF/ELSE/ENDIF as constructed above, the ENDIF is in line with the IF.
The same applies for WHILE/ENDWHILE etc…
Language Independence
Resist the urge to write in whatever language you are most comfortable with, in the long run you will save time. Remember you are describing a logic plan to develop a program, you are not programming!
Pseudocode Advantages
· Easily modified
· Implements structured concepts
· Done easily on Word Processor
Pseudocode Disadvantages:
· Not visual
· No accepted standard, varies from company to company
Example
Computing Sales Tax: Pseudo-code the task of computing the final price of an item after figuring in sales tax.
[Note the three types of instructions: input (get), process/calculate (=) and output (display)]
1. Get price of item
2. Get sales tax rate
3. Sales tax = price of time times sales tax rate
4. Final prince = price of item plus sales tax
5. Display final price
6. Halt
Variables: price of item, sales tax rate, sales tax, final price
Introduction to flowcharts
A flowchart is a graphical representation of an algorithm. These flowcharts play a vital role in the programming of a problem and are quite helpful in understanding the logic of complicated and lengthy problems. Once the flowchart is drawn, it becomes easy to write the program in any high level language. Often we see how flowcharts are helpful in explaining the program to others. Hence, it is correct to say that a flowchart is a must for the better documentation of a complex program.
Purpose of a Flowchart
Flowcharts help business managers, CEOs, project managers and organization planners assess the flow of data. Flowcharts are primarily used to help brainstorm ideas in order to build strategies in the planning stage of any new product or company. As visual representations of the flow of data, flowcharts present key points to investors, clients, customers, business partners and employees
Definition:
Definition:
1. A flowchart is a diagram that depicts the “flow” of a program.
2. Flow Chart is a Snap Shot of your Business Processes.
3. A flowchart is a graphic representation of all the major steps of a process
Types of flowchart
Sterneckert (2003) suggested that flowcharts can be modeled from the perspective of different user groups (such as managers, system analysts and clerks) and that there are four general types:[10]
· Document flowcharts, showing controls over a document-flow through a system
· Data flowcharts, showing controls over a data flows in a system
· System flowcharts showing controls at a physical or resource level
· Program flowchart, showing the controls in a program within a system
Notice that every type of flowchart focuses on some kind of control, rather than on the particular flow itself.
Guidelines In Flowcharting: - In drawing a proper flowchart, all necessary requirements should be listed out in logical order.
- The flowchart should be clear, neat and easy to follow. There should not be any room for ambiguity in understanding the flowchart.
- The usual direction of the flow of a procedure or system is from left to right or top to bottom.
- Only one flow line should come out from a process symbol.
or
- Only one flow line should enter a decision symbol, but two or three flow lines, one for each possible answer, should leave the decision symbol.
- Only one flow line is used in conjunction with terminal symbol.
Example of a flowchart:
START
|
Input x
|
Input y
|
Sum = x + y
|
Average = sum/2
|
Output Average
|
END
|
Algorithm:
Input: two numbers x and y
Output: the average of x and y
Steps:
- input x
- input y
- sum = x + y
- average = sum /2
- output average
ADVANTAGES OF USING FLOWCHARTS
- Communication: Flowcharts are better way of communicating the logic of a system to all concerned.
- Effective analysis: With the help of flowchart, problem can be analyzed in more effective way.
- Proper documentation: Program flowcharts serve as a good program documentation, which is needed for various purposes.
- Efficient Coding: The flowcharts act as a guide or blueprint during the systems analysis and program development phase.
- Proper Debugging: The flowchart helps in debugging process.
- Efficient Program Maintenance: The maintenance of operating program becomes easy with the help of flowchart. It helps the programmer to put efforts more efficiently on that part
LIMITATIONS OF USING FLOWCHARTS
- Complex logic: Sometimes, the program logic is quite complicated. In that case, flowchart becomes complex and clumsy.
- Alterations and Modifications: If alterations are required the flowchart may require re-drawing completely.
- Reproduction: As the flowchart symbols cannot be typed, reproduction of flowchart becomes a problem.
- The essentials of what is done can easily be lost in the technical details of how it is done.