Algorithms | ThatsMaths

Posts Tagged 'Algorithms'

Weather Warnings in Glorious Technicolor

Published February 16, 2023 Irish Times Closed
Tags: Algorithms, Geophysics

Severe weather affects us all and we need to know when to take action to protect ourselves and our property. We have become familiar with the colourful spectrum of warnings issued by Met Éireann.

For several years, Met Éireann has issued warnings of extreme weather. These depend on the severity of the meteorological event and the level of confidence in the forecast. They are formulated using forecasts produced by computer, algorithms that determine the likely impacts of extreme weather, and the expertise of the forecasters [TM242 or search for “thatsmaths” at irishtimes.com]. Continue reading ‘Weather Warnings in Glorious Technicolor’

The Power of the 2-gon: Extrapolation to Evaluate Pi

Published November 3, 2022 Occasional Closed
Tags: Algorithms, Numerical Analysis, Pi

Lewis Fry Richardson

Richardson’s extrapolation procedure yields a significant increase in the accuracy of numerical solutions of differential equations. We consider his elegant illustration of the technique, the evaluation of ${\pi}$ , and show how the estimates improve dramatically with higher order extrapolation.

[This post is a condensed version of a paper in Mathematics Today (Lynch, 2003).]

Continue reading ‘The Power of the 2-gon: Extrapolation to Evaluate Pi’

Making Sound Pictures to Identify Bird Songs

Published September 15, 2022 Irish Times Closed
Tags: Algorithms, Fourier analysis

Top: Audio signal with three chirps. Bottom: Time-Frequency spectrogram of signal.

A trained musician can look at a musical score and imagine the sound of an entire orchestra. The score is a visual representation of the sounds. In an analogous way, we can represent birdsong by an image, and analysis of the image can tell us the species of bird singing. This is what happens with Merlin Bird ID. In a recent episode of Mooney Goes Wild, Niall Hatch of Birdwatch Ireland interviewed Drew Weber of the Cornell Lab of Ornithology, a developer of Merlin Bird ID. This phone app enables a large number of birds to be identified [TM237 or search for “thatsmaths” at irishtimes.com].

Continue reading ‘Making Sound Pictures to Identify Bird Songs’

Why Waffle when One Wordle Do?

Published February 24, 2022 Occasional Closed
Tags: Algorithms, Recreational Maths

A game of Wordle solved in 3 guesses (a birdie).

Hula hoops were all the rage in 1958. Yo-yos, popular before World War II, were relaunched in the 1960s. Rubik’s Cube, invented in 1974, quickly became a global craze. Sudoku, which had been around for years, was wildly popular when it started to appear in American and European newspapers in 2004.

Continue reading ‘Why Waffle when One Wordle Do?’

Kalman Filters: from the Moon to the Motorway

Published July 1, 2021 Irish Times Closed
Tags: Algorithms

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].

Continue reading ‘Kalman Filters: from the Moon to the Motorway’

Hanoi Graphs and Sierpinski’s Triangle

Published May 27, 2021 Occasional Closed
Tags: Algorithms, Fractals, Games

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?

Published February 4, 2021 Irish Times Closed
Tags: Algorithms, Computer Science

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].

Continue reading ‘Complexity: are easily-checked problems also easily solved?’

On what Weekday is Christmas? Use the Doomsday Rule

Published December 17, 2020 Irish Times Closed
Tags: Algorithms

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].

Continue reading ‘On what Weekday is Christmas? Use the Doomsday Rule’

The Monte-Carlo Method

Published May 28, 2020 Occasional Closed
Tags: Algorithms, Numerical Analysis

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}$ .

Monte-Carlo-Wide-4panel

Continue reading ‘The Monte-Carlo Method’

The Mathematics of Fair Play in Video Games

Published April 2, 2020 Irish Times Closed
Tags: Algorithms, Games, Hamilton

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.

Continue reading ‘The Mathematics of Fair Play in Video Games’

Having your Christmas Cake and Eating it

Published December 19, 2019 Irish Times Closed
Tags: Algorithms

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].

