An adjacency list represents a graph (or a tree) as an array of nodes that include their list of connections. Let’s first see how it looks like with a graph and its equivalent adjacency list representation:

The idea is pretty simple : the index of the array represents a node and each element in its list represents an outgoing connection with another node. Easy to create, easy to manipulate, here is how the data could be represented in JSON :

[
  [1, 2, 3],
  [0, 2],
  [0, 1],
  [0]
]

Yes, it’s that simple! It includes all the information we need to go through and to visualize graphs or trees. This is for instance the data structure we choose to handle our mazes:

Applications

The advantage of the adjacency list implementation is that it allows us to compactly represent a sparse graph. The adjacency list also allows us to easily find all the links that are directly connected to a particular node. It is used in places like: BFS, DFS, Dijkstra, A* (A-Star) etc.

Note: dense graphs are those which have a large number of edges and sparse graphs are those which have a small number of edges.

For a sparse graph with millions of vertices and edges, this can mean a lot of saved space.

Perfect, we know everything to create and manipulate our graphs!

Objectives

Operate Adjacency Lists and Graphs.
Build our own structures.
Understand graph traversal algorithms.
Understand the advantages over an adjacency matrix.

What is next?

If you haven’t jumped yet to maze generation algorithms, playing with them and using our explorer gives you visual insights of adjacency lists. We will soon study more graph data structures such as adjacency matrix which may be useful in particular cases.

Build our own

To model this in C++, we can create a class called Node, which has two member variables:

- data: Any extra data you want to store
- neighbors: List of outgoing connections (using index as id)

struct Node
  {
    Node(const T& data, set< int > connections) : 
      data(data), neighbors(connections) {}

    T data;                // Any extra data you want to store
    set< int > neighbors;  // List of outgoing connections
  };

  class Graph
  {
  public:
    Graph(vector< Node > nodes) : nodes(nodes);

  private:
    vector< Node > nodes; // All nodes contained in the graph
  };

Let’s create a bidirectional graph!

typedef Node< string > NodeT; // We choose to store the name's node

  auto graph = Graph({
                  NodeT("Globo", {1, 2, 3}),
                  NodeT("Whisky", {0}),
                  NodeT("Hybesis", {0, 1}),
                  NodeT("Boudou", {1, 2})});

Yup, that’s it!
Great. Since we have all we need, let’s define some useful methods.

// Manipulations
  int Insert(Node node);                         // Insert a node
  void Connect(int idxA, int idxB, bool isBoth); // Add a connection

  // Return the node's degree
  int GetDegree(int idx);      
        
  // Return all the outgoing connections from a node
  set< int > GetNeighbors(int idx);

Manipulations

Insert / Connect

  // Insert a new node and return it's id
  int Insert(Node data)
  {
    nodes.push(data);
    return nodes.size() - 1;
  }

  // Connect two nodes together
  void Connect(int idxA, int idxB, bool isBoth)
  {
    [...] // Checks indexes validity
    nodes[idxA].insert(idxB);
    if (isBoth) nodes[idxB].insert(idxA);
  }

Quite easy, right?!

Node Information

GetDegree / GetNeighbors

// Return the degree of a node (number of connections)
  int GetDegree(int idx)
  {
    [...] // Checks index validity
    return node[idx].neighbors.size();
  }

  // Get all outgoing connections of a node
  set< int > GetNeighbors(int idx)
  {
    [...] // Checks index validity
    return nodes[idx].neighbors;
  }

From this one, we can easily find out the total number of nodes connected to any node, and what these nodes are.

Graph Traversal

Let’s finish the coding by implementing a graph traversal. We will use a simple BFS (Breadth First Search) strategy straight from our Graph definition.

  // We use the bool "isVisited" to keep track of our traversal
  typedef Node< bool > NodeT;

  BFS(int startIdx)
  {
    auto start = nodes.data()[startIdx];  // Get the start node
    start->data = true;                   // Set node to be visited
    Queue queue(start);                   // Put node in the queue

    // While there is node to be handled in the queue
    while (!queue.empty())
    {
      // Handle node in the front
      auto node = queue.pop();

      // Take neighbors, mark as visited, and add to the queue
      auto neighbors = node->GetNeighbors();
      for (auto it = neighbors.begin(); 
           it !== neighbors.end(); ++it)
      {
        auto linkedNode = nodes.data()[*it]; 
        if (linkedNode->data) continue;      // Check if visited

        linkedNode->data = true;    // Set visited
        queue.push(linkedNode);     // Add to the queue
      }
    }
  }

Voila ! You can code a GPS now.

What if I want to add some weights (distances)?

Adjacency Lists can also be used to represent a weighted graph. The weights of edges (links / connections) can be represented as lists of pairs:

[
  [{ "idx": 1, "weight": 4 }, { "idx": 2, "weight": 2 }, 
   { "idx": 3, "weight": 0 }],
  [{ "idx": 0, "weight": 3 }, { "idx": 2, "weight": 3 }],
  [{ "idx": 0, "weight": 4 }, { "idx": 1, "weight": 4 }],
  [{ "idx": 0, "weight": 10 }]
]

Try to implement this yourself as an exercise and try to find find the shortest path in this new graph. You may use a slightly modified version of our BFS algorithm seen above.

In Short

Adjacency Lists and Adjacency Matrix are the two most commonly used representations of a graph. Let’s compare them shortly with:

- N the number of nodes.
- M the number of edges.
- degree(i) denotes the number of outgoing connections from node i.

Adjacency Lists
Memory space: O(N + M)
Check if two nodes are connected: O(degree(i))
Get all outgoing connections of a node: O(1)

Adjacency Matrix
Memory space: O(N * N)
Check if two nodes are connected: O(1)
Get all outgoing connections of a node: O(N)

Implementations Performances

For the most courageous, we will finish by seeing some trade-off between using STL’s vector, set, or list to represent the nodes (vertices) and the connections (edges). Let’s first review some main differences:

Set
A set is automatically sorted
Insert/Delete/Find: O(log n)

Unordered Set
An unordered set is not sorted
Insert/Delete/Find: O(1)

Vector
A vector is not sorted
Insert/Delete/Find: O(n)

Linked List
A list is not sorted
Find takes O(n)
Insert/Delete: O(1)

Based on this, if you want to keep your edges or vertices sorted, you should probably go with a set. If you want a very fast search time, you should go with an unordered_set.

If find time is not that important, you can go with a list or a vector. But there is one more important reason that one might use a vector/list instead of set, which is representing multi-graph.

A multi-graph is similar to a graph, but it can have multiple edges between two nodes.

Handling Graphs With Adjacency Lists was originally published in The Startup on Medium, where people are continuing the conversation by highlighting and responding to this story.

Introduction

A pull request flow is a lightweight, 6 steps, branch-based workflow.
Note: this guide some quotations from GitHub Guides (Open Source).

Here is an overview of the pull request workflow:
0. “Pull” the changes to your local machine (get the most recent base)
1. Create a “branch” (version)
2. Commit the changes
3.a Push your changes
3.b Open a “pull request” (propose changes)
4. Discuss and review your code
5. Rebase and tests
6. “Merge” your branch to the master branch

1. Create a branch

Branches

The master branch is the “default” branch when you create a repository. Use other branches for development and merge them back to the master branch upon completion.

create a new branch named “feature_x” and switch to it using
git checkout -b feature_x
a branch is not available to others unless you push the branch to your remote repository
git push origin <branch>

Note : Git comes with built-in GUI tools for browsing — gitk. We recommend you to use it in order to get a good overview of your branches. You just have to launch it within your repository:
gitk

Tip : There’s only one rule: anything in the master branch is always deployable.

Because of this, it’s extremely important that your new branch is created off of master when working on a feature or a fix. Your branch name should be descriptive (e.g., refactor-authentication, build-maze-visualizer, use-embedded-format).

2. Commits

This process of adding commits keeps track of your progress as you work. Commits also create a transparent history of your work that others can follow to understand what you’ve done and why. Each commit has an associated commit message, which is a description explaining why a particular change was made.

Furthermore, each commit is considered a separate unit of change. This lets you roll back changes if a bug is found, or if you decide to head in a different direction.

Add & commit

You can propose changes (add it to the Index) using
git add <filename>
git add *
To actually commit these changes use
git commit -m "Commit message"

Note : Git comes with built-in GUI tools for committing — git-gui. We recommend you to use it in order to avoid being struggled with the command line. You just have to launch it within your repository:
git gui

Tip : Commit messages are important, they describe your code history. By writing clear commit messages, you can make it easier for other people to follow along and provide feedback.

3.a Push your changes

A branch is not available to others unless you push the branch to your remote repository
git push origin <branch>

3.b Open a Pull Request

Pull Requests initiate discussion about your commits. Anyone can see exactly what changes would be merged if they accept your request.

You can open a Pull Request at any point:
when you have little or no code but want to share some screenshots or general ideas,
when you’re stuck and need help or advice,
or when you’re ready for someone to review your work.

Tip : Pull Requests are useful for contributing to open source projects and for managing changes to shared repositories.

4. Discuss and review your code

