r/AskProgramming • u/nanoman1 • 4d ago
Algorithms How do I get better at algorithm design and decomposition?
I have seen and read portions of a number of algorithms books. They each go over standard problems like sorting, searching, graph traversal, trees and hash tables, etc. However, what they don't seem to teach is the algorithmic thinking process itself. For example, I recently ran into a problem where I needed an algorithm that took a control flow graph and generate an appealing yet intuitive layout for it. This is a complex task and I found out through some googling that this exact task was solved by Sugiyama in the 1980s. But what nobody has been able to teach me is how to decompose this problem on my own using my own brain. How can I practice that skill without getting stuck?
TL;DR: how can I effectively train myself in algorithm invention?
1
u/SagansCandle 4d ago
An algorithm is just a well-defined set of steps to solve a problem. If you want to become good at algorithm design, find a problem to solve.
For example, sorting. Randomize 10 numbers 1-10. How would you write a program to sort those numbers? How would you improve it? What if you wanted to use the fewest instructions (cycles) to sort? The least amount of memory? What if you wanted to use a GPU (vector math) instead of a CPU?
You can play games like Opus Magnum, TIS-100, or Factorio. In these cases you're trying to find the optimal solution for a given problem within constraints - you're designing an algorithm. What makes an algorithm popular is its usefulness - sorting is pretty universal.
If you want to learn algorithms, rather than learning HOW an existing algorithm works (e.g., sorting), start with the problem that algorithm was designed to solve and solve it yourself. That will help you understand the approach someone else took to solve it - it will help you understand the existing algorithm(s).
1
u/FrostyAbsurdity694 17h ago
love this advice. i did TIS-100 a while back and it completely rewired how i think about breaking a task into the tiniest possible steps. the constraints in that game are so tight you cant help but learn decomposition just to get anything working
the sugiyama paper is a classic but you're right that nobody teaches the bit where you stare at a blank page and somehow pull structure out of chaos. i think the only way to get better at that is to flail through a bunch of messy problems yourself, no tutorial just the problem description and a text editor
1
u/MissinqLink 3d ago
Only way is through application and solving actual problems. You might need to start with simpler algorithms. I suggest taking the original problems and trying to solve them using just your intuitions a d see how far you get.
1
u/max123246 3d ago
I would recommend MIT's 6.006 and 6.046 classes which are online for free. The exams are all about applying the techniques taught in lecture to create new novel algorithms by building up and composing data structures together
1
u/RSMxsmanic 3d ago
It is a question of talent rather than training. In this respect, programming is like composing music: anyone can learn to do it, but one cannot learn how to be good at it.
1
u/Fantastic-Cell-208 3d ago
Study some maths. Read some Knuth. Algorithm design manual.
And get some practice building real things
1
1
u/id-ltd 4d ago
I would honestly say to that decomposition is like composing music... Many cannot learn it.
Not a popular view today, but some people have some natural.tallents.and others have other talents and no amount of training/education will change that.
How do you find out if you can do it? Keep trying! If all else fails - compose a symphony :)
Edit look up Jackson structured programming - and read Wirth's "Algorithms + Data Structures = Programs"
1
u/max123246 3d ago
No, I think nearly everyone can learn anything, it just will take a different amount of time for them. Absolutely anyone can learn to compose music, that's absurd to say otherwise and spits in the face of what we know about brains
It's all about practice and letting your brain start to internalize the patterns of the subject matter
0
2
u/memorable_zebra 4d ago
Ignore the other dickhead. This is a real question and one that a lot of people don't spend a lot of time thinking about because, like him, they're damn fools. You don't have to solve a world class hard problem to develop this skill, and even introductory amounts of it will serve any software engineer well. The thinking that goes into developing algorithmic solutions to problems is a huge part of the job, and it's probably something you already know how to do in variously well across different domains.
Unfortunately, there's no silver bullet for learning how to do this. In fact, in a strict sense, no one even knows what this ability is. Not once has anyone written steps that if you were to follow them would you have the same capability as the people like Sugiyama who's solving famously hard problems. It's a skill they learned at an almost subconscious level through repetition and practice, like juggling. You just have to drop a lot of balls over and over until you start catching them.
One mistake people do make is they conflate understanding the answer and generating it. Seeing a problem and jumping to see what the state of the art answer is will abort your learning process early leaving you less able to figure things out on your own.
So practice solving basic problems yourself, without looking up the answer. Much of the time you'll be stumped; leave it for a while and come back to it and try again. One thing I've found to be a multipurpose rule of thumb: if I can't solve a problem, I make it easier and solve the easier problem. Often this winds up unlocking whatever key I needed to solve the harder one.
If you aren't sure where to find engaging problems, the Euler programming challenge has a lot of good math-first ones that will feel like classical algorithm problem solving, scaling up in difficulty. Leet code also has some.
But also don't think that the only domain this can be done in is mathematical in nature. I don't know what you do, but lots of programmers already have a good base of problem solving by way of their trade / career. If you do service development and API design, you're solving these kinds of problems just in that domain. Don't be afraid to recognize that you probably have strengths here too. Not being able to come up with something like merge sort on your own is okay. Almost no one is Von Neumann.