Introduction to Algorithms, Programming, and Compilers

Imagine texting a friend directions to your house. If you write “come over,” your friend is stuck. If you write “take the bus to Oak Street, walk two blocks north, and it’s the blue door on the left,” your friend can get there without asking you anything. The second message works because it is a list of clear steps that anyone can follow.

Computers need exactly that kind of message, and then some. A friend can guess what you meant when a step is fuzzy. A computer cannot guess. It does exactly what it is told, step by step, even when the result is silly. In this chapter, we will call this kind of reader a literal follower: someone who carries out every instruction exactly as written and fills in nothing. (It is our name for the idea, not an official term, but it describes a computer perfectly.)

So before anyone writes a line of Java, they need a plan written as clear, ordered steps. That plan has a name. An algorithm is a set of steps, done in order, that gets a job done or solves a problem. A recipe is an algorithm. So are the instructions for assembling a bookshelf, and so is the routine you follow to get ready for school.

Why do the steps have to be so precise? Because the person or machine following them is not allowed to fill gaps. “Add some salt” works for a cook who knows what “some” means. A literal follower does not know, so it might add none, or the whole box.

Now change one thing: the reader. If the same three short steps were given to a seven-year-old, a parent might still need to explain them. If they were given to a robot, the robot would fail at step 1. The more literal the follower, the more precise the algorithm has to be. A computer is the most literal follower there is, which is why programming starts with precise algorithms.

You now know that an algorithm is a list of precise steps. But a list in your head is not useful to anyone else. To share an algorithm, or to check it, you have to write it down. How should you write it?

The two most common ways are words and pictures. Written language means writing each step as a sentence, usually as a numbered list so the order is obvious. A diagram shows the steps as a picture. The kind of diagram used most for algorithms is a flowchart: each step goes in a box, and arrows show which step comes next.

Now vary one thing. Suppose someone draws the flowchart again but the arrow from “Type your username” points straight to “Click Sign in,” skipping the password box. The boxes are all still there, but the arrows describe a different order, and the password is never typed. That is a different algorithm, and a broken one. In a flowchart, the arrows are the order.

In the last question, two of the wrong answers had exactly the right steps. They failed only because the steps were in the wrong order. That is worth a closer look, because it is one of the most important ideas in all of programming.

Why does order deserve a name of its own? Because getting the steps right is not enough; they must happen in the right order.

In plain words: you cannot frost a cake before you bake it. The steps are completed one after another, and each step happens in the situation the earlier steps left behind. Sequencing is the order in which the steps of a process are completed. In a sequence, steps are completed one at a time: the follower finishes one step completely before starting the next.

Change one thing again: swap steps 2 and 3 in the original. You get “put on socks, tie laces, put on shoes.” Step 2 now asks you to tie laces on shoes you are not wearing, so it cannot be completed at all. Some reorderings produce a wrong result; others make a step impossible.

Not every swap matters, though. If an algorithm says “1. Put a fork on the table. 2. Put a spoon on the table,” swapping the two gives the same table. Order matters when a later step depends on what an earlier step did. Part of checking an algorithm is noticing which steps depend on which.

So far every algorithm has been written for a person. But the goal of this course is to have a computer carry out algorithms. A computer cannot read “put on your socks,” and it cannot read an English sentence at all. How do we write an algorithm so that a computer can follow it?

Building on 1.1.1 and 1.1.3: a computer is the ultimate literal follower, and it does steps one at a time, in order. So we need a way of writing steps that is completely precise and has a fixed order.

In plain words: we translate the algorithm into a special language that has strict rules, so that every instruction means exactly one thing. That language is a programming language, and this course uses the programming language Java. An algorithm written in a programming language is a program, and the text of the program that a person writes and reads is called source code, or just code.

Where code is written

Source code is plain text, so it can be written in any text editor, even a basic notes app. In practice, programmers almost always use an integrated development environment, or IDE. An IDE is one application that lets you type your code, check and translate it, and start it running, without switching between programs. It colors different parts of the code so they are easier to read, points out some mistakes as you type, and has a button to run your program. You will learn what “compile” means in 1.1.5.

