Introduction to algorithms, programming, and compilers
A computer does exactly what it is told, one instruction at a time, and nothing else.
Programming is the job of writing those instructions so precisely that a machine with no common sense still gets the right answer.
Before any Java, this section sets out the three ideas everything else rests on: an algorithm (the plan), sequencing (the order of the steps), and the trip your code takes from a file you type to a program that runs, including the three kinds of error that can stop it.
On the exam, these ideas are tested in the multiple-choice section (naming the type of an error, saying when it is detected, putting steps in order), and every free-response question is an algorithm you design and then write in Java.
Algorithms and sequencing
An algorithm is a step-by-step process for completing a task or solving a problem.
You follow algorithms all day without calling them that.
Here is one for adding money to a transit card at a station kiosk, written in plain language:
- Step 1: Tap the card on the reader.
- Step 2: Read the current balance from the card.
- Step 3: Choose the amount to add.
- Step 4: Pay for that amount.
- Step 5: Work out the new balance as the current balance plus the amount added.
- Step 6: Write the new balance to the card and show it on the screen.
Two things make this an algorithm and not just a list of tips.
Each step is definite (there is no "add a reasonable amount"), and the steps happen in a fixed order.
That order is sequencing: steps are completed one at a time, each one finishing before the next one starts.
Swap Step 5 and Step 2 and the kiosk computes a new balance from a balance it has not read yet.
The steps are all still there, but the algorithm is wrong.
An algorithm can be written in words, as above, or drawn as a diagram.
A flowchart draws each step as a box and joins the boxes with arrows in the order they happen.
In this unit every algorithm is a straight line of steps; in Unit 2 the arrows start to branch (selection) and loop back (iteration).
Java code is an algorithm written in a language the computer can follow.
The statements in a block run from top to bottom, one at a time, exactly like the numbered steps.
Here is Step 5 and Step 6 of the kiosk in Java (every piece of this syntax is taught in the next few sections; for now, read it as instructions):
int balance = 12;
int reload = 20;
balance = balance + reload;
System.out.println("New balance: " + balance);
New balance: 32
Move the println line above the line that adds reload, and the program prints New balance: 12.
Nothing in the language stops you; the order of statements is part of the algorithm, and getting it wrong is your mistake to find.
Writing, compiling and running a program
You can type Java in any text editor, but most programmers use an integrated development environment (IDE): one program that lets you write the code, compile it and run it, with tools such as color-coded keywords, error markers and a button that runs your program.
A computer's processor cannot follow Java directly.
The compiler (for Java, a program called javac) reads your whole source file first and translates it into a lower-level form called bytecode.
Only if the translation succeeds is there anything to run; the Java Virtual Machine then runs the bytecode one instruction at a time.
The diagram below shows the trip and where each kind of error is caught.
While it translates, the compiler checks your code against the rules of the language.
It can find some errors, and those errors must be fixed before the program can be run at all.
It cannot find every error, because it only checks whether your code is legal Java, not whether it does what you meant.
Why it works (not examined). Java compiles to bytecode, not to the instructions of one particular processor, so the same .class file runs on any computer with a Java Virtual Machine: a school laptop, a phone or a server.
That is why the exam can ask you about code without caring what machine it runs on.
Three kinds of error
Every bug you will ever meet in this course falls into one of three groups, and the exam expects you to name which.
Syntax errors. A syntax error breaks a rule of the language: a missing semicolon, a misspelled keyword, a quotation mark that is never closed, a value of the wrong type stored in a variable.
The compiler finds these, reports the line, and refuses to produce a program.
int seats = 40
System.out.println(seats);
The compiler reports ';' expected at the end of the first line.
Nothing runs, not even the lines that were fine.
A second example: storing text in a variable declared to hold a whole number breaks Java's type rules, and the compiler stops with "incompatible types".
int seats = "forty";
Logic errors. A logic error is a mistake in the algorithm or the program that makes it behave incorrectly or unexpectedly.
The program compiles and runs to the end; it just gives the wrong answer.
The compiler cannot help, because the code is perfectly legal.
The only way to find a logic error is to test the program with specific data whose correct result you already know, and compare.
int quiz1 = 80;
int quiz2 = 90;
double average = quiz1 + quiz2 / 2;
System.out.println(average);
125.0
The average of 80 and 90 is 85, so a test with these values exposes the bug: Java divides before it adds (you will see why in the section on arithmetic), so the code computes 80 + 45.
The fix is to group the sum and to divide by a double so the half is kept: (quiz1 + quiz2) / 2.0, which prints 85.0.
Run-time errors. A run-time error happens while the program is running.
The code compiled, but when the computer reaches a certain statement with certain values, it cannot carry it out, and the program typically stops abnormally.
In Java most run-time errors are exceptions: an exception is a run-time error caused by something unexpected that the compiler did not detect, and it interrupts the normal flow of the program.
Dividing an int by the int zero is the first one you meet.
int riders = 0;
int fare = 60;
System.out.println("Start");
System.out.println(fare / riders);
System.out.println("End");
Start
Start prints, because the first statements run normally.
When the division is reached with riders equal to 0, Java throws an ArithmeticException: the program stops and reports java.lang.ArithmeticException: / by zero with the line where it happened, and End is never printed.
The compiler could not have caught this: riders might have held any value, and the code is legal.
Later units add more exceptions with the same behavior: asking for a position past the end of a String, an array or a list throws an exception and stops the program.
It never quietly hands back an empty value or null.
Answers that earn the "no bounds errors" points never rely on an out-of-range access being harmless.
- The free-response section has four questions worth 7, 7, 5 and 6 points (25 in all), and each multiple-choice question is worth 1 point.
- Every free-response point is scored 0 or 1, and each is earned on its own: a mistake in one place does not stop you earning points elsewhere.
- Most points check one feature of your code: a correct call to a method, a loop over the right range, a comparison, an accumulator that is set up and updated.
- One or two points per question are "algorithm" points. They check that all the steps are present and connected in the right order, so the whole method works.
- Algorithm points are lost by an early
return, by printing when the question asks you to return, by using[ ]on an ArrayList, or by changing data that the question says stays unchanged.
- Small typing slips, such as a missing semicolon, are forgiven when your indentation makes your meaning clear. Still write real Java: your code is typed in Bluebook and is never compiled, so no tool will warn you.
- When the question gives you a helper method, use it: rewriting what it does at length costs credit.
- Algorithm: Algorithms define step-by-step processes to follow when completing a task or solving a problem. These algorithms can be represented using written language or diagrams.
- Sequencing: Sequencing defines an order for when steps in a process are completed. Steps in a process are completed one at a time.
- Integrated development environment (IDE): Code can be written in any text editor; however, an integrated development environment (IDE) is often used to write programs because it provides tools for a programmer to write, compile, and run code.
- Compiler: A compiler checks code for some errors. Errors detectable by the compiler need to be fixed before the program can be run.
- Syntax error: A syntax error is a mistake in the program where the rules of the programming language are not followed. These errors are detected by the compiler.
- Logic error: A logic error is a mistake in the algorithm or program that causes it to behave incorrectly or unexpectedly. These errors are detected by testing the program with specific data to see if it produces the expected outcome.
- Run-time error: A run-time error is a mistake in the program that occurs during the execution of a program. Run-time errors typically cause the program to terminate abnormally.
- Exception: An exception is a type of run-time error that occurs as a result of an unexpected error that was not detected by the compiler. It interrupts the normal flow of the program’s execution.
Telling the three apart
When a question describes or shows an error, ask two questions in order.
Does the program compile?
If not, it is a syntax error.
If it compiles, does it stop part way with an exception?
Then it is a run-time error.
If it compiles and runs to the end but the result is wrong, it is a logic error.
Kind of error
Compiles?
Runs to the end?
Who finds it
Example
Syntax
No
Never starts
The compiler
int seats = 40 with no semicolon
Run-time (exception)
Yes
No, stops at the bad statement
The computer, while running
fare / riders with riders equal to 0
Logic
Yes
Yes
You, by testing with known answers
quiz1 + quiz2 / 2 for an average
The same mistake can be a different kind of error depending on the values.
fare / riders is fine when riders is 3 and is a run-time error when riders is 0.
That is why testing uses several values, including edge cases such as zero.
A high school sells tickets to its fall play.
An adult ticket costs $12 and a student ticket costs $7.
Write an algorithm, in words, that a ticket booth volunteer could follow to charge a family and give change, then say which two steps must not be swapped.
- Step 1: Count the adult tickets and the student tickets the family wants.
- Step 2: Multiply the number of adult tickets by 12 and the number of student tickets by 7.
- Step 3: Add the two products to get the total cost.
- Step 4: Take the family's payment.
- Step 5: Subtract the total cost from the payment to get the change.
- Step 6: Hand over the tickets and the change.
Step 3 must come before Step 5: the change is computed from the total, so the total must already exist.
(Steps 1 and 4 could happen in either order without changing the result, which shows that sequencing matters only where one step uses what another produced.)
The same algorithm in Java, for 2 adults, 3 students and a $50 payment:
int adults = 2;
int students = 3;
int total = adults * 12 + students * 7;
int paid = 50;
int change = paid - total;
System.out.println("Total: " + total);
System.out.println("Change: " + change);
Total: 45
Change: 5
Check: 2 × 12 = 24 and 3 × 7 = 21, so the total is 45 and the change from 50 is 5, matching the output.
Each code segment below is meant to print the number of buses needed for a field trip.
Name the kind of error in each one and say when it is detected.
Segment I:
int students = 58;
int perBus = 0;
System.out.println(students / perbus);
Segment II:
int students = 58;
int perBus = 0;
System.out.println(students / perBus);
Segment III:
int students = 58;
int perBus = 40;
System.out.println(perBus / students);
0
Segment I is a syntax error, found by the compiler before anything runs: Java is case-sensitive, so perbus is a different name from perBus, and no variable called perbus exists (the compiler says "cannot find symbol").
Segment II compiles, because every name and type is legal.
It is a run-time error: when the division runs with perBus equal to 0, the program throws an ArithmeticException and stops.
Segment III compiles and runs to the end, printing 0.
That is a logic error: the division is the wrong way round.
It is found only by testing, by knowing that 58 students need at least 2 buses and seeing that the program says 0.
A park ranger's program is meant to print the number of visitors who are still inside the park at closing time.
Consider the following code segment.
int entered = 214;
int left = 0;
int inside = entered - left;
left = 187;
System.out.println("Inside: " + inside);
Inside: 214
What is printed, what kind of error is this, and how is it fixed?
Trace the statements one at a time, writing each variable's value after each line:
Line run
entered
left
inside
Output
int entered = 214;
214
int left = 0;
214
0
int inside = entered - left;
214
0
214
left = 187;
214
187
214
System.out.println(...)
214
187
214
Inside: 214
The program prints Inside: 214.
It compiles and finishes, but 187 people have left, so the answer should be 27: a logic error caused by sequencing.
inside was computed once, from the old value of left; changing left afterwards does not go back and recompute it.
The fix is to move left = 187; above the subtraction (or to compute inside after left has its final value):
int entered = 214;
int left = 187;
int inside = entered - left;
System.out.println("Inside: " + inside);
Inside: 27
What a weaker answer gets wrong: calling this a syntax error because "the answer is wrong".
The compiler accepted the code, so it cannot be a syntax error.
Connecting it
Every free-response question you will meet is an algorithm problem first and a Java problem second.
The habit this section starts, writing the steps in order before typing, then checking the order by tracing a small example, is the same habit that earns the algorithm points later.
A tracing table like the one in Worked example 3 is the tool you will use in every unit: it is how you find logic errors without a computer, which is exactly what the multiple-choice section asks you to do.
To name an error type, ask in order: does it compile (if not, syntax), does it stop part way with an exception (run-time), or does it finish with a wrong result (logic)?
A run-time error always involves a statement that is legal Java, such as dividing by a variable that turns out to be 0.
- Calling every wrong answer a syntax error. It is tempting because "error" sounds like "the computer complained". A program that compiles and prints a wrong value has a logic error; the compiler only checks the rules of the language.
- Thinking the compiler finds all errors. The compiler checks some errors only.
fare / riderscompiles whether or notriderscould be 0, so a clean compile proves nothing about run-time or logic errors. Fix: test with specific values, including 0 and other edge cases.
- Expecting a variable to update itself. In Worked example 3,
insidekept the value it was given. A statement runs once, when it is reached; it is not a rule that stays true. Fix: compute a value after everything it depends on has its final value.
- Thinking a bad position gives back nothing. An index past the end of a String, array or list throws an exception and stops the program; it never returns
nullor an empty value. Fix: keep every index in range.
- Assuming Java ignores capital letters.
perBusandperbusare different names, so a slip in case is a syntax error ("cannot find symbol").
Check your understanding
1. Which of the following best describes a logic error? (A) The program does not compile because a semicolon is missing. (B) The program compiles and runs to the end but produces an incorrect result. (C) The program compiles but stops part way because an exception is thrown. (D) The program cannot be opened in an integrated development environment.
Total [1]
2. Consider the following code segment. Line numbers are shown in comments.
int laps = 8; // Line 1
int lapLength = 400; // Line 2
int distance = laps * lapLength; // Line 3
System.out.println(Distance); // Line 4
Which of the following best describes what happens when the code segment is compiled and run?
(A) It prints 3200.
(B) It prints distance.
(C) The code does not compile because of Line 4.
(D) An exception is thrown when Line 4 runs.
Total [1]
3. Consider the following code segment.
int boxes = 0;
int books = 36;
System.out.print("Books per box: ");
System.out.println(books / boxes);
Which of the following best describes the result of executing the code segment?
(A) The code does not compile because boxes is 0.
(B) Books per box: 0 is printed.
(C) Books per box: is printed, and then an ArithmeticException is thrown.
(D) Nothing is printed, and the program continues with the next statement.
Total [1]
4. Which of the following statements about compiling and running a Java program is true? (A) The compiler detects every error in a program before it runs. (B) Errors that the compiler detects must be fixed before the program can be run. (C) A program with a logic error will not compile. (D) A run-time error is detected by the compiler and reported with a line number.
Total [1]
5. Consider the following code segment.
int score = 3;
System.out.println(score);
score = score + 4;
System.out.println("score");
score = 10;
System.out.println(score + 1);
Write exactly what is printed as a result of executing the code segment.
Total [2]
6. Code drill. The four statements below are in the wrong order. They are meant to print the cost of renting kayaks at a lake for one group: 3 kayaks at $18 each, plus a $10 cleaning fee, so that the program prints Cost: 64.
System.out.println("Cost: " + cost);
int kayaks = 3;
int cost = kayaks * 18 + fee;
int fee = 10;
Write the four statements in an order that makes the code segment print Cost: 64, and say which kind of error the order shown gives.
Total [2]
7. A student's program computes the total price of a cart of items in an online store. It compiles, runs to the end and prints a total, but for one test cart it prints $41 when the correct total is $47. Describe what kind of error this is, and describe how the student should go about finding it.
Total [2]
8. Consider the following algorithm for a school's late-bus sign-up, written in words.
- Step A: Count the students who signed up.
- Step B: Work out the number of buses needed, at 40 students per bus.
- Step C: Post the number of buses on the school website.
- Step D: Close the sign-up sheet.
The algorithm sometimes posts a number of buses that is too small, because students keep signing up after the number is posted.
Which change fixes this?
(A) Move Step D so that it comes before Step A. (B) Move Step C so that it comes before Step A. (C) Remove Step D. (D) Move Step B so that it comes after Step C.
Total [1]
Answers
1. (B). A logic error lets the program compile and finish but gives the wrong result. (A) is a syntax error; (C) is a run-time error (an exception); (D) is not an error in the program at all.
2. (C). Java is case-sensitive: Distance is not the same name as distance, and no variable Distance exists, so the compiler reports "cannot find symbol" at Line 4 and nothing runs. (A) is what the intended code prints; (B) would need the quotation marks of a string literal; (D) confuses a compile-time error with a run-time error.
3. (C). The code compiles (dividing by a variable is legal). The print statement runs first, so Books per box: appears, then books / boxes divides an int by the int zero and throws an ArithmeticException, which stops the program. (A) forgets that the compiler does not know the value of boxes; (B) treats division by zero as giving 0; (D) forgets that the exception stops the program.
4. (B). The compiler checks for some errors, and those must be fixed before there is a program to run. (A) is false because logic and run-time errors get past the compiler; (C) is false because a logic error compiles; (D) is false because run-time errors happen while the program runs.
5. The statements run in order. score is 3 and prints as 3; score becomes 7, but the next line prints the string literal score, not the variable; score becomes 10, and score + 1 prints 11.
3
score
11
Point 1 (3 and 11 on the first and third lines) Point 2 (the literal text score on the second line, with no value)
6. Model answer:
int kayaks = 3;
int fee = 10;
int cost = kayaks * 18 + fee;
System.out.println("Cost: " + cost);
Cost: 64
Point 1 (kayaks and fee both given values before the line that computes cost, and cost computed before it is printed; the first two lines may be in either order) Point 2 (the order shown is a syntax error: it uses cost and fee before they exist, so it does not compile)
7. Point 1 It is a logic error: the program compiles and runs to the end, but the result is wrong. Point 2 The student should test with specific data whose correct answer is known (for example, a cart with one item, then two items), compare each result with the expected total, and trace the code by hand on the first test that fails to find the step that goes wrong.
8. (A). Closing the sign-up before counting means no one can sign up after the count is taken, so the posted number is based on the final count. (B) posts before anything is counted; (C) leaves the sheet open, which is the cause of the problem; (D) posts before the number of buses has been worked out.