How can I improve my algorithmic ingenuity?

Question

During undergrad I felt my education was mostly comprised of applying existing theory to real world problems (ie. algorithm design/analysis). I've seen derivations of many algorithms and proofs of their complexity, but I'm often left bothered by the question of how one comes to discover an algorithm. It seems daunting to imagine developing a novel algorithm given the ingenuity involved in crafting an effective approach. I'm wondering if there are ways to train that ingenuity.

My question is, how I can cultivate the skills necessary to develop original approaches to quantitative problems? Are there any resources that focus on these skills?

Answer 1

It seems that competitive programming might help you. Or just the "programming" part of it. If you want to hone your problem solving skills (and therefore your ability to come up with original ideas), it seems that solving competitive problems is the way to go, since they by design target this skill.

You would need two kinds of resources: problem archives and theory materials.

For problem archives I can suggest you to try out

• timus.online (problems requiring some clever insights/observations start after ~270 difficulty)
• codeforces.org (problemset tab, richer variety of problems, but the overall quality is somewhat lower than that on the timus)
• onlinejudge.org (in uHunt there is a table with problems that cover a great variety of problems; a supplement for the book Competitive Programming 3)
• urionlinejudge.com.br (has some great problems)

Also, there's atcoder.co.jp which is like codeforces but primarily targets math-related problems.

The key to finding original ideas is to know what people have come up with already. If you understand these ideas and can apply them relatively easily then you a) can come up with a clever idea by combining these older ideas in a clever way and b) you can search for fundamentally new ideas much more efficiently because you know what is not a new idea and what is not the new way of thinking to find new ideas.

If you agree with the previous paragraph, then you'll need resources where you'll be able to learn new concepts and ideas. The key with this is to not only understand the theorem or the algorithm but to understand the intuition and the proof(s) also. Proofs give explicit insight as to how to come up with and how to be sure that the idea works. Understanding the tricks and algorithms (of thinking) used in proofs is the key to come up with your own ideas.

Intuition, on the other hand, is an implicit insight, it's something that connects problems, its proofs (or a subset of proofs) and the topic of the problem in general. I say this so that you wouldn't think that intuition is something magical or that if you didn't get it when you read a proof then you wouldn't get it at all. To acquire it you have to perform these steps

• Before seeing the solution, try to think on it for at least 30 minutes (for me, doodling helps a lot to come up with intuitive solutions)
• Then, if you feel that some ideas that you think are going to work 100% are there but you can't quite reach them in your brain, don't give up on it and hold on to them until you go to sleep. If you won't be able to sleep thinking on the problem, then you're sure to get some insight when you wake up. (https://psychology.stackexchange.com/a/13366 + my experience).
• Without any dependence on whether you have solved the problem or not after such a procedure, when you'll open the proof(s), you'll be able to absorb and analyze them much more efficiently, since you'll read not to know the ideas but to find out why your ideas weren't working, how close were you, where you have made a mistake in your thinking, what have you missed, why that thing you focused too much on wasn't that relevant, what have you had to know to solve it anyway, etc. etc.... (this is how SQ3R method works also, it makes you question the text first and only then lets you read it as a way to answer the questions; an active reading, instead of passive reading).
• If you were able to extract some guideful intuition out of the proofs, congrats! Now, forget about this problem and come back after two or three days and solve another similar or a little harder problem on the same topic. This way you'll "imprint" this intuition in your brain, so to say, for a relatively long time (See, spaced repetition)
• If you haven't then don't be sad. You understood more or less how the proofs work. This means that the only thing that's left is to unite them somehow with intuition. To do that just continue solving problems on the same general topic (strings, graphs, number theory, etc.). Intuition is not bound to some concrete problem (if that was, the intuition wouldn't be able to help solve other problems), if you'll understand intuitions behind other problems then naturally you'll understand the intuition behind the original problem as well!

Okay, so. With this, you'll be able to grasp the old ideas efficiently, understand the intuition and ingenuity behind them. These are plausible resources (although, I think you might already use them):

1. Introduction to Algorithms. Cormen
2. geekforgeeks.com
3. wikipedia.com (seriously, they have great articles on some algorithms)
4. visualgo.net (especially, if you're a visual learner ;)

From my experience at this point, you'll be able to come with original ideas by yourself and naturally. You'll be able to see the connections between the ideas clearly and they'll start to just pop into your head. Solving problems will sustain the neural paths in your brain and you won't forget the theoretical basis and intuition you've built. Solving problems will also build new neural connections and will bring joy when discovering new insights.

Lastly, I want to say that if your insight is nothing you've learned before, then it has value. If you combine two ideas together, even if it was simple, you'll get a new idea and it will have value. Every time you come up with such ideas, in any case, you create something valuable. If your goal would be to come up with something valuable, then you'll succeed every time. If your goal would be to come up with an "original insight", then you'll be quick to get severely demotivated, since no matter what you'll do, you'll most probably fail (at the beginning for sure). In the end, if you follow these steps or something similar, you cannot get not better! Surely, somewhen in the future, every tenth of your ideas will be a truly original one ;)