## Posts Tagged 'Algorithms'

### Kalman Filters: from the Moon to the Motorway

Before too long, we will be relieved of the burden of long-distance driving. Given the desired destination and access to a mapping system, electronic algorithms will select the best route and control the autonomous vehicle, constantly monitoring and adjusting its direction and speed of travel. The origins of the methods used for autonomous navigation lie in the early 1960s, when the space race triggered by the Russian launch of Sputnik I was raging  [TM214 or search for “thatsmaths” at irishtimes.com].

### Hanoi Graphs and Sierpinski’s Triangle

The Tower of Hanoi is a famous mathematical puzzle. A set of disks of different sizes are stacked like a cone on one of three rods, and the challenge is to move them onto another rod while respecting strict constraints:

• Only one disk can be moved at a time.
• No disk can be placed upon a smaller one.

Tower of Hanoi [image Wikimedia Commons].

Continue reading ‘Hanoi Graphs and Sierpinski’s Triangle’

### Complexity: are easily-checked problems also easily solved?

From the name of the Persian polymath Al Khwarizmi, who flourished in the early ninth century, comes the term algorithm. An algorithm is a set of simple steps that lead to the solution of a problem. An everyday example is a baking recipe, with instructions on what to do with ingredients (input) to produce a cake (output). For a computer algorithm, the inputs are the known numerical quantities and the output is the required solution [TM204 or search for “thatsmaths” at irishtimes.com].

Al Khwarizmi, Persian polymath (c. 780 – 850) [image, courtesy of Prof. Irfan Shahid].

### On what Weekday is Christmas? Use the Doomsday Rule

An old nursery rhyme begins “Monday’s child is fair of face / Tuesday’s child is full of grace”. Perhaps character and personality were determined by the weekday of birth. More likely, the rhyme was to help children learn the days of the week. But how can we determine the day on which we were born without the aid of computers or calendars? Is there an algorithm – a recipe or rule – giving the answer? [TM201 or search for “thatsmaths” at irishtimes.com].

### The Monte-Carlo Method

Learning calculus at school, we soon find out that while differentiation is relatively easy, at least for simple functions, integration is hard. So hard indeed that, in many cases, it is impossible to find a nice function that is the integral (or anti-derivative) of a given one. Thus, given ${f(x)}$ we can usually find ${d f /d x}$, whereas we may not be able to find ${\int f(x)\,d x}$.

### The Mathematics of Fair Play in Video Games

Video games generate worldwide annual sales of about \$150 billion. With millions of people confined at home with time to spare, the current pandemic may benefit the industry. At the core of a video game is a computer program capable of simulating a range of phenomena in the real world or in a fantasy universe, of generating realistic imagery and of responding to the actions and reactions of the players. At every level, mathematics is crucial [TM184 or search for “thatsmaths” at irishtimes.com].

League of Legends, from Riot Games.

### Having your Christmas Cake and Eating it

As Christmas approaches, the question of fair sharing comes into focus. Readers can rejoice that there has been a recent breakthrough in cake-cutting theory. Cake cutting may sound limited, but it is important for many practical problems. A cake is a metaphor for a parcel of land to be divided, broadcast frequencies to be allocated, divorce settlements, chores to be done by flatmates, border resolutions or any other valuable or scarce resource to be shared  [TM177 or search for “thatsmaths” at irishtimes.com].

### Airport Baggage Screening with X-Ray Tomography

When you check in your baggage for a flight, it must be screened before it is allowed on the plane. Baggage screening detects threats within luggage and personal belongings by x-ray analysis as they pass along a conveyor belt. Hold-baggage and passenger screening systems are capable of detecting contraband materials, narcotics, explosives and weapons [TM175 or search for “thatsmaths” at irishtimes.com].

3D X-ray image of baggage [image from Rapiscan Systems ].

### Emergence of Complex Behaviour from Simple Roots

It is exhilarating to watch a large flock of birds swarming in ever-changing patterns. Swarming is an emergent behaviour, resulting from a set of simple rules followed by each individual animal, bird or fish, without any centralized control or leadership.

