Algorithms and Data Structures · Chapter 4
Classic algorithms
Some algorithms are older than any computer and still show up in almost every exam: Euclid, primes, number systems, check digits and making change. They are short, easy to trace on paper and show how much running time a good idea saves.
GCD and LCM with Euclid
You can find the greatest common divisor (GCD) without trial and error. Euclid uses this: the GCD of a and b is the same as that of b and a % b. So you keep replacing (a, b) with (b, a % b) until b is 0. Then a holds the GCD.
(1071, 462) 1071 % 462 = 147(462, 147) 462 % 147 = 21(147, 21) 147 % 21 = 0(21, 0) b is 0, GCD = 21If a is smaller than b, the first step only swaps the two. The numbers shrink fast: the number of steps only grows with the number of digits of the smaller number, so O(log n).
The least common multiple follows from it: lcm(a, b) = a / gcd(a, b) · b. Divide first, otherwise a · b quickly overflows.
public class Main { public static int gcd(int a, int b) { while (b != 0) { int r = a % b; System.out.println("a = " + a + ", b = " + b + ", r = " + r); a = b; b = r; } return a; }
public static long lcm(int a, int b) { return (long) (a / gcd(a, b)) * b; }
public static void main(String[] args) { System.out.println("gcd: " + gcd(1071, 462)); System.out.println("lcm: " + lcm(4, 6)); }}Primes and the sieve
A prime is greater than 1 and only divisible by 1 and itself. For the test it is enough to try divisors up to √n: if n = a · b, one of the two factors is at most √n. Instead of t <= Math.sqrt(n) you usually write t * t <= n. The test then needs O(√n) steps instead of O(n).
If you need all primes up to n, the Sieve of Eratosthenes is faster. You create a boolean array and, for every prime i, cross out its multiples starting at i · i. Whatever is not crossed out at the end is prime. The sieve needs O(n log log n) steps, almost linear in practice, but it needs an array of size n.
import java.util.ArrayList;import java.util.List;
public class Main { public static boolean isPrime(int n) { if (n < 2) { return false; } for (int t = 2; t * t <= n; t++) { if (n % t == 0) { return false; } } return true; }
public static List<Integer> sieve(int n) { boolean[] composite = new boolean[n + 1]; List<Integer> primes = new ArrayList<>(); for (int i = 2; i <= n; i++) { if (!composite[i]) { primes.add(i); for (long k = (long) i * i; k <= n; k += i) { composite[(int) k] = true; } } } return primes; }
public static void main(String[] args) { System.out.println(isPrime(91) + " " + isPrime(97)); System.out.println(sieve(50)); }}Number systems
A number in the system with base b has the place values 1, b, b², b³, …, counted from the right. 1101 in binary is 1·8 + 1·4 + 0·2 + 1·1 = 13.
- Decimal → base b (remainder method): divide by
brepeatedly and note the remainders. The first remainder is the last digit, so reverse at the end. - Base b → decimal (Horner's method): go from left to right and compute
value = value · b + digit.
Both need as many steps as the number has digits, so O(log n). Hexadecimal uses the digits 0–9 and A–F. Java has ready-made methods like Integer.toHexString and Integer.parseInt(text, base). In the exam, though, you should be able to do it yourself.
public class Main { public static String toBinary(int n) { if (n == 0) { return "0"; } StringBuilder bits = new StringBuilder(); while (n > 0) { bits.append(n % 2); n = n / 2; } return bits.reverse().toString(); }
public static int fromBinary(String bits) { int value = 0; for (int i = 0; i < bits.length(); i++) { value = value * 2 + (bits.charAt(i) - '0'); } return value; }
public static void main(String[] args) { System.out.println(toBinary(13)); System.out.println(fromBinary("1101")); System.out.println(Integer.toHexString(255)); System.out.println(Integer.parseInt("FF", 16)); }}Caesar and check digits
In the Caesar cipher, every letter is shifted by n places. You can calculate with char: c - 'a' is the position in the alphabet, % 26 makes it continue at a after z. Decrypting means shifting by -n. The + 26 prevents negative remainders. It is not secure: there are only 25 keys, and you can try them all.
A check digit does not protect against attacks, but against typing errors. In the Luhn algorithm (credit cards), every second digit from the right is doubled, and 9 is subtracted from results above 9. If the sum of all digits is divisible by 10, the number is valid. This catches every single wrong digit and most swaps of two neighbours. Both methods go through each character once: O(n).
public class Main { public static String caesar(String text, int shift) { StringBuilder result = new StringBuilder(); for (char c : text.toCharArray()) { if (c >= 'a' && c <= 'z') { result.append((char) ('a' + (c - 'a' + shift + 26) % 26)); } else if (c >= 'A' && c <= 'Z') { result.append((char) ('A' + (c - 'A' + shift + 26) % 26)); } else { result.append(c); } } return result.toString(); }
public static boolean luhn(String digits) { int sum = 0; for (int i = 0; i < digits.length(); i++) { int digit = digits.charAt(digits.length() - 1 - i) - '0'; if (i % 2 == 1) { digit = digit * 2; if (digit > 9) { digit = digit - 9; } } sum += digit; } return sum % 10 == 0; }
public static void main(String[] args) { String secret = caesar("Hello, World!", 3); System.out.println(secret); System.out.println(caesar(secret, -3)); System.out.println(luhn("79927398713")); System.out.println(luhn("79927398710")); }}Greedy and its limits
A greedy algorithm makes the choice that looks best right now in every step and never takes it back. For change, that means: always the largest coin that still fits. With euro coins this gives the fewest coins.
With other coin systems it goes wrong. With 4, 3 and 1, greedy pays 6 as 4 + 1 + 1, although 3 + 3 would do. And with 5 and 2 it finds no solution at all for 6, although 2 + 2 + 2 works. Greedy is fast, but only optimal for suitable problems. To find the best solution in every case you need other methods such as backtracking (chapter 6).
public class Main { public static void change(int amount, int[] coins) { System.out.print(amount + " ="); for (int coin : coins) { while (amount >= coin) { System.out.print(" " + coin); amount -= coin; } } System.out.println(amount == 0 ? "" : " (rest " + amount + ")"); }
public static void main(String[] args) { int[] euro = {200, 100, 50, 20, 10, 5, 2, 1}; change(388, euro);
int[] odd = {4, 3, 1}; change(6, odd); }}Running times at a glance
- GCD with Euclid: O(log n)
- Prime test up to √n: O(√n)
- Sieve of Eratosthenes: O(n log log n)
- Converting to another base: O(log n)
- Caesar, Luhn (text of length n): O(n)
- Greedy change with k sorted coin values: O(k), with
/and%per coin value
Common mistakes
int overflow
a * bwith twoints is computed asint, even if the result ends up in alongvariable. For100000 * 99999you get a wrong, even negative number. Divide first (a / gcd(a, b) * b) or make one factor along. The same applies tot * t <= nwhennis close toInteger.MAX_VALUE.Digits in the wrong order
The remainder method delivers the last digit first. If you simply append the remainders, you get
011instead of110for 6. The other way round, when reading, the first character is the highest place. So never test only with numbers like101that read the same forwards and backwards.Character instead of digit
'7'is acharwith the numeric value 55, not 7. If you calculate withtext.charAt(i), you get nonsense. The digit value istext.charAt(i) - '0'. In the same way,c == 1is something other thanc == '1'.