A Swift Introduction to Algorithms – Part 2

 

cutting-a-log

 

In part 1 we took a general look at algorithms, what they are and how you can compare and measure them. In this article we are going to start exploring the wonderful world of algorithms based on what problems they solve.

What kind of algorithms are there?

Algorithms come in different flavours and are the result of extensive years of research solving problems encountered in computer science. The fundamental algorithms sum up all the wisdom built upon the experience coming from one century of solving problems using machines. Therefore, the most basic algorithms make up a kind of mini-toolbox (magnifying glass, saw, hammer) which you can carry around to solve almost any problem. Let us have a look at 4 broad categories of algorithms.

Searching Algorithms

These are the algorithms for finding a certain solution in a given solution space. Given the problem description, you abstract away the redundant details and define a solution space, which you then explore to find the best solution. The resulting algorithm will simply iterate through all/some states of the problem and pick the best one it finds.

MagnifyingGlass

Recursive & Inductive Algorithms

A big problem is split into several smaller subproblems, whose solutions – if we were to know them – could be combined into solving the big problem. Your task is to observe the pattern of the generalized problem: how it is composed of smaller subproblems similar to the initial problem. Example: How can I maximize my happiness over iunits of time with j units of money or some other resource? Of course, the answer to this might have something to do with maximizing the level of happiness obtained by spending a smaller chunk of time and less resources. The idea is to keep asking such questions until you reach a very basic case with an obvious solution. And then propagate the solution upwards…

Algorithms for Data Structures

Your task is to implement the behaviour of certain data structures by describing how it should be manipulated. The behaviour for this type of algorithms should especially take into account the number of steps performed for all the available operations, the memory used and the how often the data structure is accessed in the program using it.

BuildingSite

Genetic Algorithms

Genetic algorithms are a more exotic category of algorithms and they are widely observable in nature. Their mechanism works by evolving solution states through repeated combinations and mutations of an initial starting pool of states. Each state must have an associated value telling how good the solution is. This value is called the fitness function and the states that we go through are called populations. Therefore, they are in a way a more abstract analogy to how life evolves over generations of individuals.

Genetic

Learning Algorithms

Imagine an algorithm which doesn’t simply follow the instructions that you give it. Instead, it learns from experience. But what is experience anyway? In the world of machines, experience translates as more data to learn from. We have an almost similar measure in everyday life if you come to think of it.

A person who is 50 years old (Jock) is considered to be more experienced than someone who is 25 years old (Jack). Jock has spent considerably more time at work with colleagues compared to Jack. Therefore, he is more efficient at his daily job and has higher social skills. However, Jack can learn at a faster pace than Jock because things for him are newer than they are for Jock and thus his daily intake of new data to learn from is higher than it is for Jock.

So what learning algorithms do – to say it in a very few words – is to adapt their behaviour according to their experience. The learning process happens in stages and it usually takes longer periods of time.

DecisionMaking

According to their type, learning algorithms known so far are broadly categorized into 3:

Supervised Learning

All supervised learning algorithms require 2 components: code and data. The role of the code is to describe a model with various parameters and the technique that changes them when data is fed into the model. This adaptation technique is referred to as training. The data is supposed to come as a labeled dataset: samples of input and their expected output. The samples are observed truths, usually labeled by humans.

Suppose you wanted to label the images taken by a camera attached to a car. For each image you want to know whether it contains a pedestrian or not. Instead of writing exact rules for this, which most likely will prove hard to implement and unreliable, we can collect a lot of data labeled by humans and adjust a model to replicate this behaviour.

The first phase of running a supervised learning algorithm is to split the labeled dataset into training data and validation data. The training data is used to adjust the parameters, while the validation data is used in order to obtain a measure of how well the algorithm performs on new data.

The second phase adjusts the parameters of the model. Supervision enforces the change of parameters in order to minimize the error. This happens by feeding part of the training data in the model. We then compute the error between the expected output and the output produced by the model. The error offers us some insight into how we should change the parameters so that be get better results. We change them and repeat the process.

The third phase validates the model. We do this by simply feeding the validation dataset to the model with the last version of parameters.

Further optional stages involve a more detailed analysis of the algorithm’s performance at producing the right output for new data. Investigating the causes of the error in the model is critical. More adjustments can be made to the model. And more data can be collected.

Unsupervised Learning

Unsupervised learning can be used when the expected output is not known. We are only given inputs for the algorithm. Supervised and unsupervised learning have slightly different purposes, but they both end up labelling the data. In unsupervised learning we cluster the data. That means we put it into categories or we identify patterns in it, without actually knowing about them.

An example that I like a lot is the one with choosing optimal T-Shirt dimensions for a pool of people. T-Shirts come in different sizes: S, M, L, XL, XXL. An unsupervised learning algorithm can find the optimal dimensions for the 5 T-shirt sizes. The sizes are considered optimal if everyone will be able to have a size that fits him/her and if the T-Shirts are spread evenly among the pool of people.

Reinforcement Learning

Have you ever played a game against an AI? How do you think it learnt to play the way it does? It might have used a reinforcement learning technique, which involves a series of action and feedback exchange between an agent(the AI) and an environment(the game).

The agent that you’re playing against could have improved its tactics prior to your game by playing many games and learning to optimize its behaviour with the purpose of maximizing its score. The increase/decrease in the score represents the feedback used by the AI to learn.

Exercises

Practice basic algorithms and data structures by solving these interactive exercises:

  1. Nobody’s Decision
  2. Rock and Roll
  3. Cooking Recipes
  4. Compute 2 to the Power of N
  5. Greatest Common Divisor
  6. Sum of Powers
  7. The Natural Base
  8. The Golden Ratio
  9. Partial sums
  10. Hash Tables

1 Star2 Stars3 Stars4 Stars5 Stars (4 votes, average: 5.00 out of 5)
Loading...

  2 comments for “A Swift Introduction to Algorithms – Part 2

  1. November 11, 2016 at 5:55 pm

    Really great that you have put practical tasks at the end of tutorial!

    • November 11, 2016 at 6:02 pm

      Thank you! It’s part of our process – all tutorials/articles must give the reader something extra to practice :)

Leave a Reply

Your email address will not be published. Required fields are marked *

Subscribe
We send about one email per week with our latest tutorials and updates
Never display this again :)