Once a Pull Request has been opened, the person or team reviewing your changes may have questions or comments (the most often through your git host platform). Perhaps the coding style doesn’t match project guidelines, the change is missing unit tests, or maybe everything looks great and props are in order. Pull Requests are designed to encourage and capture this type of conversation.

You can also continue to push to your branch in light of discussion and feedback about your commits. If someone comments that there is a bug in the code, you can fix it in your branch and push up the change.

5. Rebase and tests

Once your pull request has been reviewed and the branch passes your tests, you can rebase your branch on master (it will use the most recent version of the code base) in order to test all the changes together (production).

Rebase

To take all the changes that were committed on master and replay them on the current branch.
git rebase master
This operation works by resetting the current branch to the same commit as master, and applying each commit of the current branch.

If your branch causes issues, you should fix it in your branch before merging with master.

6. Merge

Merge

Now that your changes have been verified in production, it is time to merge your code into the master branch.
git checkout master
git merge <branch> --no-ff

— no-ff | No Fast Forward

The — no-ff option is useful when you want to have a clear notion of your feature branch. So you treat a feature branch with a bunch of commits as a single unit, and merge them as a single unit. It is clear from your history when you do feature branch merging with — no-ff.

Tag & Version

It is recommended to create tags for software releases. You can create a new tag named Hurna v1.3.0 by executing
git tag -a v1.3.0 -m "Hurna v1.3.0"

This makes it easy to keep track of your versions and rollback if needed.

Find playgrounds and more about git at https://hurna.io/academy/git/index.html

Introduction

“Git is a free and open source distributed version control system designed to handle everything from small to very large projects with speed and efficiency. Git is easy to learn and has a tiny footprint with lightning fast performance.” (Git)

But first thing first : what is a “version control system”, and why should we care?

A version control system (VCS) tracks changes to files. As we modify files, the system records and saves each change within an history. This allows to restore a previous version of your code at any time. Using a VCS also generally means that if we screw things up or lose files, we can easily recover to any checkpoint.

In a collaborative environment, it is common for several developers to share and work on the same source code. While some developers will be fixing bugs, others will be implementing new features, etc. Git is the standard system used to manage all of this.

In short, a version control system like Git is essential for all kind of programming and software development. It makes it easy to:

- Keep track of code history
- See which changes were made
- See why were changes made
- See who made which changes
- Collaborate on code as a team
- Deploy to staging or production

We will learn here Git from essentials like repositories, branches, commits, and Pull Requests to more advanced topics such as workflow, statistics, automatic build integration and how to collaborate with other developers.

What if I don’t use it?

I am sure any of us has already been doing some file renaming to keep track of different versions, as for instance : “resume”, “resume_v2”, “resume_062018”…

In other words, any of us has already been stuck to manually save multiple versions of files using different names. Renaming a file also doesn’t give us any context as to what changes were made or who they were made by. When multiple team members edit the same file, overwriting occurs and it starts being impossible to keep up with the latest file version.

This problem already occurs for a unique file. I let you imagine how messy it can be with thousands of them.

Why using Git in particular?

The very short answer would be : Git is the most widely used version control system in the world and is considered the modern standard for software development.

Unlike older centralized version control systems such as SVN and CVS, Git is distributed: every developer has the full history of their code repository locally. Thus, if any server dies, and these systems were collaborating via that server, any of the client repositories can be copied back up to the server to restore it. Every clone is really a full backup of all the data.

Git also has excellent support for branching, merging, and rewriting repository history, which has lead to many innovative and powerful workflows and tools. Pull requests are one such popular tool that allow teams to collaborate on Git branches and efficiently review each others code.

Great, since we know for what and why we are using Git. Let’s get started!

Simple guide — 5 steps

This guide is a simple and practical introduction to start working with git from scratch. Here, we will go straight to the point. This step by step guide to a Git workflow aims to help give an introductory overview for managing any project.

Let’s get started on using Git now.

1. Installation

Git for Linux

Git for OSX

Git for Windows

Verify if Git is installed by using the following command in the command prompt:
git --version

2. Create or get a repository

To start working on a Git repository, you have the choice to either create a new one or use an existing one (from GitHub for instance).

Create a new repository

create a new directory, create a directory and perform a
git init
inside to create a new git repository.

Checkout a repository

create a working copy of a local repository by running the command
git clone /path/to/repository
when using a remote server, your command will be
git clone username@host:/path/to/repository

3. Save our changes

Our local repository consists of three “trees” maintained by git.
The first one is your Working Directory which holds the actual files.
The second one is the Index which acts as a staging area.
And finally, the HEAD which points to the last commit we have made.

A. Commit

Note : Git comes with built-in GUI tools for committing — git-gui. We recommend you to use it in order to avoid being struggled with the command line. You just have to launch it within your repository:
git gui

Add & commit

You can propose changes (add it to the Index) using
git add <filename>
git add *
This is the first step in the basic git workflow. To actually commit these changes use
git commit -m "Commit message"
Now the file is committed to the HEAD, but not in your remote repository yet.

B. Push

First thing first, we need a host (such as Github, Gitlab, Bitbucket…) to put it online. If it has not been done yet, just create an account on one of this platform.

Pushing changes

Your changes are now in the HEAD of your local working copy. To send those changes to your remote repository, execute
git push origin master
Change master to whatever branch you want to push your changes to.

If you have not cloned an existing repository and want to connect your repository to a remote server, you need to add it with
git remote add origin <server>
Now you are able to push your changes to the selected remote server

The full workflow results as the following:

4. Branching

A. Branches

Branching allows each developer to branch out from the original code base and isolate their work from others. It also helps Git to easily merge versions later on.

Imagine that you are working with your colleagues on the same file. There is a solid chance that someone will, at least partially, overwrite one other’s work. We can avoid that by branching in order to isolates our work from that of other team members.

In short, a Git branch is an independent line of development.
Note: each node on the image above represents a commit.

Branches

The master branch is the “default” branch when you create a repository. Use other branches for development and merge them back to the master branch upon completion.

create a new branch named “feature_x” and switch to it using
git checkout -b feature_x
switch back to master
git checkout master
and delete the branch again
git branch -d feature_x
a branch is not available to others unless you push the branch to your remote repository
git push origin <branch>

Note : Git comes with built-in GUI tools for browsing — gitk. We recommend you to use it in order to get a good overview of your branches. You just have to launch it within your repository:
gitk

B. Update & Merge

update & merge

To update your local repository to the newest commit, execute
git pull
in your working directory to fetch and merge remote changes.
to merge another branch into your active branch (e.g. master), use
git merge <branch>
in both cases git tries to auto-merge changes. Unfortunately, this is not always possible and results in conflicts. You are responsible to merge those conflicts manually by editing the files shown by git. After changing, you need to mark them as merged with
git add <filename>
before merging changes, you can also preview them by using
git diff <source_branch> <target_branch>

Reverting changes

If you instead want to drop all your local changes and commits, fetch the latest history from the server and point your local master branch at it like this:

Replace local changes

git fetch origin
git reset --hard origin/master

5. Extras

Tag & Version

It is recommended to create tags for software releases. You can create a new tag named Hurna v1.3.0 by executing
git tag -a v1.3.0 -m "Hurna v1.3.0"

Log

in its simplest form, you can study repository history using
git log
You can add a lot of parameters to make the log look like what you want. To see only the commits of a certain author:
git log --author=michael-jeulinl
To see a very compressed log where each commit is one line:
git log --pretty=oneline
Or maybe you want to see an ASCII art tree of all the branches, decorated with the names of tags and branches:
git log --graph --oneline --decorate --all
See only which files have changed:
git log --name-status
These are just a few of the possible parameters you can use. For more, see
git log --help

Wonderful! If you get this far, you master everything you need to manage a project and its versions. The next courses are about putting everything into advanced practices.

Here is a list of some more Git commands to get you going with Git in a day-to-day workflow: https://hurna.io/academy/git/general_commands.html

In our previous courses, we have seen how to perform the four fundamental operations (add, subtract, multiply and divide) on both natural numbers and integers. However, we didn’t handle more complex cases such as when it was not dividing things up exactly. This is the subject of this important course: the Euclidean division — or division with remainder.

Don’t worry, the name and importance hide something very easy to understand and perform ;)

Euclidean division, and algorithms to compute it, are fundamental for many questions such as for finding the greatest common divisor (GCD) or in modular arithmetic — modulo operation (used absolutely everywhere in computer science: from website to cryptography through video games).

But first, a small reminder about the division!

Reminder — Dividing

The division allows us to calculate the sharing problems, it is the opposite of multiplying.

Example:
There are 12 blue candies, and 4 friends want to share them, how do we divide the candies?

The answer may seem evident: if each friend takes 3 candies, we are all good. Division is splitting into equal parts or groups. It is the result of “fair sharing”.

Note:
As we said, another way to think of division is as the opposite of multiplication. Taking this example we got:

→ 12 / 4 = 3 (we gives 3 candies to each of us)

Now if we invert the operation using the result, we replace the ‘=’ with a ‘x’ sign and the ‘/’ with an ‘=’ sign:

→ 12 = 3 x 4 (if 3 candies are given to each of us, we shared a total of 12 candies)

This is, indeed, a mathematical definition of the division:
a / b = a ∗ 1 / b

