Implementing a stack data structure in C

Stack is a way we can store information. It follows the simple process of Last In, First Out or LIFO. Adding an item to the top of the stack is called a “push” operation. Removing an item from the top of a stack is called a “pop” operation. Another operation is “top”. Top simply returns the latest item that has been pushed the stack. Depending on the application, sometimes the pop operation can also be used as a top by returning what has been removed to the caller. These operations have a constant time or a time complexity of O(1).

We can implement a stack using arrays or a linked list. In array implementation, you can push a stack only until you reach the size of an array. We can have a situation where we consume the array and we cannot push anymore. This is what we call a stack overflow. There a few ways to avoid a stack overflow:

1. Add a semantic check before you push a new item to the stack

2. We can create a new large array and copy the contents of the older filled up array. The cost of copy is O(n) where n is the size of the filled up array. Simple strategy of deciding the size of the new array is doubling n

Here is a simple example of a stack implementation in C

#include <stdio.h>

#define STACK_CAPACITY 10

//A int stack data Structure
struct Stack {
    int     list[STACK_CAPACITY];
    int     size;
};
typedef struct Stack Stack;


//Initialize stack
void initStack(Stack *s)
{
    s->size = 0;
}

//Return the top of stack
int top(Stack *s)
{
    if (s->size == 0) {
        printf("Error: stack empty\n");
        return -1;
    } 

    return s->list[s->size-1];
}

//Returning the current size of a stack
int size(Stack *s)
{
    return s->size;
}


//Push an item to the stack
void push(Stack *s, int item)
{
    if (s->size < STACK_CAPACITY)
        s->list[s->size++] = item;
    else
        printf("Error: stack full\n");
}

//Pop an item to the stack
void pop(Stack *S)
{
    if (S->size == 0)
        printf("Error: stack empty\n");
    else
        S->size--;
}

int main()
{
  //Create local variables
  int item=-1, currentSize = -1;

  //Create a stack strucuture
  Stack s;
  
  //Initialize stack
  initStack(&s);

  //Get the current size of a stack
  currentSize = size(&s);
  printf("Current size of a stack %d\n", currentSize);

  //Push three items to a stack
  item = 2;
  push(&s, item);

  item = 1996;
  push(&s, item);

  item = 203;
  push(&s, item);

  //Get the current size of a stack
  currentSize = size(&s);
  printf("Current size of a stack %d\n", currentSize);

  //Get the current top item of the stack
  item = -1;
  item = top(&s);
  printf("Current top item of the stack %d\n", item);
 
  //Use the pop operations couple of times
  pop(&s); //pop 203
  pop(&s); //pop 1996

  //Get the current size of a stack
  currentSize = size(&s);
  printf("Current size of a stack %d\n", currentSize);

  //Get the current top item of the stack
  item = -1;
  item = top(&s); //returns 2
  printf("Current top item of the stack %d\n", item);

  item = 0;

  //Try to overlow the stack by push "0" ten times
  for(int i=0; i < STACK_CAPACITY; i++)
  {
      push(&s, item);
  }

  //Get the current size of a stack
  currentSize = size(&s);
  printf("Current size of a stack %d\n", currentSize);

  //Try to empty the stack
  for(int i=0; i < STACK_CAPACITY; i++)
  {
      pop(&s);
  }

  //Get the current size of a stack
  currentSize = size(&s);
  printf("Current size of a stack %d\n", currentSize);

  //Empty the stack while it is empty
  pop(&s);
  
  return 0;
}

 

Here is an output of our simple C program:

output

Some of the applications of a stack data structure in Computer Science are:

1. Stack Memory Management

2. Text Parsing

3. Expression Evaluation

4. Backtracking Algorithms

For more resources on the applications of the stack data structure see the following: Stack Applications

What does “static” means in a C program?

A “static” variable inside a function keeps its value between invocations.

For example:

#include <stdio.h>

void printValue();

int main()
{
  int i;
  for(i=0; i<5; i++)
  printValue();

  return 0;
}

void printValue()
{
  static int x = 0;
  int y =0;

  x++;
  y++;

  printf("x=%d y=%d\n", x, y);
}

 

Printout:

output

