How should I approach CS problems?

[Ankit1010]

I'm a junior in college, majoring in Computer Science, but I'm having a hard time approaching CS problems.. I'm at a very prestigious university with a tough curriculum, but I'm still able to keep up in class and solve the assignments, because we are generally told what data structures / algorithms we should be using, and at the end of the day it's just a matter of implementing them.

In regards to complex algorithms we cover in lecture, I find that I don't really understand them during lecture, but after a lot of self-study, I can get to the point where I can reproduce the steps of the algorithm on paper and have a basic understanding of the steps (i.e for Djikstra's write down the current state of the priority queue of distances), but this is somewhat mechanical, and I don't feel as if I really get the algorithm (i.e intuitively understand how it works, or see why it's the best possible algorithm for a certain task).

Another place where this manifests itself is in interview questions, or if I'm trying to solve problems on sites like InterviewStreet / TopCoder (they are algorithm based programming challenges). Most of the times, I simply can't come up with a good answer, but after someone tells me the answer I can understand it. This isn't always the case, but it is a lot of times. I find that I get easily confused when trying to reason about complex problems - understand which algorithms/data structures would apply, calculating the time complexity of different approaches.

I love computers, and am skilled at application - stuff that a real programmer would do in most cases - web apps, mobile apps, scripts, networking, but I'm having a hard time with algorithms and theory - which is really what CS is about. I'm not going to switch majors to something more application based because I'm confident I can learn those things on my own. I'd rather utilize this time to learn CS, especially given that my university is excellent at it.

I've been active on the forums for a while, and I know that the XKCD community is brilliant at theoretical aspects, so I'd like your advice. How can I become better at understanding algorithms and CS theory? Any advice on how to think about problems, books to read/problems to solve or anything else is appreciated.

[Yakk]

One of the things that makes reasoning about complex problems easier is improving your working memory when working on the problem -- or, equivalently, improving your ability to compress information about algorithms and problems so they take up less working memory.

How are you at generating mathematical proofs? Do you have any training in that area?

You basically have said that you have no experience with generating algorithms/picking an algorithm to solve a problem. Why are you surprised that you aren't all that good at a task you have little practice at?

"Best possible algorithm" -- with few exceptions, we rarely know that in CS. The theoretical tools CS has to prove that kind of thing are limited. We just know if an algorithm is better than the alternatives we know about, usually.

Maybe you need to start working on building algorithms for relatively simple cases -- try a bunch of them -- and then try to improve it. Or get someone who knows more than you to suggest not an ideal solution, but an improvement. Failure is going to be common, because learning without failure is just rote learning.

[Ankit1010]

One of the things that makes reasoning about complex problems easier is improving your working memory when working on the problem -- or, equivalently, improving your ability to compress information about algorithms and problems so they take up less working memory.

How are you at generating mathematical proofs? Do you have any training in that area?

This is exactly my problem - it feels like I don't have enough working memory to hold all the parts of a problem together in my head to reason about it. To express the above question far more succintly - I want suggestions on how to improve my working memory.

I see how you relate this to mathematical proofs - I'm quite good at solving mathematical problems, in the sense that I often see the "trick" to solve tricky ones before others do. But when the problem in question has a lot of things going on, or a rather large proof it overpowers my working memory.

The reason I'm asking for advice is I've had the same problem for a while now, and just trying those kinds of problems again isn't helping, so I want more concrete plans on what I should be doing to improve that.

[mfb]

Training allows you to compress stuff and relate it to something you already know, so you can "see" more with the same working memory. And, depending on the definition of "size" of a working memory, it can increase that size.

There are always problems (and solutions) which are so complex that it is nearly impossible to see every detail at the same time - not even for the person who worked that thing out. You have to divide it into smaller parts.
It means that it is harder to find a solution, of course - it is likely that your first idea does not work. Or at least not in the way you thought of. But hey, that is the interesting part... problems which are not trivial!

[WarDaft]

One way is to simply assume you've already done most of the work, and have the final operations you'll need to piece together to write the actual program. Make sure you use them in a consistent way.

Then, build those, under the same assumption. Repeat until you can solve the problem directly. Then debug. A lot. With practice, you'll spend less time debugging and get the answer faster with more general solutions. In some languages, assuming you have already solved the problem can actually make the smaller parts easier to build. You'll start to find that you can use larger and more complicated operations as building blocks intuitively.

Most importantly, try to keep track of what you're doing, why you're doing it, and the decision making process you're using, the results you get, how much time you spend debugging afterwards, and that sort of thing. Take notes if your diligent enough. Try to find the mindsets and strategies that ended up working most for you. It's a general life strategy, but extremely useful for CS because your options in writing a program are so vast, and so many of them are just bad. Do note that no one actually does this, but it's still a good idea.

[jj7947]

The ability to solve complex problems may not be something that is taught or even learned by reading. From my own experience I have found the only way to get better at solving problems is to keep solving problems. There are different methodologies and techniques that you can read about and one such book helped me to understand better on our own thinking, reacting and learning. The title of the book is Pragmatic Thinking and Learning: Refactor Your Wetware. You can Google it.

[Jplus]

A good idea might be to first find out how much you can keep in your working memory, at most. Then find a problem that is just slightly larger than that, and solve it. Keep stretching like that until you start to feel kind of satisfied with the capacity of your memory.

Note: if you keep solving problems your capacity will still grow after that point, but you'll probably be less aware of it.

[freakish777]

Play a game that requires significant planning and "look ahead." Chess or Go for example. You can play each of those online, ideally you play one game (or more) a day (not blitz Chess games).

Many people like to dismiss games as childish, but there's a lot of critical thinking skills and life skills someone can learn from a game as simple as Chess:

Patience
Planning
How to properly evaluate your options

In fact, the University of Florida uses Starcraft 2 to teach business students how to manage resources, and there's at least one Silicon Valley manager who has said that his playing SC2 made him much better at coordinating his direct reports to get projects done on time.


Also, can't resist:

How should I approach CS problems?

With gusto.