What is an algorithm?! Part one

Problem

The current state of programming is learning the craft mostly through personal practice or analysis of examples of third-party code that, for some reason, you have to deal with.

As a result, you learn programming on a whim. Collections of algorithms, applied techniques and design patterns help only a little in this work. The totality of the recipes they offer is built up in a long list, and its length threatens each of the read techniques to be forgotten (as the 53rd personal group in the “cart” was forgotten before the introduction of cataloging). But even the technique that remains in memory is most often simply a description of an applied problem in which its use was successful.

Why was a particular technique successful in the sample problem? Will he be successful in your project? What signs of the project make it clear that the use of the technique is appropriate?

In my personal experience of existing in the profession, it has been noted more than once that every Junior fights with the same windmills and comprehends the methods of creating programs based only on their mistakes. But many people have already made such mistakes. Why hasn’t a system of programming rules been created yet that will help a newly minted ship-programmer bypass the underwater coastal rocks? Well, for example, an explanation of the harm of using the “Copy-Paste” method for code development. If such rules can be explained by a small set of reasons that formed them, then this explanation will ensure their memorization and subsequent use in practice, thereby helping to evade the countless rakes laid out here and there.

For a compact and useful set of explanations you need:

• systematize methods of working with code;
• sort into groups the techniques of working with algorithms, which are the main goal of writing any code;
• highlight simple signs of using design patterns;
• develop universal rules and sets of effective ways to construct complex algorithms.

To summarize, we need algorithms to write and develop algorithms.

The intended series of articles does not claim to be a complete solution to this problem. A controversial attempt is being made to take the first step towards this solution. This step consists of highlighting the structure and properties of the main building block of the programmer - the Algorithm.

Task

Let's formulate the main problem that we want to solve. To do this, we first write down the operations on the algorithms that the programmer performs while writing his project:

• methods for synthesizing a macro-algorithm from sub-algorithms (sequential, parallel and mixed grouping);
• methods of structural transformation of macro-algorithms (optimization, specialization, docking...);
• methods for saving and transferring algorithms;
• methods for synthesizing a universal algorithm from similar algorithms in different areas of execution;
• methods for specializing a universal algorithm in a new area of ​​execution;
• methods for the formation and development of a complex system of jointly working algorithms;
• methods of interaction between simultaneously executed algorithms;
• and other methods, a complete list of which is difficult to provide and is not necessary.

Let’s look at the currently existing variants of the meaning of the word “algorithm” in search of clues on how to work with algorithms.

So, for example, the formulation “a finite set of precisely defined rules for solving an arbitrary class of problems” says that it is possible to somehow “precisely set the rules” from them to collect a “set” and with this set “solve” a certain “class of problems”.

A lot of questions immediately arise regarding this definition:

• What is a rule?
• How, to whom and for whom can this rule be set?
• What is unification as a whole?
• How do the rules relate to the task?
• What forms a task class?
• Is the way the population is formed determined by rules and objectives?
• …

Another formulation “a set of instructions describing the order of actions of an executor to solve a certain problem” says that there is an “executor” who can perform some “actions”, and with a certain “order” of performing these “actions” the “task is solved”. There are no fewer questions:

• What is the structure of the set?
• What are the options for action and performers?
• Is there a minimum possible action, a minimum set of necessary actions?
• How are actions built into the performer?
• What are the ways to create a copy of the performer (for example, if the performer is a person)?
• How do actions depend on each other in orderly execution?
• What is a task other than the fact that it is accomplished by a sequence of actions?
• How does the task relate to the performer and the actions?
• Is it possible to use the solution to a problem as an action?
• What are the possible options for specifying the order of actions?
• If playing a recording of forest sounds on a gramophone is an algorithm, then what is the structure of this problem?
• If DNA replication is an algorithm, then what is its executor?
• If the performer is a Turing Machine, how can it be used to solve a mechanical problem, such as sound reproduction?

Many questions are listed, but they do not help much in finding methods for working with the algorithm. Therefore, we will set ourselves a smaller task, but one that is also very important to us. Let's try to formulate what an algorithm does as a way to solve our problems, and what processes are “actions” for it. Even the solution to this “small” problem turns out to be very voluminous for one article, so we will break it down into parts. And therefore, we will devote the first article in the series entirely only to “Action” and its characteristics, which are omitted in the above definitions of the algorithm, but are very important for answering all the questions asked.

"Mo's Algorithm"

Let's discuss another solution to the same problem: this time we will group requests by both temporal and spatial characteristics. Let all requests be given to us in advance, and there are no update requests. Again, let's pretend that we haven't heard about prefix amounts.