A “static” global variable or a function is “seen” only in the file it’s declared

beautiful-mountains-wallpaper-8

Simple Quote Gems

Quran Verses

  • Indeed, Allah loves those who rely upon Him (3:159).

Prophet Peace Be Upon Him (PBUH)

  • Whoever believes in Allah and the Last Day should speak a good word or remain silent. (Bukhari and Muslim)
  • It is better to sit alone than in company with the bad; and it is better still to sit with the good than alone. It is better to speak to a seeker of knowledge than to remain silent; but silence is better than idle words. (Bukhari)
  • Allah the Most Great said, ‘If My servant likes to meet me, then I like to meet him; and if he dislikes to meet Me, then I dislike to meet him.’ (Bukhari)

Islamic Quotes

  • Happiness comes from 3 things:
    1. To be thankful for your blessings.
    2. To be patient at times of adversity.
    3. When you repent from sins.
  • Do not be selfish in prayer by praying for yourself. Pray for others too and stand a better chance of having your own prayers answered. Mufti Ismail Menk.
  • If you want God to help you, help another person. And if you want God to forgive you, forgive another person. Yasmin Mogahed.
  • We can’t blame the laws of physics when a twig snaps because we leaned on it for support. The twig was never created to carry us. Our weight was only meant to be carried by God. Yasmin Mogahed.

Inspiring Quotes

  • Confidence is preparation. Everything else is beyond your control. Richard Kline.
  • I walk slowly, but I never walk backward. Abraham Lincoln.
  • Discipline is doing what needs to be done, even if you don’t want to do it. Unknown.
  • The man who removes a mountain begins by carrying away small stones. Chinese Proverb.
  • When you improve a little each day, eventually big things occur. When you improve conditioning a little each day, eventually you have a big improvement in conditioning. Not tomorrow, not the next day, but eventually a big gain is made. Don’t look for the big, quick improvement. Seek the small improvement one day at a time. That’s the only way it happens – and when it happens, it lasts. John Wooden.
  • You miss 100% of the shots you don’t take. Wayne Gretzky.
  • I’ve got a theory that if you give 100% all of the time, somehow things will work out in the end. Larry Bird.
  • Whether you think you can or think you can’t – you are right. Henry Ford.

Human Relations

  • Those who always see beauty in others are beautiful. Dr. Bilal Philips.
  • Assumptions are the termites of relationships. Henry Winkler.
  • Your value doesn’t decrease based on someone’s inability to see your worth. Boonaa Mohammed.
  • No one can make you feel inferior without your consent. Eleanor Roosevelt.

Interesting Observations

  • It is the mark of an educated mind to be able to entertain a thought without accepting it. Aristotle.
  • Did you ever consider how ridiculous it would be to try to cram on a farm — to forget to plant in the spring, play all summer and then cram in the fall to bring in the harvest? The farm is a natural system. The price must be paid and the process followed. You always reap what you sow; there is no shortcut. Stephen Covey.
  • The objective is the journey, the process; the work matters. In a race you can be first, miles and miles ahead of anyone else, and then, metres from the line, fall over. And? Are you going to write that race off? You ran brilliantly. And it’s far more complex than saying: win, good; don’t win, bad. What enriches you is the game, not the result. The result is a piece of data. The birth rate goes up. Is that enriching? No. But the process that led to that? Now that’s enriching. Fulfilment comes from the process. You debate the game not the results. Results are not debatable, they are. Do you buy a paper on a Monday morning for a euro and the only thing in it is list after list of results? Do you go into a football stadium, in the last minute of a game, have a look at the scoreboard and leave? You watch 90 minutes, which is the process. You can’t validate the process through the results. Human beings tend to venerate what finished well, not what was done well. We attack what ended up badly, not what was done badly. Juanma Lillo.
VfL Wolfsburg's Dutch Striker Bas Dos. Source: ESPN FC

Most efficient forwards in Europe (2014/2015)

“Four things come not back: The spoken word, The sped arrow, The past life, The neglected opportunity.” An Arabian Proverb.

