Thread: Arrays: General Operations and Algorithms.

Actually, I think this forum is pretty good for generating problems all on it's own. People generally come here with an idea of what they want to do, and a semi-complete example of code that they think can get the job done (I just typed in "array problem" into the search bar, and got a whole host of problems ).

My advice is to not worry about memorizing the information needed to solve every conceivable problem however. It's much better to try and come up with a system you can view the problem by, then come up with an answer. The system I use sort of looks like this:

1. Identify the problem. (What does my program need to do?).

2. Identify the information needed. (What does my program need to do it?)

3. Identify where the information will come from. (Where will I get what I need? Is the information part of the system already, or will I need to add it?)

4. Identify how to use the information to meet the needs of my program (At this stage we have the puzzle pieces, all that's left is setting them in place.)

This sounds pretty easy, but in real life I've noticed that things rarely go so smoothly. It's important to try and solve one problem at a time, don't try an do to much with a single step.

Anyway, my point is that by trying to memorize solutions to specific problems, you become like a military commander who is always ready for his opponents last operation. All I've done in trying to create my problem solving steps is to identify the points at which pieces of the solution become more apparent, there could be a better more comprehensive way.

Originally Posted by skyliner

I had a test this Tuesday; I failed. Three problems, all array related. A 45 minute time limit.

I don't know if this matters, but the test sounds suspect to me, unless the course covered these types of problems explicitly.

Just out of curiosity, I wrote the three programs in C (assuming by 'streak' you meant a consecutive sequence of numbers that sums to zero). I consider myself pretty proficient in C, and good at problem solving, but it still took me half an hour, at zero pressure, to implement these. (One reason I did this is that I don't remember solving these particular problems before. For the first, I used a simple nested loop. For the second, I found the minimum (and counted duplicates), then used a loop to find new minimums larger than the previous minimum (and count duplicates), until the sum total count matches the sum length of the two input arrays; this approach is roughly O(N^2) but robust, and works even in case of duplicates and one array being empty. For the last, I used a simple triple loop.)

In a test situation, I might have failed, too. Their loss.

I do understand that in current IT culture, output is all-important, and quality is an afterthought, perpetually pushed to future versions. In that kind of culture, this test does make sense: it teaches you to go for the fast, easy solutions using memorized patterns. The intent is to produce productive drones, not thinkers.

You might be like me, someone who does need time to think, and is not suited for high-volume code output. On the other hand, given a day or two to think, I can solve problems others take weeks to hack at and declare unsolvable in frustration. My rate of production is low, but the quality thus far seems to compensate for it. (Considering my posts are excessively long and verbose, I don't want to consider what it means for the quality. Reader beware, I guess. Also, I'm often wrong.)

Originally Posted by skyliner

I decided never to let that happen again. Array problems have always been my weakness.

Don't go that way. That way lies clinical depression, burnout, and lots of wasted time. Instead, accept it, and only decide to work on it, without promising anything or demanding any specific results from yourself.

I made a similar decision after picking a business path instead of research as I wished I had. I did quite well business-wise, but my mind crashed and burned. Twice. I have been trying to recover for the last five years or so. It's slow going.

Originally Posted by skyliner

In general, any kind of timed problem solving exercise makes me uneasy.

Me too, because they're designed to measure your productivity and ability to memorize solution patterns, and not your ability to find new solutions.

I even avoid timed puzzle and adventure games (I'm not kidding).

Originally Posted by skyliner

I marvel at the way others can come up with solutions so fast when I'm barely starting to dissect the problem into pieces.

For years, I had a similar problem with higher mathematics (solutions to differential equations and so on). I've never been good at memorizing stuff (other than the first 20 digits of Pi); I easily remember the overview and interesting features (applicable domain, problem spots), but the actual equation or full name of some long-dead scientists the equation is named after, often escapes me.

I had painstakingly pored over my Arfken-Weber (Mathematical Methods for Physicists), with very poor results, almost failing my classes. Suddenly, I realized there was a gaping hole: instead of being shown ways of deconstructing and classifying mathematical problems, my lecturers had concentrated on showing how to prove a solution is a correct solution after you have found a solution. I scanned through the books I had at hand, and created a four-page synopsis for solving differential equations (pretty similar to this WikiHow page). Armed with that one, mostly skipping the lectures as useless, I got a 4 (equivalent to a B) on my next exam.

There is a very similar issue to problem solving. There is a definite craft to it, mostly related to how one should construct their perception of a problem, and how to be willing to discard or revise parts of that mental model, at will. I find it similar to constructing several competing structures in parallel, comparing their merits and failures, and sometimes getting a kick out of the childlike wonder and energy you get by just stomping all over them, and finding a completely different approach to the thing. All of this takes time, but it seems to work.

I have not talked about this with more than two or three different people, so I believe I'm quite likely reinventing the proverbial wheel. I do like to call this area -- the craft of systematic problem solving -- meta-problem-solving, because at the core, it is about solving the problem of problem solving. (Corny name, maybe, but I like the pun. If it wasn't fun, I wouldn't be doing it for fun.) If you or anyone else find good references or books or articles about this, please let me know. The ones I've encountered tend towards philosophy, and have not had any practical relevance to the craft. At this point, I'm just about resigned to trying to compare the few known structured approaches to problem solving in their own respective domains, and trying to find the similarities and differences, to try and uncover the craft beneath.

The thing I do have found, is that the human brain is really, really good at finding that craft all by itself, without specifically knowing what the craft really boils down to, as it is exercised in different problem domains. This is very good news. It means that if you just get experience in solving different types of problems, using different methodologies, your brain tends to become better and better at it.

A good example of this happening is something many programmers have noticed: When you learn new programming languages, learning new programming languages becomes easier. You might think it is just because the programming languages necessarily have similarities, sharing a common mathematical basis, but I disagree: I've found and seen in others that also the capability to understand new paradigms -- like object-oriented programming, or say functional programming -- grows easier. I think it has something to do with "thinking outside the box"; that once your mind realizes its own current limitations, it can overcome them, and that after a few times of realizing the limitations, the mind becomes more able to both perceive and overcome its own limitations in general.

In practice, it seems to me that a wider background experience will produce better problem solvers than current, pipelined limited-to-one-small-domain study programs produce. Feel free to disagree, though; I'm often wrong.

Originally Posted by skyliner

I would like to know if you guys are aware of any good site with programming exercises related to this topic

Um, picking up a specific tool and going looking for problems to solve using that tool, is a pretty poor approach.

Instead, try to branch into areas you're interested in -- even areas you might think you don't have the necessary background knowledge --, and see what kind of problems the enthusiasts there discuss, and how they solve them.

Fortran code -- still very commonly used for scientific computation -- relies heavily on arrays, so you might wish to see if there are scientific computation fields that interest you. On the other hand, Fortran code is often quite poor, more accrued or congealed than designed, written by people with little formal education in abstract data structures or algorithm analysis, resulting in code where brilliant ideas and groan-worthy implementation are happily mixed. However, looking at the problems the code solves, and trying to find better ways to solve the same problems, might help you develop the skills you need.

Originally Posted by Nominal Animal

A good example of this happening is something many programmers have noticed: When you learn new programming languages, learning new programming languages becomes easier. You might think it is just because the programming languages necessarily have similarities, sharing a common mathematical basis, but I disagree: I've found and seen in others that also the capability to understand new paradigms -- like object-oriented programming, or say functional programming -- grows easier. I think it has something to do with "thinking outside the box"; that once your mind realizes its own current limitations, it can overcome them, and that after a few times of realizing the limitations, the mind becomes more able to both perceive and overcome its own limitations in general.

Paradigms overlap like anything else, so yes, it becomes easier to grok new ones because you've already come to already understand some shared aspects.

If the mind learned to "think outside the box" to "overcome its own limitations in general", then learning new programming languages would make you be able to learn new musical instruments faster, and vice versa, but this is not the case.

Originally Posted by Yarin

If the mind learned to "think outside the box" to "overcome its own limitations in general", then learning new programming languages would make you be able to learn new musical instruments faster, and vice versa, but this is not the case.

I disagree.

First, learning new musical instruments is a matter of training your motor cortex, rather than anything to do with your mind.

Second, learning logic, structures and algorithms, I do believe does help you understand music: that there is structure, and the structures define how we perceive the "moods" in it, how specific structures evoke specific reactions in humans (consider harmonies et cetera), and so on. (In this respect, the current mass-produced four-chord music is utter crap compared to some classical music.)

I'm definitely not claiming it's magic or magick-like: by learning to program, you do not suddenly understand music (or anything else) better. I claim that learning new things open up your mind into new ways of thinking. (Or something like that; it does not work if you only memorize or learn the same kind of things. It's more about being able to perceive in new ways, really.)

Perhaps a funny test might show you how weird this stuff works. If you can think (subvocalize) in more than one language, pick two different but similar puzzles or programming problems. Work on each while thinking completely in one language -- not by translating, but keeping even your subvocalized thoughts in that language --, and compare the results and how long it took you. Then, do the same four or five times, and notice how your performance changes. Perhaps this has more to do with how language itself affects our thinking, but my point is that the relationship between learning new concepts and new ways of thinking, and how you solve problems, is much more complicated than you might believe.

Originally Posted by Yarin

If the mind learned to "think outside the box" to "overcome its own limitations in general", then learning new programming languages would make you be able to learn new musical instruments faster, and vice versa, but this is not the case.

Is that "but this is not the case" based on only your gut feeling, or do you have something to back it up?

It seems that learning a musical instrument seems to help your mind grow in other ways, too.

So, at least the inverse seems to happen in real life.

(The Slashdot link was just too funny a coincidence to ignore, sorry!
I don't have any scientific proof myself either way.)

Originally Posted by Nominal Animal

Is that "but this is not the case" based on only your gut feeling, or do you have something to back it up?

It seems that learning a musical instrument seems to help your mind grow in other ways, too.

So, at least the inverse seems to happen in real life.

(The Slashdot link was just too funny a coincidence to ignore, sorry!
I don't have any scientific proof myself either way.)

Eh, learning code just makes you more confident of your intellectual abilities, and the more confident you are the less likely you are to fail. I do agree that learning one language helps you learn a second, ect, I just think it's like Yarin says, that you begin to recognize patterns (that is the brains job after all).

It would be nice if it was more than that, but I would need to know the mechanism before I could believe it (if a psychological mechanism even means anything).

Originally Posted by phantomotap

"How to Solve It" by George Pólya

Thanks; that and TRIZ look very promising. (Although now I'm pretty miffed nobody pointed these out when I started my university studies; they just might have saved me countless hours of frustration.)

Originally Posted by Alpo

makes you more confident of your intellectual abilities, and the more confident you are the less likely you are to fail

I guess so too. Or, perhaps, it is more about fear restricting your intellectual abilities, rather than confidence making you less likely to fail. (Confidence just makes it easier to learn from your failures and move on, without dwelling and getting stuck in the failures.)

Certainly, looking at business analysts, high-powered executives, and politicians, intellectual ability seems to not be required at all to be successful. As long as you portray the correct image, failures just do not matter.

Originally Posted by Yarin

playing is diverse in what it demands from the brain, it's benefits are diverse, and so can benefit a more diverse range of activities.

Yes; I cannot rule out that everything I've observed could be simply boiled down to "problem solving in general is a skill that benefits from a wide, diverse background of activities and concepts".

Originally Posted by Yarin

There just isn't any evidence that learning new instruments helps you to learn new programming paradigms, simply because they don't overlap (at least that I know of).

I don't know of any such evidence, either. However, the human brain is excellent at drawing analogies and parallels between completely different scenarios, so I'm not at all sure they do not overlap.

For example, if someone is learning how to play guitar, you could use that to teach how something like an I2C bus works: your hand on the neck controls the pitch/data (SDA line), and plucking the string corresponds to the clock (SCL line). If you move your hand on the neck too early or too late, it'll change the tone. And so on.

You could say that I claim that having a diverse background makes it easier for the human mind to find analogies (even incorrect ones) that yield ideas on how to attack a specific problem; and to compare multiple such attacks, to select the best one. This is what I think is "thinking outside the box". In my experience, this process is mostly subconscious, and somehow a good sleep (a good nap or a full nights sleep) seems to help the process; and only the "best ones" percolate up to the conscious part of my mind.

Most call this process intuition, and it's as good a name as any. I do not think there is anything "magical" or unknowable about it, it's just a natural process related to problem solving and situation awareness, that our brains have evolved.

---

Segueing back to the original thread, and the post by the OP:

1. Timed problem-solving tests are not designed to evaluate thinkers. They are designed to yield productive drones who can memorize and apply existing solutions without wasting time.
   
2. Concentrating on a single problem type -- say array operations and algorithms -- is not the best approach to develop your problem solving skills.
   Instead, go for a diverse background. Learn new things, even if they don't seem really relevant. Compare, analyse, consider analogies. Have fun. Use your intuition as another tool you have.
   
3. Understand that social image and actual being/skills are two completely different things.
   Some people are good at projecting an image of being a genius (often simply by being well prepared; not being asked questions they haven't prepared to answer). That does not mean they really are.
   Ignore the person, and look at what they do instead.
   
4. Have fun. Life is too short to dwell on our perceived deficiencies. If you have to, learn to work around your weak spots. But most of all, pick something you find fun, and get good at it: the positive experiences and discoveries are what makes life worth living, in my opinion.

Originally Posted by Nominal Animal

1. Timed problem-solving tests are not designed to evaluate thinkers. They are designed to yield productive drones who can memorize and apply existing solutions without wasting time.

I remember a line from the movie "Jobs" (Not a good movie, but I liked this line ), it went something like "A system can only produce itself". This was where Steve Jobs was explaining why college wouldn't be any help in making him a person who could innovate. The more I think about my own experience, the more true this rings. A school is a place of disseminating knowledge, but it also disseminates a particular system of thought that once ingrained becomes hard to think outside of.