algorithm

Knapsack Problem

The knapsack problem is a problem in combinatorial optimisation.

Imagine you are going to visit your friends for whom you have bought lots of presents. So many, in fact, that you can’t fit them all in your luggage meaning you must leave some behind. If we decide to pack a combination of presents with the highest value but that doesn’t exceed the weight limit imposed by airline, how can we find such a combinations? This is the Knapsack Problem.

File:Knapsack.svg

Source: Wikipedia

We could solve this by trying all the possible combinations, calculating their value and weight and then picking one that is below the weight limit but maximises the value. Whilst this is okay when we are dealing with a small number of items, it is simply unfeasible when the number of items is large as the number of combinations is too big. So, is there an algorithm which can work for any number of items that doesn’t take too long?

Computer scientists have a way of measuring the complexity of a problem by how fast the time taken grows as the size of the input increases. Polynomial growth, i.e. if the size of the input is n then the time taken grows by a factor of n^k, describes and ‘easy problem’; the growth is nowhere near as “explosive” as  exponential growth, e.g. 2^n.

Whether or not a polynomial time algorithm exists to solve the knapsack problem is unknown, meaning it is in a class of problems called NP-Hard Problems.

Complexity classes

Source: plus.maths.org

Complexity Classes:

  • Class P: problems that can be solved in polynomial time
  • Class NP: a potential solution can be checked in polynomial time
    • NP-Complete: within the NP class but particularly hard
    • NP-Hard: as least as hard as the NP class.

It is possible that the NP class = P class, though this is still unknown (and is one of the Millennium Prize Problems), hence the two diagrams above.

M x

P.S. My posts may be more sporadic in the next month because I’m in exam term!

New Books in Maths: March 2017

Today I decided to do another instalment of my series ‘New Books in Math’, where I talk about books which have been recently released or will be released soon.

Bad Choices: How Algorithms Can Help You Think Smarter and Live Happier – Ali Almossawi

51xY50vfprL.jpg

Release Date: April 2017

Ali Almossawi, the author of the popular book Bad Arguments, has returned with a funny and smart introduction to algorithms.

This book aims to answer questions such as “why is Facebook so good at predicting music?” and “how do you discover new music?

To demystify a topic of ever increasing importance to our lives, Almossawi presents us with alternative methods for tackling twelve different scenarios, guiding us to better and more efficient choices “that borrow from same systems that underline a computer word processor, a Google search engine, or a Facebook ad”.

“Bad Choices will open the world of algorithms to all readers making this a perennial go-to for fans of quirky, accessible science books.”

Are Numbers Real?: The Uncanny Relationship of Mathematics and the Physical World – Brian Clegg

Release Date: March 2017

28220651.jpgWhat was life like before numbers existed? Numbers began as simple representations of everyday things, but mathematics rapidly took a life of its own and grew into what it is today.

In Are Numbers Real?, Brian Clegg explores the way that maths has become more and more detached from reality, but yet remains the driving force of the development of modern physics.

“From devising a new counting system based on goats, through the weird and wonderful mathematics of imaginary numbers and infinity to the debate over whether mathematics has too much influence on the direction of science, this fascinating and accessible book opens the reader’s eyes to the hidden reality of the strange yet familiar world of numbers.”

The Mathematics Lover’s Companion: Masterpieces for Everyone – Edward R. Scheinerman

51879845.jpg

Release Date: March 2017

How can a shape have more than one dimension but fewer than two? What is the best way to elect public officials when more than two candidates are vying for the office? Is it possible for a highly accurate medical test to give mostly incorrect results? Can you tile your floor with regular pentagons? How can you use only the first digit of sales numbers to determine if your accountant is lying? Can mathematics give insights into free will?

Edward Scheinerman answers these questions and more in The Mathematics Lover’s Companion, in bite-size chapters that require only secondary school mathematics. He invites readers to get involved in solving mathematical puzzles, and provides an engaging tour of numbers, shapes and uncertainty.

The result is an unforgettable introduction to the fundamentals and pleasures of thinking mathematically.

M x

 

 

 

Mazes

What’s the difference between a maze and a labyrinth?

It is generally accepted that a labyrinth contains only one path, which often spirals around folding back in on itself in ever-decreasing loops. On the other hand, a maze contains branching paths, which lead to nowhere, and therefore present the person with choices and the potential for them to get lost.