When asked why the Manchester United forward Andy Cole was not picked for the 1998 World Cup Squad, former England Coach Glenn Hoddle said: “Andy Cole needed five chances before he converted.” This quote has always stuck with me when evaluating an attacking player. As a forward, you usually only get few chances to convert a goal during a game. Sometimes, missing a crucial chance might even subject you to the unforgiving wrath of the Internet.

After thinking about who is the most efficient striker in Europe currently, I could not come up with an answer. I guessed Suárez or Lewandowski but I was not 100% sure. So I decided to do some research based on data from last season. Statistically, there are two ways you can do this. Count the number of goals per-minute played or count the number of goals per shots taken. I prefer the latter because it normalizes the number of minutes played between the players. In this method, I do not have to worry about Ronaldo playing 18 hours and 15 minutes more than Charlie Austin when comparing the two.

I decided to research the players from the following leagues and tournaments from last season because of the perceived quality of the competition: UEFA Champions League, Italian Serie A, English Premier League, Spanish La Liga, French Ligue 1, Dutch Eredivisie, German Bundesliga and UEFA Europa League. I also decided to only look at players who scored at least 18 goals. An obvious limitation of this research is that the quality of opprutunities or shots taken were not compared.

Here is what I found:

Player Name Total Shots Goals Ratio(%)
1. Bas Dost 54 18 33.33333
2. Carlos Bacca 89 27 30.33708
3. Alexandre Lacazette 96 27 28.125
4. Antoine Griezmann 94 24 25.53191
5. Karim Benzema 88 21 23.86364
6. Alexander Meier 80 19 23.75
7. Neymar 136 32 23.52941
8. Diego Costa 94 20 21.2766
9. Luis Suárez 113 23 20.35398
10. Aduriz 94 19 20.21277
11. Lionel Messi 270 53 19.62963
12. Cristiano Ronaldo 296 58 19.59459
13. Zlatan Ibrahimovic 109 21 19.26606
14. Sergio Aguero 167 32 19.16168
15. Harry Kane 112 21 18.75
16. Thomas Müller 107 20 18.69159
17. Carlos Tevaz 152 27 17.76316
18. Luca Toni 125 22 17.6
19. Arjen Robben 110 19 17.27273
20. Mark Uth 116 20 17.24138
21. Edinson Cavani 143 24 16.78322
22. Gonzalo Higuaín 150 25 16.66667
23. Luuk de Jong 133 22 16.54135
24. André-Pierre Gignac 130 21 16.15385
25. Mauro Icardi 140 22 15.71429
26. Pierre-Emerick Aubameyang 123 19 15.44715
27. Robert Lewandowski 151 23 15.23179
28. Charlie Austin 131 18 13.74046
29. Alexis Sánchez 142 19 13.38028
30. Memphis Depay 188 25 13.29787

 

Based on the research, VfL Wolfsburg’s Dutch striker Bas Dost was the most efficient striker in Europe with a impressive ratio of 33.333% chances of scoring a goal per shot. The 26 year old 6’5 striker had a wonderful season in the Bundesliga and Europa League. The big man is an excellent finisher, moves wonderfully off the ball and is great in the air.  AC Milan’s new Colombian summer signing  Carlos Bacca came in second with 30.337% chances of scoring, while Lyon’s French striker Alexandre Lacazette came in third with 28.125%. These three players have two things in common: they are currently not house hold names and do not start for their national teams. Maybe another season with 18 or more goals with the same level of efficiency will cement them with the elite of European football.

Carlo Ancelotti and a white board

Introduction to Football Tactics I

If you know the enemy and know yourself you need not fear the results of a hundred battles. Sun Tzu.

Introduction

My first introduction to football tactics was playing Sega’s Football Manager 2008. I was introduced to weird concepts such as defending deep or playing a high-line which made no sense to me. Today most people who watch at least one football match a week have a good understanding of the basics of football tactics because of YouTube videos of Gary Neville and his over-sized iPad on Monday Night Football or reading Michael Cox’s zonal marking blog.