We will group all requests into root blocks along their left border, within each block we will sort the requests by their right border and process each such block separately. We will go through the requests of the block, maintaining the sum of the current segment. For the first segment, we will calculate the sum honestly, and for all the rest, we will shift its boundaries each time and update the sum - one element at a time.

The trick is that the right border will move by \(O(n)\) in total, because the segments are sorted, and the left one will move by \(O(\sqrt n)\) each time. The final asymptotics of the solution will be \(O(q \sqrt n + n \sqrt n)\): changing the left boundaries in total across all blocks will take \(O(q \sqrt n)\) operations, and the right ones will take \(O(n \sqrt n)\),

struct query { int l, r, idx; }; // idx is the request number to be answered int a[maxn]; vector b[c]; int ans[maxq]; // array of responses to queries // somewhere in main: for (query q : queries) b[ql / c].push_back(q); for (int i = 0; i < c; i++) { sort(b .begin(), b .end(), [](query a, query b){ return ar < br; }); for (int i = 0; i < c; i++) { int l = i * c, r = i * c - 1; // boundaries of the current segment int s = 0; // sum on the current segment for (query q : b ) { while (r < qr) s += a[++r]; while (l < ql) s -= a[l++]; while (l > ql) s += a[—l]; ans[q.idx] = s;

This algorithm is not needed specifically for this problem, but it is useful for answering more complex questions: finding the \(k\)th order statistic on an interval, its median, the number of different elements, the most frequently occurring element, and so on. In all these cases, you just need to maintain some structure instead of a sum - for example, a hash table - responsible for many elements on a segment, and recreate it between blocks.

Note. The algorithm is named after some unknown Chinese and is accepted under this name in ICPC folklore. The author doesn’t like it, but what can you do: they couldn’t come up with another name.

Variations

On the trees. Some problems require reading the results of operations on a tree. For example: there is a number next to each vertex, and we need to return the quantities of different values ​​along the paths.

The idea is roughly the same as when reducing LCA to RMQ. We can write out an Euler traversal of the tree (we write out each vertex twice - at the moments of entry and exit), and now the problem is reduced to a problem on an array, with only one exception: we must add to the structure only those elements that are contained on the segment exactly 1 time.

Use root decomposition as structure. Often something complex is required from the internal structure in Mo’s algorithm, and we resort to using some “heavy” structures, like a segment tree. But this case differs from ordinary query processing problems: we have \(O(n \sqrt n)\) updates, and only \(O(n)\) queries. Here it is more efficient, instead of a segment tree, which requires \(O(\log n)\) time for both types of queries, to take a structure that works quickly during updates, and not very fast on the queries themselves - for example, root decomposition, which works in \( O(1)\) and \(O(\sqrt n)\) respectively.

In fact, this is about the only place where it is most effective to use a root heuristic as a structure—within another root heuristic.

"3D Mo." If you really want to, this approach can also be used in tasks where you need to process update requests. To do this, you need to enter the third parameter of the get request \(t\), which will be equal to the number of update requests before the current get.

Let's sort all the get requests again, but this time in the order \((\frac{t}{n^{\frac 2 3}}, \frac{l}{n ^{\frac{2}{3}} }, r)\), and process them with the same algorithm, only in three dimensions. The running time of the new approach will be \(O(n^{\frac{5}{3}})\), which is proven similarly to the original algorithm.

Algorithm Definition

Let's consider the definition of an algorithm, which says that it is a sequence of actions leading to the solution of a problem. As a programmer, I have to write a lot of code. This code consists of parts. Such parts are functions, classes, and modules. When I write the text of a function, I am writing an algorithm.

Previously, the algorithm was created in the form of block diagrams and semi-automatically compiled into machine codes. Now I am freed from the need to be an artist and a compiler to write a program. The text of my function is a recording of the algorithm in text form - its text flowchart. Here you can recall Scratch, which uses the visual creation of a flowchart of an algorithm without writing text. The way the algorithm is written is not so important now.

It is important that in writing a function algorithm I can use calls to other functions that I or another programmer have already written up to this point. Recalling the phrase “a sequence of actions leading to the solution of a problem,” we can note that the functions written earlier are my “actions.” That is, "actions" can be functions. To generalize, “actions” can be algorithms.

If “action = algorithm”, then you can try to rewrite the definition recursively “an algorithm is a sequence of using existing algorithms that leads to the solution of a problem” (atomic algorithm), which can be used in the development of an algorithm;

Action

First, let's look at the “action” and try to find the reason that makes it possible to use an existing “action” to create a new algorithm.