Image from https://www.irishcentral.com/%5D

Continue reading ‘Having your Christmas Cake and Eating it’

Airport Baggage Screening with X-Ray Tomography

Published November 21, 2019 Irish Times Closed
Tags: Algorithms

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 ].

Continue reading ‘Airport Baggage Screening with X-Ray Tomography’

Emergence of Complex Behaviour from Simple Roots

Published October 3, 2019 Irish Times Closed
Tags: Algorithms, biology, Computer Science

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.

Continue reading ‘Emergence of Complex Behaviour from Simple Roots’

ToplDice is Markovian

Published August 29, 2019 Occasional Closed
Tags: Algorithms, Games, Statistics

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.

Continue reading ‘ToplDice is Markovian’

Algorithms: Recipes for Success

Published August 1, 2019 Irish Times Closed
Tags: Algorithms, Computer Science

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].

Continue reading ‘Algorithms: Recipes for Success’

Cumbersome Calculations in Ancient Rome

Published June 27, 2019 Occasional Closed
Tags: Algorithms, History

Arithmetica-Woodcut “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.

Continue reading ‘Cumbersome Calculations in Ancient Rome’

Simple Curves that Perplex Mathematicians and Inspire Artists

Published June 20, 2019 Irish Times Closed
Tags: Algorithms, Topology

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].

Continue reading ‘Simple Curves that Perplex Mathematicians and Inspire Artists’

Bouncing Billiard Balls Produce Pi

Published May 9, 2019 Occasional Closed
Tags: Algorithms, Numerical Analysis, 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.

Archimedes-Polygons

Continue reading ‘Bouncing Billiard Balls Produce Pi’

Multiple Discoveries of the Thue-Morse Sequence

Published February 21, 2019 Irish Times Closed
Tags: Algorithms, Number Theory

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].

Axel Thue (1863-1922) and Marston Morse (1892-1977)

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

Consider a Spherical Christmas Tree

Published December 20, 2018 Irish Times Closed
Tags: Algorithms, Topology

ChristmasTreeLights

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.

Continue reading ‘Consider a Spherical Christmas Tree’

Stan Ulam, a mathematician who figured how to initiate fusion

Published May 3, 2018 Irish Times Closed
Tags: Algorithms, Fluid Dynamics, Set Theory, Topology

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

Continue reading ‘Stan Ulam, a mathematician who figured how to initiate fusion’

Staying Put or Going with the Flow

Published February 1, 2018 Irish Times Closed
Tags: Algorithms, Geophysics, Numerical Analysis

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/

Continue reading ‘Staying Put or Going with the Flow’

Andrey Markov’s Brilliant Ideas are still a Driving Force

Published September 21, 2017 Irish Times Closed
Tags: Algorithms, Statistics

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].

Continue reading ‘Andrey Markov’s Brilliant Ideas are still a Driving Force’

Drawing Multi-focal Ellipses: The Gardener’s Method

Published August 31, 2017 Occasional Closed
Tags: Algorithms, Geometry

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

Published August 24, 2017 Occasional Closed
Tags: Algorithms, Geometry

Motivation

IrelandProvincialCapitalsMap 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.

Continue reading ‘Locating the HQ with Multi-focal Ellipses’

Fractal Complexity of Finnegans Wake

Published June 15, 2017 Irish Times Closed
Tags: Algorithms, Fractals

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).

Continue reading ‘Fractal Complexity of Finnegans Wake’

When Roughly Right is Good Enough

Published May 4, 2017 Irish Times Closed
Tags: Algorithms, Education

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].

Continue reading ‘When Roughly Right is Good Enough’

Voronoi Diagrams: Simple but Powerful

Published February 2, 2017 Irish Times Closed
Tags: Algorithms, Geometry

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).

Continue reading ‘Voronoi Diagrams: Simple but Powerful’

The Shaky Foundations of Mathematics

Published December 1, 2016 Irish Times Closed
Tags: Algorithms, Logic, Number Theory

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.