A murmuration of starlings at dusk near Ballywilliam, Co Wexford. Photograph: Cyril Byrne.

### ToplDice is Markovian

Many problems in probability are solved by assuming independence of separate experiments. When we toss a coin, it is assumed that the outcome does not depend on the results of previous tosses. Similarly, each cast of a die is assumed to be independent of previous casts.

However, this assumption is frequently invalid. Draw a card from a shuffled deck and reveal it. Then place it on the bottom and draw another card. The odds have changed: if the first card was an ace, the chances that the second is also an ace have diminished.

### Algorithms: Recipes for Success

The impact of computing on society is ever-increasing. Web-based commerce continues to grow and artificial intelligence now pervades our lives. To make wise choices, we need to understand how computers operate and how we can deploy them most constructively. Listen to any computer scientist and soon you will hear the word “algorithm” [TM168 or search for “thatsmaths” at irishtimes.com].

### Cumbersome Calculations in Ancient Rome

Typus Arithmeticae” is a woodcut from the book Margarita Philosophica by Gregor Reisch of Freiburg, published in 1503. In the centre of the figure stands Arithmetica, the muse of mathematics. She is watching a competition between the Roman mathematician Boethius and the great Pythagoras. Boethius is crunching out a calculation using Hindu-Arabic numerals, while Pythagoras uses a counting board or abacus (tabula) and – presumably – a less convenient number system. Arithmetica is looking with favour towards Boethius. He smiles smugly while Pythagoras is looking decidedly glum.

The figure aims to show the superiority of the Hindu-Arabic number system over the older Greek and Roman number systems. Of course, it is completely anachronistic: Pythagoras flourished around 500 BC and Boethius around AD 500, while the Hindu-Arabic numbers did not arrive in Europe until after AD 1200.

### Simple Curves that Perplex Mathematicians and Inspire Artists

The preoccupations of mathematicians can seem curious and strange to normal people. They sometimes expend great energy proving results that appear glaringly obvious. One such result is called the Jordan Curve Theorem. We all know that a circle has an inside and an outside, and that this property also holds for a much larger collection of closed curves [TM165 or search for “thatsmaths” at irishtimes.com].

Detail from Michaelangelo’s The Creation of Adam, and a Jordan Curve representation [image courtesy of Prof Robert Bosch, Oberlin College. Downloaded from here].

### Bouncing Billiard Balls Produce Pi

There are many ways of evaluating ${\pi}$, the ratio of the circumference of a circle to its diameter. We review several historical methods and describe a recently-discovered and completely original and ingenious method.

### Multiple Discoveries of the Thue-Morse Sequence

It is common practice in science to name important advances after the first discoverer or inventor. However, this process often goes awry. A humorous principle called Stigler’s Law holds that no scientific result is named after its original discoverer. This law was formulated by Professor Stephen Stigler of the University of Chicago in his publication “Stigler’s law of eponymy”. He pointed out that his “law” had been proposed by others before him so it was, in a sense, self-verifying. [TM157 or search for “thatsmaths” at irishtimes.com].

Continue reading ‘Multiple Discoveries of the Thue-Morse Sequence’

### Consider a Spherical Christmas Tree

A minor seasonal challenge is how to distribute the fairy lights evenly around the tree, with no large gaps or local clusters. Since the lights are strung on a wire, we are not free to place them individually but must weave them around the branches, attempting to achieve a pleasing arrangement. Optimization problems like this occur throughout applied mathematics [TM153 or search for “thatsmaths” at irishtimes.com].

Trees are approximately conical in shape and we may assume that the lights are confined to the surface of a cone. The peak, where the Christmas star is placed, is a mathematical singularity: all the straight lines that can be drawn on the cone, the so-called generators, pass through this point. Cones are developable surfaces: they can be flattened out into a plane without being stretched or shrunk.

### Face Recognition

As you pass through an airport, you are photographed several times by security systems. Face recognition systems can identify you by comparing your digital image to faces stored in a database. This form of identification is gaining popularity, allowing you to access online banking without a PIN or password.  [see TM146, or search for “thatsmaths” at irishtimes.com].

Jimmy Wales, co-founder of Wikipedia, answering a question. Face detection indicated by squares.