This reason is the possibility of reusing the “action” with obtaining the same result. Only then will an algorithm for solving a certain problem developed using this “action” solve this problem in the same way again and again. We have found important laws of our world, in which:

• there are “actions”, the main property of which is the sameness of the results of their execution at different points in time and in different places,
• It is possible to create a scheme for using several “actions” that will form a new “action” from them, which we called an algorithm.

What signs of “action”, besides repeatability, make it possible to use it in creating an algorithm? What is a terminal indivisible "action"? To answer this question, it is worth considering different examples of “actions” from our experience. Programmers have encountered them many times. This includes addition, multiplication, and setting the color of a pixel on the screen. But we are familiar with them outside of programming. All science is based on repeatable phenomena.

The law of gravity, which describes the repeated phenomenon of an apple falling, can also become an action. After all, any apple will fall to the ground? So this process can be used as an “action”! For example, solving the problem of driving Newton away from the apple tree that you accidentally climbed earlier.

Let's look at what happens when an "action" is performed. For example, when an apple falls from an apple tree branch to the ground. Several changes occur in this process. If we recall school physics and consider the situation in a reference frame tied to the Earth, then the force of gravity causes a change in the speed of the apple, accelerating it. At the same time, another important change is noted in the process - the distance between the apple and the Earth decreases.

In the example of the “Earth-Apple” process, the following characteristics can be considered:

• the presence of a process of change (distance and movement parameters of objects);
• the presence of objects whose interaction causes such changes;
• the presence of locality of the process, that is, the existence of a distance between objects, beyond which their interaction ceases to cause the process of change, which makes it impossible to use the “action” (Earth and a hypothetical apple located outside the solar system).

Let us consider different areas and processes with these signs, highlighting examples of “actions” in them and monitoring the features of these signs in the description of the structure of the “action”.

Physical processes

For physical systems, the processes of which we observe in our world, characteristic objects and changes are based on fundamental interactions and therefore they are quite simple to identify by analogy with the gravitational interaction of the Earth and an apple. For example, for a system of a proton and an electron or a system of two protons.

Separate from these simple interactions of two objects are multicomponent processes, for example, nuclear reactions (in the structure of the “actions” they are close to the chemical processes discussed below). Processes described by the total interaction of a large number of elements, for example, “ideal gas,” are also complex. Let's put aside their consideration for now and focus on the simplest examples.

Chemical processes

Let's move on to the next big area - chemical processes. Chemical reactions (for example), due to their repeatability, are also “actions”. The objects in them are atoms and molecules. To describe the changes taking place, it is necessary to slightly transform the “physical” changes. Thus, changes in movement parameters together give us a change in temperature during a chemical reaction. And among changes in distances between molecules, we, ignoring Brownian motion, can highlight the fixation of distance in the form of repeatable formation and destruction of bonds between parts of interacting molecules. Locality for a chemical reaction also exists - this is the absence of a reaction when sodium hydroxide and hydrochloric acid are in different test tubes and the presence of a reaction when the substances come into contact. Of course, in the “chemical” field of “actions” there are features that are not reducible to molecules, for example, photochemical reactions, where photons must be added to objects. The simplest processes were deliberately chosen for consideration.

Mathematical processes

The next area will be “actions” from the abstract algorithms known to us. Their most striking representatives are mathematical processes. There are some truly "hard cases" in this area, but familiar examples are sufficient for this article. Let us consider as an “action” a fairly elementary operation—addition. An example of this “action” is the addition of two integers by a mathematician.

In the situation with a mathematician, many objects can be distinguished, but from the point of view of “action” (“a mathematician’s addition of two integers”), there are only three objects: this is the “mathematician” object, the “first number” object and the “second number” object. Unlike all previously discussed objects, numbers are notations, that is, virtual objects. And their transformation in the algorithm is more complex than changing the distance and parameters of the movement of objects, as was the case for “chemical” actions. The details of such a transformation are the topic of a separate fascinating article. And within the framework of the current one, we will consider an ancient mathematician who adds numbers using piles of pebbles (Rom. 'calculi'), and a more “modern” mathematician who uses an abacus. Abstractions of such methods of calculating the sum are not so far removed from physical and chemical processes, therefore the structure of the processes of their “actions” is completely described by changes in distances and connections.

Interestingly, using the example of an ancient mathematician, the meaning of the word “add” becomes clear, which refers us to the action “put” and to the phrase “put together.”

Addition and the ancient mathematician

For a mathematician operating with pebbles, a sum is an “action” with the following characteristics.

Source objects:

• this is the “mathematician” himself (he interacts with the terms);
• a separate pile No. 1, containing and linking pebbles together (like chemical bonds), and denoting the first term;
• a separate pile of pebbles No. 2, indicating the second term.

Processes:

• the “mathematician” approaches the piles (physically changes the distance between the piles and himself) and begins to interact with them;
• "mathematician" combines two piles (physically changes the distance between two piles or transfers all the pebbles of one pile to another, perhaps using the "action" "Transfer one by one" pebbles)

Resulting objects:

• a formed pile of pebbles indicating the result (sum);
• a “mathematician” who moved away from the pile of results and stopped influencing it.

Addition and the Abacus mathematician

For a mathematician, the situation with the abacus is more complicated. The piles are divided according to their value into discharge grooves.

You can consider the simplest abacus with two grooves. Let it be decimal. Then one pebble on the tens furrow corresponds to ten pebbles on the ones furrow. And 10 is the maximum number of pebbles in a furrow of units. Compared to the action of the first mathematician, the representation of the terms changes. And in the arsenal of a mathematician several ready-made “actions” are already needed.

Actions:

• “Transfer one by one” from furrow to furrow of the same level (an action borrowed from the first mathematician);
• “Transfer to tens”, which must be performed if the units groove is completely filled, then all pebbles are removed from it except one, which is transferred to the tens groove.

Source objects:

• this is the “mathematician” himself (he interacts with the terms);
• a group of pebbles No. 1, lying and held by two grooves (units and tens), and denoting the first term;
• a group of pebbles No. 2, lying and held by two grooves (units and tens), and denoting the second term;

Processes:

• the “mathematician” approaches groups of grooves (physically changes the distance between them and himself) and begins to interact with them;
• “mathematician” combines pebbles from two grooves of units (physically changes the distance between pebbles, destroys connections with the old groove and creates connections with a new one) using the actions “Transfer one at a time” and “Transfer into tens”;
• "mathematician" combines pebbles from two tens grooves using the "Carry One by One" action

Resulting objects:

• a formed group of pebbles in two grooves (units and tens), indicating the result (sum);
• a “mathematician” who moved away from the group of pebbles of the result and stopped influencing them.

Locality in these mathematical “actions” is described by the absence of interaction between two terms that are far from the mathematician, and the launch of addition processes when all three objects of addition are “close”. A repeatable change in the mathematical “action” is expressed in a change in the connections between the stones and the locations holding them (piles, furrows).

Addition and the Turing machine

We can go a little further and replace the mathematician in such “actions” with the “control device” of a Turing machine. Then the “tape cells” of the Turing machine will contain terms.

In this case, both the sign of locality remains as the ability of the control device to interact only with the current cell of the tape, and the sign of changing the parameters of objects, which can be described as a change in the state of the cells.

A detailed description of the initial and resulting states of objects, as well as the “actions” that produce these changes for addition performed by a Turing machine, will be left outside the scope of this article. But let us mention that by moving to a machine we reduce the requirements for the “action” performer, which is the main way to create formal methods for working with the algorithm. You can set yourself the goal of simplifying each component of the algorithm to the point where its execution can be entrusted to a computer. Then there will be no dark places left in the definition of the algorithm, and numerous questions listed at the beginning will find their answer. So far, only the performer has been formalized. Let's say thanks to Turing for this and remember about “action”, the formalization of which is already on the threshold.

Not for crazy coders: books on algorithms and data structures

To be a good programmer, it is not enough to know the syntax of a language and write code well. When it comes to small template projects, this is enough. But then you come across something truly serious and large-scale, and it becomes clear that without knowledge of algorithms and the ability to work with data structures, you will not get far.

Tproger will help you - in this article you will find a selection of books that will help you start the path of a real programmer. By the way, to get acquainted with the topic, we recommend reading our series of articles on algorithms and data structures.

Algorithms, Etc.

These are lectures and other teaching notes for algorithms courses at the University of Illinois at Urbana-Champaign. In addition to theory, on the site you can find a large number of homework and exam assignments - although without answers.

Algorithms (Algorithms in Java)

Read Buy
Algorithms in Java by Sedgwick and Wayne is a classic reference guide that provides the programmer's essential knowledge of algorithms, accumulated over the past several decades.

The book covers a wide range of topics: comprehensive explanations of data structures and algorithms for sorting, searching, graph and string processing, including fifty algorithms that every programmer should know. New implementations of algorithms in Java are described, written in a clear modular style, in which all the code is accessible to the reader and completely ready for use. The book explores Java algorithms in the context of critical scientific, engineering, and commercial applications.

Binary Trees