Using multiplication is a great way to check our division and master our math tests. But remember this rule, it is the only one to know when dealing with division:

We never divide by 0!

But… Sometimes it does not fit perfectly!

Let’s deal with it!

The Remainder

As we have seen, division is breaking a number up into an equal number of parts, but… there may be something left over. Let’s go back on our previous example, however, this time the 4 friends have 13 (one more than before) blue candies to share:

We can see that there is 1 left over; we call that the Remainder.
Note: it may eventually be possible to cut the remaining candy in four (a quarter — 1/4 — of candy for each), but this is addressed in the course dealing with Fractions.

We will now learn how to perform all divisions (even with large numbers) by hand. But first, a quick overview of the vocabulary.

Dividend, Divisor, Quotient and Remainder

Each part of a division has a name:

— Dividend: The dividend is the number you are dividing up.
 — Divisor: The divisor is the number you are dividing by.
 — Quotient: The quotient is the main result (the number of candies you can give to each one).
 — Remainder: The left over.

For instance: 13 (dividend) ÷ 4 (divisor) = 3 (quotient) ‘R’1 (remainder)

Great, I think we are now fully ready to tackle the process!

Euclidean division

To perform a division by hand, every student learns (without knowing) an algorithm which is one of the oldest algorithms in use (it appeared in Euclid’s Elements around 300 BCE).

We will decompose the process step-by-step (only 2 steps to repeat) through an example: 533 ÷ 4.

Here is the color legend used:

Red: the number we will try to divide by our divisor.
Blue: the divisor, how many of them do we have within the red number?
Green: the amount of divisor found within the red number.
Yellow: subtracting ‘Blue x Green’ from the red number.

Now, we just repeat with the process with the result of the subtraction as the dividend.

And finally…

We found out that: 533 ÷ 4 = 133, ‘R’1
We can also say that: 533 = 4 x 133 + 1

Woaw, this is very handy!

Euclid’s algorithm — always find the GCD

To always find the GCD we will use Euclid’s algorithm:

- Perform the Euclidean division of the greatest number (noted a) of the fraction on the smallest number (noted b) and keep the rest (noted r).

- As long as the rest is different from 0, we reiterate the division replacing a by b and b by r.

We will then be able to write:
1053=81 * 13
325=25 * 13

We will use the GCD a lot starting with mastering the fractions whether to simplify them or to perform operations.

This may be used as a first overview of the programming world. This glossary is also a good fit if you ever wanted to be able to understand and communicate with developers or any other people working on digital projects.

Back End

The back-end, or the “server-side”, is basically everything that is behind the scene. Systems have all kinds of logic that happen in the background that make them work: data needs to be stored and retrieved, business logic needs to be followed, results need to be calculated… For a website or web application, this refers to everything the user can’t see in the browser, like databases and servers.

Command Line Interface (CLI)

A Command Line Interface is used to process commands to a computer program in the form of lines of text. They are opposed to GUI (Graphic User Interface). We use it all the when using the Terminal (e.g. Unix console), for instance using Git:

$ git clone https://github.com/Hurna/Hurna-Core.git

Code Review

Code review is a phase in the software development process in which the authors of code and peers review the code to make sure that the overall code is healthy, does not contain bug, and is improving over time.

Code reviews are classless: being the most senior person on the team does not imply that our code does not need review.

Continuous Delivery — Continuous Integration(CI/CD)

For big apps, pushing to production requires a lot of steps. Continuous integration and continuous delivery (CI/CD) is the activity of automated build, integration, and testing processes. It allows to release continuously new updates. Managing this process is often the work of people called DevOps.

Front End

For an application, the Front End is the part that is exposed to the user. The front end of a website is the part that users interact with. Everything that you see when you’re navigating around the Internet, from fonts and colors to dropdown menus and sliders, is a combo of HTML, CSS, and JavaScript being controlled by your computer’s browser.

Middleware

A Middleware is a software that bridges gaps between other applications, tools, and databases in order to provide unified services to users. It is commonly characterized as the glue that connects different software platforms and devices together.

In web development, it often lies between the part of the code that receives the request and the other part of the code that do database updates, generates the response, etc.

Refactoring

Refactoring is a disciplined technique for restructuring an existing body of code, altering its internal structure without changing its external behavior.

The basic purpose of code refactoring is to make the code more efficient and maintainable. This is key in reducing technical cost since it’s much better to clean up the code now than pay for costly errors later.

Unit Testing (UT)

Unit testing is an essential part of developing software applications. Also called component testing, it is all about isolating one unit of code to verify that it’s working as it should be.

Unlike many types of testing, UTs are usually done by the developer of the code itself. If you’re not doing unit testing now, I recommend you to get started on it.

Another way to look at unit testing is that we write the tests first. This is known as Test-Driven Development (TDD for short). TDD brings additional advantages:
- We don’t write speculative “I might need this in the future” code — just enough to make the tests pass to cover our API.
- By writing the test first, we are forced into thinking about how you want to call the code, which usually improves the design of the code in the long run.

Algorithm

Everything that we do with a computer relies in some way on an algorithm. Any software (even the most advanced Artificial Intelligence) are only algorithms put together with some structured data (cf. below).
That’s it: Algorithms + Data Structures = Software.

In other words, it is a list of instructions, procedures, or formula that solves a problem… It can be a code to sort search results efficiently, a code to find the shortest route between A and B on a map, a formulal to encrypt and decrypt sensitive information, etc.

Data Structure

Data structures are the way we can store and retrieve data, they represent the knowledge to be organized in memory. No matter what problem are we solving, in one way or another we have to deal with them !

Dead Code

Dead code is any section of the codebase that is never used by the application.

Infinite loop — Endless loop

An infinite loop is a sequence of instructions that will continue endlessly, unless an external intervention occurs. It may be intentional, but most of the time, our breaking condition doesn’t work. The result of such infinite loop often results in a application that freezes (and consume most of our CPU which may then lead to general lags) or even crash.

Functional Programming

Functional programming or FP is a programming paradigm. This is a style of building software applications. Some of its principles are the way of building a program by composing pure functions, avoiding shared state, mutable data, and side-effects.

Garbage collection

When a program is running, it uses the computer’s memory. Garbage collection does exactly what it says, it looks for memory that can’t be used by the program anymore and frees it, allowing this freed space to be used again.

Memoization

Memoization is a technique used to store, the result of a computationally expensive function by storing it in a cache. If the function is called later using the same arguments, the result is loaded from the cache rather than being recomputed, saving CPU resources.

In brief: Memoization is a way to remember what we already found.
It is used to lower a function’s time cost in exchange for space cost.

Where naive recursion falls short with Fibonacci: the tree above shows for each indice (root) the nodes to be computed (all of its children). The red nodes are showing useless computation which may instead use the results already computed by the blue ones.

As a reminder the Fibonacci numbers are defined as follow:
F(0) = 0
F(1) = 1
F(n) = F(n−1) + F(n−2)

Parse

The action of transforming data described textually into data stored within a data structure. When we fetch data from a web API, it is usually a JSON (just a string). We need to parse it, to transform it into an object, to manipulate data efficiently:

// JSON data (stored as a string)
  {
    "name": "Maze Solver - Pathfinding",
    "list": {
      "a_star": "A* (A-Star)",
      "bfs": "Breadth First Search",
      "dfs": "Depth First Search",
      "dijkstra": "Dijkstra"
    }
  }

// JS manipulate data through an Object built from the string parse.
  const parsedData = JSON.parse(data);

  // parsedData is now an object and can be accessed as follows:
  parsedData.name;              // "Maze Solver - Pathfinding"
  parseData.list.forEach(...);  // Iterate over the list

Spaghetti code

Spaghetti code is a slang used to describe a program’s source code that is difficult to read or follow by a human because of how the original programmer wrote the code. It can be caused by several factors, such as volatile project requirements, lack of programming style rules, and insufficient ability or experience of the programmer.

Class (Prototype) — Object (Instance)

A class (prototype) is a template that defines object properties and may also describe object behavior.
An object is an instance of a class.

We can think of class as a sketch (prototype) of a car. It contains all the details about the number of tires, the doors, the color… Based on these descriptions we build a car, let’s say the Green car: this Green car is the object. As many cars can be made from the same prototype, we can create as many objects as we want from a class.

Find more details in the ‘Function — Class’ glossary.

Constant

A constant is a value or a variable with a value that will never change during the running time of the program. The keyword ‘const’ is used to define such data in most programming language:

const auto lastName = "CantBeChanged";

Data Structure

Data structures are the way we can store and retrieve data, they represent the knowledge to be organized in memory. No matter what problem are we solving, in one way or another we have to deal with them !

A data structure instance is an Object.

Null — Nullptr

Null and NullPtr represent an intentional absence of a value.

let uninstantiated = null; // JS

Car* lostPtr = nullptr; // C++

Pointer

A pointer is a variable that holds a memory address where a value lives. As an analogy, a page number in a book’s index could be considered a pointer to the corresponding page.

Pointers are the foundation of how computers allocate and deal with memory in hardware. They allow us to read and write directly in memory space.

String

A string is a sequence of characters used to represent text.

const string = "hello world";

A string can be manipulated as an Array containing chars (cf. below).

