Algorithms

7 Key excerpts on "Algorithms"

• 

  eBook - ePub

  The Social Power of Algorithms

  • David Beer(Author)
  • 2019(Publication Date)
  • Routledge

    (Publisher)

  This paper synthesises, critiques and extends these studies. Divided into two main sections – thinking critically about and researching Algorithms – the paper makes four key arguments. First, as already noted, there is a pressing need to focus critical and empirical attention on Algorithms and the work that they do in the world. Second, it is most productive to conceive of Algorithms as being contingent, ontogenetic, performative in nature and embedded in wider socio-technical assemblages. Third, there are three main challenges that hinder research about Algorithms (gaining access to their formulation; they are heterogeneous and embedded in wider systems; their work unfolds contextually and contingently), which require practical and epistemological attention. Fourth, the constitution and work of Algorithms can be empirically studied in a number of ways, each of which has strengths and weaknesses that need to be systematically evaluated. With respect to the latter, the paper provides a critical appraisal of six methodological approaches that might profitably be used to produce insights into the nature and work of Algorithms.

  Thinking critically about Algorithms

  While an algorithm is commonly understood as a set of defined steps to produce particular outputs it is important to note that this is somewhat of a simplification. What constitutes an algorithm has changed over time and they can be thought about in a number of ways: technically, computationally, mathematically, politically, culturally, economically, contextually, materially, philosophically, ethically and so on.

  Miyazaki (2012) traces the term ‘algorithm’ to twelfth-century Spain when the scripts of the Arabian mathematician Muḥammad ibn Mūsā al-Khwārizmī were translated into Latin. These scripts describe methods of addition, subtraction, multiplication and division using numbers. Thereafter, ‘algorism’ meant ‘the specific step-by-step method of performing written elementary arithmetic’ (Miyazaki, 2012, p. 2) and ‘came to describe any method of systematic or automatic calculation’ (Steiner, 2012, p. 55). By the mid-twentieth century and the development of scientific computation and early high level programming languages, such as Algol 58 and its derivatives (short for ALGOrithmic Language), an algorithm was understood to be a set of defined steps that if followed in the correct order will computationally process input (instructions and/or data) to produce a desired outcome (Miyazaki, 2012).

  From a computational and programming perspective an ‘Algorithm = Logic + Control’; where the logic is the problem domain-specific component and specifies the abstract formulation and expression of a solution (what is to be done) and the control component is the problem-solving strategy and the instructions for processing the logic under different scenarios (how it should be done) (Kowalski, 1979). The efficiency of an algorithm can be enhanced by either refining the logic component or by improving the control over its use, including altering data structures (input) to improve efficiency (Kowalski, 1979). As reasoned logic, the formulation of an algorithm is, in theory at least, independent of programming languages and the machines that execute them; ‘it has an autonomous existence independent of “implementation details”’ (Goffey, 2008, p. 15).

  Sign up to read

  Learn more about book
