Definition and History of Algorithms
– Algorithms are a finite sequence of rigorous instructions used in mathematics and computer science.
– They are used to solve specific problems or perform computations.
– Algorithms serve as specifications for calculations and data processing.
– More advanced algorithms can incorporate conditionals and automated decision-making.
– Algorithms can be expressed in a well-defined formal language for calculating a function.
– Step-by-step procedures for solving mathematical problems have been used since antiquity.
– Babylonian, Egyptian, Indian, Greek, and Arabic civilizations developed mathematical algorithms.
– These algorithms included methods for finding the greatest common divisor and cryptographic algorithms.
– Ancient algorithms were based on different numeral systems and arithmetic techniques.
– They laid the foundation for modern algorithmic thinking.
– Muḥammad ibn Mūsā al-Khwārizmī wrote texts on Indian computation and arithmetic in the 9th century.
– Latin translations of al-Khwārizmī’s works introduced the term ‘algorismi’ and ‘algorithmus’ in the 12th century.
– The term ‘algorithm’ was derived from al-Khwārizmī’s name and referred to the art of reckoning by numerals.
– Al-Khwārizmī’s texts played a significant role in spreading Indian numerals and arithmetic in Europe.
– The term ‘algorithm’ evolved over time in different languages.
– The English word ‘algorism’ was attested around 1230 and later adopted the French term.
– In the 15th century, the Latin word was altered to ‘algorithmus’ under the influence of the Greek word ‘arithmos.’
– Early English dictionaries defined ‘algorism’ as the art of numbering by cyphers and ‘algorithmus’ as skill in accounting or numbering.
– The term ‘algorithm’ began to be used to signify a step-by-step procedure in English since at least 1811.
– The word ‘algorithm’ has undergone various interpretations and usages throughout history.
– In 1928, attempts to solve the Entscheidungsproblem led to the partial formalization of algorithms.
– Formalizations included recursive functions, lambda calculus, and Turing machines.
– These formalizations aimed to define effective calculability and effective methods.
– Alan Turing’s Turing machines, proposed in the late 1930s, are considered a fundamental model of computation.
– The development of formalized algorithms paved the way for modern computer science.
Expressing and Designing Algorithms
– Algorithms can be expressed in natural languages, pseudocode, flowcharts, etc.
– Natural language expressions of algorithms are rarely used for complex or technical algorithms.
– Pseudocode, flowcharts, and control tables provide structured ways to express algorithms.
– Programming languages are primarily used to execute algorithms.
– Different representations of algorithms are possible, such as machine tables, flowcharts, and quadruples.
– Algorithm design is a method for problem-solving and engineering algorithms.
– Different solution theories, such as divide-and-conquer or dynamic programming, contribute to algorithm design.
– Algorithm design patterns, like the template method pattern and decorator pattern, aid in designing and implementing algorithms.
– Resource efficiency, such as run-time and memory usage, is an important aspect of algorithm design.
– The big O notation describes an algorithm’s run-time growth as input size increases.
– Simplicity and elegance are desirable qualities in algorithms.
– Good algorithms are adaptable, simple, and elegant.
– The length of time taken to perform an algorithm is one criterion for evaluating its goodness.
– Chaitin defines an elegant program as the smallest possible program for producing a specific output.
– Tradeoffs may occur between speed and compactness in elegant programs.
Computers and Models of Computation
– A computer is a discrete deterministic mechanical device that follows instructions.
– Models of computation, like Melzaks and Lambeks primitive models, have discrete locations, counters, an agent, and a list of effective instructions.
– Minsky’s machine, a variation of Lambeks abacus model, follows instructions sequentially.
– Conditional and unconditional GOTO statements can change program flow.
– Different algorithms can compute the same function.
Simulation and Execution of Algorithms
– Algorithms are essential to the way computers process data.
– Algorithms detail specific instructions for a computer to perform a task.
– Algorithms can be simulated by a Turing-complete system.
– Not all computational processes defined by Turing machines terminate.
– Algorithms often involve reading, writing, and storing data.
– Programmer must translate the algorithm into a language that the computer can execute.
– Effective language choice depends on the target computing agent.
– Knowledge of effective language is necessary for the programmer.
– Model choice for simulation introduces the notion of simulation.
– Speed of execution depends on the instruction set of the computer.
– Any algorithm can be computed by a Turing complete model.
– Structured programs can be written using conditional and unconditional GOTOs, assignment, and HALT instructions.
– Undisciplined use of GOTOs can result in spaghetti code.
– Additional canonical structures include DO-WHILE and CASE.
– Structured programs lend themselves to proofs of correctness using mathematical induction.
– Flowchart is a graphical aid to describe and document an algorithm.
– Flowchart starts at the top and proceeds down.
– Primary symbols include directed arrow, rectangle (SEQUENCE, GOTO), diamond (IF-THEN-ELSE), and dot (OR-tie).
– Böhm-Jacopini canonical structures can be built using these symbols.
– Sub-structures can nest in rectangles with a single exit.
Example of Euclid’s Algorithm and Algorithmic Analysis
– Euclid’s algorithm is a method for finding the greatest common divisor (GCD) of two numbers.
– The algorithm involves a series of steps that use subtraction to find the remainder.
– It is named after the ancient Greek mathematician Euclid.
– The algorithm has been used for centuries and is still widely used today.
– Euclid’s algorithm is efficient and can find the GCD of very large numbers.
– Inelegant is a version of Euclid’s
In mathematics and computer science, an algorithm (/ˈælɡərɪðəm/ ⓘ) is a finite sequence of rigorous instructions, typically used to solve a class of specific problems or to perform a computation. Algorithms are used as specifications for performing calculations and data processing. More advanced algorithms can use conditionals to divert the code execution through various routes (referred to as automated decision-making) and deduce valid inferences (referred to as automated reasoning), achieving automation eventually. Using human characteristics as descriptors of machines in metaphorical ways was already practiced by Alan Turing with terms such as "memory", "search" and "stimulus".
In contrast, a heuristic is an approach to problem solving that may not be fully specified or may not guarantee correct or optimal results, especially in problem domains where there is no well-defined correct or optimal result. For example, social media recommender systems rely on heuristics in such a way that, although widely characterized as "algorithms" in 21st century popular media, cannot deliver correct results due to the nature of the problem.
As an effective method, an algorithm can be expressed within a finite amount of space and time and in a well-defined formal language for calculating a function. Starting from an initial state and initial input (perhaps empty), the instructions describe a computation that, when executed, proceeds through a finite number of well-defined successive states, eventually producing "output" and terminating at a final ending state. The transition from one state to the next is not necessarily deterministic; some algorithms, known as randomized algorithms, incorporate random input.