Primitives

The primitive data type is the basic building block of data. They hold one single value. They represent a char, number, or boolean.

Note: the actual range of primitive data types that is available is dependent upon the specific programming language that is being used (those are the most basic ones).

Boolean — bool

A boolean has 2 possible values: true or false.

bool truth = true;

Character — Char

It stores a single character and requires a single byte of memory:

const char letter = 'H';

Number — Integer (Int), Float…

A numeric data type.

const pi = 3.14; // :p

Undefined

Undefined with JS is a primitive value automatically assigned to a variable that has just been declared or to the argument of a function that has not been provided.

Formats

JSON

JSON stands for JavaScript Object Notation. It is a way to format data so that it can be human readable, storable as a string and thus be transmitted from one place to another. It is most commonly used in web development.

{
  "id" : 8,
  "name" : "Globo",
  "functions" : ["solver", "player", "teacher"],
  "isAvailable" : true
}

XML

XML stands for eXtensible Markup Language and was designed to store and transport data in a readable way for both humans and machines. Both XML and JSON have the same purpose.

Argument — Parameter

A parameter (or formal argument) is a variable in a function or method definition. When the function is called, the argument is the data we pass in the function call.

int square(int number)  // number is the parameter
  { return number * number; }
  ---
  auto result = square(3); // 3 is the argument

Callback

A callback is a function that is passed as an argument to a function, which is expected to call back (execute) at a convenient time. This may for instance be to display information (as the number of lines) of a file once read.

// Callback definition
  function displayCount(count)
  { console.log("File contains " + count + " lines."); }

  readFile("text.txt", displayCount); // Callback passed as argument

Callbacks are used everywhere in association with events in web development. In the case of an asynchronous call, call back can be executed when a response has been received.

Constructor

The constructor is a method, inside a class, that is used to instantiate (create an instance) an object. It is automatically called when an object is built.

Function

A function is a named section of a program that performs a specific task.

multiply(3, 3); // multiply is the function called

Some programming languages make a distinction between a function, which returns a value, and a procedure, which performs some operation but does not return a value.

Method

A method is a function that belongs to a class or an object. It is bound to it, defined only within that scope of usage.

Nested Function

A nested function is a function contained inside of another function. It can be used to limit the scope of the inner function.

function getSurfBoard(weather, size, height) {
  const boardList = getBoardForWeather(weather);

  // Nested function
  function filterBoardByBody(size, height) {...}
}

Recursive Function

The term recursive describes a function or method that calls itself.

Understanding how recursion works is a fundamental programming skill.

function fibonacci(number) {
  if (number === 0) return 0;
  if (number === 1) return 1;
  return fibonacci(number - 1) + fibonacci(number - 2);
}

As a reminder the Fibonacci numbers are defined as follow:
F(0) = 0
F(1) = 1
F(n) = F(n−1) + F(n−2)

Git — Version Control

Git is an open-source distributed version control system designed to track changes and in computer files and coordinating work on those files among multiple people and locations. It is primarily used to allow programmers to work together in a codebase.

One might never know all the git commands because they are numerous but there are some that every developer is expected to know to be able to collaborate with other developers.

Branch

Branching allows each developer to branch out from the original code base and isolate their work from others. It also helps Git to easily merge versions later on.

Imagine that you are working with your colleagues on the same file. There is a solid chance that someone will, at least partially, overwrite one other’s work. We can avoid that by branching in order to isolates our work from that of other team members.

In short, a Git branch is an independent line of development.
Note: each node on the image above represents a commit.

$ git checkout -b [branch name] // Create a new branch and switch to it

Commit

To commit is the action of adding your changes to the local repository. It needs to be accompanied with a commit message that describes what this change is bringing to the code base:

$ git commit -m "This fix a bug in the code base" // Commit changes

We recommend to use a GUI to manage commits, it gives us a better control on what we want to commit.

$ git gui // (git-gui)

Conflicts

When working in Git, users can combine commits from two different branches through an action known as merging. Files are automatically merged unless the commits update the same line of code differently. In that case there is a conflict: which version of this line should be taken?

Merge conflicts can traditionally cause developers a lot of grief when working in the terminal. This is why we advise to use a GUI (such as meld) to resolve conflicts.

GitHub

GitHub, Inc. is a US-based global company that provides hosting for software development version control using Git. This is the world’s largest open source platform. It is now a subsidiary of Microsoft, which acquired the company in 2018 for US$7.5 billion.

Merge

To merge one branch into another is the action of fusing 2 different versions of the project together. If you are done working on a branch named “my-feature”, you can merge it to master in order for the master branch to be updated with your work.

$ git merge [source branch] [target branch] // Merge a branch into a target branch

Pull

This is the action of updating your local version of a repository to the newest commit. Do not forget to do it before starting to work on something!

$ git pull // Update local repository to the newest commit

Push

This is the action of sending your commits to the remote repository (on GitHub or GitLab, for example).

$ git push // Push changes to remote repository

Repository (repo)

Take it as a folder that contains all the source files and tracks all the changes made, building a history over time. On Github, each project is a repo.

Web — HTTP

CSS

CSS stands for Cascading Style Sheets, it describes how HTML elements are to be displayed. It allows you to create great-looking web pages and control their layout all at once form external stylesheets (stored in CSS files).

CSS saves a lot of work.

// All of the tag h1 are green and centered
  h1 {
    color: green;
    text-align: center;
  }

Document Object Model (DOM)

The HTML we write is parsed by the browser and turned into the DOM (Object), which is essentially an API to the page that allows to read and manipulate the page’s content, structure, and styles.

With the DOM, JavaScript gets all the power it needs to manipulate our pages dynamically.

Event, Event Listener

Clicking, scrolling, pressing a key on our keyboard are what is called: “event”. There are a lot of them. On a website, we might want to listen to them by creating an event listener in order to do form validation, react to a click on a button, etc.

HTML (Hypertext Markup Language)

HTML (Hypertext Markup Language) is the code that is used to structure a web page and its content. HTML is not a programming language; it is the standard markup language used to create web pages and web applications. This markup uses tags ‘<>’ to tell a web browser how to display text, images and other forms of multimedia on a webpage.

HTTP

HTTP is a protocol which allows the fetching of resources, such as HTML documents. It is the foundation of data exchange on the Web and it is a client-server protocol, which means requests are initiated by the recipient, usually throughout he Web browser. A complete document is constructed (or fetched) on the server side and then sent to the useer.

HTTPS

Hypertext transfer protocol secure (HTTPS) is the secure version of HTTP. HTTPS is encrypted in order to increase security of data transfer. This is particularly important when users transmit sensitive data, such as by logging into a bank account, email service, or health insurance provider.

Any website, especially those that require login credentials, should use HTTPS. In modern web browsers, websites that do not use HTTPS are marked differently than those that are. Look for a green padlock in the URL bar to signify the webpage is secure.

JWT

JWT or JSON Web Token is a standard used to create secure access tokens for an application.

In the case of a web application, the server will generate a token that certifies the user identity and send it to the Client. The Client will, for every subsequent request, attach the JWT to it so the server knows the request comes from a particular identity.

VOILA ! Don’t hesitate to visit H.urna Academy to get deeper knowledge for each of these concepts: https://hurna.io/academy/glossaries/index.html

H.urna - Opening sciences for all

Illustrated guide to terms used daily in programming was originally published in Level Up Coding on Medium, where people are continuing the conversation by highlighting and responding to this story.

In other words, the set of integers is the union of the set of natural numbers and their opposites. If a is an natural number then -a is an integer of opposite sign. On a graduated axis, two opposite numbers are symmetrical with respect to the origin (0).

Please note that Zero is considered to be both positive and negative.

Note: Some people may have different definitions for the same word used to define a number set. Some people say that whole numbers can also be negative, which makes them exactly the same as integers. Some people also say that zero is NOT a whole number.

To be precise, the easiest way is to use the mathematical notation. This notation is strict and therefore avoids any confusion:
Z : all integers.
Z* : (Z star) all integers except 0 (zero).
Z+ : all integers greater or equal to 0. It is the same as N.
Z*+ : all integers greater than 0. It is the same as N+.

Why using negative numbers?
What do they represent?

In the 7th century AD, the Indian mathematician BRAHMAGUPTA set out for the first time rules to operate on three kinds of numbers displayed “goods”, “debts” and “zero”. Debts (somehow negative numbers) were then used in India for trade.

Today we find examples of negative numbers absolutely everywhere:
- Elevator: To go down into the basement we have a “-” sign telling us to go below the ground floor.

- Weather: If the temperature is below 0°, the “-” sign will indicate this negative temperature.

• Video game: When we lose life points, we see on the screen “-” signs in front of the numbers.
  - Chronological frieze: A date before our year 0 will be noted with a “-” sign or will be annotated “BC”.

- Finance: A bank uses positive numbers to represent deposits and negative numbers to represent withdrawals.
- Etc.

If these negative numbers are used absolutely everywhere today, you should know that they were ignored for a very long time, or even looked down upon as difficult for the human mind to grasp. Here is a little bit of history which will also console all those who encounter difficulties with negative numbers!

A little history