“Good tactics” is only a single factor for a football team’s ability to beat another football team or reach its objective. Other components such as technical proficiency, physical ability, physical condition, mental strength and motivation of the players are just as important. Harry Redknapp, former QPR, Tottenham and West Ham manager,  once said: “You can argue about formations, tactics and systems forever, but to me football is fundamentally about the players, Whether it is 4-4-2, 4-2-3-1, 4-3-3, the numbers game is not the beautiful game in my opinion. It’s 10% about the formation and 90% about the players. If you have the best ones and they do their jobs, then they can pretty much play any way you want them to.” I fundamentally agree with Redknapp but the ratios are more like 30 to 40% vs 60 to 70%.

Legendary basketball coach John Wooden once told Roy Williams (University of North Carolina’s basketball coach): “Roy, you can coach talent. Some guys can’t. Nobody can coach no talent, but you can coach talent.” I believe this principle also applies in football. No matter what great plan you come up with to defeat another opponent, if you do not have the personnel to execute the plan effectively then tactics become almost useless. Almost useless instead of just useless because teams can use tactics as damage control, for example instead of losing 10-0, you only lose 3-0. Good tactics are an effective tool but not the whole piece of the pie.

A football match consists of 5 important reference points: your team, the opponent, the space, time and the ball. Tactics is an overall strategy or framework or game plan or philosophy to balance all these factors to gain a competitive advantage in a match. There is no one single perfect way of achieving that balance but instead multiple ways or different schools of thought. Barcelona and Chelsea have won the league effectively in their respective countries in the 2014/2015 season by playing two completely different brands of football when facing their competition rivals. Chelsea beat Manchester United 1-0 in Stamford Bridge with only seeing the ball 29.6% of the time while Barcelona beat Atletico Madrid in the Vicente Calderón Stadium with the same score with 77% of the ball. With respect to effectiveness, both strategies are sound, however when it comes to entertainment value there are criticisms from a majority of football fans against the “Chelsea way.” Argentina’s 1986 world cup winner Jorge Valdano once said “Playing against a defensive opponent is just as bad as making love to a tree.” Personally, I agree with Valdano, but I also enjoy watching a top team trying to break down Chelsea and being extremely frustrated.

In this article series, I will try to comprehensively explain the basics of football tactics. Initially, I will introduce an important component of football tactics that has survived for more than half a century.

Principles of Play

In 1967, The English Football Association also know as The FA published a manual called “The FA Guide to Training and Coaching.” It was written by Allen Wade who was the “Director of Coaching” at the time. This book became a Bible to a generation of coaches, especially to Roy Hodgson who currently leads the English National Team. In the manual, Wade introduces 5 attacking principles countered by 5 defending principles:

Attack Defence
Penetration Delay
Support Depth
Width Compactness
Mobility Balance
Improvisation/Creativity Discipline/Patience
10 Principles of Play

These principles have stood the test of time because of their effectiveness. Each principle can easily be transmitted into practice drills which represents a specific situation during a match. Before we present the principles, we must first clarify and prioritize the objectives of teams when attacking and when defending:

Attacking Objectives Defending Objectives
1. Score 1. Stop Scoring
2. Advance 2. Delay the Attack
3. Maintain Possession 3. Regain Possession

The principle of play aid teams to reach these objectives during the course of a game. Let us explore the practicality of each principle.

Penetration

As soon as possession is regained by a player or they receive the ball in an advance position the player now becomes the “first attacker.” The first attacker should ask themselves if they can score. If not, then is there a player we can pass to in an advance position or can we move to an advance position closer to the opponent’s goal. If not, then is there space closer to the opponent’s goal they can dribble the ball into. Players are required to make a lot of decisions in half a second. Therefore, repetitive drills that emphasize these decision making skills are great in order to improve a player’s intuition(speed of execution) during a game.

Delay

As soon as a defender becomes the closest player to the first attacker they then become the “first defender.” The first defender now has a choice either to press, delay or concede the space away from the goal to the first attacker. Depending on your location on the pitch you can concede space towards the touchline. According to Pep Guardiola, FC Bayern’s Head Coach, “The touchline is the best defender in the world.” The player must not over-commit when pressing the first attacker because it may lead to a goal scoring opportunity or an overloading situation (more attackers vs. defenders). To delay the first attacker try to maintain an arms length distance away from them. For pacy attackers back off a little bit more than arms length or they will knock the ball to space and blow past you.

Support