Mathematicians have created maze-generating algorithms, which tend to fall into two main types:

  • Ones that start with a single bounded space and then sub-divide it with walls to produce smaller sub-spaces;
  • Ones that start with a bunch of disconnected rooms and then demolish walls to create paths between them.

Escaping Mazes

Most methods work for ‘simple mazes’, i.e. mazes with no short-cuts via bridges or passage loops (circular paths that lead back to where they started).

So, if we assume the maze is simple, the most common method to escape the maze is wall-following. Here, you place a hand on the wall of the maze, keep walking maintaining contact with the wall and eventually you will get out.

Why does this work? If you imagine picking the wall of the maze and stretching its perimeter to remove any corners. You will eventually create a circle-like shape, which must form part of the maze’s outer border.

Trémaux’s Algorithm

The problem is that most mazes aren’t simple, for example the Escot Gardens’ beech hedge maze in Devon.

Beech Hedge Maze in Devon | lotstodo.co.uk

So, another method of maze escape is known as Trémaux’s algorithm, which works is all cases.

Here’s how it works. Basically, with this algorithm, you leave a trail as you navigate your way through the maze. Then follow these rules:

  • If you arrive at a junction you have not previously encountered, randomly select a way to go;
  • If that leads you to a junction where one path is new but the other is not, select the path you have not been on;
  • If you are choosing between a once or twice-used path, choose the path that has only be used once, then leave a second trail behind you;
  • Never select a path that already has two trails.

This method works for all mazes and is guaranteed to get you out!

M x

The Maths of Facebook

Everyday millions of users will spend a quarter of their time on Facebook scrolling mindlessly through their Newsfeed. The Newsfeed, arguably the most important part of the site, is controlled by a unique algorithm called the ‘Edgerank’ algorithm. In this post, I’ll talk you through what this is and how it works.

What is it?

Edgerank is the algorithm that dictates what stories appear on a users Newsfeed. Say you are a Facebook user. Every action that your Facebook friends take is a possible Newsfeed story. Facebook calls these actions ‘edges’. Whenever someone visits their Newsfeed there are around 1,500 stories waiting to be seen, and since most people don’t have the time or simply don’t want to read through 1,500 posts, this algorithm prioritises the stories to show users what they’re most likely to be interested in. It is called ‘EdgeRank’ because it ranks the edges.

How does it work?

There are three things that this algorithm takes into consideration:

  1. Affinity Score
  2. Edge Weight
  3. Time Decay

Affinity Score

This means how ‘connected’ you are to the edge. It is calculated by considering how close you are with the person who’s posting. For example, if the story is by someone you frequently interact with, have several mutual friends with, or are related to, the algorithm is more likely to give the edge a higher affinity score.

Edge Weight

Not all actions, or edges, are considered to be of equal importance; a friend creating a status update would carry more weight than someone liking a photo.

Time Decay

As time passes and the posts gets older, it is likely that it has already been seen or that it is no longer as relevant. To solve this, the algorithm multiplies the story by 1/x, where x is the time since the action happened, to decrease its importance as time passes.

The formula below is then used to give each edge an overall score of importance:

the-three-pillars-of-edgerank-and-what-they-should-mean-to-you-equation.jpg

The higher the score, the more the story will be prioritised on your Newsfeed. Simple right!

Updates

Although the three factors remain the same, to refine the scores there are multiple weight levels and categories/sub-categories of affinity. Also, the algorithm now takes into account global interactions, which can outweigh personal interactions if the score is strong enough.

There are also relationship settings that Facebook users can apply; you can now label each of your Facebook friends a ‘close friend’ or ‘acquaintance’ (the stories of your ‘close friends’ will have a higher affinity score). Additionally, when you like a page you can now choose to ‘get notifications’ or ‘receive updates’ which is another way to control what appears on your Newsfeed.

Lastly, although the Edgerank algorithm is completely separate from the algorithm that decides what ads to show, when to show them and where, how you interact with these ads can influence what appears in your Newsfeed. Companies cleverly utilise this to get their advertisements to show up on their target audience’s Newsfeed.

Although this algorithm seems quite simple (in comparison to the PageRank algorithm) it is a vital component to the functionality of Facebook. Let me know what you think! M x