### Stan Ulam, a mathematician who figured how to initiate fusion

Stanislaw Ulam, born in Poland in 1909, was a key member of the remarkable Lvov School of Mathematics, which flourished in that city between the two world wars. Ulam studied mathematics at the Lvov Polytechnic Institute, getting his PhD in 1933. His original research was in abstract mathematics, but he later became interested in a wide range of applications. He once joked that he was “a pure mathematician who had sunk so low that his latest paper actually contained numbers with decimal points” [TM138 or search for “thatsmaths” at irishtimes.com].

Operation Castle, Bikini Atoll, 1954

### Staying Put or Going with the Flow

The atmospheric temperature at a fixed spot may change in two ways. First, heat sources or sinks may increase or decrease the thermal energy; for example, sunshine may warm the air or radiation at night may cool it. Second, warmer or cooler air may be transported to the spot by the air flow in a process called advection. Normally, the two mechanisms act together, sometimes negating and sometimes reinforcing each other. What is true for temperature is also true for other quantities: pressure, density, humidity and even the flow velocity itself. This last effect may be described by saying that “the wind blows the wind” [TM132 or search for “thatsmaths” at irishtimes.com].

Hurricane Ophelia approaching Ireland, 16 October 2017, 1200Z. Image from https://earth.nullschool.net/

### Andrey Markov’s Brilliant Ideas are still a Driving Force

A A Markov (1856-1922)

Imagine examining the first 20,000 letters of a book, counting frequencies and studying patterns. This is precisely what Andrey Markov did when he analyzed the text of Alexander Pushkin’s verse novel Eugene Onegin. This work comprises almost 400 stanzas of iambic tetrameter and is a classic of Russian literature. Markov studied the way vowels and consonants alternate and deduced the probabilities of a vowel being followed by a another vowel, by a consonant, and so on. He was applying a statistical model that he had developed in 1906 and that we now call a Markov Process or Markov chain. [TM123 or search for “thatsmaths” at irishtimes.com].

### Drawing Multi-focal Ellipses: The Gardener’s Method

Common-or-Garden Ellipses

In an earlier post we saw how a gardener may set out oval flower-beds using a well-known property of ellipses: the sum of the distances from any point on the ellipse to the two foci is always the same value, ${2a}$, the length of the major axis. The gardener puts down two stakes and loops a piece of rope around them. Using a stick, he pulls the loop taut, marking the points around a curve. This is illustrated here.

Gardener’s method of drawing an ellipse [Image Wikimedia].

Continue reading ‘Drawing Multi-focal Ellipses: The Gardener’s Method’

### Locating the HQ with Multi-focal Ellipses

Motivation

Ireland has four provinces, the principal city in each being the provincial capital: Belfast, Cork, Dublin and Galway. The map here shows the location of these cities. Now imagine a company that needs to visit and to deliver goods frequently to all four cities. Where might they locate their HQ to minimize transport costs and travel times?

One possibility is to find the location with the smallest distance sum:

$\displaystyle d(\mathbf{r}_0) = \sum_{j=1}^{4} |\mathbf{r}_0-\mathbf{p}_j|$

where ${\mathbf{r}_0}$ is the position of the HQ and ${\mathbf{p}_j, j\in\{1,2,3,4\}}$ are the positions of the cities.

### Fractal Complexity of Finnegans Wake

Tomorrow we celebrate Bloomsday, the day of action in Ulysses. Most of us regard Joyce’s singular book as a masterpiece, even if we have not read it. In contrast, Finnegans Wake is considered by some as a work of exceptional genius, by others as impenetrable bafflegab [See TM117 or search for “thatsmaths” at irishtimes.com].

Wavelet transform of sentence length sequence in Ulysses. Note the structural change around sentence number 13,000. Image from Drozdz, et al (2016).

### When Roughly Right is Good Enough

How high is Liberty Hall? How fast does human hair grow? How many A4 sheets of paper would cover Ireland? How many people in the world are talking on their mobile phones right now? These questions seem impossible to answer but, using basic knowledge and simple logic, we can make a good guess at the answers. For example, Liberty Hall has about 16 floors. With 4 metres per floor we get a height of 64 metres, close enough to the actual height. Problems of this nature are known as Fermi problems. [TM114 or search for “thatsmaths” at irishtimes.com].

