In the Chapter 1 Introduction we briefly described algorithms as something like a recipe or directions to a friend’s house: a specific set of steps to perform for achieving some result. But the features of Java we’ve learned so far aren’t really sufficient to create algorithms in Java. The most complex code we’ve written so far has only involved code that proceeds in an essentially straight line. We may use methods to break up the code but each method runs from top to bottom and if we wanted we could get rid of all the methods but one and—at the cost of some duplication—put all the code in one sequence in that one method.
One of the most important, and perhaps surprising, facts about computers is that we only need a three pretty simple building blocks to be able to create code that implements any algorithm that can be run on any computer. The three building blocks of algorithms are sequencing, selection, and repetition each of which control how our program executes.
Sequencing is the simplest of the three building blocks. In fact we’ve been using all this time without even mentioning it. It just means running one step of an algorithm after after another in the order they are written. That is the default control flow in Java and most other programming languages where a step roughly corresponds to a line of code. It may seem trivial but it is important. Consider this simple bit of code, assuming x and y have already been declared somewhere.
x = 10;
y = x + 20;
x = 30;
System.out.println("x: " + x + "; y: " + y);
It’s only because of sequencing that we can know that that program will print "x: 30; y: 30". If we didn’t know that the lines would run in order maybe the assignment to y would happen after x was set to 30 rather than before. Or maybe the println would run before either variable had been given a value! But the default control flow of sequencing one thing after another lets us understand what is going to happen when.
Selection—sometimes called branching control flow—is when some code either runs or doesn’t. We “select” whether to run it—based on some other values. For instance, an algorithm for assigning grades might contain a line to set a student’s grade to an A but will only run that line if the student’s average score is greater than 90%.
As we’ll see there are all kinds of ways to make complicated selections but ultimately they all boil down to some combination of a simple selection based on some condition being either true or false. Either the student’s average score is greater than 90% and they get an A or it’s not and they don’t.
Selections are made based on a true or false decision. Look for the word "if" to identify selections.
Morning routine:
1. Wake up.2. Snooze for 5 more minutes.3. Check your phone and the weather4. If there is a text from your friend, answer it.5. Brush teeth and shower.6. If it’s cold, wear a sweater.7. Check if you have homework due. If so, pack it in your bag.8. Put on your sunglasses if it’s sunny.9. Leave for school or work.
Finally, the third building block, repetition—also called looping control flow or iteration—is when some code is run repeatedly. Usually it is combined with selection to repeatedly run some code until a desired outcome is reached. In Java repetition is achieved through a couple flavors of loops that build in the selection. We’ll discuss loops in the next unit.
And thats it! Any algorithm that any computer can execute can be built out of some combination of those three building blocks plus the ability to store and retrieve values (i.e. variables).
Repetition is when a process repeats itself until a desired outcome is reached. Look for the word "repeat" or "all" or "keep" to identify repetition.
Morning routine 2:
1. Wake up.2. Snooze for 5 more minutes.Keep waking up and snoozing for the next 15 minutes3. Answer all new texts from your friends.4. Brush teeth and shower.5. If it’s cold, wear a sweater.6. For each of your classes where you have homework due, pack it in your bag.8. Leave for school or work.
Although we can build any algorithm with some combination of just three simple building blocks, as is often the case with programming, when we are building complex things out of simple parts it can be hard to keep track of how everything fits together. Indeed, arguably the whole task of learning to program is really about learning to manage that complexity.
When we are trying to design and implement even slightly complicated algorithms, For complex problems, it can be useful to make a plan before we start writing code. Two common ways of describing algorithms that programmers will use before trying to write actual code are pseudocode and flowcharts.
Pseudocode is a simplified, informal way of describing the steps in an algorithm in a language that’s part way between a human language like English and an actual programming language like Java. As long as we have some way of describing sequences, selection, and repetition we can describe an algorithm.
Flowcharts do the same thing but graphically, representing the steps in an algorithm in a diagram like the one below. Sequences of code are typically represented with a rectangle labeled with a description of what happens inside that box. Decisions points in selections are usually represented as a diamond with a yes/no question in it and arrows coming out labeled “yes” and “no” or “true” and “false”. And repetition is created by arrows that create loops in the diagram.
Once we have an algorithm described in pseudocode or a flowchart, we can then use it as a guide to implementing the algorithm, translating the sequences, selections, and repetitions into actual Java code using the constructs we’ll learn about in the rest of this unit and the next.
The top box below contains a scrambled pseudocode description of an algorithm for buying a birthday gift for your friend with the goal of buying as the most expensive gifts possible given a certain amount of money.
Put the steps into the correct order by dragging them into the lower box. The indented steps are intended to go inside another construct such as the repetition.
Initialize *total* amount of money.
---
Repeat while still money in *total*:
---
If total more than $25, buy a gift card and subtract 25 from total.
---
If total more than $10, buy a small cake and subtract 10 from total.
---
If total more than $5, buy some candy and subtract 5 from total.
---
If total more than $1, buy a card and subtract 1 from total.
---
Otherwise, give them the change.
In this group activity, you will work together to create an algorithm for a common problem: choosing a snack! Create pseudocode for this problem. Make sure you include selection and repetition in your algorithm. For example, if there is no chocolate, you may want to keep searching for another snack. If you’re thirsty, you may want to consider the drinks in the fridge. You may want to consider every item in the fridge or your leftover halloween candy stash before deciding on the perfect snack. Be creative!