• 

  eBook - ePub

  Rules

  A Short History of What We Live By

  • Lorraine Daston(Author)
  • 2022(Publication Date)
  • Princeton University Press

    (Publisher)

  algorithm was the solution of specific problems by step-by-step procedures of calculation.

  But long before the word there was the thing. From ancient mathematical traditions in Babylonia, Egypt, India, China, and elsewhere, texts survive that contain numerical problems and sophisticated solutions that are clearly algorithmic in the sense that crystallized around the word as it came to be assimilated into medieval Latin and other languages after circa 1200 CE. A brief and incomplete sampling of the kinds of problems to which the term algorithm is retrospectively applied might include: ancient Egyptian problems (c. 1650 BCE) on how to distribute 100 loaves of bread among 10 men if 50 are to be distributed among 6 men and the other 50 among the remaining 4;9 Old Babylonian prediction rules (c. 1100 BCE) for the length of the lunar month;10 Chinese procedures for the extraction of square and cube roots (1st c. CE);11 and medieval Sanskrit problems (12th c. CE) on how to determine the purity of gold compounded of four parcels of gold, all of different weights and degrees of fineness.12 All of these problems and the methods used to solve them—which often require great erudition and insight on the part of modern scholars to reconstruct—fit neatly into at least the broader modern category of Algorithms: a step-by-step procedure to solve mathematical problems by calculation.

  Was this also the category to which such problems belonged in the learned cultures that posed and solved them? Scholars who have painstakingly reconstructed these traditions have expressed doubts on this score, even if they are convinced that the methods qualify as Algorithms in the modern sense. Historian of Babylonian mathematics Jim Ritter points out that the canon of ancient mathematical texts was first constituted by European scholars in the nineteenth century, when the prevailing assumption was that mathematics was mathematics was mathematics, regardless of context, and that modern definitions (and algebraic notation) could be applied unproblematically to diverse past traditions. In the case of Old Babylonian problem texts, Ritter suggests that it may be illuminating to interpret surviving cuneiform problem texts not only in the context of other mathematical texts but also in that of other “rational practice” texts from the ancient Near East, including Akkadian tablets about medicine, divination, and jurisprudence. Why? Because all of these texts exhibit striking semantic and syntactical similarities, and all would have been rooted in the practices of the same professional class of scribes. Modern historians of mathematics might not recognize the broader category of procedural texts, but perhaps “the grouping would have made sense to the ancient Babylonians.”13

  Sign up to read

  Learn more about book
