A Swift Introduction to Algorithms – Part 1

Welcome to your journey throughout the vast world of algorithms!

Whether you are still wondering what an algorithm is or hoping to deepen your knowledge about them, in this article will help you dive swiftly into the subject, carve out some valuable thinking patterns through various exercises and hammer a few hard problems using the power of algorithms.

What is an algorithm?

An algorithm is simply a series of actions performed with the purpose of completing a task.

Try thinking about the next few questions. This should help you understand what is essential to an algorithm.

• Can you think of any algorithm taken from everyday life?
• How many steps does it take to complete it?

• How would you describe it to someone who wants to perform the same algorithm for a task?
• Does it involve decision-making?

• Is there any part a computer couldn’t do in executing the algorithm given the right tools and enough time?

A computer can run in principle any algorithm you give it as long as the decisions to make and the steps to take are clear.

• What about the decisions and steps involved in your favorite activity?

Assuming you were a passionate cook with a secret recipe to bake pancakes, this secret recipe of yours would qualify as an algorithm for baking delicious pancakes.

This algorithm describes the process you have to apply in order to take the ingredients in their raw form: eggs, milk, flour, etc. and transform them into warm ready-to-serve pancakes.

This process should be well described, in the manner of sequential steps and should guarantee that if you follow it correctly, it produces some tasty pancakes.

Without us noticing it, both ourselves and our computers are running millions of algorithms for various tasks every day. They are similar to cooking recipes, but smaller or larger in their complexity.

Algorithms are problem solvers

All of us encounter problems throughout everyday life. One could argue that we spend most of our time solving problems. A problem can be any task requiring someone to take several steps in order to finish it. The solution describing the series of actions needed to solve a problem is also an algorithm.

Many problems reoccur throughout certain time spans, so being able to reuse old solutions designed for past problems, but applicable to new situations is vital for saving time. We don’t want to make a hammer that can be used only one time and then breaks. It would be more useful to make a hammer that can nail several times or otherwise the cost of making a hammer wouldn’t be justified.

Our power to adapt fast is partly due to understanding well the problems that occur to us more often. The mind designs algorithms that solve generalized versions of our problems. These algorithms work in different situations, without us necessarily remembering the exact solution for each individual case. We build up reflexes or remember sequences of steps taken, which we later adapt to new inputs.

Take the action of making coffee for instance. If you were a coffee drinker, you would probably make yourself one cup of coffee every morning right after you wake up. Your coffee-making algorithm would require heating water and dissolving coffee in heated water. Your input would be water and coffee. But what if you were to make coffee for your friends too? Then your algorithm should take into account the variability in the amount of water and coffee and be able to produce a larger number of cups of coffee.

Thus, an algorithm should be able to perform on a range of different inputs considered by its designer. The language of algorithms uses inputs and outputs, which are simply numbers that have a meaning in real life.

Another way to see algorithms is as a recipe for transforming input in to output. This transformation of the input to output is our goal or problem.

What kind of problems do algorithms solve?

Algorithms solve problems involving automation of clearly defined tasks. One such example is looking up a word in a large dictionary. Or periodically checking that some signal is on/off, such as a plane on a radar map.

Algorithms prove very useful at scanning, organizing and storing data. Even more, their mathematical precision allows them to handle complex systems and their problems better than us. For instance, face detection algorithms methodically scan an image and send a signal when a certain feature is detected in the image.

Another power of algorithms is that you don’t have to reinvent the wheel each time. Once the complex system is described in algorithms, it can be used millions of times and it will produce an accurate result each time.

Without us noticing it, step by step instructions, working quietly behind the scenes, dictate how complex technological systems take over modern life: online shopping, booking flights, dating people online, software in hospitals, etc.

How to analyze and test algorithms?

Analysing algorithms usually involves several stages and a few checks from behalf of its designer. The first thing to do right before even thinking of an algorithm is to take examples of different inputs and work out the solution to them by hand. You will most probably notice that your brain intuitively develops a way to solve the problem, even if the steps are not yet fully translatable to a machine. Therefore, test your solution on various examples until the solution becomes very clear.

The next step would be to implement the solution that you came up with, using some programming language – Swift in this case. However, prior to running your solution it would be advisable to check the algorithm’s time and memory complexity.

Smart algorithms take less time and memory to perform a task than it would take by simply applying the obvious solution to the problem. Let us take a short look at what the time and memory analysis of an algorithm involve.

Time analysis means estimating the time complexity of an algorithm, which is a measure of how much slower the algorithm will become if we increase the size of the input. For instance, an algorithm which we call liniar, will have time complexity O(n), which means that the number of steps to compute the desired result is more or less equal to the size of the input.

Imagine a Halloween scene with children coming to trick-or-treat. You have to give candies to a group of n children. The algorithm that does this by giving candies to one child at a time, is linear. If 3 kids are at your door you will spend 3 times how much it takes you to take one candy and give it to a kid.

What about the situation when a group of n people leave a party and they want to hug each other? Assuming only one hug can take place at a time, the algorithm would have to process n<sup>2</sup> hugs, thus a time complexity of O(n<sup>2</sup>). If there are 3 people at the party, there will be a total of 3 hugs. If there are 4 people, there will be 6 hugs, for 10 there will be 45, and for 100 there will be 4950.

Let us assume you had a machine that could run 1 million operations per second.

• How long would it take to run the trick-or-treat simulation for n = 1.000.000?
• What if n = 1.000.000.000?
• How long would it take to run the hugging simulation for n = 1.000?
• What if n = 1.000.000?

The memory complexity of an algorithm is a measure of how much additional space for computation would be required if we were to increase the size of the input. Thus, the number of variables used while running an algorithm gives you the memory complexity.

When the number of steps does not depend on the input size the complexity of that algorithm is called constant or O(1). For example the complexity of getting the first element from an array does not depend on the number of elements the array contains.

What is the memory complexity for the trick-or-treat simulation?

What is the memory complexity for the hugging simulation?

let n = 3
for i in 1..<n {
    for j in i+1...n {
        print("\(i) hugs \(j)")
    }
}
// 1 2 
// 1 3
// 2 3

let names = ["Ana", "Bob", "Cady", "Dan"]

for i in 0..<names.count-1 {
    for j in i+1..<names.count {
        print("\(names[i]) hugs \(names[j])")
    }
}
// Ana hugs Bob
// Ana hugs Cady
// Ana hugs Dan
// Bob hugs Cady
// Bob hugs Dan
// Cady hugs Dan

let names = ["Ana", "Bob", "Cady", "Dan"]
var hugged: [(String, String):Bool] = [:]

for firstName in names {
    for secondName in names {
        if let didHug = hugged[(firstName, secondName)] {
        continue
    }

        print("\(firstName) hugs \(secondName)")
        hugged[(firstName, secondName)] = true
    }
}
// Ana hugs Bob
// Ana hugs Cady
// Ana hugs Dan
// Bob hugs Cady
// Bob hugs Dan
// Cady hugs Dan

Is it possible to design an algorithm with time complexity less than its memory complexity?

Conclusion

Algorithms are solutions to problems. The solution is usually a list of steps to take in order to solve a specific problem. The number of steps and memory used by an algorithm usually depends on the size of the input. This property is called the complexity of an algorithm.

In part 2 we are going to take a quick look at a the types of problems algorithms can solve.

If you enjoyed reading this article please take a second and share it with your friends!