Although the first set of rules for dealing with negative numbers was stated in the 7th century by the Indian mathematician Brahmagupta, it is surprising that in the 18th century, negative numbers were still considered absurd in Europe.

In 1758, the British mathematician Francis Maseres was claiming that negative numbers “… darken the very whole doctrines of the equations and make dark of the things which are in their nature excessively obvious and simple”.

Negative numbers aren’t that easy.
What, exactly, do negative numbers mean?
How can you take 4 pens from 3?
How could you have less than nothing?
Yet today, it seems absurd to think negatives aren’t logical or useful.

What happened?
Negatives are not something we can touch or hold.

Things started to change when European scholars started translating Arabic texts obtained from North Africa. They were finally exposed to new ways of thinking, and started catching up with the Indian and Chinese subcontinent.

Rather than saying “I owe you 30″ and reading words to see if I’m up or down, I can write “-30″ and know it means I’m in the hole. The positive and negative signs automatically keep track of the direction — you don’t need a sentence to describe the impact of each transaction.

With the “minus” sign notation Math became easier and more elegant. It didn’t matter if negatives were “tangible” — they had useful properties, and we used them until they became everyday items.

But let’s not be smug about the struggle: negative numbers were a huge mental shift. Even Euler, the genius who discovered exponential and much more, didn’t understand negatives as we do today. They were considered “meaningless” results.

As Bernard de Chartres, Isaac Newton or Blaise Pascal would say:
We are “Dwarfs on the shoulders of giants”.

Easily perform our operations

Addition & Subtraction

Good news: these operations are done exactly as for natural numbers !
Except that this time, we can go below 0; please note that ‘-a’ means exactly the same as ‘0 - a’.

There are two unique things to know to quickly become a real ninja in the art of carrying out our operations:

1. Adding a negative is the same as subtracting a positive:
(−b) + a = a − b

a+(−b)=a−b

2. Subtracting a negative is the same as adding a positive:

a−(−b)=a+b

Let’s take an example that looks complicated and turn it into something very simple:
5 + 4 − 3 + (−2) −2 − (−4) = ?

Rule 1 : +(-2) →- 2
Rule 2 : -(-4) → + 4

Thus:
… = 5 + 4 − 3 − 2 − 2 + 4 = 65

And voila!
We already know everything about addition and subtraction!

Multiplication & Division

We still have good news!

As for additions and subtractions:
- These operations are done exactly as for natural numbers
- There are two unique things to know.
- The combination of signs results the same.

1. The product of two numbers of opposite sign is negative:
−b ∗ a = −(a∗b)

a ∗ −b = −(a∗b)

2.The product of two numbers of the same sign is positive:
(−a) ∗ (−b) = a∗b

Here are some very simple examples to illustrate:
a. −3 ∗ −3 = 9
b. 2 ∗ −3 = −6
c. 2 ∗ 2 = 4
d. −3 ∗ 6 = −18

e.−3 ∗ 3 ∗ −3
= −9 ∗−3
=27

f. −2 ∗ 2 ∗ −2 ∗ 2 ∗ −2
=−4 ∗−4 ∗ −2
= 16 ∗ −2
= −32

And finally, a mnemonic often used, a friend is ‘+’, an enemy is ‘-’:
+ + ⇒ + | a friend of a friend is my friend
+ − ⇒ − | a friend of an enemy is my enemy
− + ⇒ − | an enemy of a friend is my enemy
− − ⇒ + | an enemy of an enemy is my friend

Be the math with your Kids!

Natural numbers are the most commonly used numbers in everyday life, they allow you to count a distinct number of objects (or units). For example, we can have 2 pens, 1 cat and a bill of 5 dollars in our pocket etc.

The set of natural whole numbers is noted N, it is a tiny part (even if it is infinite) of existing numbers. It is for example a set smaller than the one of the integers Z.

The theory stops there! We will now get to the heart of the matter. We will first see how to write whole numbers, then what mathematical operations mean and how to perform them.

Decomposing a Number — Number Units

Given an integer, the rightmost digit is the units digit, which is written in the units column. The one immediately to the left is the tens digit, which is written in the tens column. We complete the table so on from right to left, until all the numbers are written.

Note: The more a digit is located to the left of the number, the greater its value. For example, 6 hundreds is greater than 6 tens because the hundreds are more to the left than the tens.

Perform a mathematical operation

Addition

Performing an addition is adding quantities, we call it: calculating the sum of several terms (or numbers). For instance, let’s count the steps we take forward: if we take one step and then two steps, we will have made 1 + 2 = 3 steps forward in total. Below is the table of the additions of the figures from 1 to 10:

The good news is that we don’t need to remember these kind of tables and that we will be able to use our blank numbering table to make all kind of additions. We put the numbers one below the other with aligning the figures (number units) in a column, then we add the numbers, column by column, from the right to the left.

Please note: we must not forget to carry over the retain when the sum of the digits is greater than 10 (as shown in our example on the right).

In the calculation of a sum, the order of the terms does not matter (the operation is said to be commutative): 2+4 = 4+2 = 6

In the calculation of a sum, we can group terms to facilitate the calculation (the operation is called associative): 8 + 2 + 8 + 2 = (8+2) + (8+2) = 20

Subtraction

The subtraction is an operation that calculates the difference between two (or more) numbers. This difference between 2 numbers is the number that must be added to one to get the other.
Let’s say I have 1 pen in my kit, how many more do I need to have 3?

The answer is : 3 - 1 = 2.
I need 2 more pens to have 3 pens in the end.

Another way of looking at subtraction is to remove quantities. For example by going down steps: if we climb 3 steps and then go down a 1 step, we will have climbed 3 - 1 = 2, that is 2 steps in total.

To subtract two numbers, the terms are laid out in the same way as for an addition, then we subtract the numbers, column by column, from the right. If the number above is less than the number below, we add 10 to the number at the top, then we transfer the retain (-1) to the left column.

In the first example, we see in the tens column that 4 is less than 5. We will then have (4 + 10) - 5 = 14 - 5 = 9. Then we carry the retain -1 on the left column.

Verification

If we have a little doubt about our result, the calculation of the verification allows us to quickly check it. We simply check that our result + the term subtracted = the first number. With the two operations carried out above, we will therefore have:

Perfect, we fall back on our initial numbers: the calculations are verified!

Subtract a larger number?

In the natural numbers set, this operation is impossible!
The operation is not stable in this set.
But don’t panic because the next lesson, the one about integers, explains how to overcome this problem ;)

Multiplication

The multiplication is an operation which allows to calculate the product between two numbers. Multiplication corresponds to an addition repeated several times. It makes it possible to greatly simplify the writings as well as the calculations.

Let’s take “3 + 3 + 3 + 3 + 3 + 3 + 3 + 3 + 3 + 3 + 3” (11 in total), this calculation can be written 11 * 3. We will also say that we have 11 times the number 3, for a total of 33. Below is the multiplication table for the numbers from 1 to 10:

When we multiply by 10, we simply shift each digit in the box to the left. For example 20 x 10 = 200 (the 2 of tens became the 2 of hundreds).

We are now used to it (it’s always the same technique), we start by arranging the numbers one below the other by aligning the numbers in columns (numbering units), then we multiply the numbers, column by column, from the right.

Warning!!!
When the multiplier is a number made up of several digits, the calculations are carried out digit after digit with all of the digits of the top number.
Then, for the next digit of the multiplier (bottom):
We go to the line and we shift the results of a column (see the example on the right).

Please note: We must not forget to defer the retain when the product of the figures is greater than 10 (this retain must be added).

In the calculation of a product, the order of the terms does not matter (the operation is said to be commutative): 2 * 4 = 4 * 2 = 8

In the calculation of a product, we can group terms to facilitate the calculation (the operation is called associative): 3 * 2 * 3 * 2 = (3 * 3) * (2 * 2) = 36

Congratulations, we have just obtained the most fundamental bases in mathematics !!
May the math be with us!

Division

Now that we have learned how to multiply integers, dividing should be a breeze. The reason is that they follow the same rules. The division allows us to calculate the sharing problems, it is the opposite of multiplying.

Example:
There are 12 blue candies, and 4 friends want to share them, how do we divide the candies?

The answer may seem evident: if each friend takes 3 candies, we are all good. Division is splitting into equal parts or groups. It is the result of “fair sharing”.

Note:
As we said, another way to think of division is as the opposite of multiplication. Taking this example we got:

→ 12 / 4 = 3 (we gives 3 candies to each of us)

Now if we invert the operation using the result, we replace the ‘=’ with a ‘x’ sign and the ‘/’ with an ‘=’ sign:

→ 12 = 3 x 4 (if 3 candies are given to each of us, we shared a total of 12 candies)

This is, indeed, the mathematical definition of the division:
a / b = a ∗ (1 / b)

Using multiplication is a great way to check our division and master our math tests. But remember this rule, it is the only one to know when dealing with division:
We never divide by 0!

But… Sometimes it does not fit perfectly!

Indeed, sometimes, we have a remainder; we will address this case and more complex ones within a dedicated course: “The Euclidean division” ;)

In this introduction we will see the vocabulary and the calculation rules used for all the set of numbers. This may seem complicated at first, but for each set (see Quick Access above) we will explain in detail and with examples how to do it. This general vision will then become super practical to quickly consult all the rules, the vocabulary and what each set represents.

