MIT 600 part 3a: Iteration, Successive Approximation and Exhaustive Enumeration

Computer programs calculate answers to all kinds of questions. How do they do it? It may look obvious or very mysterious, depending on whether you have already “entered” the logic of computer programming. Once you are in, it’s hard to even remember what it was like not to understand. But if you are out, it’s not trivial to know where to start from, to “get” programming and the idea that makes it click. You might start with iteration. It may even surprise you to know that the computer program often just tries many different answers until something fits. There are even fancy names for that approach, like exhaustive enumeration. No kidding. And some other names, like, I don’t know, brute force searching. A term which has, strangely enough, gained a sinister reputation in various circles, for whatever reason. Ironically, it’s a legitimate problem solving technique. I’m not being sarcastic.

MIT Open Course Ware’s 600 course (“Introduction…”) has an interesting approach to getting people to get into the mindset of computer programming. It takes you step by step and tries to make sure you don’t take those steps for granted. And talking about steps takes us right back to the concept of iteration. It’s in the nature of the computer to loop. The task of the programmer is to use this tendency to her or his own advantage. For example, we can add controls that get us out of the loops we no longer need. Or we can control how a variable changes and code behaves as the computer loops through the program. But I’m getting too abstract and vague, so let’s go back to technical and concrete.

Now you can either watch the lecture 3 video and/or read the transcripts, or click “Continue reading” to read the rest of this post, or none of the above. I’ll be mentioning flowcharts that let you really see code and its flow, and the method of iterating by hand on a piece of paper pretending you are the computer. Either way, have fun.

So, let’s imagine we want to write a program that finds a square root for a number. How do you go about that? Somebody who is new to computers may think that computers have strange and magical ways of figuring things out, including figuring out the square roots for numbers. Somebody else might just try one number after another until one works. That can, clearly, be optimized. But the idea is, finding answers by successive approximations is not dumb or “brute force”, but has its own place in the world. Especially when you are writing your first computer programs and need to grasp the basic concepts that make a programming language Turing complete. When you need to walk before you can run. I guess. I’m not an expert on algorithms, that’s for sure. One day I’m going to study all the mathematical and historical aspects of various problem solving techniques, but today I am a code apprentice and my job is to learn to code, so let’s stick to that. No running.

Getting into he mindset of computer programming has a lot to do with learning to see computer programs. Actually see, on paper. Paper is useful, don’t underestimate paper. Because putting things on paper lets us see them from above, like from an airplane. And the act of physically writing helps think, clarify and memorize, but that’s a long story. Flowcharts are useful for anyone, but pure gold for beginners. With flowcharts we can actually see iteration, and it becomes that much more intuitive. We can see all sorts of things. And this lecture teaches that too.

Not only does MIT advise the use of flowcharts, they also suggest you might try to simulate code by hand. On a piece of paper. Writing the variables down as they change. Come on, it’s not boring. Please, I know you are all Tron fans, and have a fantasy of being a computer program. Or being a person who can live out the experience of a program. Or whatever. Simulating code by hand can help you fantasize all that, while at the same time doing something useful, since it’s also a valuable tool.

Well, that’s all for now. See you in the next approximation. I mean iteration. Have a nice day. Really.

Advertisements

About apprenticecoder

My blog is about me learning to program, and trying to narrate it in interesting ways. I love to learn and to learn through creativity. For example I like computers, but even more I like to see what computers can do for people. That's why I find web programming and scripting especially exciting. I was born in Split, Croatia, went to college in Bologna, Italy and now live in Milan. I like reading, especially non-fiction (lately). I'd like to read more poetry. I find architecture inspiring. Museums as well. Some more then others. Interfaces. Lifestyle magazines with interesting points of view. Semantic web. Strolls in nature. The sea.
This entry was posted in online courses, tutorials and tagged , , , , , . Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s