Ask HN: How should I study algorithms and datastructures?

[PixZxZxA]

Dear all, I am currently studying towards a Bachelor's degree in Computer Science in Sweden. Right now I am attending a course called "Algorithms and datastructures", where we get an introduction to sorting, searching, priority queues etc.

If feel that I need to spend a lot of time in order to really understand the essence of the algorithms, which gets very time consuming when you need two days only to understand insertion sort and merge sort.

How do I study these topics the most efficiently? How well should I know certain algorithms and datastructures?

[veddox]

Short answer: code them ;-)

Long answer:

The Algorithms and Data Structures course is one of the foundational courses of a CS degree. Even if you think you don't need to be able to implement the algorithms you learn in your work later on, it is important to have some idea of which algorithms exist for a given task.

Also, and perhaps even more importantly, understanding how these algorithms work really hones your problem solving skills. You learn how to abstract the information given to you as part of a problem into an appropriate data structure, and what kind of operations you can carry out with which data structures. You learn how to cope with several different layers of abstraction and develop an intuition for programming approaches that are fast and/or light on memory. Basically, the ADS course doesn't teach you how to be a programmer, but how to think like one.

As for studying for this course: there's nothing like doing it yourself. Chances are, you already have to do so anyway as part of your course work. Take the programming tasks seriously and really do try to do it yourself. (Get friends to help you by all means, but don't let them do the work for you.)

I would advise you not to slack either: based on your information and the ADS course at my uni, I'm guessing that you're still at the very beginning of your degree. It isn't going to get easier in terms of workload, and the algorithms you learn about later on in the course are a lot more complicated than those at the beginning. But if you've made the effort to understand the first bunch of algorithms, you'll be in good shape to understand the latter ones too. So yes, it is hard work, but you can do it :-)

[marvy]

Two days to understand the ESSENCE?? I understand that there are a lot of details, and those can take a lot of time to master, but the essence should be really quick. To wit:

1. Merge sort. Given two sorted sequences, they can be merged in linear time. Given an algorithm that does so, we can sort a list in O(n log n) time, as follows: split the list into two equal halves, merge sort each half, and then merge the result. (The base case is that sorting lists of length 1 is really easy.)

2. Insertion sort. Let's say you want to sort in increasing order. To make things concrete, let's say your given list is

[3, 1, 4, -1, 5, 9, 2, 6, -5, -3]

You start by walking through the list: 3, 1, ... WAIT. That's not right, 1 should come before 3. Let's drag it to the front of the list where it belongs. We now have:

[1, 3, 4, -1, 5, 9, 2, 6, -5, -3]

Now we again walk through the list: 1, 3, 4, -1 ... WAIT. What's -1 doing here, let's drag it to the front of the line:

[-1, 1, 3, 4, 5, 9, 2, 6, -5, -3]

Again: -1, 1, 3, 4, 5, 9, 2, ... WAIT. What's 2 doing here, we need to drag it forward, but not all the way to the front:

[-1, 1, 2, 3, 4, 5, 9, 6, -5, -3]

And so on. Is this what you meant by essence?

[PixZxZxA]

I probably used the wrong word. I meant it took me two days in order to really understand the algorithm, to understand different implementations and find all the little details, to get some kind of intution that makes me able to code the algorithm just from my head in an efficient way.

[marvy]

Oh. Then I suppose two days is quite good. I don't think you really need quite that depth, but if you want it, I don't know if doing it much faster is possible. (It might be possible, I just don't know.)

[Jtsummers]

This may be too late for you to notice it, hopefully not. Something useful for me was not learning any particular algorithm or data structure in depth, but learning the "shapes" of algorithms and data structures.

When starting out you'll be learning, for example, the different sorting algorithms in great detail. This isn't terribly useful later on (the level of detail at least). What is useful is that they each have a shape, a style of functioning. Merge sort as one of the quintessential divide-and-conquer algorithms provides an excellent template for other algorithms with the same shape, but meant to compute something different. While bubble sort is a terrible sort algorithm, the pattern of bubble sort for computation is present in numerous algorithms. Same with insertion sort and shell sort and the rest.

It's like language acquisition, or at least like language acquisition is for me. When learning Spanish, I learned a lot of specific instances (hablo, hablas, habla, hablamos, hablan as 5 distinct things). Then I learned the pattern (grammar rules, -ar verbs generally drop the -ar and -o means I <verb>, -as means you <verb>, etc.), then I focused on root words in vocabulary (hablar means to speak) rather than memorizing every conjugated form of a verb.

Same as physics and calculus. Learn specific cases at the start, then you learn the rules, then you apply the rules to new forms to construct novel (to you) solutions.

And as others said, code. My algorithms class didn't require much programming, technically, it was rather high level. But I coded everything I could to try things out and understand them. Sitting down with pencil and paper to understand it was sometimes helpful, but the act of coding was more effective.

EDIT: High level in that it was focused a lot on the maths of algorithm analysis. I had one earlier in college that was more practically focused, on implementing algorithms, but the one that really stuck with me was the later one.

[kiloreux]

I would first ask. Do you really need this in your day to day life? I know a lot of companies use this for hiring, but you can still get a job without them.

However if you still want to study them, there are plenty of resources online, like this youtube channel[1].

Taking 2 days to understand insertion sort is fine but you just need to practice learning more often and use the things you learn more often. Even if it's on toy projects.

https://www.youtube.com/user/mycodeschool

[Muuuchem]

He is in college taking an algorithms class, so I would say he does need the knowledge haha.

[kerneldeveloper]

I must recommend two books, both of them are awesome. One is Algorithm by Sedgewick and the other is The Algorithm Design Manual by Steven S. Skiena. You can read the first book and then the other. If you want some challenges and practice, try LeetCode and HackerRank. By the way, it'd be better to keep a discrete math book at hand, it would help you if you encounter some mathematical proof problems. I would recommend Discrete Mathematics and Its Applications by Kenneth H. Rosen for reference.

[vskarine]

not the fastest but IMHO most practical way is through http://www.usaco.org/ training program @ http://train.usaco.org/usacogate, it's free and it will teach you to code and use most data structures and algorithms you'd ever encounter

[fadzlan]

Would this count?

https://visualgo.net/en/sorting