Let’s start with the big picture, how are the first sets of numbers categorized?

N : A natural integer is a positive and “without comma” number such as 0, 1, 2, 3 …

Z : An integer is either a positive or negative number and “without comma” such as
 …-3, -2, -1, 0, 1, 2, 3…

Q : A rational number is a number which can be written as a fraction such as 1/3, -2/7 etc.

R : Some numbers like √2 or π are not rational. The set of reals completes the set Q.

Priorities (order) of operations

Like the rules (below), the operational priorities are true all the time. We will have to follow them each time we have a calculation to perform :

1. Calculations in parentheses
2. Powers
3. Multiplication and Division
4. addition and subtraction
5. In case of operations with the same priorities, it is at our convenience (we do as we want).

Some examples

4×3+6 = 12+6 = 18

3×5−2×3+5 = 15−6+5 = 14

(5−3)×(7+1) = 2∗8 = 16

Calculation rules and vocabulary

This vocabulary and these calculation rules will follow you until the end of your studies and will remain unchanged. It may seem a little heavy at first, but we will use it daily in math whatever the level of study. Let’s go:

Division

We never divide by 0 !

Neutral element

we call neutral element a number that does not change the result of an operation.

The addition has a neutral element, the null element: a + 0 = a
The multiplication has a neutral element, the unit : a × 1 = a

Inverse number

We call inverse of the number a (not zero) the number noted a-1 or 1/a that verifies :

a ∗ 1/a = 1

or

a ∗ a^(−1) = 1

Opposite number

We call opposite of the number a the number noted –a that verifies :

a +(−a) = 0

On a graduated axis, two opposite numbers are symmetrical with respect to the origin (0).

Associative operation

An operation is associative if the result is invariable whatever the grouping of consecutive terms. In other words if the operator (noted ❄︎) has the following properties regardless of the elements a, b and c:

(a❄︎b)❄︎c = a❄︎(b❄︎c)

The addition is associative : (a + b) + c = a + (b + c)
The multiplication is associative : (a × b) × c = a × (b × c)

Attention: Subtraction and division are not associative!

Commutative operation

A commutative operation is an operation which allows to change the order of terms without changing the result.

The addition is commutative : a + b = b + a
The multiplication is commutative : a × b = b × a

Mathematically, this would be written:

∀x,y∈R:x+y=y+x

∀x,y∈R:x×y=y×x

Attention: Subtraction and division are not commutative!

Distributive operation

Multiplication is distributive on addition. This translates as follows:

a∗(b+c)=(a∗b)+(a∗c)

The image above is a visual demonstration. Indeed, we can see that the area of the total rectangle “c * (a + b)” is equal to the sum of the two interior areas “(c * a) + (c * b)”.

Stable operation

In mathematics, we say that a part A of a set E is stable (or closed) for an operation defined on E if this operation, applied to elements of A, produces an element of A.

For example, the set N (natural integers or positive integers) is stable for addition and multiplication: this means that if I add or multiply any two natural integers, the result will still be a natural integer.

N is not stable for subtraction (or division): for example 2–3 = -1, which is not in N.

Voilà ! We now know the rules of the game for performing mathematical calculations.

Introduction

A Binary Search Tree (BST), Ordered Tree or Sorted Binary is the first tree data structure we are studying. Unlike Arrays, Linked Lists, Stacks and Queues which are linear data structures, a Tree is a hierarchical (and nonlinear) data structure which is intrinsically recursive. Still, BST are easy to understand and manipulate. Here is how it looks:

One reason to use trees might be because we want to store information that naturally forms a hierarchy. Another one is their very important characteristic that allows fast — O(log n) — insert, search and delete operations.

Tree, Binary Trees and Binary Search Trees (BST)

Before tackling BST it is important to precise the terminologies, which are often confused.

Tree

A tree has no restrictions on the number of children each node can have. The topmost node in a tree is called the root node and the nodes with no children are called leaf nodes. They are also called N-ary trees:

The height of a tree is the number of edges from the root to the deepest leaf (here height = 3).

Binary Tree

Binary trees is a general concept of particular tree-based data structure. Various specific types of binary trees (e.g. BST below) can be constructed with different properties based on this concept. Binary trees can have at most two children for each node. Every node in a binary tree contains:
- A data element (e.g. 6)
- A pointer to the ‘left child’ node (may be ‘null’)
- A pointer to the ‘right child’ node (may be ‘null’)

It may sound surprising, but the organization of the Morse code is a binary tree.

Some other applications of binary trees

• Use to structure mathematical expressions within a calculator (Syntax Tree). This is for instance what is used by our AI Globo to solve your quadratic equations step-by-step.
• Constructed by compilers to parse expressions as calculators (Syntax Tree)
• Used in almost every 3D video game to determine what objects need to be rendered (Binary Space Partition).
• Use in compression algorithms such as mp3, jpg (Huffman Coding Tree)…

Binary Search Tree — BST

Finally comes our BST, which is a binary tree data structure with the two following constraints:
- All nodes of the left subtree of a node have a value less than or equal to the node’s value.
- All nodes of the right subtree of a node has a value greater to its parent’s value.

The binary tree on the right isn’t a binary search tree because the right subtree of the node “3” contains a value smaller than it.

Advantages / Drawbacks

• + Use the principle of binary search for insert, delete and lookup operations which have an O(log n) complexity.
• + Get all keys in sorted order by just doing a inorder traversal.
• + Doing order statistics, closest lower/greater elements, range queries etc. operations are easy.
• + Trees are very flexible data, allowing to move subtrees around with minimum effort.
• - The shape of the binary search tree depends on the order of insertions and deletions, and may become very unbalanced (if not managed — more detailed further). If the tree is completely degenerate, we finish up with something similar to a linear data structure : a linked list.

Let’s have a break with some peaceful binary tree fractals

Objectives

Operate a BST.
Build our own BST structures.
Put into practice pointers and recursion.
Understand the advantages / disadvantages of balancing a tree.

What is next?

If you haven’t jumped yet to maze generation algorithms, playing with them and using our explorer gives you visual insights of the duality between a maze and a tree structure. We will soon study more advanced tree structures such as red-black tree or, quadtrees and octrees which are two very useful structures to partition 2D and 3D spaces.

Build our own

We will first simply define our structure with Binary Trees that contains a data, a pointer to the left subtree (node), a pointer to the right subtree (node). The code is simplified for reading purpose, please use the github link to get access to the full version.

class BST
  {
    BST(const Value data) : data(data) {}
    ...

  private:
    T data;
    unique_ptr< BST > leftChild;
    unique_ptr< BST > rightChild;
  }

The semantic of the code shows that recursion plays a major role in tree data structures. Indeed, the left and right nodes of a BST are subtrees also defined as BST.

Binary search trees support everything you can get from a sorted array: efficient search, in-order forward/backwards traversal from any given element, predecessor/successor element search, and max/min queries…

Why not using a simple sorted array and use binary search then?

Having a sorted array is useful for many tasks because it enables binary search to be used to efficiently locate elements : O(log n). The problem with a sorted array is that elements can’t be inserted and removed efficiently in comparison with binary search trees.

Great. Since we have good reasons to proceed, let’s define an API.

// Manipulation
  void Insert(Value data)     // Insert an element
  BST* Remove(Value data)     // Remove an element

  // Traversal
  Value GetMin()              // Return the minima
  Value GetMax()              // Return the maxima
  List< Value > InOrder()     // Proceed in order traversal 
  BST* Search(Value data)     // Find an element

That’s a pretty big API, we will take it one section at a time to master tree operations. We will tackle them from the traversal methods to the manipulative ones.

Traversals

GetMin / GetMax

They are the easiest methods and they allow us to remember the properties of a BST:
- All nodes of the left subtree of a node have a value less than or equal to the node’s value.
- All nodes of the right subtree of a node has a value greater to its parent’s value.

// GetMin is getting the left most child
  const BST* GetMin()
  {
    auto curNode = this;
    while (curNode->leftChild)
      curNode = curNode->leftChild;

    return curNode;
  }

  // GetMax is getting the right most child
  const BST* GetMax()
  {
    auto curNode = this;
    while (curNode->rightChild)
      curNode = curNode->rightChild;

    return curNode;
  }

See below the recursive version for illustration (more memory consumption).

const BST* GetMin() 
{ return this->leftChild ? this->leftChild->GetMin() : this; }

const BST* GetMax() 
{ return this->rightChild ? this->rightChild->GetMax() : this; }

Search

Searching for a value uses the same principle as the Binary Search in a sorted array. If the value is lesser than the current node, we can say for sure that the value is in the left subtree, otherwise it is in the right one.

Inorder traversal

In an inorder traversal, we first visit the left child (including its entire subtree), then visit the current node and finally visit the right child (including its entire subtree). Note that the binary search tree makes use of the inorder traversal method to get all nodes in ascending order of value.

static void Inorder(const BST* node, List< Value >& result)
  {
    if (!node) return; // end of a branch (no data)

    Inorder(node->leftChild)  // Recurse in left subtree
    result.push(node->data);  // Get data
    Inorder(node->rightChild) // Recurse in right subtree
  }