A small manual from Stanford University, entirely dedicated to binary trees. Attention is paid to both theory and problems with analysis of solutions, both in Java and C.

Linked List Basics

Linked List Problems

Two more manuals from Stanford. The first contains theoretical materials on linked lists, and the second contains 18 problems. Will be useful to anyone who is learning C and wants to learn about the possibilities of using pointers.

Clever Algorithms: Nature-Inspired Programming Recipes

Read
In this book, the author systematizes information about the most popular algorithms used in the field of machine learning and artificial intelligence. It is perfect for students, teachers and people interested in AI development as a detailed reference book.

The Algorithm Design Manual

Read
The book is one of the most comprehensive guides to developing effective algorithms. The first part of the book contains practical recommendations for developing algorithms: basic concepts are given, an analysis of algorithms is given, types of data structures, basic sorting algorithms, graph traversal operations and algorithms for working with weighted graphs are considered, examples of the use of combinatorial search, heuristic methods and dynamic programming. The second part of the book contains an extensive bibliography and a catalog of 75 of the most common algorithmic problems, for which existing software implementations are listed.

The book can be used as a reference book on algorithms for programmers, researchers and as a teaching aid for students of relevant specialties.

Gems of Algorithm Design: The Functional Approach

Buy
An excellent book on algorithms that takes an unconventional approach.

The book is divided into 30 chapters, each of which is called a pearl. At the beginning of the chapter, the reader is given a task, for example, on data compression or related to a game. The problem is formulated using the Haskell language. Then, using functional programming methods, the “skeleton” of the program begins to acquire various ready-made functions. In this way, the reader will be able to better understand the essence of a particular algorithm.

Algorithms. Introductory course

Buy
If “Algorithms. Construction and Analysis" is a fundamental work designed to provide maximum information on certain algorithms, written by the same computer science professor Thomas Cormen, and is intended for an audience that is not ready to cope with a work of 1300 pages. So if you are one of them, but still need to get familiar with algorithms, then this book is for you.

Algorithms. Construction and analysis

Buy
Another weighty book on algorithms, first published in 1990 at the Massachusetts Institute of Technology, authored by local teachers. Despite the fact that it is written in simple and understandable language, due to the volume and presentation of the material (each chapter has a finished appearance), it is better to use it as a reference book, periodically referring to the necessary information.

The Art of Programming

Buy
The Art of Programming - a monumental work by Donald Knuth. The book series consists of 4 volumes, each of which covers certain types of algorithms. This is a classic that is still compulsory in universities. The material is presented in a rather complex format, but the books have a special purpose - to tell as fully as possible about existing algorithms.

Algorithmic tricks for programmers

Buy
Author Henry Warren described in his book many of the techniques that he learned over several decades working in the field of compiler development and computer architecture, application and systems programming. Here you will find many tricks for working with individual bits, bytes, and calculating various integer functions; Most of the material is accompanied by strict mathematical justification.

The second edition added material about CRC, error-correcting codes (ECC), various methods of dividing by constants (for example, using byte shifts), and much more.

Algorithms. Reference book with examples in C, C++, Java and Python

Buy
You won't find much theory in this book. All material in the book is focused on the practical application of various algorithms. The book is illustrated with examples in C, C++, Python and Java. Each algorithm is analyzed, its complexity and the various conditions under which it achieves maximum efficiency are indicated. In addition, in the book you will find recommendations on the use of various data structures in certain algorithms. Therefore, the book is perfect as a reference that will lie on your shelf and be used during the implementation of your projects.

Planning Algorithms

Read
This book contains a huge number of planning algorithms. They are used in one way or another in robotics, control theory, AI and computer graphics. The theoretical material is provided with a large number of illustrations and examples.

Purely Functional Data Structures

This book talks about the features of functional data structures. It examines the functional implementations of many structures: lists, queues, heaps and others.

Matters Computational

This book covers a huge number of different low-level algorithms. C++ is used to implement the examples. We recommend reading to everyone who works with calculations in one way or another.

Text Algorithms

This book is devoted to text processing algorithms. It sequentially examines various string comparison algorithms and data structures. The book can be mentally divided into two parts, devoted to practical and theoretical algorithms, respectively, so everyone will find something interesting in it.

The Design of Approximation Algorithms

This book is intended for those who are already familiar with the basics of algorithms, methods of proving their truth, and the theory of probability. Useful for students working with approximate calculations.

Data Structures and Algorithms

The authors of the book pursued three goals: to explain the basic algorithms as simply and accurately as possible, to provide them with diagrams, and to write clear listings in pseudocode that can be easily translated into C++, C# and Java. Did they succeed - read and find out