Continue reading ‘The Shaky Foundations of Mathematics’

A Toy Example of RSA Encryption

Published August 11, 2016 Occasional Closed
Tags: Algorithms, Computer Science

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.

L2R: Ron Rivest, Adi Shamir, Len Adleman (2003). Image from https://www.usc.edu

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.

Continue reading ‘A Toy Example of RSA Encryption’

Can Mathematics Keep Us Secure?

Published August 4, 2016 Irish Times Closed
Tags: Algorithms, Computer Science

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

Continue reading ‘Can Mathematics Keep Us Secure?’

Lateral Thinking in Mathematics

Published July 7, 2016 Irish Times Closed
Tags: Algorithms, Puzzles, Recreational Maths

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].

Continue reading ‘Lateral Thinking in Mathematics’

Big Data: the Information Explosion

Published June 2, 2016 Irish Times Closed
Tags: Algorithms, Computer Science, Graph Theory

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.

Continue reading ‘Big Data: the Information Explosion’

Computus: Dating the Resurrection

Published March 17, 2016 Irish Times Closed
Tags: Algorithms, History

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]

Continue reading ‘Computus: Dating the Resurrection’

Peano Music

Published March 10, 2016 Occasional Closed
Tags: Algorithms, Logic, 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.

Continue reading ‘Peano Music’

Prime Number Record Smashed Again

Published January 28, 2016 Occasional Closed
Tags: Algorithms, Number Theory

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

M_p = 2^p – 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.

Image from http://primes.utm.edu

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.

Continue reading ‘Prime Number Record Smashed Again’

Entropy Piano Tuning

Published January 21, 2016 Irish Times Closed
Tags: Algorithms, Music

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).

Continue reading ‘Entropy Piano Tuning’

New Tricks: No Clicks

Published October 1, 2015 Irish Times Closed
Tags: Algorithms, Computer Science

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 ]

Continue reading ‘New Tricks: No Clicks’

Hamming’s Smart Error-correcting Codes

Published September 24, 2015 Occasional Closed
Tags: Algorithms, Computer Science

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.

Continue reading ‘Hamming’s Smart Error-correcting Codes’

Buffon was no Buffoon

Published August 13, 2015 Occasional Closed
Tags: Algorithms, Probability

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

Published August 4, 2015 Irish Times Closed
Tags: Algorithms, Euler, Topology

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 ]

Continue reading ‘The Bridges of Paris’

Who Needs EirCode?

Published July 28, 2015 Occasional Closed
Tags: Algorithms, Arithmetic, Ireland

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.

Continue reading ‘Who Needs EirCode?’

Game Theory & Nash Equilibrium

Published June 11, 2015 Occasional Closed
Tags: Algorithms, Applied Maths, Computer Science, Games

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.

Continue reading ‘Game Theory & Nash Equilibrium’

The Tragic Demise of a Beautiful Mind

Published June 4, 2015 Irish Times Closed
Tags: Algorithms, Games, Number Theory

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.

Continue reading ‘The Tragic Demise of a Beautiful Mind’

Modelling the Markets

Published May 7, 2015 Irish Times Closed
Tags: Algorithms, Applied Maths, Computer Science

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 Aversge for 6 May 2010. Graphic adapted from Sunday Times, 26 April, 2015.

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

Continue reading ‘Modelling the Markets’

The Steiner Minimal Tree

Published January 29, 2015 Occasional Closed
Tags: Algebra, Algorithms, Gauss, Maps, Topology

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

Published January 22, 2015 Occasional Closed
Tags: Algorithms, Fluid Dynamics, Physics, Topology

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

Continue reading ‘Plateau’s Problem and Double Bubbles’

Barcodes and QR Codes: Zebra stripes and Leopard spots

Published January 15, 2015 Irish Times Closed
Tags: Algorithms, Computer Science

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.

Continue reading ‘Barcodes and QR Codes: Zebra stripes and Leopard spots’

Posts Tagged 'Algorithms'

Tags

Last 50 Posts

Categories

Archives