### Voronoi Diagrams: Simple but Powerful

We frequently need to find the nearest hospital, surgery or supermarket. A map divided into cells, each cell covering the region closest to a particular centre, can assist us in our quest. Such a map is called a Voronoi diagram, named for Georgy Voronoi, a mathematician born in Ukraine in 1868. He is remembered today mostly for his diagram, also known as a Voronoi tessellation, decomposition, or partition. [TM108 or search for “thatsmaths” at irishtimes.com].

Voronoi diagram drawn using the applet of Paul Chew (see Sources below).

### The Shaky Foundations of Mathematics

The claim is often made that mathematical results are immutable. Once proven, they remain forever valid. But things are not so simple. There are problems at the very core of mathematics that cast a shadow of uncertainty. We can never be absolutely sure that the foundations of our subject are rock-solid [TM104 or search for “thatsmaths” at irishtimes.com].

Left: Plato and Aristotle. Centre: Pythagoras. Right: Euclid [Raphael, The School of Athens]

The ancient Greeks put geometry on a firm footing. Euclid set down a list of axioms, or basic intuitive assumptions. Upon these, the entire edifice of Euclidean geometry is constructed. This axiomatic approach has been the model for mathematics ever since.

### A Toy Example of RSA Encryption

The RSA system has been presented many times, following the excellent expository article of Martin Gardner in the August 1977 issue of Scientific American. There is no need for yet another explanation of the system; the essentials are contained in the Wikipedia article RSA (cryptosystem), and in many other articles.

The purpose of this note is to give an example of the method using numbers so small that the computations can easily be carried through by mental arithmetic or with a simple calculator.

### Can Mathematics Keep Us Secure?

The National Security Agency is the largest employer of mathematicians in America. Mathematics is a core discipline at NSA and mathematicians work on signals intelligence and information security (US citizenship is a requirement for employment). Why is NSA so interested in mathematics? [See TM096, or search for “thatsmaths” at irishtimes.com].

Flag of the National Security Agency

### Lateral Thinking in Mathematics

Many problems in mathematics that appear difficult to solve turn out to be remarkably simple when looked at from a new perspective. George Pólya, a Hungarian-born mathematician, wrote a popular book, How to Solve It, in which he discussed the benefits of attacking problems from a variety of angles [see TM094, or search for “thatsmaths” at irishtimes.com].

### Big Data: the Information Explosion

The world is awash with data. Large data sets have been available for many decades but in recent years their volumes have grown explosively. With mobile devices and internet connections data capture is simple and with powerful computers the analysis of “big data” is feasible [see TM092, or search for “thatsmaths” at irishtimes.com].

Google image search for “Big Data”

But there are challenges: many data sets are too large and too complex to be analysed or understood using traditional data processing methods. Our current armoury of analysis techniques is inadequate and new mathematical methods are needed.

### Computus: Dating the Resurrection

Whatever the weather, St Patrick’s Day occurs on the same date every year. In contrast, Easter springs back and forth in an apparently chaotic manner. The date on which the Resurrection is celebrated is determined by a complicated convolution of astronomy, mathematics and theology, an algorithm or recipe that fixes the date in accordance with the motions of the Sun and Moon [TM087, or search for “thatsmaths” at irishtimes.com].

Iona Abbey, the last Celtic monastery to hold out against  Easter reform [Image Wikimedia Commons]

### Peano Music

The links between mathematics and music are manifold. Mathematics can be set to music in a simple but surprising manner. For the award ceremony of the Gödel Medal in 2014, a musical interpretation of Gödel’s incompleteness Theorems was written by Danish composer Niels Marthinsen. It encodes the basic axioms of number theory that form the focus of Gödel’s Theorems.

The Peano Axioms in symbolic form.

### The Mathematics of Voting

Selection of leaders by voting has a history reaching back to the Athenian democracy. Elections are essentially arithmetical exercises, but they involve more than simple counting, and have some subtle mathematical aspects [TM085, or search for “thatsmaths” at irishtimes.com].