public class Greeting
{
    public static void main(String[] args)
    {
        System.out.println("Good morning!");
        System.out.println("Welcome to AP CSA.");
    }
}

Good morning!
Welcome to AP CSA.

Now change one thing: the order of the statements. This version has the same greeting lines plus one more, with the first two swapped:

public class GreetingReordered
{
    public static void main(String[] args)
    {
        System.out.println("Welcome to AP CSA.");
        System.out.println("Good morning!");
        System.out.println("Let us begin.");
    }
}

Because statements run in sequence, the output follows the new order exactly:

Welcome to AP CSA.
Good morning!
Let us begin.

This is the same sequencing idea from 1.1.3, now in Java. The computer does not rearrange your statements into an order that makes more sense; it runs them in exactly the order you wrote them.

public class LunchRoutine
{
    public static void main(String[] args)
    {
        System.out.println("Wash your hands.");
        System.out.println("Unpack your lunch.");
        System.out.println("Eat.");
        System.out.println("Unpack your lunch.");
        System.out.println("Clean up.");
    }
}

Wash your hands.
Unpack your lunch.
Eat.
Unpack your lunch.
Clean up.

There is a gap between the code you type and what the computer can actually do. The computer’s processor does not understand words like System.out.println. Something has to check your Java and translate it into a form the computer can run. And because the computer is a literal follower, it would be good if something caught certain mistakes before the program starts running and doing the wrong thing.

In plain words: before your program runs, a checker reads the whole program, makes sure it follows the language’s rules, and, if it does, translates it into instructions the computer can carry out. If the checker finds a broken rule, it refuses to translate and tells you what is wrong. That checker is called the compiler. Running the compiler on your code is called compiling. Carrying out the translated instructions is called running (or executing) the program.

So every Java program goes through two separate stages, always in this order:

Here is the rule that matters most: errors the compiler detects must be fixed before the program can run. If the compiler finds even one, there is no translated program, so there is nothing to run. Notice the word some in the table: the compiler catches some kinds of mistakes, not all of them. You will meet the kinds it misses in 1.1.7 and 1.1.8.

public class MissingSemicolon
{
    public static void main(String[] args)
    {
        System.out.println("Good morning!")
        System.out.println("Welcome to AP CSA.");
    }
}

MissingSemicolon.java:5: error: ';' expected
        System.out.println("Good morning!")
                                           ^
1 error

You have seen the compiler refuse to run a program with a missing semicolon. That kind of mistake is so common that it has its own name, and learning to read the compiler’s messages about it will save you a lot of time.

In plain words: every language has grammar rules. In English, “the dog ran” follows the rules and “dog the ran” does not. Java’s rules are much stricter than English’s, and the computer allows no exceptions. The rules for how code must be written are called the language’s syntax. A syntax error is code that breaks the language’s rules, like a sentence with broken grammar. Syntax errors are detected by the compiler, which is why a syntax error stops a program from running.

Here are some common syntax errors and the message the compiler gives for each:

Java is case-sensitive: uppercase and lowercase letters are different, so system and System are two different words to Java.