Manipulate

Insert

Inserting a value in the correct position is similar to searching because we want to maintain the rule that left subtree is lesser than root and right subtree is larger than root. We keep going to either right or left depending on the value until we are a leaf. Then, we put the new node (or BST) there.

We may have noticed that the order of insertion may change the shape of our BST. This is the drawback mentioned earlier : our tree can be very unbalanced (or degenerate).

Left: we insert in order [4,2,5,1,3,6] → O(log n)
Right: we insert in order [1,2,3,4,5,6] → O(n)

We can see that the running times of algorithms on binary search trees depend on the shapes of the trees, which, in turn, depends on the order in which keys are inserted.

There are techniques known as tree balancing which maintain the tree balanced. We will see them with more advanced tree data structures such as red-black trees.

However, it is reasonable for many applications to use a BST if we assume that data are inserted in a random order. In that case, our operations with n nodes requires about 2 ln n.

As a first exercise we may write the procedure that will produce a balanced BST from a sorted array.

Remove

The last operation in the BST that we are going to discuss in depth is removing a node based on a given value. Deletion is somewhat more tricky than insertion as there are three cases to consider if the node exists in the tree:

Voila ! We now master BST and its operations, which give us a solid foundation daily used in software development.

Some exercises

bool IsBalanced()   // Check if the tree is balanced
int MinHeight()     // Return the smallest branch height
int MaxHeight()     // Return the highest branch height
int Size()          // Return number of nodes composing the tree

Stay connected for more advanced courses.

H.urna — Science for everyone.

Mastering Binary Search Tree — BST was originally published in Level Up Coding on Medium, where people are continuing the conversation by highlighting and responding to this story.

Introduction

What’s the shortest drive from our place to the nearest park?
How do we find a way through a maze?
Can we program a game character to find the exit avoiding enemies?

Pathfinding algorithms address the problem of finding a path from a source to a destination avoiding obstacles and minimizing the costs (time, distance, risks, fuel, price, etc.). This is a common programming challenge. Mainly known from navigation and games, we will find that the core algorithms apply to a huge range of problems.

For a brief introduction about mazes and why we enjoy them so much, please refer to ‘Introduction to Maze Generators’.

Objectives

We will first study Breadth First Search and Depth First Search because they are fundamental for traversing a graph (or a tree) and are often a required first step for many other types of analysis. We will then cover more advanced algorithms such as Dijkstra or A* (A-Star).

Understanding the data

The first thing to do when studying an algorithm is to understand the data.
What is the input? What is the output?
Here is the kind of board we will play with.

How is the data structured?
Here is a labyrinth with a few more details.

In this grid, each box represents a node. A connection between two nodes is represented by a path between two boxes. This information is also displayed textually (top left box in the image). Here, our mouse is on the first node (0,0) and displays connections with the nodes (0,1) and (1,0).

We choose to describe our grid (or graph) using an adjacency lists data structure. The idea is pretty simple : an array of nodes with node storing the list of their neighbors. Easy to create, easy to manipulate, here is how the data could be represented in JSON :

The node id is given by its array index, this id is used to refer to the neighbors.
Yes, it’s that simple! It includes all the information we need to go through and to visualize the maze.

What is the output?

The most basic output that could be expected is the path found between two nodes. To represent this, an ordered (by step order) array is quite sufficient:

Starting from the node 0, we go to node 3, then to node 19 etc. until the goal.

Perfect, we know everything to build our pathfinders!

Note: A grid can use a non-grid pathfinding graph, or vice versa.
Here, grids are used for explanations as it is easier to understand, work and visualize.

Overview

Breadth First Search

Breadth First Search explores equally in all directions.

This is an incredibly useful algorithm, not only for regular traversal, but also for procedural map generation, flow field pathfinding, distance maps, and other types of map analysis.

This may be the algorithm of choice to identify nearby places of interest in GPS.

BFS guarantees the shortest path.

Depth First Search

Traverses by exploring as far as possible down each path before backtracking.

As useful as the BFS: DFS can be used to generate a topological ordering, to generate mazes, to traverse trees, to build decision trees, to discover a solution path with hierarchical choices…

DFS does not guarantee the shortest path.

Dijkstra

Dijkstra’s Algorithm lets us prioritize which paths to explore. Instead of exploring all possible paths equally, it favors lower cost paths.

We can assign lower cost to encourage moving on roads while assigning high cost on highway to avoid them.

It is the algorithm of choice for finding the shortest path paths with multiple destinations.

A* (A-Star)

A* is a modification of Dijkstra’s Algorithm that is optimized for a single destination.

Dijkstra’s Algorithm can find paths to all locations; A* finds paths to one location. It prioritizes paths that seem to be leading closer to a goal.

In a game, we could set costs to be attracted or discouraged in going near some objects : how useful it is for an AI.

It is more or less the golden ticket or industry standard algorithm for all applications finding directions between two locations.

Breadth First Search (BFS)

Breadth First Search (BFS) is one of the two most fundamental graph traversal algorithms. First published in 1959 by Edward F. Moore to find the shortest path out of a maze, it is now used in a daily basis not only for regular traversal, but also for networks analysis, GPS, Search Engines, scheduling and other types of graph analysis.

In short : this is an incredibly useful algorithm that guarantees the shortest path between two nodes (when connections have the same cost).

Breadth First Search explores equally in all directions until the goal is reached. In other words, it starts from a chosen node and examine all its neighbors, then it examines all the neighbors of the neighbors, and so on… If we consider a tree (which is a simplified graph), the BFS will proceed as follows:

How To Build

Steps

• Add the start node in the queue and mark as visited.
• While there is a node waiting in the queue:
• 1. Take the node at the front of the line (queue).
• 2. Add to the queue all available neighbors, note the parent and mark as visited
• Done: backtrack from goal to start using parent link in order to get the shortest path.

BFS uses the opposite strategy as depth-first search (DFS), which instead explores the node branch as far as possible before being forced to backtrack. Still, both algorithms have the same lines of code; the only difference is the data structure used:

BFS use a Queue (FIFO)

This algorithm is, compared to the DFS, a little more tricky to implement in a recursive manner. As such we will only see the iterative approach ;)

Code

BFS(Maze maze, Node start, Node end)
{
  // Put the start node in the queue
  start.visite = true;
  Queue queue(start);

  // While there is node to be handled in the queue
  while (!queue.empty())
  {
    // Handle the node in the front of the line 
    Node curNode = queue.pop();

    // Terminate if the goal is reached
    if (curNode == end)
      break;

    // Handle neighbors
    auto neighbors = curNode.GetUnvisitedNeighbors();
    for (auto i = 0; i < neighbors.size(); ++i)
    {
      neighbors[i].visite = true;
      neighbors[i].parent = curNode;
      queue.push(neighbors[i]);
    }
  }

  // Done ! At this point we just have to walk back from the end using the parent
  // If end does not have a parent, it means that it has not been found.
}

Visualization

Depth First Search (DFS)

Depth First Search (DFS) is the other fundamental graph traversal algorithm; Breadth First Search (BFS) is the other one. As useful as the BFS, the DFS can be used to generate a topological ordering, to generate mazes (cf. DFS maze generators), to traverse trees in specific order, to build decision trees, to discover a solution path with hierarchical choices, to detect a cycle in a graph…

However, please first note that the DFS does not guarantee the shortest path.
Then, this is not a very good algorithm if the unique purpose is to do a simple pathfinding.

Depth First Search Traverses by exploring as far as possible down each path before going back. It is the reason why you may also find this algorithm under the name of Backtracking. Furthermore, This property allows the algorithm to be implemented succinctly in both iterative and recursive forms. If we consider a tree (which is a simplified graph), the DFS will proceed as follows:

How To Build

Steps

• Add the start node in the stack and mark as visited.
• While there is a node waiting in the stack:
• 1. Take the node at the top of the stack.
• 2. Add on the stack all available neighbors in order, note the parent and mark as visited
  (we chose for the visualization North, East, South, West as order)
• Done: backtrack from goal to start using parent link in order to get the path.

DFS uses the opposite strategy as breadth-first search (BFS), which instead explores the node circle by circle. Still, both algorithms have the same lines of code; the only difference is the data structure used:

DFS use a Stack (LIFO)

Code

DFS(Maze maze, Node start, Node end)
{
  // Put the start node in the stack
  start.visite = true;
  Stack stack(start);

  // While there is node to be handled in the queue
  while (!stack.empty())
  {
    // Handle the node in the front of the line
    Node curNode = queue.pop();

    // Terminate if the goal is reached
    if (curNode == end)
      break;

    // Take unvisited neighbors in order 
    // set its parent, mark as visited, and add to the queue
    auto neighbors = curNode.GetUnvisitedNeighbors();
    for (auto i = 0; i < neighbors.size(); ++i)
    {
      neighbors[i].visite = true;
      neighbors[i].parent = curNode;
      stack.push(neighbors[i]);
    }
  }

  // Done ! At this point we just have to walk back from the end using the parent
  // If end does not have a parent, it means that it has not been found.
}

Recursive version