In order to keep possession, the first attacker needs passing options if he cannot penetrate the defence.  Guardiola also said “If you want to help your teammates, don’t move towards them, move away from them, so you can open up a passing line, open up the game, give more space to the player with the ball. So moving away from them is a good thing if you do it right.” The more options you provide for your teammate the more chances you will have in keeping possession. Players supporting the first attacker are known as the “second attacker” or “second attackers.” Ideally, second attackers should always be looking and moving to the largest space where a clear passing lane exists. Sometimes this identified space is in between a couple of opponents.  This is sometimes termed as “playing between the lines” or working the “channels.”

Barcelona’s legend Xavi is the perfect role model to observe how to provide support for your teammates. In a interview with The Guardian’s Sid Lowe , Xavi explained the process behind mastering this skill: “Think quickly, look for spaces. That’s what I do: look for spaces. All day. I’m always looking. All day, all day. Here? No. There? No. People who haven’t played don’t always realise how hard that is. Space, space, space. It’s like being on the PlayStation.”

Barcelona players supporting Xavi. Barcelona vs. Manchester United, 2011 Champions League Final
Barcelona players supporting Xavi (first attacker). Barcelona vs. Manchester United in the 2010/2011 Champions League Final.

Depth

One of the main objectives of a “second defender” or “second defenders” is to take away the first attacker’s passing lanes. This is done by trying to get tight on the second attackers or blocking the path between the first attacker and the second attacker. The latter involves a lot shoulder checking. By getting tight on a second attacker the defender makes it difficult for them to make a turn once they receive the ball from the first attacker (only if the second attacker has their back to goal). Being a second defender also involves being ready to take the loose ball as the first attacker tries to get past the first defender.

Manchester United players supporting Park Ji-sung (first defender).
Manchester United players supporting Park Ji-sung (first defender).

When the first defender commits but does not win the ball, then the closest second defender should quickly move into space and becomes the new first defender. The previous first defender should now drop back as quickly as possible and become a seconder defender.

12defender
Second Defender becoming a First Defender

Manchester United’s holding midfielder Michael Carrick is an excellent second defender. Carrick’s critics focus on why he does not make Roy Keane/Bryan Robson type of tackles when plays in front of his back four as reason why he is not a great holding midfielder. I completely disagree with this notion because another great second defender Xabi Alonso once described tackling as not a really quality or skill but “more something you are forced to resort to when you don’t have the ball.” In a interview with FourFourTwo Performance, Carrick discusses the principles of how he defends: “Shut off the angles. If you press the player on the ball you’re creating space in behind you and they can pass into that space. Force the opposition to play the ball where you want. Do this by stepping off the player you’re marking and drawing them into a pass, then trying to intercept it. If their biggest threat is out on one wing, focus on defending that area, pushing them to the other side. If they have someone playing off the front, like Messi, cut the space through the middle by bringing your wide men in, forcing them out wide.” In another interview with FourFourTwo, Carrick adds “A lot people are screaming at you press the ball, press the ball specially the fans because they want you to be serious and defend, which is fair enough but it is not the right thing to do.”

Here is a clip of Gary Neville illustrating what Carrick does off the ball:

Width

Legendary Dutch coach and player Johan Cruyff once remarked “If you have the ball you must make the field as big as possible, and if you don’t have the ball you must make it as small as possible.” The objective of making the field as big as possible is to stretch your opponent’s defence to free up the space in front of goal. The opponents can be stretched laterally(horizontally) by having players in wide areas or making runs into wide areas. Players away from the ball in areas outside the opposition’s first or second defender’s field of vision are called “third attackers”, while that area of the pitch is known as the “blindside” or “weakside.” Passing the ball to a third attacker in the weakside is called “switching the play.” In a Four Four Two Magazine Interview, Former West Ham Academy Director Tony Carr explains the objective of switching the play “You want to try and catch the opposition off guard by dragging them over to one side of the pitch, where we can quickly change the play to the other side of the pitch to exploit the space…It needs to be done quickly, it needs to be done sharply. Once we’ve got the ball into that wide position, we’re asking the wide player to cross the ball as early as possible for the two strikers waiting in the middle.”

Below is a famous example of how using the width of the field can catch the opposition off guard. Pele’s pass to Carlos Alberto secured Brazil a comfortable 4-1 win in the 1970 World Cup Final against Italy.

