What Algorithms Worth Studying?

Here's what I was guided by asking this question:

Almost any employer wants to see a good algorithmic "base". Also, this "base" is needed in practice. But what should this "base" be? What algorithms to study? Yes, you can pounce on the infinite set of all algorithms and study them. But there are too many of them to implement them programmatically. Therefore, the implementation has to score.

I don't like this way. I think not only me. I tried to find such lists on the Internet, but found only people's advice - “Who knows what will be useful to you?”, “I have enough knowledge of sorting with a bubble” and so on.

Read a variety of books, such as Knut .. Again, there are many algorithms. I do not want to run and forget; I would like that knowledge would remain. But to master everything first is long, secondly many of these algorithms are of theoretical interest only and are not applied in practice.

Closed due to the fact that off-topic participants aleksandr barakin , PashaPash ♦ , Vladimir Glinskikh , Kromster , Alexey Shtanko 16 Aug '15 at 14:52 .

It seems that this question does not correspond to the subject of the site. Those who voted to close it indicated the following reason:

  • " Questionnaires are forbidden on Stack Overflow in Russian . To get an answer, rephrase your question so that it can be given an unambiguously correct answer." - aleksandr barakin, PashaPash, Vladimir Glinskikh, Kromster, Alexey Shtanko
If the question can be reformulated according to the rules set out in the certificate , edit it .

Blocked by a member Nofate ♦ 26 Aug '15 at 11:19 .

This question has been preserved because of its historical importance, but it is not regarded as a good question on a topic relevant to the specifics of this site , so please do not consider it as confirmation of your ability to publish similar questions. This question and its answers are frozen, they cannot be changed. Read more: help .

Read more about blocked messages here .

    3 answers 3

    Of course, it’s impossible to make a complete list, so I’ll go over what seems to me important.

    1. The complexity of the algorithms. You should know the O-notation and be able to immediately evaluate the O-complexity of the algorithm, at least for simple cases.
    2. Data structures! Not only simple structures, such as an array, but also complex ones: you have to imagine what happens when you add an element to a red-black tree ( std::map from C ++), and understand why adding to it is quick.
    3. Sorting. Simple (you need to know and understand the disadvantages and advantages of bubble sorting) and complex (to understand at least quicksort, and be able to explain his idea on the fingers).
    4. Algorithms for working with trees: for example, their various rounds.
    5. Search in the graph: in width and in depth, Dijkstra's algorithm and A *. Binary search in a sorted array, of course.
    6. Maths! Matrix algorithms (determinant, solution of a system of linear equations not through determinants), conversion between number systems (including mixed ones). Working with recurrent sequences: calculating the degree and the n th Fibonacci number for logarithmic time. Finding a convex hull and vector stunts (such as the distance between intersecting straight lines through a vector product) were still useful to me, but they are needed less often.
    7. Databases are important. You have to imagine how the JOINs are executed and what the “cost” of materialization of a VIEW is. You need to understand how indexes are built, how much they “cost”, and how they help. (In terms of O-notation.)
    8. Analysis of games can be useful. For example, the construction of a set of winning positions "from the tail."
    • I would also add matrices. And at least the base for discrete algebra. And of course +1 for the answer. - SilverIce
    • @SilverIce: I am still writing :-) If I remember more, add to my reply, maybe it will turn out to be a good list. - VladD
    • one
      @VladD. 7. - Sometimes it seems to me that a serious database designer, loaded, distributed, multi-user projects is a religion)) - SilverIce
    • one
      @SilverIce: Yeah, so you need to know its basics, so that when confronted with its adepts, you won’t be surprised :) - VladD

    Most of the employers who are interested in the "algorithmic base" were actually latent perverts who wanted to show you the olympiad curve, how boundless they are, and how small and latex everyone is around)) There were problems with the questions of payment and career growth.

    In fact, the lion’s share of the people is interested in three things in hired programmers:

    • the ability to quickly complete their education and creatively solve problems;
    • the ability to write quality code - that is, it does not contain bugs, does not contain errors in security, does not contain stupid errors that reduce speed;
    • ability to adapt to teamwork.

    Algorithms - good. But the general understanding of what sorting is, what indexing is, how best to store data, so that it is optimal in terms of costs and accessibility, how best to build a cycle (what actions are needed inside and what can be taken out), what errors might be in this code , and how they need to be screened and processed. What kind of data can users slip into the entrance on a fool, and which according to malicious intent - and how to protect the code as much as possible from external data errors? This is more important from the point of view of a good programmer.

    Algorithms as such you will need in three cases:

    • you find a job in a foreign office where qualifications as a whole are analyzed - but tests are usually built to understand whether you understand what it is all about - well, have you read the Whip, Sedgwick, Wirth, Stroustrup to the end);
    • you find a job in an office that writes low-level software, here you can run into the fact that many of the algorithms that "are only of theoretical interest and are not used in practice" still live and long live;
    • You settle in the office, which writes software for modeling, graphics and 3D engines))

    By the way, according to friends working in the latter category, knowledge of physics as a whole, the subject area, as well as algebra, geometry, mathematical analysis and the ability to click the five-story equations (and correctly) - they need more often than Knut.

    Diversification of knowledge and skills, as for me, is as useful as income;)

      On the advice of @VladD, the commentary on his answer was also transformed into a response.

      I would add:

      Understanding of compilation-interpretation-linking (here (except for linking) there are regular expressions, and you also need to understand how their algorithms are designed).

      The idea of ​​working with disks (now also with flash). In this regard, it is useful to know how external sorting works.

      More on the same topic - when index access to data in the database is useful, and when, on the contrary, it only slows down the execution of the query.

      Well, how the LAN (TCP / UDP / ICMP, etc.) works. Here first of all it is necessary to get acquainted with sockets.

      Another fashionable topic is threads (synchronization of memory access, respectively). Immediately recall the processes and algorithms of interprocess communication.

      Algorithms are not directly related to algorithms, but certain knowledge in the field of modern computer architectures is desirable. First of all, pipelining command execution, command and data prefetching, extraordinary execution, processor caches and the problem of cache coherence in SMP and NUMA architectures, the order of delay times for accessing cache and RAM, and the organization of virtual memory (separation of functions between hardware (MMU, TLB) and OS), interrupt handling principles (also what iron does and what OS does).

      ( if something else good (or asked about what or I asked) remember, I will add here )