The recursion of the DFS algorithm stems from the fact that we don’t actually finish checking a “parent” node until we reach a dead end, and inevitably pop off one of the “parent” node’s children from the top of the call stack. More than words, the code talks for itself ^^

bool Recursive_DFS(Maze maze, Node start, Node end)
{
  // Terminate if the goal is reached
  if (start == end)
    return true;

  // Visite current node
  start.visite = true;

  // Take unvisited neighbors in order
  auto neighbors = start.GetUnvisitedNeighbors();
  for (auto i = 0; i < neighbors.size(); ++i)
  {
    neighbors[i].parent = start;

    // Recurse and Terminate if the goal is reached
    if (Recursive_DFS(maze, neighbors[i], end)) return true;
  }

  return false;
}

Visualization

Dijkstra

Pathfinding has gained prominence in the early 1950’s in the context of routing; that is, finding shortest directions between two or more nodes. In 1956, the Dutch software engineer Edsger Wybe Dijkstra created the best-known of these algorithms : Dijkstra.

Dijkstra’s algorithm finds the shortest path from a root node to every other node (until the target is reached). Dijkstra is one of the most useful graph algorithms; furthermore, it can easily be modified to solve many different problems.

Traversal algorithms such as breadth-first-search and depth-first-search explore all possibilities : they iterate over all possible paths until they reach the target. However, it may not be necessary to examine all possible paths; Dijkstra’s algorithm eliminates useless traversal using heuristics to find the optimal paths.

Some applications

• Widely used in Network routing protocols.
• In digital mapping services such as Google Maps.
• In Biology by finding the network model in spreading of infectious diseases.
• In finding the optimal agenda of flights.
• In path planning for mobile robot transportation…

Eg. used to compute a romantic riverside walk in Paris.

How To Build

This algorithm begins with a root (or start) node and a queue of candidate nodes. At each step, we compute minimal distance between the root and each unvisited neighbors. Then, we add them to the queue; the one with the lowest distance is the next one that will be taken from the queue. This process repeats until a path to the destination has been found.

Since the lowest distance nodes are examined first, the first time the destination is found, the path to it will be the shortest path.

Minimizing the distance from the root node is our heuristic here.

Here is the distance map computed for a maze from the top left corner (root). You may notice that each connection between two adjacent nodes has a distance cost of 1.

Steps

Let’s take a root node and note D the distance from a node to the root. Dijkstra’s algorithm will assign some initial distance values and improve them step by step.

• 1. Set all node distance D to infinity except for the root (current) node which distance is 0.
• 2. Mark current node as visited and update D for all of its unvisited neighbors with the shortest distance.
  Note: we can stop the algorithm here if we have reached the target node.
• 3. Add to the queue the unvisited neighbors and go back to step 2.

Yes, one of the most useful and used algorithms is as simple as that !

As we have seen : by calculating and continually updating the shortest distance, the algorithm compiles the shortest path to the destination. A key part of this approach is maintaining an ordered line of nodes to visit next; to set up that part of the algorithm, we will use a priority queue (a regular queue with the ability to set priorities).

For Dijkstra’s algorithm, it is always recommended to use priority queue (or heap) as the required operations (extract minimum and decrease key) match with specialty this data structure. Here the priority is defined by D (the distance between a node and the root). Higher priorities are given for nodes with lower distance D.

You may see it as a regular attraction queue with some people having access to shortcut heading to different checkpoints. A priority queue should have the following methods:

// Add new element at the end of the queue
void enqueue(const T& data, const int priority);

// Remove element from the beginning of the queue
void dequeue();

// Change the priority of the element in the queue.
void changePriority(const T& item, const int priority);

Now that we know all we need to know, here is the implementation (the visual explanation follows):

Code

Dijkstra(Maze maze, Node start, Node end) {
    priority_queue queue();

    // Init all distances with infinity
    for (auto&& node : maze.nodes) node.distance = Infinity;

    // Distance to the root itself is zero
    start.distance = 0;

    // Init queue with the root node
    queue.add(start, 0);

    // Iterate over the priority queue until it is empty.
    while (!queue.isEmpty()) {
      curNode = queue.dequeue();  // Fetch next closest node
      curNode.discovered = true;  // Mark as discovered

      // Iterate over unvisited neighbors
      for (auto&& neighbor : curNode.GetUnvisitedNeighbors())
      {
        // Update minimal distance to neighbor
        // Note: distance between to adjacent node is constant
        const minDistance = 
          Math.min(neighbor.distance, curNode.distance + 1);
        if (minDistance !== neighbor.distance) {
          neighbor.distance = minDistance;  
          neighbor.parent = curNode;        

          // Change queue priority of the neighbor 
          if (queue.has(neighbor))
           queue.setPriority(neighbor, minDistance);
        }

        // Add neighbor to the queue for further visiting.
        if (!queue.has(neighbor)) 
          queue.add(neighbor, neighbor.distance);
      }
    }

  // Done ! At this point we just have to walk back from the end using the parent
  // If end does not have a parent, it means that it has not been found.
}

NOTE
Dijkstra’s algorithm does not support negative distances. The algorithm assumes that adding a relationship to a path can never make a path shorter, an invariant that would be violated with negative distances.

Visualization

A* (A-Star)

The A* (A-Star) algorithm improves on Dijkstra’s by finding the shortest path more quickly. It was invented by Peter Hart, Nils Nilsson, and Bertram Raphael (three American computer scientists) and described in their paper “A Formal Basis for the Heuristic Determination of Minimum Cost Paths” in 1968.

A* pathfinding algorithm is arguably the best pathfinding algorithm when we have to find the shortest path between two nodes. A* is the golden ticket, or industry standard, that everyone uses.

Dijkstra’s Algorithm works well to find the shortest path, but it wastes time exploring in directions that aren’t promising. A* improves this by allowing the inclusion of extra information that the algorithm can use as part of the heuristic function:
 — Dijkstra’s Algorithm use the distance from the root node.
 — The A* algorithm uses both the actual distance from the root and the estimated distance to the goal.

That’s it !
In fact A* algorithm is just a variant of Dijkstra’s algorithm.

Applications

As a variant of Dijkstra’s algorithm, A* is used everywhere : it is widely used in video games, in machine learning, navigation systems, autonomous vehicles, natural language processing (NLP) etc.

How To Build

A* selects the path that minimizes the following function : f(n)=g(n)+h(n), where:
 — g(n) is the cost of the path from the starting point to node n (Dijkstra distance).
 — h(n) is the estimated cost of the path from node n to the destination node, as computed by the Manhattan distance in our case.

Ok… but what’s the Manhattan distance ?

The Manhattan distance (or Taxicab distance) origin is based on the well-known grid like street geography of the New York borough of Manhattan. It is the distance between two points in a grid based environment (with only horizontal and vertical moves). The Manhattan distance is the simple sum of the horizontal and vertical moves, whereas the diagonal or “as the crow flies” distance might be computed by applying the Pythagorean theorem.

This distance is ideal for our mazes that allow 4-way movement (up, down, left, right).h(n)=|goal.x−root.x|+|goal.y−root.y|

Here are the distance maps computed (Manhattan, Dijkstra and A*) :

Manhattan distance map (from right bottom destination) : h(n)
We may reinforce the Manhattan heuristic by using a factor. For instance : h(n)

Steps

As simple as Dijkstra, the only change is the cost function (we add the Manhattan distance) !

Code

AStar(Maze maze, Node start, Node end) {
    priority_queue queue();

    // Init all distances with infinity
    for (auto&& node : maze.nodes) {
      node.distance = Infinity;
      node.rootDistance = Infinity;

      // Note: we may reinforce the manhattan heuristic
      node.manhattanD = 2 * 
        (Math.abs(end.x - node.x) + Math.abs(end.y - node.y));
    }

    // Distance to the root itself is zero
    start.rootDistance = 0;

    // Init queue with the root node
    queue.add(start, 0);

    // Iterate over the priority queue until it is empty.
    while (!queue.isEmpty()) {
      curNode = queue.dequeue();  // Fetch next closest node
      curNode.discovered = true;  // Mark as discovered

      // Iterate over unvisited neighbors
      for (auto&& neighbor : curNode.GetUnvisitedNeighbors())
      {
        // Update root minimal distance 
        neighbor.rDistance =
          Math.min(neighbor.rootDistance, curNode.rootDistance + 1);
        const minDistance =
          Math.min(neighbor.distance, 
            neighbor.rootDistance + neighbor.manhattanD);
        
        if (minDistance !== neighbor.distance) {
          neighbor.distance = minDistance;  
          neighbor.parent = curNode;        

          // Change queue priority of the neighbor 
          if (queue.has(neighbor)) 
            queue.setPriority(neighbor, minDistance);
        }

        // Add neighbor to the queue for further visiting.
        if (!queue.has(neighbor)) 
          queue.add(neighbor, neighbor.distance);
      }
    }

  // Done ! At this point we just have to walk back from the end using the parent
  // If end does not have a parent, it means that it has not been found.
}

Visualization

To better understand the differences between these algorithms and their operations, you may use H.urna Explorer : our interactive platform, which will allow you to manipulate and compare them.

Pathfinding algorithms : the four Pillars. was originally published in Level Up Coding on Medium, where people are continuing the conversation by highlighting and responding to this story.