current community

your communities

more stack exchange communities

company blog
Stack Exchange Inbox Reputation and Badges
tour help

algorithm


Getting started with algorithm Introduction Topic

edit move examples delete

This draft deletes the entire topic.

expand all collapse all

Examples

  • 2
    A sample algorithmic problem
    edit move example delete
    2

    An algorithmic problem is specified by describing the complete set of instances it must work on and of its output after running on one of these instances. This distinction, between a problem and an instance of a problem, is fundamental. The algorithmic problem known as sorting is defined as follows: [Skiena:2008:ADM:1410219]

    Problem: Sorting
    Input: A sequence of n keys, a_1, a_2, ..., a_n.
    Output: The reordering of the input sequence such that a'_1 <= a'_2 <= ... <= a'_{n-1} <= a'_n

    An instance of sorting might be an array of strings, such as { Haskell, Emacs } or a sequence of numbers such as { 154, 245, 1337 }.

    edited Nov 16 at 17:15
+ Add Example
Please consider making a request to improve this example.

Remarks

edit

Introduction to Algorithms

Algorithms are ubiquitous in Computer Science and Software Engineering, and it is through the selection of appropriate algorithms and data structures that our programs do not consume an inordinately amount of memory and executes within a reasonable time-frame.

What is an algorithm? Informally, an algorithm is a procedure to accomplish a specific task. [ Skiena:2008:ADM:1410219] Specifically, an algorithm is a well-defined computational procedure, which takes some value (or set of values) as input and produces some value, or a set of values, as output. An algorithm is thus a sequence of computational steps that transform the input into the output. Cormen et. al. does not explicitly remark that an algorithm does not necessarily require an input. [Cormen:2001:IA:580470]

Formally, an algorithm must satisfy five features: [Knuth:1997:ACP:260999]

  1. Finiteness. An algorithm must always terminate after a finite number of steps.
  2. Definiteness. Each step of an algorithm must be precisely defined; the actions to be carried out must be rigorously and unambiguously specified. It is this quality that [Cormen:2001:IA:580470] refers to with the term "well-defined".
  3. Input. An algorithm has zero or more inputs. These are quantities that are given to the algorithm initially before it begins or dynamically as it runs.
  4. Output. An algorithm has one or more outputs. These are quantities that have a specified relation to the inputs. We expect that an algorithm produces the same output when given the same input over and over again.
  5. Effectiveness. An algorithm is also generally expected to be effective, in the sense that its operations must all be sufficiently basic that they can in principle be done exactly and in a finite length of time by someone using pencil and paper.

A procedure that lacks finiteness but satisfies all other characteristics of an algorithm may be called a computational method. [Knuth:1997:ACP:260999]

Versions

Versions

edit
edited Nov 16 at 17:15
Still have a question about Getting started with algorithm? Ask Question

Topic Outline


    Save Draft Discard