01 / 21

Algorithms, Programming
& Compilers

Discover how step-by-step instructions become running programs: from algorithm design through high-level code to machine-executable output.

AP Computer Science A

What Is an Algorithm?

An algorithm is a finite, ordered sequence of well-defined steps that solves a specific problem or performs a computation. Algorithms exist independently of any programming language: you can express them in English, pseudocode, or flowcharts.

Finite
Must terminate after a limited number of steps
Definite
Each step is precisely and unambiguously defined
Effective
Every operation can actually be carried out

A Simple Sorting Algorithm

Let's trace a selection sort on the list [5, 3, 8, 1]. Each pass finds the smallest unsorted element and places it in the correct position.

Original: 5 3 8 1 Pass 1: 1 3 8 5 min = 1, swap Pass 2: 1 3 8 5 min = 3, no swap Pass 3: 1 3 5 8 min = 5, swap Sorted! [1, 3, 5, 8] : 3 passes for 4 elements

Why Algorithms Matter

Every piece of software, from search engines to medical imaging, relies on algorithms. Choosing the right algorithm determines whether a task takes milliseconds or hours.

1
Correctness: The algorithm must produce the right answer for every valid input.
2
Efficiency: We measure time and space complexity using Big-O notation, e.g., \( O(n^2) \) vs. \( O(n \log n) \).
3
Generality: A good algorithm solves a class of problems, not just one instance.

What Is Programming?

Programming is the process of translating an algorithm into a specific programming language so that a computer can execute it. A program is an algorithm expressed in code.

High-Level
Java, Python, C++ : human-readable, portable across machines
Low-Level
Assembly, machine code : hardware-specific, harder to read

Algorithm → Java Code

Here's how the "find the maximum" algorithm translates into Java:

// Algorithm: scan array, track largest value
public static int findMax(int[] arr) {
  int max = arr[0];
  for (int i = 1; i < arr.length; i++) {
    if (arr[i] > max) {
      max = arr[i];
    }
  }
  return max;
}

What Is a Compiler?

A compiler is a program that translates source code written in a high-level language into a lower-level language (machine code or bytecode) before execution. It checks for errors and optimizes the output.

Source Code (.java file) Compiler (javac) Checks + Translates Bytecode (.class file) Compile-time errors reported here

Compiled vs. Interpreted

Compiled Interpreted
Translation Entire program at once, before running Line by line, during execution
Error Detection At compile time (before running) At runtime (while running)
Speed Generally faster (pre-optimized) Generally slower (translated on-the-fly)
Examples Java, C, C++ Python, JavaScript, Ruby
Output Machine code or bytecode file No separate output file

The Java Build Pipeline

1. Write Hello.java 2. Compile javac Hello.java 3. Bytecode Hello.class 4. JVM Executes java Hello "Hello, World!" Compile-time errors caught in steps 2-3 Runtime errors caught in step 4

One bytecode, compatible runtimes

The same compiled bytecode can execute on suitable Java virtual machines; the connecting arcs are conceptual rather than literal packets.

The same Java source compiles to bytecode that suitable JVMs can execute on different platforms.
The same Java source compiles to bytecode that suitable JVMs can execute on different platforms.

Compile-Time vs. Runtime Errors

Compile-Time Errors
Caught by the compiler before the program runs. These are syntax errors and type mismatches.
Runtime Errors
Occur during execution. Division by zero, null pointer access, array out of bounds.
// Compile-time error: missing semicolon
int x = 5  // ← won't compile!

// Runtime error: division by zero
int y = 10 / 0; // ← compiles fine, crashes at runtime

Step-by-Step: Your First Program

1
Design the algorithm: Write pseudocode or draw a flowchart describing what your program should do.
2
Write source code: Translate the algorithm into Java. Save the file as ClassName.java (filename must match the class name).
3
Compile: Run javac ClassName.java. Fix any compile-time errors the compiler reports.
4
Execute: Run java ClassName. The JVM loads the bytecode and executes your program.
5
Test and debug: Verify output with different inputs. Fix runtime errors and logic bugs.

Example 1: Hello, World!

public class HelloWorld {
  public static void main(String[] args) {
    System.out.println("Hello, World!");
  }
}
1
public class HelloWorld : declares a class. The file must be named HelloWorld.java.
2
public static void main(String[] args) : the entry point. The JVM calls this method first.
3
System.out.println(...) : prints the string to the console and adds a newline.

Example 2: Sum of an Array

Algorithm: Initialize a running total to 0. For each element in the array, add it to the total. Return the total.

public static int sum(int[] arr) {
  int total = 0;
  for (int val : arr) {
    total += val;
  }
  return total;
}

Example 3: Linear Search

Problem: Find the index of a target value in an array. Return \( -1 \) if not found.

public static int linearSearch(int[] arr, int target) {
  for (int i = 0; i < arr.length; i++) {
    if (arr[i] == target) {
      return i;
    }
  }
  return -1;
}

Common Mistakes

✕ File Name Mismatch
The file must be named exactly ClassName.java. A mismatch causes a compile error.
✕ Missing Semicolons
Every statement in Java ends with a semicolon. Forgetting one triggers a compile-time error.
✕ Confusing = and ==
Single = is assignment. Double == is comparison. Using the wrong one causes logic bugs.
✕ Off-By-One Errors
Array indices start at 0. Using <= arr.length instead of < causes an ArrayIndexOutOfBoundsException.
✕ Infinite Loops
Forgetting to update the loop variable means the termination condition is never met. The program hangs.
✕ Skipping Testing
Code that compiles isn't necessarily correct. Always test with edge cases: empty arrays, one element, negative numbers.

Putting It All Together

Concept Definition Key Point
Algorithm Finite sequence of well-defined steps Language-independent
Program Algorithm expressed in a programming language Executable by a computer
Compiler Translates entire source code before execution Catches errors early
Interpreter Translates and executes code line by line Errors found at runtime
Bytecode Intermediate, platform-independent code Java's "write once, run anywhere"
JVM Runs Java bytecode on any platform Handles memory and execution

Question 1 of 5

Which of the following best describes an algorithm?

Question 2 of 5

What does the Java compiler (javac) produce as output?

Question 3 of 5

A student writes int x = 10 / 0; in their Java program. The code compiles successfully. What happens next?

Question 4 of 5

What is the worst-case time complexity of a linear search through an array of \( n \) elements?

Question 5 of 5

Which statement correctly describes the difference between a compiler and an interpreter?