Rock-paper-scissors, a zero-sum game. There is a cyclic relationship: rock beats paper, paper beats scissors and scissors beats rock [Image: Wikimedia Commons].

### Prime Number Record Smashed Again

Once again the record for the largest prime number has been shattered. As with all recent records, the new number is a Mersenne prime, a number of the form

Mp = 2p 1

where p itself is a prime. Participants in a distributed computing project called GIMPS (Great Internet Mersenne Prime Search) continue without rest to search for ever-larger primes of this form.

Most of the recent large primes have been found in the GIMPS project (for an earlier post on GIMPS, click Mersennery Quest. The project uses a search algorithm called the Lucas-Lehmer primality test, which is particularly suitable for finding Mersenne primes. The test, which was originally devised by Edouard Lucas in the nineenth century and extended by Derek Lehmer in 1930, is very efficient on binary computers.

### Entropy Piano Tuning

An ingenious method of tuning pianos, based on the concept of entropy, has recently been devised by Haye Hinrichsen of Würzburg University. Entropy, which first appeared in the mid-nineteenth century in thermodynamics and later in statistical mechanics, is a measure of disorder. Around 1948 Claude Shannon developed a mathematical theory of communications and used entropy as an indicator of information content [TM084, or search for “thatsmaths” at irishtimes.com].

Tuning curve showing the stretch for high and low notes (Image: Wikimedia Commons).

### New Tricks: No Clicks

The readable surface of a Compact Disc has a spiral track over 5 km in length.

The quality of music recordings on compact discs or CDs is excellent. In the age of vinyl records, irritating clicks resulting from surface scratches were almost impossible to avoid. Modern recording media are largely free from this shortcoming. But this is curious: there are many reasons why CD music can be contaminated: dirt on the disc surface, flaws in the plastic substrate, errors in burning on the recording, scratches and fingerprints, and so on [TM077; or search for “thatsmaths” at irishtimes.com ]

### Hamming’s Smart Error-correcting Codes

Richard Hamming (1915 – 1998)

In the late 1940s, Richard Hamming, working at Bell Labs, was exasperated with the high level of errors occurring in the electro-mechanical computing equipment he was using. Punched card machines were constantly misreading, forcing him to restart his programs. He decided to do something about it. This was when error-correcting codes were invented.

A simple way to detect errors is to send a message twice. If both versions agree, they are probably correct; if not, there is an error somewhere. But the discrepancy gives us no clue where the error lies. Sensing the message three times is better: if two versions agree, we assume they are correct and ignore the third version. But there is a serious overhead: the total data transmitted is three times the data volume; the information factor is 1/3.

### Buffon was no Buffoon

The Buffon Needle method of estimating ${\pi}$ is hopelessly inefficient. With one million throws of the needle we might expect to get an approximation accurate to about three digits. The idea is more of philosophical than of practical interest. Buffon never envisaged it as a means of computing ${\pi}$.

Image drawn with Mathematica package in: Siniksaran, Erin, 2008: Throwing Buffon’s Needle [Reference below].

Continue reading ‘Buffon was no Buffoon’

### The Bridges of Paris

Leonhard Euler considered a problem known as The Seven Bridges of Königsberg. It involves a walk around the city now known as Kaliningrad, in the Russian exclave between Poland and Lithuania. Since Kaliningrad is out of the way for most of us, let’s have a look closer to home, at the bridges of Paris. [TM073: search for “thatsmaths” at irishtimes.com ]

### Who Needs EirCode?

The idea of using two numbers to identify a position on the Earth’s surface is very old. The Greek astronomer Hipparchus (190–120 BC) was the first to specify location using latitude and longitude. However, while latitude could be measured relatively easily, the accurate determination of longitude was more difficult, especially for sailors out of site of land.

OSi Mapviewer. XY coordinates indicated at bottom left.

French philosopher, scientist and mathematician René Descartes demonstrated the power of coordinates and his method of algebraic geometry revolutionized mathematics. It had a profound, unifying effect on pure mathematics and greatly increased the ability of maths to model the physical world.

### Game Theory & Nash Equilibrium

Game theory deals with mathematical models of situations involving conflict, cooperation and competition. Such situations are central in the social and behavioural sciences. Game Theory is a framework for making rational decisions in many fields: economics, political science, psychology, computer science and biology. It is also used in industry, for decisions on manufacturing, distribution, consumption, pricing, salaries, etc.

Theory of Games and Economic Behavior.
Centre: John von Neumann. Right: Oskar Morgenstern.

During the Cold War, Game Theory was the basis for many decisions concerning nuclear strategy that affected the well-being of the entire human race.

### The Tragic Demise of a Beautiful Mind

John Nash, who was the subject of the book and film A Beautiful Mind, won the Abel Prize recently. But his journey home from the award ceremony in Norway ended in tragedy [see this week’s That’s Maths column (TM069): search for “thatsmaths” at irishtimes.com].

Russell Crowe as John Nash in the movie A Beautiful Mind.

### Modelling the Markets

Mathematics now plays a fundamental role in modelling market movements [see this week’s That’s Maths column (TM067) or search for “thatsmaths” at irishtimes.com].

Dow-Jones Industrial Average for the Flash-Crash on 6 May 2010.
Graphic adapted from Sunday Times, 26 April, 2015.

### The Steiner Minimal Tree

Steiner’s minimal tree problem is this: Find the shortest possible network interconnecting a set of points in the Euclidean plane. If the points are linked directly to each other by straight line segments, we obtain the minimal spanning tree. But Steiner’s problem allows for additional points – now called Steiner points – to be added to the network, yielding Steiner’s minimal tree. This generally results in a reduction of the overall length of the network.

A solution of Steiner 5-point problem with soap film [from Courant and Robbins].

Continue reading ‘The Steiner Minimal Tree’

### Plateau’s Problem and Double Bubbles

Bubbles floating in the air strive to achieve a spherical form. Large bubbles may oscillate widely about this ideal whereas small bubbles quickly achieve their equilibrium shape. The sphere is optimal: it encloses maximum volume for any surface of a given area. This was stated by Archimedes, but he did not have the mathematical techniques required to prove it. It was only in the late 1800s that a formal proof of optimality was completed by Hermann Schwarz [Schwarz, 1884].

Computer-generated double bubble

### Barcodes and QR Codes: Zebra stripes and Leopard spots

Barcodes and QR codes are described in this week’s That’s Maths column in The Irish Times (TM060, or search for “thatsmaths” at irishtimes.com).

EAN-13 barcode.

### Information Theory

That’s Maths in The Irish Times this week (TM059, or Search for “thatsmaths” at irishtimes.com) is about data compression and its uses in modern technology.

Left: An equation form Shannon (1948), the paper that launched Information Theory.

### The Year of George Boole

This week’s That’s Maths column in The Irish Times (TM058, or search for “thatsmaths” at irishtimes.com) is about George Boole, the first Professor of Mathematics at Queen’s College Cork.

### Sunflowers and Fibonacci: Models of Efficiency

The article in this week’s That’s Maths column in The Irish Times ( TM046 ) is about the maths behind the efficient packing of sunflowers and many other plants

Strolling along Baggot Street in Dublin recently, I noticed a plaque at the entrance to the Ibec head office. It showed a circular pattern of dots, reminiscent of the head of a sunflower. According to the Ibec website, “The spiral motif brings dynamism … and hints at Ibec’s member-centric ethos.” Wonderful! In fact, the pattern in the logo is vastly more interesting than this. Continue reading ‘Sunflowers and Fibonacci: Models of Efficiency’

### The Chaos Game

The term “Chaos Game” was coined by Michael Barnsley [1], who developed this ingenious technique for generating mathematical objects called fractals. We have discussed a particular fractal set on this blog: see Cantor’s Ternary Set.

The Chaos Game is a simple algorithm that identifies one point in the plane at each stage. The sets of points that ultimately emerge from the procedure are remarkable for their intricate structure. The relationship between the algorithm and fractal sets is not at all obvious, as there is no evident connection between them. This element of surprise is of one of the delights of mathematics.