Algorithms and Psuedocode

From

Revision as of 18:19, 9 April 2009 by Admin (Talk | contribs)
(diff) ← Older revision | Current revision (diff) | Newer revision → (diff)
Jump to: navigation, search
Begin ↑ Contents: CS2 Searching →


Contents

Algorithms

In mathematics, computing, linguistics and related subjects, an algorithm is a finite sequence of instructions, using an effective, step-by-step procedure for solving a problem, often used for calculation and data processing. It is formally a type of effective method in which a list of well-defined instructions for completing a task will, when given an initial state, proceed through a well-defined series of successive states, eventually terminating in an end-state. The transition from one state to the next is not necessarily deterministic; some algorithms, known as probabilistic algorithms, incorporate randomness.

Expressing algorithms

Algorithms can be expressed in many kinds of notation, including natural languages, pseudocode, flowcharts, and programming languages. Natural language expressions of algorithms tend to be verbose and ambiguous, and are rarely used for complex or technical algorithms. Pseudocode and flowcharts are structured ways to express algorithms that avoid many of the ambiguities common in natural language statements, while remaining independent of a particular implementation language. Programming languages are primarily intended for expressing algorithms in a form that can be executed by a computer, but are often used as a way to define or document algorithms.

Pseudocode/Structured English

Pseudocode is a compact and informal high-level description of a computer programming algorithm that uses the structural conventions of some programming language, but is intended for human reading rather than machine reading. Pseudo-code typically omits details that are not essential for human understanding of the algorithm, such as variable declarations, system-specific code and subroutines. The programming language is augmented with natural language descriptions of the details, where convenient, or with compact mathematical notation. The purpose of using pseudocode is that it is easier for humans to understand than conventional programming language code, and that it is a compact 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.

No standard for pseudocode syntax exists, as a program in pseudocode is not an executable program. Pseudocode resembles, but should not be confused with, skeleton programs including dummy code, which can be compiled without errors. Flowcharts can be thought of as a graphical alternative to pseudocode.

Writing Pseudocode

As the name suggests, pseudocode generally does not actually obey the syntax rules of any particular language; there is no systematic standard form, although any particular writer will generally borrow style and syntax for example control structures from some conventional programming language. Variable declarations are typically omitted. Function calls and blocks of code, for example code contained within a loop, is often replaced by a one-line natural language sentence.

Depending on the writer, pseudocode may therefore vary widely in style, from a near-exact imitation of a real programming language at one extreme, to a description approaching formatted prose at the other.

Psuedocode/Structured English generally consists of the following elements:

  1. Operation statements written as English phrases executed from the top down
  2. Conditional blocks indicated by keywords such as IF, THEN, and ELSE
  3. Repetition blocks indicated by keywords such as DO, WHILE, and UNTIL
  4. Definitions and Calls to Subprograms


Use the following guidelines when writing Psuedocode/Structured English:

  1. Statements should be clear and unambiguous
  2. Use one line per logical element
  3. All logic should be expressed in operational, conditional, and repetition blocks
  4. Logical blocks should be indented to show relationship
  5. Keywords should be capitalized


Examples of keywords that might be used

START, BEGIN, END, STOP, DO, WHILE, DO WHILE, FOR, UNTIL, DO UNTIL, REPEAT, ENDWHILE, ENDUNTIL, ENDREPEAT, IF, IF THEN, ELSE, IF ELSE, ENDIF, THEN, ELSE THEN, ELSE IF, SO, CASE, EQUAL, LT, LE, GT, GE, NOT, TRUE, FALSE, AND, OR, XOR, GET, WRITE, PUT, UPDATE, CLOSE, OPEN, CREATE, DELETE, EXIT, FILE, READ, EOF, EOT

A Psuedocode Syntax


Assignment statement (memory write):

    <variable> = <expression>

Conditional statement (flow of control):

    IF <condition>
        do stuff
    ELSE
        do other stuff
    ENDIF

Interation/Repetition (flow of control):

    WHILE <condition>
        do stuff
    ENDWHILE


    FOR <variable> FROM <first value> TO <last value> BY <step>
        do stuff with variable
    ENDFOR

Subprogram/Function/Procedure/Method definition:

    FUNCTION <function name>(<arguments>)
        do stuff with arguments
        return something
    ENDFUNCTION

Subprogram/Function/Procedure/Method call:

    <function name>(<arguments>)



Example of Psuedocode/Structured English

A bank will grant loan under the following conditions

  1. If a customer has an account with the bank and had no loan outstanding, loan will be granted.
  2. If a customer has an account with the bank but some amount is outstanding from previous loans then loan will be granted if special approval is needed.
  3. Reject all loan applications in all other cases.
    IF customer has a Bank Account THEN
      IF Customer has no dues from previous account THEN
          Allow loan facility
      ELSE
        IF Management Approval is obtained THEN
          Allow loan facility
        ELSE
          Reject
        ENDIF
      ENDIF
    ELSE
      Reject
    ENDIF

CS2: Data Structures
Theory of Computation - ADT Preliminaries
Linear ADTs - Tree ADTs - Graph ADTs - Unordered Collection ADTs


Personal tools
MediaWiki Appliance - Powered by TurnKey Linux