Introduction to Algorithms, Programming, and Compilers: Study Guide (Computer Science A 1.1)

An algorithm is a plan you can follow one step at a time

Every program you will write in this course starts as an idea about how to get something done. That idea, written as an ordered set of steps, is an algorithm. You already use algorithms every day. A recipe is one. So are the directions you give a friend to your house, or the steps for borrowing a library book.

An algorithm can be written in everyday language, as a numbered list, or drawn as a diagram of boxes and arrows. The form does not matter. What matters is that anyone (or any machine) who follows the steps exactly gets the intended outcome.

Here is an algorithm for a small task, working out how much change a customer should get when they pay with a 20-unit note:

1. Read the price of the item.
2. Subtract the price from 20.
3. Display the result as the change.

The three steps happen one at a time, in this order. This idea is called sequencing: a sequence defines the order in which steps are completed, and the machine does not start step 3 until step 2 is finished. Sequencing is the first of three building blocks of algorithms. You will meet the other two, selection (making a decision) and iteration (repeating), in Unit 2. For the whole of Unit 1, a program is just a sequence of statements run from top to bottom, with the occasional detour into a method.

Why does order matter? Imagine swapping steps 2 and 3. “Display the result” before the result has been calculated would show nothing useful. Order also matters when two steps use the same storage, as in the worked example later in this guide.

From idea to running program

Writing the steps in English is not enough for a computer. The algorithm must be turned into a program in a programming language, here Java. The path from your keyboard to a running program has a fixed order.

• You can write code in any text editor, but most programmers use an integrated development environment (IDE). An IDE puts an editor, a compiler and a way to run the program in one place, and it provides tools to write, compile and run code.
• The compiler translates your source code into a form the machine can run, and on the way it checks the code for some errors. If the compiler finds an error it reports it, and the program cannot be run until the error is fixed.
• Once the code compiles, you run it. Statements execute one at a time in order. Problems that appear now are discovered during execution.

Here is the smallest complete Java program you need for now. It has a class with a main method, which is where execution begins:

public class Greeting {
    public static void main(String[] args) {
        System.out.println("Plan first, then code.");
        System.out.println("Test with chosen data.");
    }
}

Plan first, then code.
Test with chosen data.

The first println statement runs first and its text appears first. If you swapped the two lines, the output would appear in the swapped order. That is sequencing in action.

Three families of error

Programmers make mistakes, and the course expects you to tell the kinds apart by when and how they show up.

Error kind	What it is	When and how it is found	Example
Syntax error	A mistake where the rules of the language are not followed	By the compiler, before the program can run	Missing semicolon; putting a text value in an int variable
Logic error	A mistake in the algorithm or program that makes it behave incorrectly or unexpectedly	By testing the program with specific data and checking the result against what you expected	Calculating an average with the wrong bracketing
Run-time error	A mistake that occurs while the program is executing, usually making it terminate abnormally	When the program runs; an error message appears and execution stops	Dividing an int by zero

An exception is a particular kind of run-time error. It occurs because of an unexpected problem that the compiler did not detect, and it interrupts the normal flow of the program’s execution. Dividing an integer by zero causes an ArithmeticException, which you will see below.

Seeing each kind

A syntax error. The compiler stops at the missing semicolon and refuses to produce a runnable program:

public class A {
    public static void main(String[] args) {
        int score1 = 80
        System.out.println(score1);
    }
}

A.java:3: error: ';' expected
        int score1 = 80
                       ^
1 error

A mismatch between what a variable holds and what you give it is also a rule breach caught at compile time. Writing int count = "five"; produces incompatible types: String cannot be converted to int.

A run-time error. This compiles, because dividing two ints is allowed by the rules of the language. The problem only appears when the division is executed:

public class C {
    public static void main(String[] args) {
        int total = 90;
        int students = 0;
        System.out.println("Average: " + total / students);
        System.out.println("Done");
    }
}

Running it prints no average. Execution stops at line 5 with Exception in thread "main" java.lang.ArithmeticException: / by zero, and the line that prints Done never runs.

A logic error. This compiles and runs to the end, so nothing complains. The answer is simply wrong:

public class D {
    public static void main(String[] args) {
        int a = 70;
        int b = 90;
        System.out.println("Average: " + (a + b / 2));
        System.out.println("Average: " + (a + b) / 2);
    }
}

Average: 115
Average: 80

