While reading the first chapter of this book, you learned about various data types. Now, it is high time to introduce the topic of algorithms. In this chapter, you will take a look at their definition, as well as some real-world examples, notations, and types. As you should take care of the performance of your applications, the subject of computational complexity of the algorithms, including time complexity, will also be presented and explained.

First, it is worth mentioning that the topic of algorithms is very broad and complex. You can easily find a lot of scientific publications about them on the internet, published by researchers from all over the world. The number of algorithms is enormous and it is almost impossible to even remember the names of all the commonly used ones. Of course, some algorithms are simple to understand and implement, while others are extremely complex and almost impossible to understand without deep knowledge of algorithmics, mathematics, and other dedicated field of science. There are also various classifications of algorithms by different key features, and there are a lot of types, including recursive, greedy, divide-and-conquer, back-tracking, and heuristic. However, for various algorithms, you can specify the computational complexity by stating how much time or space they require to operate with the increasing size of a processed input.

Does this sound overwhelming, complicated, and difficult? Don’t worry. In this chapter, I will try to introduce the topic of algorithms in a way that everyone can understand, not only mathematicians or other scientists. For this reason, in this chapter, you will find some simplifications to make this topic simpler and easier to follow. However, the aim is to introduce you to this topic and make you interested in algorithms, not create another research publication or book with a lot of formal definitions and formulas. Are you ready? Let’s get started!

In this chapter, we will cover the following topics:

• What are algorithms?
• Notations for algorithm representation
• Types of algorithms
• Computational complexity

Did you know you typically use algorithms every day and that you are already an author of some algorithms, even without writing any lines of code or drawing a diagram? If this sounds impossible, give me a few minutes and read this section to get to know how is it possible.

Definition

First, you need to know what an algorithm is. It is a well-defined solution for solving a particular problem or performing a computation. It is an ordered list of precise instructions that are performed in a given order and take a well-defined input into account (if any) to produce a well-defined output, as shown here:

Figure 2.1 – Illustration of an algorithm

To be more precise, an algorithm should contain a finite sequence of unambiguous instructions, which provides you with an effective and efficient way of solving the problem. Of course, an algorithm can contain conditional expressions, loops, or recursion.

Where can you find more information?

