Chapter 1 - An Introduction to Problem-Solving¶
Computer Programming¶
This is a course in problem-solving using a computer. Writing down a set of steps or instructions to make a computer perform some task for you is called programming. We’ll see that there are two parts to this process:
- figure out what the steps are in solving the problem, and then
- write them down in such a way that a computer can interpret and carry them out.
You might be concerned about the second part. How do you talk to a computer? But that turns out to be relatively easy. We just need a programming language that our computer can interpret. In this course, we will be using a language called Python. Python is a good choice because it is very simple to start using. (However, keep in mind that this is not an in-depth course in Python; we will really only be using a small fraction of the features of the language.)
We will soon discover that the first part (figuring out exactly what steps are involved in solving a problem) is actually much harder than writing instructions in a programming language. Here we will need a pencil and paper and some clear thinking.
It isn’t that solving problems is difficult. In fact, it is precisely the opposite: people are so good at solving problems, most of the time we’re not aware of how we’re doing it! For example, think about some of the things you do every day that involve some kind of problem-solving strategy:
- Making a peanut butter and jelly sandwich
- Finding a parking spot
- Arranging a time for three friends to meet
- Getting a good deal on a phone
- Driving across town
Now, suppose you had to spell out all the steps and little decisions you had to make in order to do one of these tasks. For example, what’s really involved in making a peanut-butter-and-jelly sandwich?
Is there bread? Check if the bread is moldy. Find the peanut butter. Remove the lid. If the jar is empty, find another jar. Remove the lid and then the seal from the jar. Find a knife. If there are no knives in the drawer, get a dirty one from the sink and wash it. Use the knife to spread peanut butter on one piece of bread.
And so on.
Programming a computer is a bit like this. You really have to spell out every step of the process, because computers can only perform very simple steps.
Example: Find the Biggest Number in a List¶
Of course, without some fancy robotic arms we certainly aren’t going to program a computer to make sandwiches for us. But here’s a much more straightforward example we can think about. Suppose you have a list of numbers, like this for example:
43 17 85 32 86 79 18
What’s the biggest number in the list? Pretty easy, right? You can just spot the biggest one without even thinking. But what if you had a longer list, maybe like this:
47 26 20 4 60 70 8 24 33 58 20 83 53 95 37 67 85 93 83 49 79 83 61 79 48 28 97 77 89 45 43 41 44 47 31 71 52 22 62 2 82 92 50 1 58 5 26 64 87 82 18 45 11 31 35 59 78 96 91 14 3 65 14 15 94 4 31 41 16 11 43 9 87 1 94 80 2 24 5 21 60 10 97 80 69 61 65 16 89 17 68 77 3 36 50 48 81 6
Well, you might have to be a bit more systematic. Go ahead and find the biggest number, and then ask yourself how you did it.
- Most of us end up doing something like this:
- Look at the first number, and remember it (that’s our maximum so far)
- Read through the rows from left to right
- If we’ve run out of numbers, then we’re done.
- Otherwise, look at the next number and compare it to the maximum we remembered
- If the new number is bigger, then remember that one instead
- Go back to step 3
The sequence of instructions above gives us a strategy, also called an algorithm, for solving the problem of finding the biggest number in a list. It is a bit more wordy than just saying “find the biggest number in the list”. But that’s how it works: you have to literally write down every step.
How do you know when the steps are clear enough? One way to think about how a computer works is that it’s like talking to a kid, say, a reasonably bright fourth-grader. She can read and do fractions and follow directions, but she doesn’t necessarily have any life experience and doesn’t have the “big picture” of what you are trying to accomplish. If you can write down your instructions clearly enough so that a reasonably bright fourth-grader can carry them out, then chances are you’ll be able to program them for a computer too.
One thing to think about here is: what does it mean to “remember” a value, as in step 4 of our strategy above? In programming we need some way to store values and recall them later. We use variables for this purpose. In programming, a variable is a bit like the variables you’ve seen in math books, for example, if someone writes:
x = 42
y = 2x + 1
you would probably agree that y is now 85. There’s just one important difference between variables in math books and variables in programming. In programming, the value of a variable can change as the steps are executed. A variable works just like the ‘memory’ key on a pocket calculator.
One way to think of a variable is that it is like a page on the clipboard our fourth-grader is holding. She can write down a number, and look it up later, but she can also cross it out and write a new number if you ask her to.
We described our strategy for finding the biggest number as a sequence of written instructions. There is a pictorial way to describe the strategy that will be useful to us, called a flowchart. Sometimes a flowchart is more clear than a sequence of written instructions. You can trace through the steps by following the arrows with your finger. In the flowchart, we’re assuming we have a variable called “max” in which we always store the largest value we’ve seen so far. Each time we find a larger value, we have to update the variable “max.”
To make sense out of the “flowchart” picture, lets just try it for a simple list like this:
17 4 137 42
Start out with max equal to 17.
Are there more numbers?
Yes, the next one is 4.
Is 4 bigger than 17?
No, so do nothing.
Follow the arrow back to the top.
Are there more numbers?
Yes, the next one is 137.
Is 137 bigger than 17?
Yes, so change the value of max to 137
Follow the arrow back to the top.
Are there more numbers?
Yes, the next one is 42.
Is 42 bigger than 137 ?
No, so do nothing.
Follow the arrow back to the top.
Are there more numbers?
No, so the result is the value of max, or 137.
Before we break for today let’s take a step back and look at the big picture. What are the ingredients that went into the strategy we described above?
Basic Ingredients of Computation¶
- store a value so we can remember it later
- do basic arithmetic (like comparing two numbers)
- check a condition and do something or not, depending on whether the condition is true
- repeat some action, continuing as long as some condition is true
- get input or produce output (in order to read the list and report the result)
The surprising thing is that those five ingredients are enough to any computation. In fact, that is all that any computer ever does!
So you can see that the difficulty is programming a computer isn’t that computers are “smart” or “complicated”. The difficulty is that they’re so incredibly stupid that we have spell everything out in detail! The challenge in learning to program is that we have to take our wonderful human problem-solving skills and slow ourselves down enough to analyze how we’re solving a problem, so we can describe the process in simple steps.
Another thing people are really good at is language. You can say all kinds of completely ambiguous things, you can use double meanings or make puns, and other people will usually know what you’re talking about. (“Hey, bring me that thing on the table.” “Fruit flies like a banana.” “Your teeth are like stars; they come out at night.”) You can misspel wurds and leave out punctuation, or, put, in, too, many, commas, and people will still be able to read your writing.
With a computer, it is just the opposite. To talk to a computer you have to use a special computer language and you have to get every detail of the grammar and punctuation and spelling just right, and you can’t have any ambiguity whatsoever.