Compactness

Being compact means decreasing playing space in the most vulnerable areas to scoring opportunities by grouping players between the goal and the ball.  This also means giving up space in less dangerous parts of the field.  Once the ball is lost to the opposition, players should quickly drop back towards their goal and be “goalside” with the ball. In the example below, Ryan Giggs needs to be goalside of Andrés Iniesta because Messi can execute a lob pass to the dangerous space marked as red or Messi could pass to Xavi who has clear passing lane to that space.

All the Manchester United Players are correctly positioned expect for Ryan Giggs
All the Manchester United Players are correctly positioned expect for Ryan Giggs.

The most vulnerable area in the field is the space in front of goal. Other dangerous parts of the field are referenced by the position of the ball. Therefore, the space a player should be covering, changes dynamically as the ball moves. In an interview with Elite Soccer Magazine, Real Sociedad’s coach David Moyes describes practical ways to help players apply this concept. For example, one drill requires the length of the field to be divided into six narrow segments of 12 meters each. The defending players should always try to occupy the nearest zones to ball. Based on the diagram below, the yellow team always gives up the space least dangerous to them using the ball as a reference. If the blue team had some width in the zones the yellow team is not occupying then they can have the option of switching the play. If the blue team decides to switch the play, the yellow team can counter by quickly shifting to zones as the ball travels to the weakside of the field.

Players shifting based on the position of the ball

Compactness1
Blue attacking on the left side of the field (a)

Compactness2
Blue attacking through the middle of the field (b)

Compactness3
Blue attacking from the right side of the field (c)

Mobility

A very compact defence can comfortably combat against a very static group of attackers since the defenders can easily adjust themselves in a way where they can see both the attacker and the ball. Therefore, attackers should make runs into different areas to drag defenders out of their position or distract them from their duties for a split second. However, making runs should be intelligent and purposeful. Former Manchester United Manager Sir Alex Ferguson once remarked: “When forwards attack from wide to inside, they are far more dangerous. It’s funny when I see centre-forwards starting off in the middle against their markers and then going away from goal. Strikers going inside are far more dangerous… Trying to escape and create space by drifting from the centre to wide positions…actually makes them less dangerous.

While talking about how the Barcelona Youth Academy La Masia trains its youth players, Pep Guardiola said “We teach our players how they can run less.” Tony Carr feels the same way “Players must know when to run and where to run. Running just for the sake of running and flying about all over the pitch is a trait of poor players who let their heart rule their heads. Running must be intelligent.” Finally, current Manchester United Manager Louis van Gaal discusses the matter “Running is for animals. You need a brain and a ball for football.

When an attacker makes a run a defender has to decide whether to track them or continue to cover their zone or their original assigned player. If the defender chooses to follow, he leaves some spaces that can be exploited by other attackers. Prime example of this is the following goal for Bayern Munich against Arsenal in the 2013/2014 Champions League. Claudio Pizarro drags Per Mertesacker to create space for Thomas Muller to exploit. Barca Sanga realizes what has happened and tries to cover that space but he is too late.

Balance

If the objective of mobility is to drag defenders out of position to create space to exploit then the principle of balance is to counter that. It is the “third defender” who gives balance to the team and not the first defender or the second defender. Players covering the weakside of the field or third attackers are called third defenders. Third defenders should not track attackers who are going away from their goal or to an area that is already covered by another defender. A defending team is considered to have “good balance” if they apply pressure on the ball and they can naturally cover dangerous areas if the ball is switched.

Improvisation/Creativity

This principle encourages players to use their individual skills to create space or shooting opportunities for themselves or their teammates. Individual skills such as dribbling, fakes, turns, back-heel passing is used to beat the first defender and/or second defenders. This principle works well against an opposition that is very compact and has good depth and balance. Messi’s goal against Atletico Bilbao in the 2015 Copa Del Rey final is one of my favourite examples of utilizing individual skill to create a brilliant goal:

Patience/Discipline