The first line is the logic error: division happens before addition, so it works out 70 + 45. The second, with brackets around the sum, gives the average of 70 and 90. Only someone who knew the expected answer, 80, would spot the fault. This is why you test with specific data: pick inputs where you already know the right answer.

Worked example 1: Sequencing and swapping two values

Task. Two cups hold different drinks: cup A holds juice and cup B holds milk. Write an algorithm to swap the contents, then express it as a Java program that swaps two numbers.

Step 1, think about the real task. You cannot pour juice straight into cup B, because B is already full of milk. You need a spare empty cup, cup T (for temporary). A correct sequence is:

1. Pour A (juice) into T.
2. Pour B (milk) into A.
3. Pour T (juice) into B.

Step 2, check the order. Suppose steps 1 and 2 were swapped: pour B into A first. Cup A already holds juice, so the milk and juice mix, and the original juice cannot be recovered. The order is not cosmetic; it decides whether the algorithm works.

Step 3, translate to Java. A variable stores a value. The spare cup becomes a third variable. Trace each statement in order. You will study declarations in Topic 1.2 and assignment in Topic 1.4; here, read int temp = a; as “make a new int box called temp and copy the value in a into it”.

public class Swap {
    public static void main(String[] args) {
        int a = 8;
        int b = 3;
        int temp = a;
        a = b;
        b = temp;
        System.out.println("a = " + a + ", b = " + b);
    }
}

a = 3, b = 8

Step 4, trace it. A trace table records the value of each variable after each statement. A dash means the variable does not exist yet.

After statement	a	b	temp
int a = 8;	8	-	-
int b = 3;	8	3	-
int temp = a;	8	3	8
a = b;	3	3	8
b = temp;	3	8	8

Step 5, check the result. The values have swapped: a is now 3 and b is 8. If you had written a = b; first, before saving a in temp, the 8 would have been overwritten and lost, exactly as with the mixed drinks.

Worked example 2: Classify the faults in a program

Task. A student writes a program meant to display the average of three test scores, 70, 80 and 90, whose correct answer is 80. Three versions of the program each contain one fault. For each, state the kind of error, say how it is detected, and correct it.

Version 1. The relevant lines are:

int sum = 70 + 80 + 90;
System.out.println("Average: " + sum / 3;

The closing bracket of println( is missing. That breaks the grammar of the language, so this is a syntax error. The compiler detects it, with an error message that points to the line, and the program will not run. Fix: System.out.println("Average: " + sum / 3);.

Version 2. The relevant lines are:

int sum = 70 + 80 + 90;
System.out.println("Average: " + sum / 2);

This compiles and runs without any complaint, and prints Average: 120. The divisor 2 should be 3, because there are three scores. This is a logic error. No tool reports it. It is found by testing: you know that the average of 70, 80 and 90 must be 80, and 120 is not. Fix: divide by 3.

Version 3. The relevant lines are:

int sum = 70 + 80 + 90;
int count = 0;
System.out.println("Average: " + sum / count);

This compiles. When it runs, the division by zero stops the program with an ArithmeticException and no average is printed. This is a run-time error, and the exception is the type of run-time error that interrupts normal execution. Fix: set count to 3.

Summary of the method. First ask whether the program can be compiled. If not, it is a syntax error. If it runs and stops with a message, it is a run-time error. If it runs to the end with a wrong result, it is a logic error.

Common misconceptions

• “If it compiles, it is correct.” Compiling means only that the rules of the language are satisfied. A program can compile and still compute the wrong thing (Version 2 above).
• “The compiler finds all errors.” It finds some of them. Logic errors and some run-time errors are invisible to it.
• “A syntax error and a run-time error are the same because both show red text.” The difference is timing. A syntax error is reported before the program starts. A run-time error appears while it is running, often after some output has already been produced.
• “Statements run in whatever order makes sense to me.” They run one at a time, top to bottom, unless a method call or (later) a decision or a loop sends control elsewhere. Moving a line changes the meaning.
• “An algorithm is code.” An algorithm is a plan; code is one way of expressing it. The same algorithm can be written in words, in a diagram or in different programming languages.
• “An exception is something only advanced programmers meet.” Exceptions are a normal kind of run-time error; the course names ArithmeticException (dividing an int by zero) and later others.

Where this leads

Next, practise on the Topic 1.1 practice questions and use the revision notes when you are short of time. Then tick off the checklist. The next topic, 1.2 Variables and Data Types, explains the boxes that held a, b and temp in the swap program: what a data type is and how a variable stores a value.