If you are interested in the topic of algorithms, you can find a lot of detailed information about them in many books, including Introduction to Algorithms, by Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Of course, there are also many resources available online, such as GeeksForGeeks (https://www.geeksforgeeks.org), The Algorithms (https://the-algorithms.com), and Algorithms, 4th Edition, by Robert Sedgewick and Kevin Wayne (https://algs4.cs.princeton.edu). A huge number of resources is also available if you browse the Algorithms topic on GitHub (https://github.com/topics/algorithms). I strongly encourage you to search for various resources, either in books or over the internet, and continue learning about algorithms when you’ve finished reading this book.

Real-world examples

With the definition of algorithms under your belt, you might be thinking, “Come on – inputs, outputs, instructions… where I can find them?” The answer turns out to be much simpler than you might expect because you can find such items almost everywhere, all the time!

Let’s start with a simple morning routine. First, you wake up and take a look at your phone. If there are any notifications, you go through them and reply to urgent messages. For any unurgent items, you postpone them. Then, you go to the bathroom. If it is occupied, you wait until it is free, telling the person inside to hurry up. As soon as you are in the bathroom, you take a shower and brush your teeth. Finally, you choose suitable clothes according to the current weather and temperature. Surprise! Your morning routine is an algorithm. You can describe it as a set of instructions, which has some inputs, such as notifications and the current temperature, as well as outputs, such as chosen clothes. What’s more, some of the instructions are conditional, such as only replying to urgent messages. Others can be executed in a loop, such as waiting until the bathroom is vacant.

The preceding morning routine also contains other algorithms, such as those for unlocking a smartphone using face recognition. It is an algorithm-based mechanism that you can use to ensure that only you can unlock your phone. What’s more, even organizing notifications on your phone is the result of an algorithm that takes into account notifications as input, arranges them into groups, and sorts them suitably before presenting them to you.

At this point, you are dressed up and ready for a healthy and yummy breakfast. Imagine that you want to prepare scrambled eggs using your grandma’s secret recipe. You need some ingredients, namely three eggs, salt, and pepper. As a result, you will have created an amazing dish for your perfect breakfast. First, you crack the eggs into a bowl and whisk them with a pinch of salt and pepper. Then, you melt butter in a non-stick skillet over medium-low heat. Next, you pour the egg mixture into the skillet and keep the eggs moving until there is no liquid egg. With that, your breakfast is ready. However, what is it if not a well-written and organized algorithm with a precise input and yummy output?

After breakfast, you need to go to work. So, you jump into your car and launch a navigation app on your smartphone to see the fastest route to work while taking the current traffic into account. This task is performed by complicated algorithms that can even involve artificial intelligence (AI), together with a computer-understandable representation of routes that use specialized data structures, as well as data obtained from other users. When combined, this forms traffic data. As you can see, the algorithm takes the complex input and performs various calculations to present you with an ordered list of route directions – for example, go to route A4, turn right to route S19, and follow this route until you reach your destination.

While at work, you need to prepare documents for your accountant, so you need to gather documents from colleagues, print some of them from emails, and then sort all invoices by numbers. How do you perform sorting? You take the first document from the stack and put it on the table. Then, you take the second document from the unsorted stack and put it either above, if the number is smaller than the first invoice, or below the previous one. Then, you take the third invoice and find a suitable place for it in the ordered stack. You perform this operation until there are no documents in the unsorted stack. Wow, another algorithm? Exactly! This is one of sorting algorithms. You'll learn about them in the next chapter.

It’s time for a break at work! You launch your favorite social app and receive suggestions for new friends. However, how are they found and proposed to you? Yes, you’re right – this is another algorithm that takes data from your profile and your activities, as well as the data of available users, as input, and returns a collection of best-suited suggestions for you. It can use many complex and advanced techniques, such as machine learning (ML) algorithms, which can learn and take your previous reactions into account. Just think for a second about the data structures that can be used in such cases. How you can organize your relationships with friends and how can you find out how many other people are between you and your favorite actor from Hollywood? It would be great to know that your friend knows Mary, who knows Adam, who is a friend of your idol, wouldn’t it? Such a task can be accomplished using some graph-based structures, as you will see later in this book.

Will you learn about AI algorithms in this book?

Unfortunately, no. Due to the limited number of pages, various algorithms related to AI are not included in this book. However, note that it is a very interesting topic that involves many concepts, such as ML and deep learning (DL), which are used in many applications, including recommendation systems, speech-to-text, searching over extremely high amounts of data (the concept of big data), generating textual and graphical content, as well as controlling self-driving cars. To achieve these goals, a lot of interesting algorithms are used. I strongly encourage you to take a look at this topic on your own or choose one of Packt’s books that focuses on AI-related topics.

Are these examples enough? If not, just think about choosing a movie in a cinema for the evening while considering the AI-based suggestions of movies with geolocation-based data of cinemas, or setting a clock alarm depending on your plan for the next day. As you can see, algorithms are everywhere and all of us use them, even if we do not realize it.

So, if algorithms are so common and so useful, why don’t we benefit from the huge collection of ones that are available or even write our own algorithms? There are still some problems that need to be solved using algorithms. I, as the author of this book, am keeping my fingers crossed for you to solve them!

In the previous section, algorithms were presented in English. However, this is not the only way of specifying and documenting an algorithm. In this section, you will learn about four notations for algorithm representation, namely natural language, flowchart, pseudocode, and programming language.

To make this task easier to understand, you will specify the algorithm for calculating an arithmetic mean in all of these notations. As a reminder, the mean can be calculated using the following formula:

Figure 2.2 – Formula for calculating an arithmetic mean

As you can see, two inputs are used, namely the provided numbers (a) and the total number of elements (n). If no numbers are provided, null is returned, indicating that no mean is available. Otherwise, you sum the numbers and divide them by the total number of elements to get the result.

Natural language

First, let’s specify the algorithm using a natural language. It is a very easy way of providing information about algorithms, but it can be ambiguous and unclear. So, let’s describe our algorithm in this way:

The algorithm reads the input, which represents the total number of elements from which an arithmetic mean will be calculated. If the entered number is equal to 0, the algorithm should return null. Otherwise, it should read the numbers in the amount equal to the expected total count. Finally, it should return the result as the sum of numbers divided by their count.

Quite simple and understandable, isn’t it? You can use this notation for simple algorithms, but it can be useless for complex and advanced algorithms. Of course, some descriptions in the natural language are often useful, regardless of the complexity of an algorithm. They can give you a brief understanding of what the aim of the algorithm is, how it works, and what aspects should be taken into account while you’re analyzing or implementing the algorithm.

Flowchart

Another way of presenting an algorithm is via a flowchart. A flowchart uses a set of graphical elements to prepare a diagram that specifies the algorithm’s operation. Some of the available symbols are as follows:

Figure 2.3 – The available symbols while designing a flowchart

The algorithm should contain the entry point and one or more exit points. It can also contain other blocks, including operation, input, output, or condition. The following blocks are connected with arrows that specify the order of execution. You can also draw loops.

Let’s take a look at a flowchart for calculating the arithmetic mean:

Figure 2.4 – Flowchart for calculating the arithmetic mean

The execution starts in the START block. Then, we assign 0 as a value of the sum variable, which stores the sum of all the entered numbers. Next, we read a value from the input and store it as a value of the n variable. This is the total number of elements used to calculate the arithmetic mean. Next, we check whether n is equal to 0. If so, the YES branch is chosen, null is returned to the output, and the execution stops. If n is not equal to 0, the NO branch is chosen and we assign 0 as a value of the i variable. It stores the number of elements already read from the input. Next, we read the number from the input and save it as a value of the a variable. The following operation block increases sum by the value of a, as well as increments the value of i.

The next block is a conditional one that checks whether i is not equal to n, which means that the required number of elements is not read from the input yet. If i is equal to n, the NO branch is chosen and a value of the result variable is set to a result of a division of sum by n. Then, the result variable is returned and the execution stops. An interesting construction is used when the conditional expression evaluates to true, which means that we need to read another input. Then, the loop is used and the execution comes back just before the input block for reading a. Thus, we can execute some operations multiple times, until the condition is met.

As you can see, a flowchart is a diagram that makes it possible to specify a way of algorithm operation in a more precise way than using natural language. It is an interesting option for simple algorithms, but it can be quite cumbersome in the case of advanced and complex ones, where it is impossible to present the whole operation within a diagram of a reasonably small size.

Pseudocode

The next notation we’ll look at is pseudocode. It allows you to specify algorithms in another way, which is a bit similar to the code written in a programming language. Here, we use the English language to define inputs and outputs, as well as to present a set of instructions clearly and concisely, but without the syntax of any programming language.

Here’s some example pseudocode for calculating the arithmetic mean:

INPUT:
n – total number of elements used for mean calculation.
a – the following numbers entered by a user.
OUTPUT:
result - arithmetic mean of the entered numbers.
INSTRUCTIONS:
sum <- 0
read n
if n = 0 then
   return null
endif
i <- 0
do
   read a
   sum <- sum + a
   i <- i + 1
while i <> n
result <- sum / n
return result

As you can see, the pseudocode provides us with a syntax that is easy to understand and follow, as well as quite close to a programming language. For this reason, it is a precise way of algorithm presentation and documentation that can be later used to transform it into a set of instructions in our chosen programming language.

Programming language

Now, let’s look at the last form of algorithm notation: programming language. It is very precise, can be compiled and run. Thus, we can see the result of its operation and check it using a set of test cases. Of course, we can implement an algorithm in any programming language. However, in this book, you will see only examples in the C# language.

Let’s take a look at the implementation of the mean calculation algorithm:

double sum = 0;
Console.Write("n = ");
int.TryParse(Console.ReadLine(), out int n);
if (n == 0) { Console.WriteLine("No result."); }
int i = 0;
do
{
    Console.Write("a = ");
    double.TryParse(Console.ReadLine(), out double a);
    sum += a;
    i++;
}
while (i != n);
double result = sum / n;
Console.WriteLine($"Result: {result:F2}");

The preceding code contains an if conditional statement and a do-while loop.

If we run the application, we need to enter the number of elements from which we would like to calculate the arithmetic mean. Then, we will be asked to enter the number n times. When the number of provided elements is equal to the expected value, the result is calculated and presented in the console, as follows:

n = 3
a = 1
a = 5
a = 10
Result: 5.33

That’s all! Now, you know what algorithms are, where you can find them in your daily life, as well as how to represent algorithms using natural language, flowcharts, pseudocode, and programming languages. With this knowledge, let’s proceed to learn about different types of algorithms, including recursive and heuristic algorithms.

As mentioned previously, algorithms are almost everywhere, and even intuitively, you use them each day while solving various tasks. There is an enormous amount of algorithms and a lot of their types, chosen according to different criteria. To simplify this topic, only a few types will be presented here, chosen from different classifications, to show you a variety and encourage you to learn more about them on your own. It is also quite common that the same algorithm is classified into a few groups.

Recursive algorithms

First, let’s take a look at recursive algorithms, which are strictly connected with the idea of recursion and are the opposite of iterative algorithms. What does this mean? An algorithm is recursive if it calls itself to solve smaller subproblems of the original problem. The algorithm calls itself multiple times until the base condition is met.

This technique provides you with a powerful solution for solving problems, can limit the amount of code, and can be easy to understand and maintain. However, recursion has some drawbacks related to performance or the requirement for more space in the stack’s memory, which could lead to stack overflow problems. Fortunately, you can prevent some of these issues using dynamic programming, an optimization technique that supports recursion.

Recursion can be used in several algorithms, including the following:

• Sorting an array with the merge sort and quicksort algorithms, which are implemented and presented in detail in Chapter 3, Arrays and Sorting
• Solving the Towers of Hanoi game, as depicted in Chapter 5, Stacks and Queues
• Traversing a tree, as described in Chapter 7, Variants of Trees
• Getting a number from the Fibonacci series, as shown in Chapter 9, See in Action
• Generating fractals, as shown in Chapter 9, See in Action
• Calculating a factorial (n!)
• Getting the greatest common divisor of two numbers using the Euclidean algorithm
• Traversing the filesystem with directories and subdirectories

Divide and conquer algorithms

Another group of algorithms is named divide and conquer. It is related to the algorithmic paradigm of solving a problem by breaking it down into smaller subproblems (the “divide” step), calling them recursively until they are simple enough to be solved directly (“conquer”), and combining the results of subproblems to get the final result (“combine”). This approach has many advantages, also taken from the pros of recursion, including ease of implementation, understanding, and maintenance. By dividing the problem into many subproblems, it supports parallel computing, which can lead to performance improvements. Unfortunately, this paradigm also has some disadvantages, including the necessity for a proper base case definition to terminate the execution of the algorithm. Performance issues, similar as in the case of recursive algorithms, can exist as well.

Divide and conquer is a popular approach for solving various algorithmic problems and you can see its implementations in a broad range of applications:

• Sorting an array with the merge sort and quicksort algorithms, which are implemented and presented in detail in Chapter 3, Arrays and Sorting
• Finding the closest pair of points located on the two-dimensional surface, which will be presented in Chapter 9, See in Action
• Calculating the power of a number
• Finding the minimum and maximum values in an array
• Calculating the fast Fourier transform
• Multiplying large numbers using Karatsuba’s algorithm

Back-tracking algorithms

Next, we’ll cover back-tracking algorithms. They are used for solving problems that consist of a sequence of decisions, each depending on the decisions that have already been taken, incrementally building the solution. When you realize that the decisions that have been taken do not provide the correct solution, you backtrack. Of course, you can support this approach with recursion to try various variants and therefore find a suitable solution, if one exists.

You can use this approach for many tasks, including the following:

• Solving the rat in a maze problem, as shown in Chapter 9, See in Action
• Solving Sudoku, as shown in Chapter 9, See in Action
• Solving crosswords by entering letters into empty spaces
• Solving the eight queens problem of placing eight queens on a chessboard and not allowing them to attack each other
• Solving the knight’s tour, where you place a knight on the first block on a chessboard and move it so that it visits all blocks exactly once
• Generating gray codes to create bit patterns where the following ones differ by one bit only
• Solving the m-coloring problem for graph-related topics

Greedy algorithms

Now that we’ve covered the recursive, divide-and-conquer, and back-tracking algorithms, it’s high time to present another type, namely greedy algorithms. A greedy algorithm builds the solution piece by piece by choosing the best option in each step, not concerned about the overall solution, and being short-sighted in its operation. For this reason, there is no guarantee that the final result is optimal. However, in many scenarios, using the local optimal solutions can lead to global optimal solutions or can be good enough.

Here are some examples:

• Finding the shortest path in a graph using Dijkstra’s algorithm, as shown and explained in detail in Chapter 8, Exploring Graphs
• Calculating the minimum spanning tree in a graph with Kruskal’s algorithm and Prim’s algorithm, as shown in Chapter 8, Exploring Graphs
• Solving the minimum coin change problem, as explained in Chapter 9, See in Action
• The greedy approach to Huffman coding in data compression algorithms
• Load balancing and network routing

Heuristic algorithms

Now, it’s time to add more “magic” to your algorithms via heuristics! A heuristic algorithm calculates a near-optimal solution for an optimization problem and is especially useful for scenarios when the exact methods are not available or are too slow. Thus, you can see a significant speed boost, but with a decreased accuracy of the result. Such an approach is popular and adequate for solving various real-world problems, often complex and big, and is applied in many different fields of science, even those regarding bioinformatics.

Heuristic algorithms have many applications and subtypes:

• Genetic algorithms, which are adaptive heuristic search algorithms, and can be used to guess the title of this book, as depicted in Chapter 9, See in Action
• Solving vehicle routing problems and the traveling salesman problem with the Tabu Search algorithm
• Solving the Knapsack problem, where you need to choose items of the maximum total value to be packed within the mass limit
• Filtering and processing signals
• Detecting viruses

Dynamic programming

Since we’re talking about various types of algorithms, it is worth mentioning dynamic programming. It is a technique that optimizes recursive algorithms by limiting the necessity of computing the same result multiple times. This technique can be used in one of two approaches:

• The top-down approach, which uses memoization to save the results of subproblems. Therefore, the algorithm can use the value from the cache and does not need to recalculate the same results multiple times or does not need to call the method with the same parameters multiple times.
• The bottom-up approach, which uses tabulation to replace recursion with iteration. It limits the number of function calls and problems regarding stack overflow.

Both of these approaches can significantly decrease the time complexity and increase performance, and therefore speed up your algorithm. Every time you use recursion, it is a good idea to try to optimize it using dynamic programming. If you want to learn how to optimize calculating a number from the Fibonacci series, go to Chapter 9, See in Action.

You can also use dynamic programming to find the shortest path between all pairs of vertices in a graph by using the Floyd-Warshall algorithm, as well as in Dijkstra’s algorithm. Another application is for solving the Tower of Hanoi mathematical game. Possibilities are even broader and you can also apply it to artificial neural networks.

Brute-force algorithms

While we’re presenting various types of algorithms, we should also consider brute-force algorithms. A brute-force algorithm is a general solution for solving a problem by checking all possible options and choosing the best one. It is an approach that can have huge time complexity and its operation can take a lot of time, so it can be useless in real-world scenarios. However, a brute-force algorithm is often the first choice when you need to solve some algorithmic problem. There’s nothing bad in doing this as you can learn more about the domain of the problem you wish to solve and see some results for simpler cases. Nevertheless, while developing an algorithm, it is a good idea to enhance it significantly by using other paradigms.

Here are some examples of where you can use brute-force algorithms:

• Guessing a password, where you check each possible password one after the other, as presented in Chapter 9, See in Action
• Finding the minimum value in an unsorted array, where you need to iterate through all items as there is no relationship between values in the array
• Finding the best possible plan for a day, placing various tasks between meetings, and trying to organize it in a way that you can start working late and ending early
• Solving the traveling salesman problem

After introducing a few types of algorithms, you can see that some of them provide you with a faster solution while others can have huge time complexity. But what does this mean? You will learn about computational complexity, especially time complexity, in the next section.

In this final section, let’s take a look at the computational complexity of algorithms, focusing on both time complexity and space complexity. Why is this so important? Because it can decide whether your algorithm can be used in real-world scenarios. As an example, which of the following do you prefer?

• (A) Absolutely the best route directions to work, but you receive them after an hour, when you are already at work.
• (B) Good enough route directions to work, but you receive them within a few seconds, a moment after you enter your car.

I am sure that you chose B – me too!

Time complexity

First, let’s focus on time complexity, which indicates the amount of time necessary to run an algorithm as a function of the input length, namely n. You can specify it using asymptotic analysis. This includes Big-O notation, which is used to indicate how much time the algorithm will take with the increasing size of the input.

For example, if you search for the minimum value in an unsorted array of size n, you need to visit all elements so that the maximum number of operations is equal to n, which is written as O(n). If the algorithm iterates through each item in a two-dimensional array of size n x n, the time complexity is O(n*n), so it is O(n2).

There are various time complexities, including the ones presented here:

Figure 2.5 – Illustration of time complexities

The first is O(1) and is named the constant time. It indicates an algorithm whose execution time does not depend on the input size. The exemplary operations consistent with the O(1) constraint are getting an i-th element from an array, checking whether a hash set contains a given value, or checking whether a number is even or odd.

The next time complexity shown here is O(log n), which is named the logarithmic time. In this case, the execution time is not constant, but it increases slower than in the linear approach. A well-known example of the O(log n) constraint is the problem of finding an item in a sorted array with binary search.

The third case is O(n) and is named the linear time. Here, the execution time increases linearly with the input length. You can take an algorithm for finding the minimum or maximum value in an unordered list or simply finding a given value in an unordered list as examples of the O(n) constraint.

The last time complexity shown here is the polynomial time, which is O(nm), so it can be O(n2) (quadratic time), O(n3) (cubic time), and so on. In this case, the execution time increases much faster than in the case of the linear constraint. It can involve solutions that use nested loops. Examples include the bubble sort, insertion sort, and selection sort algorithms. We'll cover these in Chapter 3, Arrays and Sorting.

Of course, there are even more time complexities available, among which you will find double logarithmic time, polylogarithmic time, fractional power time, linearithmic time, exponential time, and factorial time.

Space complexity

Similar to time complexity, you can specify the space complexity using asymptotic analysis and the Big-O notation. Space complexity indicates how much memory is necessary to run the algorithm with the increasing length of input. You can use similar indicators, such as O(1), O(n), or O(n2).

Where can you find more information?

In this chapter, only a very brief introduction to the subject of algorithms was presented. I strongly encourage you to try to broaden your knowledge regarding algorithms on your own. It is an extremely interesting and challenging topic. For example, you can learn more about various types of algorithms at https://www.techtarget.com/whatis/definition/algorithm and at https://www.geeksforgeeks.org/most-important-type-of-algorithms/, while about the computational complexity at https://en.wikipedia.org/wiki/Computational_complexity. I am keeping my fingers crossed for you success with algorithms!

You’ve just completed the second chapter of this book, which was all about data structures and algorithms in the C# language. This time, we focused on algorithms and indicated their crucial role in the development of various applications, regardless of their types.

First, you learned what an algorithm is and where you can find algorithms in your daily life. As you saw, algorithms are almost everywhere and you use and design them without even knowing it.

Then, you learned about notations for algorithm representation. There, you learned how to specify algorithms in a few ways, namely in a natural language, using a flowchart, via pseudocode, or directly in a programming language.

Next, you learned about a few different types of algorithms, starting with the recursive algorithms that call themselves to solve smaller subproblems. Then, you learned about divide and conquer algorithms, which divide the problem into three stages, namely divide, conquer, and combine. Next, you learned about back-tracking algorithms, which allow you to solve problems consisting of a sequence of decisions, each depending on a decision that’s already been taken, together with the backtrack option if the decisions do not provide a correct solution. Then, you learned about greedy algorithms, which choose the best option in each step of their operation while not being concerned about the overall solution. Another group you learned about was heuristic algorithms for finding near-optimal solutions. Then, you learned that you can optimize recursive algorithms using dynamic programming and its top-down and bottom-up approaches. Finally, you learned about brute-force algorithms.

The final part of this chapter looked at computational complexity in terms of time and space complexity. Asymptotic analysis, together with Big-O notation, was presented.

In the next chapter, we’ll cover arrays and various sorting algorithms. Are you ready to continue your adventure with data structures and algorithms in the C# language? If so, let’s go!