If a team is observing all the first 4 defending principles then it should not practice reckless and impatient defending. First defenders should not make poorly timed tackles or attempts to go for the ball. Second defenders should not try to leave large amounts of space to intercept passes between a first and second attacker. If an attempt to retrieve the ball fails, then most likely a team has broken one of the defending principles. Defending teams should look for visual cues on when to press or try to intercept the ball and not base their decisions on instinct or emotions. Below are some examples of precise indicators to look for before attempting to retrieve the ball:

  • If an opponent controls the ball badly
  • If the ball bounces off the ground
  • If a opponent has their back to goal or they do not have an overview of the pitch
  • If an opponent is looking around for their teammate
Background

How does a search engine work?

Search Engine Optimization (SEO) Blog Series

Have you ever wondered how to get your business website to rank higher in Google? If you desperately want to answer this question, then you need to know what Search Engine Optimization (SEO) is. In this blog series, I will give you a brief introduction to SEO and explore the basic SEO techniques available today.

Before you understand what SEO is, you need to understand how a (web based) search engine works. A search engine consists of three important operations:

  • Web crawling
  • Indexing
  • Serving results

Web Crawling

A web crawler or web spider is a piece of automated software that systematically (based on rules) browses the World Wide Web and collects information to be used for indexing. A real world analogy of this would be you visiting every bus stop (website) in the city you live in (the Internet) and taking a picture of the bus schedule in each stop (gathering content for the index). A search engine website such as Google has many web crawlers (known as Googlebots in their case) since there are billions of pages on the Internet. Web crawling is a never-ending process due to the fact that the Internet is always growing.

Going to every single bus stop in Toronto would be a hectic task
Going to every single bus stop in Toronto would be a hectic task

The web crawler process typically begins with a list of addresses of web pages usually generated from the previous web crawl process. The web crawler visits each of these web pages and detects links to other web pages. These newly detected links are added to the list of pages to crawl. The crawler also saves the content of the web page in order to be indexed later. The web crawler process ends when there are no more web pages to crawl or when an algorithmic condition is met. Only crawl 1,000 web pages is an example of an algorithmic condition.

Indexing

Once the web crawler has completed the content gathering processes, the index table needs to then be created or updated. An index table is used because of the speed benefits it provides when the search engine results are returned to the user. The creation or updating of an index table is usually a long process, however this is acceptable since the process is hidden from the user. The major steps of building an index are:

1. Collect the documents returned from the web crawler. For example, suppose the web crawler returned the following documents:

Document Content
D1 Humpty Dumpty sat on a wall, Humpty Dumpty had a great fall.
D2 Jack and Jill went up the hill to fetch a pail of water.
D3 Private Jack Powers tried to save General George Humpty by climbing the Berlin wall.

 

2. Remove stop words and punctuation marks from the documents. Stop words are extremely common words in the English language like “a”, “the” and “or”. These words are removed in order to improve efficiency of the search engine when returning results.

Document Content
D1 Humpty Dumpty sat wall Humpty Dumpty great fall
D2 Jack Jill went up hill fetch pail water
D3 Private Jack Powers tried save General George Humpty climbing Berlin wall

 

3. More linguistic processing is completed by converting each word to its root word. For example, “climbing” to “climb” or “friends” to “friend” or “children” to “child”.

4. Create an index of terms where it contains the document and the frequency in which the word occurs. Below is a sample of the index based on the content above:

Term Document, Frequency
Humpty D1, 2 D3, 1
Jack D2, 1 D3, 1
Jill D2, 1
Powers D2

This example is a very simple indexing method. Search engines today use more complex techniques. The frequency of a term in a document is an important property, however other properties (such as positioning of a term in a document or the geographical location of the server hosting the document) can also be added to the index table.

 

Serving results

The serving results process occurs once the user enters words (the query) into the search engine and presses okay. Suppose the user searched the following query “I love humpty chips”. Obviously, the search engine returns Documents D1 and D3, but which document is more relevant to the user? This is not an issue for this user since the sample size is so small. But what if it is not? Search engines today rank documents using a sophisticated (secret) technique based on many factors such as the frequency property in our previous example. Overall, the main objective of Search Engine Optimization (SEO) is the understanding of what those factors are in order to improve your website’s rank.

 

Further Readings

Here is a selected list of readings you can do if you would like to gain more knowledge of how search engine works: