Algorithms: Definition, History, Types, and Characteristics
What is an Algorithm?
An algorithm is a finite set of precise instructions that perform a task, which, given an initial state, will end after producing a recognizable end state.
What is the Order of Algorithm Execution?
The order of execution will almost always be critical for its operation. Generally, it is assumed that explicit instructions are listed explicitly and must run from top to bottom.
Provide Examples of Algorithms
- Instruction manuals (user manuals)
- Euclid’s algorithm for calculating the greatest common divisor of two positive integers
- The Gaussian elimination method for solving a linear system of equations
Who is Credited with the Digital Computer and Why?
Alan Mathison Turing, a famous English mathematician (1912-1954), devised an imaginary device which he called a Logical Computing Machine (LCM), but it has received in his honor the name of the Turing Machine.
What Constitutes the Turing Machine?
It is a device that moves on a linear sequence of data. At each instant, the machine can read a single data sequence (usually a character) and perform certain actions based on a table that takes into account its current (internal) state and recently read data.
What Actions Can it Perform?
It has the ability to write new data to the stream, move the stream in both directions, and change state within a finite set of states.
How to Specify an Algorithm?
To specify an algorithm so that its implementation is correct, i.e., that it does exactly what is expected of it, which, in turn, can be implemented with different languages or tools, a method is to define its inputs and outputs, with corresponding preconditions and postconditions.
How is the History of the Algorithm?
The name comes from the mathematician named Muhammad ibn Musa al-Khwarizmi. His job was to simplify mathematics to the point that it could be understood and applied by a greater number of people. He also discussed ways to reduce operations forming the calculations. The word algorism originally referred to the rules of use, using Arabic numerals. It evolved into the Latin word, a derivation of al-Khwarizmi, algobarismus, that later became algorithm in the 18th century. The word has changed, and its definition now includes all finite procedures to solve problems.
What are the Requirements of the Algorithm?
According to computer scientist Donald Knuth, the characteristics are: finite, precision, input, output, and efficiency.
What Constitutes a Finite Characteristic?
An algorithm must always terminate after a finite number of simple steps.
What Constitutes Precision?
Each step of an algorithm must be precisely defined; the operations to be carried out must be specified rigorously and unambiguously in each case.
What Constitutes Input?
An algorithm has zero or more inputs: quantities that are given before the algorithm starts, or dynamically while the algorithm runs. These inputs are taken from specific sets of objects.
What is the Output?
An algorithm has one or more outputs: quantities that have a specific relationship with the input.
What Constitutes Effectiveness?
It is also expected that an algorithm is effective in the sense that all operations to be performed on an algorithm must be basic enough that, in principle, they can be done accurately and in a finite time by a human using pencil and paper.
How to Calculate an Algorithm?
As any finite set is countable, and any whole number can be expressed in terms of a set of natural numbers (infinite, but countable; in fact, there is no bigger set, it is also a number), essentially, every algorithm calculates functions defined in purely natural numbers.
What are Functions with an Algorithm Called?
A function is called computable (partially computable or fully computable depending on the degree of the function definition) if there is an algorithm that calculates it.
What are Partially Computable Functions?
A partial function on natural numbers that belong to its domain (i.e., there are natural numbers on which the function is not defined) only returns a result (i.e., spends a finite calculation time) for values where the function is defined, returning no result (calculation time is infinite) for other values.
What are Totally Computable Functions?
An algorithm calculates a total function that always returns a result for every value, and as with partial functions, this must exactly match the value returned by the function it calculates. If, instead, it calculated that function but for another, then any algorithm calculates a function defined on the natural numbers, whatever its nature.
How Can Algorithms be Expressed?
Natural language, pseudocode, flowcharts, and programming languages.
What are the Levels of Algorithm Description?
High-level description, formal description, implementation.
What are Each of the Above?
High-level description: The problem is established, a mathematical model is selected, and the algorithm is explained verbally, possibly with illustrations and omitting details.
Formal description: Pseudocode is used to describe the sequence of steps that include the solution.
Implementation: The algorithm is expressed in a specific programming language or some object capable of carrying out instructions.
What is a Flowchart?
A flowchart is a graphical representation of an algorithm or a part of it.
Name Symbols of a Flowchart
Terminal, process, decision, input/output, connector, and flow line.
What is Pseudocode?
Pseudocode is an artificial and informal language that helps programmers develop algorithms.
According to their Function, What are the Types of Algorithms?
Sorting algorithms and search algorithms.
What is a Sorting Algorithm Responsible for?
It is an algorithm that puts elements of a list or a vector in a given sequence of a list command.
What are the Most Used Order Relations?
Numerical order and lexicographical order.
How Can Sorting Algorithms be Classified?
The most common way is according to where the sorting is performed:
a. Internal sorting algorithms: in the computer’s memory.
b. External sorting algorithms: off-site, such as a hard disk.
By the time it takes to perform the sorting, given already ordered or inversely ordered inputs:
c. Natural sorting algorithms: it takes the minimum possible time when the input is sorted.
d. Unnatural sorting algorithms: it takes the minimum possible time when the input is reverse-ordered.
For stability: a stable computer maintains the relative order that originally had or expected an element with the same key.
Classification of Sorting Algorithms by Order?
Internal sorting algorithms, external sorting algorithms, natural sorting algorithms, unnatural sorting algorithms.
What is a Search Algorithm?
It is one that is designed to locate a particular item within a data structure.
Mention Some of the Techniques
Greedy algorithms, parallel algorithms, probabilistic algorithms, non-deterministic algorithms, deterministic algorithms, divide and conquer, metaheuristics, dynamic programming, branch and bound, backtracking.
What Algorithm is Said to Have Linear Behavior?
Deterministic algorithm.
What is the Way the Divide and Conquer Algorithm Works?
It divides the problem into disjoint subsets, obtaining a solution for each one, and after joining them, thus achieving the solution to the whole problem.
How is the Branch and Bound Algorithm Based?
It is based on the construction of solutions to the problem through an implicit tree that is traversed in a controlled manner, finding the best solutions.
When Selecting the Most Promising Elements of the Set of Candidates to Find a Solution, What are we Talking About?
Greedy algorithms.
What do Metaheuristic Algorithms Tell Us?
They find approximate solutions (optimal or not) to problems based on prior knowledge (sometimes called experience) of them.
What is the Algorithm that Tries to Solve Computational Problems by Reducing their Cost by Increasing the Space Cost?
Dynamic programming.
How to Calculate the Measure of Efficiency of Algorithms?
They tend to study the resources (memory and time) consumed by the algorithm.
What is the Analysis of Algorithms?
The analysis of algorithms has been developed to obtain values that indicate in some way (or specifying) the evolution of time and memory expenditure as a function of the size of the input values.
Mention a Way to Express or Encode an Algorithm
Write it in pseudocode or use a very simple language such as Lexico, whose codes can be in the programmer’s language.