public class UnclosedQuote
{
    public static void main(String[] args)
    {
        System.out.println("Good morning!);
        System.out.println("Welcome to AP CSA.");
    }
}

UnclosedQuote.java:5: error: unclosed string literal
        System.out.println("Good morning!);
                           ^

Change one thing: put two mistakes in the program instead of one.

public class TwoMistakes
{
    public static void main(String[] args)
    {
        system.out.println("Good morning!");
        System.out.printn("Welcome to AP CSA.");
    }
}

TwoMistakes.java:5: error: package system does not exist
TwoMistakes.java:6: error: cannot find symbol
2 errors

Line 5 uses a lowercase s. Java is case-sensitive, so system is not the same word as System, and Java does not know what system is. Line 6 misspells println as printn, and “cannot find symbol” means Java looked for something with that name and found nothing. The compiler listed both errors this time, and the program will not run until both are fixed. (The real messages include more lines showing the code and a caret; only the first line of each is shown here.)

public class PracticeQuote
{
    public static void main(String[] args)
    {
        System.out.println("Practice makes progress.");
        System.out.printline("Mistakes help you learn.");
    }
}

System.out.println("Mistakes help you learn.");

The compiler is helpful, but it only checks whether code follows Java’s rules. It has no idea what you wanted the program to do. So what happens when the code follows every rule but does the wrong thing?

Building on 1.1.3 and 1.1.5: the compiler checks for some errors, and statements run in sequence, one at a time, in the order written.

In plain words: you can write a perfectly grammatical sentence that gives the wrong directions. “Turn right at the light” is good English, but if you should have turned left, your friend still gets lost. A logic error is a mistake in the plan or the code that makes the program do the wrong thing, or something you did not expect. The program compiles and runs to the end, but its result is wrong. The compiler cannot detect logic errors, because the code follows every rule.

So how are logic errors found? By testing: running the program with specific data and checking whether it produces the expected outcome. You decide in advance what the correct result should be, run the program, and compare. If the actual result differs from the expected result, there is a logic error.

public class SandwichSteps
{
    public static void main(String[] args)
    {
        System.out.println("1. Put the top slice of bread on the sandwich.");
        System.out.println("2. Spread peanut butter on one slice.");
        System.out.println("3. Take out two slices of bread.");
    }
}

1. Put the top slice of bread on the sandwich.
2. Spread peanut butter on one slice.
3. Take out two slices of bread.

public class SandwichStepsFixed
{
    public static void main(String[] args)
    {
        System.out.println("1. Take out two slices of bread.");
        System.out.println("2. Spread peanut butter on one slice.");
        System.out.println("3. Put the top slice of bread on the sandwich.");
    }
}

1. Take out two slices of bread.
2. Spread peanut butter on one slice.
3. Put the top slice of bread on the sandwich.

Look back at the lunch program from Question 7. It compiled and ran, displaying “Unpack your lunch.” after “Eat.” If the expected outcome was a sensible lunch routine, that second “Unpack your lunch.” is a logic error, and only comparing the output with what you expected reveals it.

There is one more way for a program to go wrong. Some code follows every rule, so it compiles, and it might even be the right plan, but when it actually runs, it asks the computer to do something impossible. Think of a recipe that says “divide the cookies evenly among the guests” on a day when no guests show up. The instruction was fine on paper; it fails only at the moment it is carried out.

Building on 1.1.5 and 1.1.3: compiling happens before running, the compiler checks for some errors, and statements run one at a time, in order.

In plain words: the program starts running normally, reaches a step it cannot possibly complete, and stops right there, without finishing the rest.

A run-time error is a problem that shows up while the program is running, not before. It usually makes the program terminate abnormally: it stops before reaching its end. An exception is one kind of run-time error: something goes wrong that the compiler did not catch, and Java interrupts the normal flow of the program, so the statements after it in the sequence do not run. When this happens, programmers say the program threw an exception.

To see a run-time error, we need code that compiles but asks for something impossible. Dividing by zero is impossible in math, and in Java the symbol / means divide, as on a calculator. (Arithmetic in Java is taught fully in Topic 1.3; here you only need to know that 10 / 0 asks Java to divide 10 by 0.) The compiler checks that 10 / 0 is written by the rules, and it is, so the compiler does not complain.

public class Snack
{
    public static void main(String[] args)
    {
        System.out.println("Sharing 10 crackers among 0 friends...");
        System.out.println(10 / 0);
        System.out.println("Enjoy your snack!");
    }
}

Sharing 10 crackers among 0 friends...
Exception in thread "main" java.lang.ArithmeticException: / by zero
	at Snack.main(Snack.java:6)

Now change one thing: move the impossible step to the top.

public class SnackFirst
{
    public static void main(String[] args)
    {
        System.out.println(10 / 0);
        System.out.println("Sharing 10 crackers among 0 friends...");
        System.out.println("Enjoy your snack!");
    }
}

This version also compiles. But the division is now the first statement, so the exception happens before anything is displayed. The console shows only:

Exception in thread "main" java.lang.ArithmeticException: / by zero
	at SnackFirst.main(SnackFirst.java:5)

Both versions compile, and both terminate abnormally. What changes is how much of the sequence finishes before the interruption, and that depends only on where the impossible step sits in the order.

Here are all three kinds of errors side by side:

public class SnackLast
{
    public static void main(String[] args)
    {
        System.out.println("Sharing 10 crackers among 0 friends...");
        System.out.println("Enjoy your snack!");
        System.out.println(10 / 0);
    }
}

Sharing 10 crackers among 0 friends...
Enjoy your snack!
Exception in thread "main" java.lang.ArithmeticException: / by zero

Jordan is writing a program that displays a short study plan. Here is Jordan’s first attempt, followed by everything that happens as Jordan fixes it. Read each stage and connect it to the subsection that explains it.

The algorithm (1.1.1 to 1.1.3). Jordan’s plan, in written language: 1. Review notes. 2. Do practice problems. 3. Check answers. Each step is clear, and the order matters: checking answers before doing the problems would make no sense.

Attempt 1: a syntax error (1.1.5, 1.1.6). Jordan types:

System.out.println("1. Review notes.")
System.out.println("2. Do practice problems.");
System.out.println("3. Check answers.");

The first statement is missing its semicolon. The compiler reports ';' expected and stops. Nothing is displayed, not even the correct lines, because the program never runs.

Attempt 2: a logic error (1.1.7). Jordan adds the semicolon but, while editing, swaps two statements:

System.out.println("1. Review notes.");
System.out.println("3. Check answers.");
System.out.println("2. Do practice problems.");

It compiles and runs to the end, displaying the lines in that order. Jordan’s expected outcome was steps 1, 2, 3. The actual output does not match, so testing reveals a logic error in the sequence. Swapping the last two statements back fixes it.

Attempt 3: a run-time error (1.1.8). Jordan adds a line intended to show minutes per problem, dividing 60 minutes by the number of problems, but types 0 as a placeholder:

System.out.println("1. Review notes.");
System.out.println("2. Do practice problems.");
System.out.println(60 / 0);
System.out.println("3. Check answers.");

It compiles, because the code follows every rule. When it runs, the first two lines are displayed, then 60 / 0 throws an ArithmeticException and the program terminates abnormally. “3. Check answers.” is never displayed.

Three different mistakes, found at three different moments: before running, after running, and during running.

• An algorithm is a set of ordered steps that gets a job done. Its steps must be precise, because a computer is a literal follower, and they can be written as numbered steps or drawn as a flowchart.
• Sequencing matters: steps are completed one at a time, in order, so the same steps in a different order can give a different result. Java statements run the same way, top to bottom.
• Code can be written in any text editor; an IDE lets you type, compile, and run it in one place. The compiler checks code before it runs, and any error it finds must be fixed before anything runs.
• A syntax error breaks Java’s rules and is caught by the compiler. A logic error runs to the end with a wrong result and is found by testing against the expected outcome.
• A run-time error happens while the program runs and stops it early; an exception is a run-time error the compiler did not catch.

public class Morning
{
    public static void main(String[] args)
    {
        System.out.println("Wake up.");
        System.out.println("Eat breakfast.");
        System.out.println("Brush teeth.");
        System.out.println("Eat breakfast.");
    }
}

Wake up.
Eat breakfast.
Brush teeth.
Eat breakfast.

public class Cheer
{
    public static void main(String[] args)
    {
        System.out.println("Go team!")
        System.out.println("We can do it!);
    }
}

System.out.println("Go team!");
System.out.println("We can do it!");

public class Countdown
{
    public static void main(String[] args)
    {
        System.out.println("3");
        System.out.println("2");
        System.out.println(1 / 0);
        System.out.println("Liftoff!");
    }
}

3
2
Exception in thread "main" java.lang.ArithmeticException: / by zero

Check each statement. If the answer is “not yet,” reread the linked subsection.

• I can explain what an algorithm is and why its steps must be precise. Reread
• I can show the same algorithm as numbered steps and as a flowchart. Reread
• I can explain why changing the order of steps can change the result. Reread
• I can explain what a text editor and an IDE are used for. Reread
• I can explain why a compiler error means no part of the program runs. Reread
• I can read a compiler message and find the syntax error it describes. Reread
• I can explain how testing with expected outcomes finds logic errors. Reread
• I can tell a run-time error (exception) apart from syntax and logic errors. Reread