Definition and History of Algorithms
– An algorithm is a finite sequence of rigorous instructions used to solve specific problems or perform computations.
– Algorithms are used as specifications for calculations and data processing.
– They can use conditionals and automated decision-making to divert code execution.
– Algorithms can deduce valid inferences and achieve automation.
– Heuristics may not guarantee correct or optimal results.
– Step-by-step procedures for solving mathematical problems have been used since antiquity.
– Babylonian, Egyptian, Indian, Greek, and Arabic mathematics all had algorithms.
– These ancient algorithms included methods for finding greatest common divisors and cryptographic algorithms.
– The Ifa Oracle, a divination system, also used algorithms.
– These algorithms were developed before the formalization of the term.
– Muḥammad ibn Mūsā al-Khwārizmī wrote texts on Indian computation and arithmetic around 825.
– Latin translations of al-Khwarizmi’s texts appeared in the early 12th century.
– The term ‘algorithm’ is a Latinization of al-Khwarizmi’s name.
– The English word ‘algorism’ was attested around 1230 and adopted from French.
– The term ‘algorithmus’ emerged in the 15th century under the influence of the Greek word ‘arithmos.’
– The English word ‘algorism’ is attested in the 13th century and used by Chaucer in 1391.
– The Latin word ‘algorithmus’ was altered to ‘algorithm’ in the 15th century.
– Early dictionaries defined ‘algorism’ as the art or use of cyphers and ‘algorithmus’ as skill in accounting or numbering.
– By at least 1811, ‘algorithm’ was used to mean a step-by-step procedure.
– The term ‘algorithm’ is still used today to refer to a set of rules or a sequence of operations.
– In 1928, formalizations of algorithms began with attempts to solve the Entscheidungsproblem.
– Formalizations included recursive functions, lambda calculus, and Turing machines.
– These formalizations aimed to define effective calculability or effective method.
– Ada Lovelace’s diagram from Note G is considered the first published computer algorithm.
– These formalizations laid the groundwork for modern concepts of algorithms.
Expressing and Designing Algorithms
– Algorithms can be expressed in natural languages, pseudocode, flowcharts, etc.
– Natural language expressions of algorithms are verbose and ambiguous.
– Pseudocode, flowcharts, and control tables provide structured ways to express algorithms.
– Programming languages are used to define or document algorithms.
– Different representations of algorithms exist, such as machine tables, flowcharts, and quadruples.
– Algorithm design is a method for problem-solving and engineering algorithms.
– It is part of solution theories like divide-and-conquer or dynamic programming.
– Techniques for designing and implementing algorithms are called algorithm design patterns.
– Resource efficiency is an important aspect of algorithm design.
– Big O notation describes an algorithm’s runtime growth as input size increases.
– Simplicity and elegance are desirable qualities of algorithms.
– Good algorithms are adaptable, simple, and elegant.
– The length of time taken to perform an algorithm is a criterion for goodness.
– An elegant program is the smallest possible program for producing a specific output.
– There may be a tradeoff between speed and compactness in an elegant program.
Computers and Models of Computation
– A computer is a discrete deterministic mechanical device that follows instructions.
– Models of computation include discrete locations, counters, an agent, and a list of instructions.
– Minsky’s machine is a variation of Lambek’s abacus model.
– Minsky’s machine follows instructions sequentially, with conditional and unconditional jumps.
– Different algorithms can compute the same function.
– Types of Operations in a Minsky Machine: ZERO operation, SUCCESSOR operation, DECREMENT operation, Conditional GOTO operation, Unconditional GOTO operation.
– Translating an algorithm into a language that a computer can execute effectively is necessary.
– The computer must have the required instructions or functions to execute the algorithm.
– The choice of simulation model for the algorithm is arbitrary.
– The speed of execution can be influenced by the available instruction set.
– A programmer must know a language effective for the target computing agent.
Structured Programming and Flowchart Symbols
– Any algorithm can be computed by a Turing complete model.
– Four instruction types are required for Turing completeness: conditional GOTO, unconditional GOTO, assignment, HALT.
– Structured programming can be achieved using only these instructions.
– Additional canonical structures like DO-WHILE and CASE can be used for structured programming.
– Structured programs lend themselves to proofs of correctness using mathematical induction.
– Flowcharts are graphical aids used to describe and document algorithms.
– Flowcharts start at the top and proceed down.
– Primary symbols in flowcharts include directed arrows, rectangles, diamonds, and dots.
– Böhm-Jacopini canonical structures can be built using these symbols.
– Sub-structures can nest in rectangles if there is a single exit from the superstructure.
Algorithm Examples and Analysis
– One example is finding the largest number in a list using a simple algorithm.
– Euclid’s algorithm is an efficient method for computing the greatest common divisor of two integers.
– Euclid’s algorithm is one of the oldest algorithms in common use.
– Euclid’s algorithm can be used to reduce fractions to their simplest form.
– Euclid’s algorithm is part of many number-theoretic and cryptographic calculations.
– Euclid’s algorithm is used to find the greatest common divisor (GCD) of two numbers.
– It is based on the principle that the GCD of two numbers is equal to the GCD of the smaller number and the remainder of their division.
– The algorithm uses a series of steps, including measuring, finding the remainder, and interchanging numbers.
– Euclid’s algorithm can be implemented in both elegant and inelegant ways.
– The elegant version requires fewer instructions and isSources: https://en.wikipedia.org/wiki/Algorithm
