It is now time to move away from the introductory posts, and delve deeper into specific topics. Being a graph theorist myself, I decided to make Graph Theory my first non-introductory post.
(For the introductory post to this field, please read this post.)
In the previous post on this topic, I finished with certain questions one can ask about graphs. The first of these is about the connectivity of graphs. Namely, the question is, given two vertices u and v in a graph, can we find some way to get from u to v, following edges in the graph? This is a very easy problem to visualise. If a graph is made up of two or more parts (known as components), then it is impossible to get from a vertex in one component to a vertex in another component. We say that the graph is disconnected. Now, let's say that for every pair of vertices u and v in a graph, you can find some path u, x1, x2, ... , v which moves through consecutively adjacent vertices x1, x2 and so on. Then there cannot be more than one component in the graph and we say the graph is connected.
This question of connectivity can be easily extended in two important ways. The first one deals with the best way to get from one vertex to another. Let's say that the vertices correspond to cities and the edges to roads connecting them. Now, for simplicity, let's say that each edge costs you 5 euros in gasoline. Then, to minimise your costs, you will want to find the path that uses the fewest edges. Going from Munich to Bologna and from there to Paris is possible, but it is generally much cheaper to go as directly as you can. This leads to the idea of the shortest path. That is, given vertices u and v in a graph, what is the shortest path between them? Clearly, for any two vertices, if you can find some path between them, a shortest path must also exist. This is because paths have non-negative length, so you cannot reduce path length indefinitely. One of the most well-known methods for finding shortest paths is Dijkstra's Algorithm. The way it works is by searching for the shortest path from the starting vertex u to every other vertex. This is done by splitting the graph into two parts: the explored vertices and the unexplored vertices. Additionally, for every vertex v, the algorithm maintains a tentative distance from u to v. Initially, only the starting vertex is explored. At each step, the algorithm picks the unexplored vertex with the shortest distance and explores it. Whenever a vertex v is explored, the algorithm attempts to find a shortest path from u to the neighbours of v, by incorporating v. If a path shorter than what was available before can be found, these neighbours are updated accordingly.
The reason this algorithm works, is that the shortest path between two vertices is made up of other shortest paths. That is, if the shortest path from u to v goes through x, then it contains the shortest path from u to x, followed by the shortest path from x to v. The algorithm seeks all such shortest subpaths and picks the best available one.
The second way in which connectivity can be extended is with the notion of k-connectivity. Let's say there are several path between two vertices, u and v. If we were to remove some vertices from the graph (and all the edges that go with them) would there still be a path between u and v? How many vertices make it impossible for us to find such a path? What about removing edges? The ideas of connectivity are important in various problems of resource management. Suppose you have to provide internet service to some locations. You would use various connecting stations, which would handle the traffic of information and route it from place to place. But what if some of these stations were to be damaged? Could your network cope? And how many stations can you safely shut down at a time for maintenance, without compromising the quality of your service? As you can see, the question of connectivity is very important for proper resource management.
Saturday, August 25, 2012
Friday, August 24, 2012
Algorithms
The joke goes that when George W. Bush found out that colleges were teaching their Computer Science majors about Algorithms, he complained about unequal representation and asked that they also teach GeorgeBushisms as well. But what exactly are Algorithms? Why do computer scientists learn about them? What do they, in fact, do?
Imagine you are about to do something. This "something" could be a very simple task, like opening your internet browser, or something more complicated, like baking a cake. How do you go about doing it?
If you think about it, all processes have certain steps, which need to be carried out, usually in a precise sequence, in order to be completed. Opening your browser can, for example, be achieved by moving your mouse until the cursor is pointing to the relevant icon, then double-clicking. Performing these steps out of sequence probably won't get you very far, unless you're lucky.
Algorithms are nothing but step-by-step instructions for performing a task. We usually use the word to denote a mathematical or computational task, but, in fact, the instructions for opening your internet browser is also an algorithm.
Now, let's take a different task. Take a piece of paper and a pen. Draw a straight line. Now draw a second line, which starts wherever the first one ended and goes in a different direction. Draw a third line, starting from the same point, but in a different direction. Now connect the remaining three end points with a curve.
Did you get the Mercedes-Benz logo? Probably not. The reason for this was that my instructions were extremely imprecise. I did not tell you how to orient the lines. I did not tell you what angles to make between them. I did not tell you how long to make them. I did not tell you to make the final curve a circle. All these omissions most likely made your drawing something completely arbitrary, not resembling the mentioned logo at all. An algorithm cannot be vague like that. Each instruction must be precise enough, so that whenever someone attempts to perform the same task under the same conditions must get the same result. (With the exception of using randomness, like rolling a die).
When it comes to computers, every piece of software is a sequence of instructions to the computer, telling it what to do, from moving numbers around, to accepting some sort of input, to controlling your enemies in a video game. These instructions are in the language of the computer itself, so there is no longer a problem about vague instructions. So, why is there a need to study algorithms? There are two main reasons. The first one is that, even though a set of instructions can be precise, this doesn't mean that it will do what is intended. The study of algorithms helps us understand ideas like data flow, prerequisites and programme correctness. The second reason is that the same task can often be performed in many different ways. Instead of using a mouse to double-click on the correct icon, you may also be able to open your browser by going into a command prompt and type the appropriate commands to get to the correct folder and run the correct file and so on. Sometimes, one of the ways of performing a task is better (faster, more efficient, less prone to error and so on) than another. However, which method is better is not always clear. This is where algorithm analysis helps. We can analyse a given set of instructions in terms of the time it takes, the possible errors it may encounter and even its correctness, before even running the programme itself.
Imagine you are about to do something. This "something" could be a very simple task, like opening your internet browser, or something more complicated, like baking a cake. How do you go about doing it?
If you think about it, all processes have certain steps, which need to be carried out, usually in a precise sequence, in order to be completed. Opening your browser can, for example, be achieved by moving your mouse until the cursor is pointing to the relevant icon, then double-clicking. Performing these steps out of sequence probably won't get you very far, unless you're lucky.
Algorithms are nothing but step-by-step instructions for performing a task. We usually use the word to denote a mathematical or computational task, but, in fact, the instructions for opening your internet browser is also an algorithm.
Now, let's take a different task. Take a piece of paper and a pen. Draw a straight line. Now draw a second line, which starts wherever the first one ended and goes in a different direction. Draw a third line, starting from the same point, but in a different direction. Now connect the remaining three end points with a curve.
Did you get the Mercedes-Benz logo? Probably not. The reason for this was that my instructions were extremely imprecise. I did not tell you how to orient the lines. I did not tell you what angles to make between them. I did not tell you how long to make them. I did not tell you to make the final curve a circle. All these omissions most likely made your drawing something completely arbitrary, not resembling the mentioned logo at all. An algorithm cannot be vague like that. Each instruction must be precise enough, so that whenever someone attempts to perform the same task under the same conditions must get the same result. (With the exception of using randomness, like rolling a die).
When it comes to computers, every piece of software is a sequence of instructions to the computer, telling it what to do, from moving numbers around, to accepting some sort of input, to controlling your enemies in a video game. These instructions are in the language of the computer itself, so there is no longer a problem about vague instructions. So, why is there a need to study algorithms? There are two main reasons. The first one is that, even though a set of instructions can be precise, this doesn't mean that it will do what is intended. The study of algorithms helps us understand ideas like data flow, prerequisites and programme correctness. The second reason is that the same task can often be performed in many different ways. Instead of using a mouse to double-click on the correct icon, you may also be able to open your browser by going into a command prompt and type the appropriate commands to get to the correct folder and run the correct file and so on. Sometimes, one of the ways of performing a task is better (faster, more efficient, less prone to error and so on) than another. However, which method is better is not always clear. This is where algorithm analysis helps. We can analyse a given set of instructions in terms of the time it takes, the possible errors it may encounter and even its correctness, before even running the programme itself.
Wednesday, August 8, 2012
Game Theory
This topic is one of the main parts of what are known as Decision Mathematics. Naturally, the title Game Theory makes the field sound like people playing chess or poker; doing recreational activities. This is actually not the case.
Game Theory is all about making choices, in given scenarios. What makes these scenarios special is that you are not the only one making choices; others are doing this as well and the outcome is affected by their choices as well as yours. One such example is that of conflict. In a battle between two opposing sides, each side may choose to fight or retreat (there are actually many more choices, but I am simplifying here for illustration purposes). If one side fights and the other retreats, the side that fought gains some advantage, e.g. some high ground. In game theory, we may assign a certain amount of points to this outcome, for example the attacking side gets 1 point, whilst the retreating side gets -1 point, to quantify the advantages gained and lost. On the other hand, if both sides fight, they will have a lot of casualties, so both sides get -2 points. Finally, if both sides retreat, they have not yielded anything to the opponent, so they both get 0 points.
Let us assume you are a military advisor of sorts, to one of the sides. What would be the best plan, for this battle? Should you attack or retreat? If we look at the possible results, fighting will get you either 1 or -2 points, whilst retreating will get you 0 or -1. If you want to make sure that you do no worse than a score of -1, you should retreat. This is known as the maximin strategy, as it seeks to maximise the minimum possible result. On the other hand, attacking ensures that the enemy will certainly have a score of at most -1. This would be an aggressive tactic. Of course, if the opponent is known to be aggressive, attacking will result in the worst possible score, for both sides. On the other hand, if the enemy is known to retreat a lot, attacking will cause a gain in points for your side.
As you can see, this sort of decision making is not always easy. In fact, depending on the scenario presented, it could be that every choice is a "bad" one. Or, alternatively, there can be an "obviously good" choice, which is always the best to choose. All these considerations are what Game Theorists study. From the above, it is obvious that the ideas of game theory have a clear practical application in such things as warfare (as well as politics, business management and so on). This may seem like a stretch, considering the simplicity of the scenario I presented, but the ideas were applied during the Cold War, amongst others. And since nuclear arms were already available by then, it can be seen how desirable it is that military advisors should be able to identify strategies such as "minimax" as the best ones to take.
As an exercise, you can try to teach yourself some elementary decision-making. Make your own scenario for two sides in a game, each having two options and each pair of options resulting in a certain point score. It should be fairly easy to figure out what scores make a perfect strategy possible. What about more choices? Or more players? Or both? Is it always clear if a scenario has a perfect strategy or not?
Game Theory is all about making choices, in given scenarios. What makes these scenarios special is that you are not the only one making choices; others are doing this as well and the outcome is affected by their choices as well as yours. One such example is that of conflict. In a battle between two opposing sides, each side may choose to fight or retreat (there are actually many more choices, but I am simplifying here for illustration purposes). If one side fights and the other retreats, the side that fought gains some advantage, e.g. some high ground. In game theory, we may assign a certain amount of points to this outcome, for example the attacking side gets 1 point, whilst the retreating side gets -1 point, to quantify the advantages gained and lost. On the other hand, if both sides fight, they will have a lot of casualties, so both sides get -2 points. Finally, if both sides retreat, they have not yielded anything to the opponent, so they both get 0 points.
Let us assume you are a military advisor of sorts, to one of the sides. What would be the best plan, for this battle? Should you attack or retreat? If we look at the possible results, fighting will get you either 1 or -2 points, whilst retreating will get you 0 or -1. If you want to make sure that you do no worse than a score of -1, you should retreat. This is known as the maximin strategy, as it seeks to maximise the minimum possible result. On the other hand, attacking ensures that the enemy will certainly have a score of at most -1. This would be an aggressive tactic. Of course, if the opponent is known to be aggressive, attacking will result in the worst possible score, for both sides. On the other hand, if the enemy is known to retreat a lot, attacking will cause a gain in points for your side.
As you can see, this sort of decision making is not always easy. In fact, depending on the scenario presented, it could be that every choice is a "bad" one. Or, alternatively, there can be an "obviously good" choice, which is always the best to choose. All these considerations are what Game Theorists study. From the above, it is obvious that the ideas of game theory have a clear practical application in such things as warfare (as well as politics, business management and so on). This may seem like a stretch, considering the simplicity of the scenario I presented, but the ideas were applied during the Cold War, amongst others. And since nuclear arms were already available by then, it can be seen how desirable it is that military advisors should be able to identify strategies such as "minimax" as the best ones to take.
As an exercise, you can try to teach yourself some elementary decision-making. Make your own scenario for two sides in a game, each having two options and each pair of options resulting in a certain point score. It should be fairly easy to figure out what scores make a perfect strategy possible. What about more choices? Or more players? Or both? Is it always clear if a scenario has a perfect strategy or not?