• 

  eBook - ePub

  Foundations of Discrete Mathematics with Algorithms and Programming

  • R. Balakrishnan, Sriraman Sridharan(Authors)
  • 2018(Publication Date)
  • Chapman and Hall/CRC

    (Publisher)

  Chapter 5

  Introduction to Algorithms and Data Structures

  Algorithms + Data Structures = Programs.

  N. Wirth

  Mathematical models have been a crucial inspiration for all scientific activity even though they are only approximate idealizations of the real-world phenomena. Inside computers such models are more relevant than ever before, because computer programs create artificial worlds in which mathematical models often apply precisely.

  Donald Knuth

  This chapter begins with the concept of an algorithm. Then the complexity of Algorithms is studied. After a brief introduction to computer architecture, an introduction to programming languages is given. Since data structures go in parallel with Algorithms, fundamental data structures like lists, stacks and queues are studied. In the last section, examples of Algorithms with different complexity functions encountered in practice are illustrated.

  5.1 Algorithms

  The word algorithm is at the very heart of computer science. The word algorithm signifies approximately the same meaning as the following words: method, procedure, function, technique, strategy, process, recipe, etc. (See [1 ] and [9 ].)

  An algorithm can be described as a systematic and progressive method to solve a problem; that is, it is a step-by-step procedure to solve a problem.

  Mathematically, it can be viewed as a function acting on a specified set of arguments/inputs to produce a specified set of results/outputs. It transforms the “raw” data into the “refined” data (just like a kitchen recipe transforms flour, sugar, milk, etc., into a cake).

  The modern description of algorithm is a method of solving a problem adapted to the computer implementation.

  Figure 5.1 Algorithm as a black box

  The concept of an algorithm is illustrated by Example 1.1.1, one of the oldest known Algorithms due to Euclid (see also Chapter 3

  Sign up to read

  Learn more about book
• 

  eBook - ePub

  Teaching Mathematics in Grades 6 - 12

  Developing Research-Based Instructional Practices

  • Randall E. Groth(Author)
  • 2012(Publication Date)
  • SAGE Publications, Inc

    (Publisher)

  Numerical thinking is often associated with performing computations, but its scope is really much broader. In their numerical work, mathematicians also engage in activities such as looking for patterns, making and testing conjectures, and visualizing quantities (Cuoco, Goldenberg, & Mark, 1996). To help students develop numerical habits of mind similar to those of mathematicians, it is imperative for the curriculum to include much more than just numerical computation. Additional aspects of numerical thinking to be explored in this chapter include number sense and estimation, proportional reasoning, understanding generalizations of arithmetic, working with number systems and number theory, understanding vectors and matrices, and combinatorial thinking.

  Algorithmic Thinking

  Advantages of Algorithms

  Usiskin (1998) defined an algorithm as a “finite, step-by-step procedure for accomplishing a task that we wish to complete” (p. 7). Students encounter many Algorithms as they progress through school. Those for long division, multidigit multiplication, and solving linear equations are among the most common. School curricula have favored teaching Algorithms largely because they are powerful, reliable, accurate, and fast (Usiskin, 1998). Once an algorithm for performing a mathematical task is known, it can be performed with minimum effort. Algorithms form an important part of the infrastructure of mathematics because they provide tools that are essential for handling tasks that would otherwise be more difficult and time-consuming (Wu, 1999a).

  Pedagogical Difficulties with Algorithms

  Despite the power and advantages of Algorithms, it is necessary to proceed with caution when teaching them. Usiskin (1998) warned that students sometimes blindly accept the results of Algorithms or apply them overzealously. Blind acceptance of results is detrimental when students think they have performed all the steps in the algorithm correctly, but have actually taken a misstep to produce an unreasonable answer. For example, students who have learned the conventional “Count the number of digits after the decimal point” algorithm for decimal multiplication may misapply it in a task such as placing the decimal point on the right side of the equation 356 × 2.30 = 8,188. Counting that there are two digits after the decimal point on the left side of the equation may lead students to produce the unreasonable answer 81.88. Students often trust their application of the algorithm to such an extent that they do not pause to realize that multiplying 356 by a number slightly larger than 2 should not decrease its size to 81.88. Overzealous application occurs when students use a complicated algorithm to perform a task that would be simpler to do using other means. Examples of overzealous application include using long division for a problem such as 11 ÷ 2 and using invert-and-multiply for ½ ÷ 2. Each division problem can be solved more quickly and efficiently if students understand the sizes of the numbers involved and the meaning of performing division.

  Sign up to read

  Learn more about book
• 

  eBook - ePub

  Companion Encyclopedia of the History and Philosophy of the Mathematical Sciences

  Volume One

  • Ivor Grattan-Guiness(Author)
  • 2004(Publication Date)
  • Routledge

    (Publisher)

  Designing Algorithms, proving their correctness, searching for Algorithms which solve problems in a small number of steps and with high accuracy, searching for instruments and machines to execute the individual steps of Algorithms, transforming objects into other sorts of objects more suitable for a particular algorithm (coding) and, last but not least, searching for proofs of the impossibility of solving problems by special sorts of Algorithms - most of these procedures have assumed a central place within mathematics, but sometimes they were displaced by an excessively deductive view of mathematics (‘the only aim of mathematics is to prove difficult and beautiful theorems’). However, in the twentieth century a general definition of the notion of an algorithm has been given, and general explicit studies of this notion have been made. The computer is a relatively new but superb instrument for executing Algorithms, so it is quite natural that the questions about problems and Algorithms listed above should once again return to the centre stage of mathematics.

  2 DEVELOPMENT OF COMMUNICATION TECHNIQUES FOR Algorithms

  An important problem, which nevertheless has been explicitly studied only in the twentieth century, is the development of linguistic means for the formulation and communication of Algorithms. The first to use letters as variables (better, ‘addresses’) for given and required quantities was Jordanus de Nemore in his treatise De numeris datis (circa 1200), but this had little influence (§2.3); the next was François Viète (second half of the sixteenth century), whose work was of lasting influence (§6.9). Before then, Algorithms could in general be communicated only by instructive numerical examples. (So it was also with the Egyptians and Babylonians, as well as medieval mathematicians.)

  Occasionally there have been attempts to formulate general rules, using several techniques which we now may characterize as ‘hidden addresses’. Those quantities about to be joined by an operation were named according to their specific mathematical context (e.g. produce the new ‘denominator’ by multiplying the ‘denominator of the first and the second fraction’), or the stage of the calculation at which they appear (e.g. add the ‘number given in the beginning’ to the ‘last computed number’), or how they were being computed (e.g. add the two ‘square roots’). Especially remarkable is the ancient Chinese ‘Computational Prescriptions in Nine Chapters (Jiuzhang suanshu)’, in which addresses for the purpose of formulating general rules are taken from an example treated before (§1.9). For instance, the ‘Gaussian algorithm’ for solving three linear equations with three unknowns is explained in terms of an example by denoting the unknowns as ‘sheaf of a good harvest’, ‘sheaf of an average harvest’ and ‘sheaf of a poor harvest’. In a similar manner, Leonardo of Pisa in his famous Liber abbaci

  Sign up to read

  Learn more about book
• 

  eBook - ePub

  C Programming

  Learn to Code

  • Sisir Kumar Jena(Author)
  • 2021(Publication Date)
  • Chapman and Hall/CRC

    (Publisher)

  Section 3.5 will introduce the concept of programming and the different components involved in executing them.

  3.3 Algorithm Design

  Before we jump into the definition of an algorithm, let us look at the image shown in Figure 3.3 . We have taken this image from a cook book by Sanjeev Kapoor. The objective of using this image is to introduce you to different features of an algorithm. We are not here to learn cooking; instead, the picture will help you to understand how to write unambiguous statements in making a recipe. The procedure written in the image has a high resemblance to algorithm design.

  Figure 3.3 A cooking recipe.

  If you analyze the recipe, you can easily see that the steps are well written, and whoever follows the steps will able to cook a tasty “crisp pohe”. No actions are ambiguous, and the procedure mentions all the ingredients required to prepare the recipe. We can say that the method specified in the image is a step-by-step method to make the food, and the ingredients are known as the input for processing. Finally, the “crisp pohe” will be the output of this process.

  Now we are ready to explain the algorithm. By following the similar analogy discussed above, we can define an algorithm as follows:

  An algorithm is a sequence of unambiguous instructions for solving a problem in a finite amount of time.

  According to the programmer’s perspective, we write the algorithm to solve a given programming task that can easily be converted into a program statement irrespective of any programming language. For example, let the job be to add two numbers; then how do we write an algorithm for that? Following the problem-solving technique, we need to analyze and identify the input to our algorithm and what should be the output produced by it. In our case, the algorithm needs two numbers, and it will provide their addition as the result. After that, we need to write the step-by-step procedure to perform the addition operation. Every step must instruct the computer to do something, and upon completion of all the steps, the machine should produce the required result. The complete algorithm to solve the addition of two numbers will be discussed in the subsequent section.

  Sign up to read

  Learn more about book
• 

  eBook - ePub

  Philosophy of Computer Science

  An Introduction to the Issues and the Literature

  • William J. Rapaport(Author)
  • 2023(Publication Date)
  • Wiley-Blackwell

    (Publisher)

  16 .

  Knuth

  Donald Knuth goes into considerably more detail, albeit still informally (Knuth, 1973 , “Basic Concepts: Section 1.1 : Algorithms,” pp. xiv–9, esp. pp. 1–9). He says that an algorithm is “a finite set of rules which gives a sequence of operations for solving a specific type of problem,” with “five important features” (Knuth, 1973 , p. 4):

  1) Finiteness. An algorithm must always terminate after a finite number of steps. (Knuth, 1973 , p. 4)

  Note the double finiteness: a finite number of rules in the text of the algorithm and a finite number of steps to be carried out. Moreover, Algorithms must halt. (Halting is not guaranteed by finiteness; see point 5.)

  Interestingly, Knuth also says that an algorithm is a finite “computational method,” where a “computational method,” more generally, is a “procedure,” which only has the next four features (Knuth, 1973 , p. 4).12

  2) Definiteness. Each step … must be precisely defined; the actions to be carried out must be rigorously and unambiguously specified …” (Knuth, 1973 , p. 5).

  This seems to be Knuth's analogue of the “precision” that Rosser and Markov mention. The best examples often come from the humor that they engender:

  Precision: In a “Zits” comic strip from 14 March 2009, teenage Jeremy's mother hands him his laundered clothes, saying “Take these clothes. Carry them in your hands and walk in that direction until you come to the stairs. Make a right turn. Walk up 22 steps. Turn right, and then enter the first room you come to. Put the clothes somewhere within those four walls.” Her husband comments, “You don't leave a lot of room for interpretation, do you?” to which she replies, “After picking up several tons of laundry off that stairway, I've learned to be specific.” (We'll return to this example in Section 10.5 and to this issue in Section 16.7

  Sign up to read

  Learn more about book