Algorithm

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