Lesson 16 - What are algorithms for?

In the last lesson, The most common C# beginner mistakes - Naming variables , we showed the most common beginner mistakes in C# .NET regarding variable naming.

Once you've learned what are variables, how for loops work, and when to use switch, the question is, what's next? Probably objects, or designing websites using HTML and CSS, Bootstrap or Android development. However, even if you focus on pure C#, the basic syntax is still just a kind of foundation that makes up good programs. Today we'll talk about why we should be interested in algorithms and why they can't be avoided (for both your health and your future boss' health).

What are algorithms?

In the simplest definition, an algorithm is a procedure for solving a specific problem. There are other articles on the web about what an algorithm must meet, what it should be like etc., we'll be satisfied with problem solving. Programming, more than almost any other profession, is about problem solving. Even if you have an idea of new games or business applications for the market in your head, you'll soon come across several problems that you have to deal with and choose a specific solution for. First, let's take a look at two main program issues.

Memory

Although the term "lack of memory" may seem to be a phrase from scholarly books from the end of the last century, we're all struggling with it. Especially if you make Android applications. If your application takes up 1GB, no one will download it. In addition, there's an interesting law here, when the memory available increases, the size of programs increases as well and we have to deal with the lack of memory again.

Time

If the memory problem is disturbing, the time is absolutely terrifying. Application users have a terrible habit, impatience. For example, when they press a button, they expect something to happen right away... Let's be real, we are such users too. We don't want to wait for our great program to give us the result. It doesn't even have to be complicated calculations. If we are programming a game, we expect the player to move as soon as the key is pressed. We expect that after opening a window, we'll see a list of users sorted by name.

Specific examples for algorithmization

We'll show that all other problems directly or indirectly affect these two stumbling blocks.

Interacting with the world

Let's take Kingdom Come Deliverance as an example, it's a game that boasts the world where you can interact with each character and with many objects. It has several problems, the first is the memory requirement. If we really created every character and every house, the world the size of a city with 300 people would take up a huge amount of memory, which in the end the antisocial player wouldn't use at all...

Life story

Let's say we have an E-shop selling one kind of clothing, specifically leather jackets. Our e-shop has various animations for the sale of jackets. But then we'll find out that our program should work in other language too. Well, we can use a simple if-else for languages and rewrite the web in Spanish. But then people from Germany will say that it'd be good to add German as well. Well, we add the German version in there too. Then the boss wants us to add a bazaar of leather jackets, which is a great idea, but we'll have to code it. The E-shop wasn't probably ready for that, so now we are making a new web with a link to the original one, which is again trilingual, this time we'll choose an effective design, if the company expands to France. The bazaar will be in the form of auctions, we enter the time and then wait to see if people can bid. But it turned out that colleagues from Russia could bid even after your time was up and colleagues from England lost an hour. So we must adjust it a bit.

We have grown and we have so many jackets that it's difficult for customers to find their way around, so our boss will decide to divide the jackets into categories, and customers will be able to search by price and name. All right, make a coffee and here we go. We've found a tutorial on how to program a search by price and by name, and we've got it there. As soon as you finish it, the boss will come up with the idea that it'd be nice if the customer could add criteria and that he could search, for example, only for his three favorite brands and in some price range. We'll book a holiday for next week and start writing. We'll find a solution for multiple tags when searching and multi-phase sorting. We have it all in a week and we're already looking forward to relaxing when the customer line calls us that our program isn't working. The code we downloaded from the Internet doesn't work for big data. Our multi-language e-shop suffers from the fact that there's sometimes another language popping in and we have the opportunity to take our job on vacation and solve everything that "someone else" messed up for us.

What to do with this?

Here we touched on two topics. The first topic we already introduced a bit, is the question of good coding practices. What we should follow to make software development go smoothly. The second, however, is the ability to think algorithmically. How to specifically solve a problem, such as sorting. If we sort first, then filter the result or vice versa. We're talking about time now, if we filter first, then for example, out of tens of thousands of items, we sort just 134. So we got the speed now. In addition, if we just take someone else's code, we have to trust them to know what they're doing. We can try the code, but what if its algorithm only works for small data?

There are a lot of problems that no one has solved and we should know how to proceed in solving problems. Our section for teaching algorithms is there for this purpose.

Example at the end - sorting using selection sort

Now let's say we want to sort the numbers in an array. Let's try to use the most basic and probably the least suitable, sorting by selection.

Algorithm idea (inefficient selection sort)

We can say that in an unsorted array we always select the smallest element not yet selected and insert it into a new array. Then we'll look for greater:

0. (3,1,5,4)
1. (1)
2. (1,3)
3. (1,3,4)
4. (1,3,4,5)

Why is this code ineffective? Because we have to create an extra array, i.e. for a million-item array, we create a second array of the same size.

Algorithm idea (effective selection sort)

We'll sort arrays in place, as is the original version of this algorithm.

Let's say we have an array of size n. We'll go from the first element of the array and find the smallest element. Then we'll swap it with the first element. We know that there isn't any smaller element in the array, so we have already one sorted element. We'll move and look for the smallest element in the rest of the array. And then we'll swap it with the second element, etc... The example of the algorithm:

0. (3,1,5,4)            original array
1. (1,3,5,4)            the smallest is 1, so we swap 1 with 3
2. (1,3,5,4)            the smallest is 3, 3 is in the appropriate place, we don't change anything
3. (1,3,4,5)        the smallest is 4, we swap 4 and 5, we have the last element left, which must be the largest, so the algorithm ends, we have it sorted

We'll now take a look at its implementation:

public static void selectionSort(int[] array) {
for (int i = 0; i < array.length - 1; i++) {
    int minimumIndex = i;
    for (int j = i + 1; j < array.length; j++) {
    if (array[j] < array[minimumIndex]) minimumIndex = j;
    }
    int temp = array[i];
    array[i] = array[minimumIndex];
    array[minimumIndex] = temp;
    }
}

Now I have no choice but to wish you good luck in the world of algorithms. Or what does a programmer do? He solves problems that a normal person wouldn't think of. But that's what it's about, isn't it?

In the following exercise, Solved tasks for C# .NET lesson 11-12, we're gonna practice our knowledge from previous lessons.