Prerequisites for Algorithms
The Algorithms course brings together programming in Java, basic data structures, discrete mathematics, proof techniques, sums and logarithms, probability and counting. The 28 topics on this page collect the background the course builds on in six groups.
Each card has a short explanation, a small example, links to the slides where the topic is used and a check question; clicking the question opens its answer.
Java and programming
What you need to read and trace the code in the slides and to write solutions in Java.
Java basics: types, conditions, loops
The code in the slides is written in Java, so you need to be able to trace on paper how many times a loop runs and how each variable changes. The int type's limit of roughly ±2.1 billion and integer division (7 / 2 = 3) are common sources of bugs.
Why it mattersAll the code-trace slides use these constructs; the classic overflow bug in binary search also comes from the int limit.
Check question
int a = 7, b = 2; double d = a / b; What is the value of d?
3.0. The division is performed on integers (3), and only then is the result converted to double. To get 3.5, write (double) a / b.
int sum = 0;
for (int i = 1; i <= 10; i++) {
if (i % 2 == 0) sum += i; // even numbers are added
}
System.out.println(sum); // 30
long big = 50_000L * 50_000; // would overflow as an int
System.out.println(big); // 2500000000Arrays and two-dimensional arrays
Sorting, searching and dynamic programming tables all work on arrays. You should know that indices run from 0 to length − 1, that an array is passed to a method by reference, and that a two-dimensional array is traversed row by row.
Why it mattersSorting algorithms work in place on an array, DP tables are two-dimensional arrays, and an adjacency matrix is a two-dimensional array too.
Check question
What happens if a[3] is read after the line int[] a = {3, 1, 2};?
An ArrayIndexOutOfBoundsException is thrown; the valid indices are 0, 1 and 2.
int[] a = new int[5]; // [0, 0, 0, 0, 0]
a[a.length - 1] = 9; // last element
int[][] dp = new int[3][4]; // 3 rows, 4 columns
for (int i = 0; i < dp.length; i++)
for (int j = 0; j < dp[i].length; j++)
dp[i][j] = i + j;
System.out.println(dp[2][3]); // 5Strings and characters
The Java code of string algorithms works on String objects. s.length() gives the length and s.charAt(i) gives the i-th character; indices start at 0 as in arrays. A String is immutable: s + c builds a new object every time, so StringBuilder is used to accumulate a string inside a loop. The char type is a 16-bit integer; ch - 'a' converts a lowercase letter to an index in the range 0–25, and a character can be used directly as an index into a counting array. The contents of two strings are compared with equals, not ==, and lexicographic order with compareTo.
Why it mattersThe brute-force, KMP, Boyer-Moore and Rabin-Karp code compares characters with charAt; trie nodes pick a child with ch - 'a', and hash functions and radix sort use character codes like numbers.
Check question
Does "kedi".compareTo("kek") return a negative or a positive value?
Negative. The first two characters are equal; at the third position 'd' (100) is compared with 'k' (107), and 100 − 107 = −7 is returned.
String s = "algorithm";
System.out.println(s.length()); // 9
System.out.println(s.charAt(0)); // a
int idx = s.charAt(2) - 'a'; // 'g' → 6
StringBuilder sb = new StringBuilder();
for (int i = s.length() - 1; i >= 0; i--) sb.append(s.charAt(i));
System.out.println(idx + " " + sb); // 6 mhtirogla
System.out.println("abc".equals("ab" + "c")); // trueMethods and parameter passing
Algorithms are usually written as methods: the input is the parameter and the result is the return value. Java passes everything by value; but for arrays and objects the copied value is a reference, so a swap inside the method changes the caller's array.
Why it mattersAll sorting algorithms use helper methods that swap or shift elements; the partition method returns the final position of the pivot.
Check question
Does writing a = new int[10]; inside a method change the caller's array?
No. Only the method's local reference is bound to the new array; the caller continues to see the old array.
static void swap(int[] a, int i, int j) {
int t = a[i]; a[i] = a[j]; a[j] = t; // the caller's array changes
}
static void increment(int x) { x++; } // the caller's variable does not change
int[] d = {5, 7};
swap(d, 0, 1); // d = [7, 5]
int y = 1;
increment(y); // y is still 1
System.out.println(d[0] + " " + y); // 7 1Recursion and the call stack
Merge sort, quicksort, DFS, backtracking and divide-and-conquer algorithms are recursive. You should know that each call is pushed onto the call stack with its own local variables, that forgetting the base case causes a StackOverflowError, and that recursion depth consumes memory.
Why it mattersFast exponentiation, merge sort, recursive DFS and the backtracking template are written directly with recursion.
Check question
In the call power(2, 10), how many times does the power method run, counting the first call?
5 times: n = 10, 5, 2, 1, 0.
static int power(int a, int n) { // a to the power n, n >= 0
if (n == 0) return 1; // base case
int half = power(a, n / 2); // the problem is halved
return (n % 2 == 0) ? half * half : half * half * a;
}
System.out.println(power(2, 10)); // 1024; depth is about log2(n)Classes, objects and comparators
Concepts such as an edge, a node, a job or an item are represented by small classes. Sorting and priority queues need a compareTo method or a Comparator to compare elements: in Kruskal's algorithm edges are sorted by weight, and in activity selection activities are sorted by finish time.
Why it mattersMost greedy algorithms start with a sort; Dijkstra and Prim put comparable objects into a priority queue.
Check question
Why is writing return w - o.w; inside compareTo risky?
With large positive and negative values the subtraction can exceed the int range and flip the sign; Integer.compare does not overflow.
static class Edge implements Comparable<Edge> {
final int u, v, w;
Edge(int u, int v, int w) { this.u = u; this.v = v; this.w = w; }
public int compareTo(Edge o) { return Integer.compare(w, o.w); }
}
List<Edge> edges = new ArrayList<>();
edges.add(new Edge(0, 1, 7));
edges.add(new Edge(1, 2, 3));
Collections.sort(edges); // ascending by weight
edges.sort((a, b) -> Integer.compare(b.w, a.w)); // descending: a Comparator
System.out.println(edges.get(0).w); // 7Java collections
The Java code in the slides often uses ready-made structures: ArrayList for adjacency lists, ArrayDeque for the BFS queue and the DFS stack, PriorityQueue for Dijkstra and Prim, HashMap for memoization. Knowing the cost of each basic operation is a prerequisite for computing an algorithm's total running time correctly.
Why it mattersBFS is written with a queue, Dijkstra with a priority queue, memoization with a map.
Check question
How long do add and poll take in a PriorityQueue? How long do contains(x) and remove(x) take?
add and poll take O(log n); contains(x) and remove(x) take O(n) because they scan the internal array from start to end.
Deque<Integer> queue = new ArrayDeque<>();
queue.offer(1); queue.offer(2);
int first = queue.poll(); // 1 (first in, first out)
PriorityQueue<int[]> pq = new PriorityQueue<>((x, y) -> Integer.compare(x[1], y[1]));
pq.add(new int[] {7, 40});
pq.add(new int[] {3, 15});
int[] smallest = pq.poll(); // [3, 15]
Map<Integer, Long> memo = new HashMap<>();
memo.put(10, 55L);
System.out.println(first + " " + smallest[0] + " " + memo.get(10)); // 1 3 55Reading and tracing pseudocode
Slides and textbooks often give algorithms in pseudocode: ← is assignment, arrays may start at 1, and “for j ← 2 to n” includes the final value. When translating to Java you need to account for these differences and be able to write the value of every variable at every step into a trace table.
Why it mattersGraph, flow and branch-and-bound algorithms are given first in pseudocode and then in Java.
Check question
How are the loops written when the pseudocode above is translated to Java with indices starting at 0?
The outer loop becomes for (int j = 1; j < n; j++), and the inner condition takes the form i >= 0 && A[i] > key.
INSERTION-SORT(A, n)
for j ← 2 to n
key ← A[j]
i ← j − 1
while i > 0 and A[i] > key
A[i + 1] ← A[i]
i ← i − 1
A[i + 1] ← keyTesting and debugging
A correct idea must also be implemented carefully and tested. Testing with empty input, a single element, repeated values, sorted and reverse-sorted arrays, disconnected graphs and large values that may cause overflow should become a habit.
Why it mattersThe “common mistakes” slide of every chapter collects such edge cases.
Check question
When does mid = (low + high) / 2 give a wrong result in binary search?
When the sum low + high exceeds the int range, it overflows and becomes negative; low + (high − low) / 2 is safe.
int[] empty = {}, one = {4}, equal = {2, 2, 2}, rev = {5, 4, 3, 2, 1};
for (int[] t : new int[][] {empty, one, equal, rev}) {
int[] k = t.clone();
Arrays.sort(k);
for (int i = 1; i < k.length; i++)
if (k[i - 1] > k[i]) throw new AssertionError("not sorted");
}
System.out.println("all tests passed");Basic data structures
The structures algorithms work on and the cost of their basic operations. These structures are covered in detail in the prerequisite course Data Structures.
Linked lists
Like an array, it stores a sequence, but the elements are not contiguous in memory; each node points to the next one. Insertion at the head takes O(1), and access to the i-th element takes O(n). Adjacency lists, chaining in hash tables and the O(1) implementation of an LRU cache rely on linked lists.
Why it mattersChained hash tables and the O(1) LRU cache use linked lists.
Check question
Why does deleting the last element of a singly linked list take O(n)?
The next field of the second-to-last node must be set to null; reaching that node requires walking from the head.
static class Node {
int value; Node next;
Node(int value, Node next) { this.value = value; this.next = next; }
}
Node head = null;
for (int x = 1; x <= 3; x++) head = new Node(x, head); // 3 → 2 → 1
for (Node n = head; n != null; n = n.next) System.out.print(n.value + " ");Stacks and queues
A stack works by the last-in, first-out (LIFO) principle and a queue by first-in, first-out (FIFO); the basic operations of both take O(1). DFS works with a stack (or with the call stack of recursion) and BFS with a queue; backtracking undoes choices in stack order.
Why it mattersIterative DFS uses an explicit stack; BFS and Edmonds-Karp use a queue.
Check question
1, 2, 3 are added in this order to both a queue and a stack. Which element comes out first from each?
From the queue, 1 comes out first; from the stack, 3 comes out first.
Deque<Character> stack = new ArrayDeque<>();
for (char c : "abc".toCharArray()) stack.push(c);
StringBuilder sb = new StringBuilder();
while (!stack.isEmpty()) sb.append(stack.pop());
System.out.println(sb); // cbaHeaps and priority queues
In a min-heap every node is smaller than its children, so the smallest element is at the root. Stored as an array, the children of node i are at 2i + 1 and 2i + 2 and its parent is at (i − 1) / 2. Insertion and extracting the minimum take O(log n); heap sort, Dijkstra, Prim, Huffman and the online median rely on this structure.
Why it mattersHeap sort, the complexity of Dijkstra's algorithm, building the Huffman tree and the online median rely on the heap.
Check question
Building a heap by inserting n elements one at a time takes O(n log n). How long does bottom-up heap construction take?
O(n); because most nodes are near the leaves, the total sift-down work stays linear.
array: [2, 5, 3, 9, 6, 4]
index: 0 1 2 3 4 5
children of 2: 5 and 3 (index 1, 2)
children of 5: 9 and 6 (index 3, 4)
child of 3: 4 (index 5)Hash tables
A hash table converts a key into an array index with a hash function; insertion and search take O(1) on average. When two keys land in the same cell, the collision is resolved by chaining or linear probing; performance drops as the load factor grows. Memoization, “visited” sets and Rabin-Karp's hash comparison rely on this idea.
Why it mattersSearch by hashing, Rabin-Karp and memoization use a hash table.
Check question
What is the worst-case search time in a hash table, and when does it occur?
O(n); when all keys land in the same cell (the same chain).
int m = 7;
int[] keys = {10, 17, 24};
for (int k : keys) System.out.print(k % m + " "); // 3 3 3 → collision
Set<String> visited = new HashSet<>();
visited.add("A");
System.out.println(visited.contains("A")); // trueTrees and binary search trees
A tree with n nodes has n − 1 edges and exactly one path between any two nodes. The terms root, parent, child, leaf, depth and height are used unchanged in DFS/BFS trees, MSTs, the union-find structure, tries and state-space trees. A binary search tree keeps smaller keys in the left subtree and larger keys in the right subtree; if the tree is balanced, search takes O(log n).
Why it mattersThe BFS tree, spanning trees, tries and state-space trees are described with the same terms.
Check question
At most how many nodes can a binary tree of height h contain?
2^(h+1) − 1 (taking the height of a single node as 0).
8 height 2; leaves 1, 6, 14
/ \
3 10 parent of 3 is 8, children are 1 and 6
/ \ \
1 6 14 inorder traversal: 1 3 6 8 10 14Graph representations
A graph consists of vertices and edges; edges may be directed or undirected, weighted or unweighted. An adjacency matrix uses V² memory and answers an edge query in O(1); an adjacency list uses O(V + E) memory and traverses sparse graphs in O(V + E) time. The terms degree, path, cycle, connectivity and bipartiteness should be familiar.
Why it mattersAll graph chapters, and the TSP examples in branch and bound, assume a graph representation.
Check question
Which representation suits a road network with 10,000 vertices and 30,000 edges?
An adjacency list: a matrix needs 10⁸ cells, while the list holds about V + 2E = 70,000 entries for an undirected graph.
int V = 4;
List<List<Integer>> adj = new ArrayList<>();
for (int i = 0; i < V; i++) adj.add(new ArrayList<>());
int[][] edges = {{0, 1}, {0, 2}, {2, 3}};
for (int[] e : edges) { // undirected: both directions are added
adj.get(e[0]).add(e[1]);
adj.get(e[1]).add(e[0]);
}
System.out.println(adj.get(0)); // [1, 2]Discrete mathematics and proof
The language used to define algorithms and prove them correct.
Sets, functions and relations
Algorithms are described in the language of sets: G = (V, E), the set of visited vertices, the cut (S, V − S) in an MST, the subset of items chosen in the knapsack. You should know union, intersection, difference, Cartesian product and subsets; the domain and codomain of a function; and the reflexivity, symmetry and transitivity of relations.
Why it mattersThe cut property, Floyd-Warshall's transitive closure and the feasible solutions in branch and bound are defined with sets.
Check question
How many subsets does a set with n elements have, and which brute-force method is that costly?
2ⁿ; trying every selection one by one in subset sum or 0/1 knapsack.
A = {1, 2, 3}, B = {2, 3, 4}
A ∪ B = {1, 2, 3, 4} A ∩ B = {2, 3} A \ B = {1}
|A × B| = 3 · 3 = 9 number of subsets of A: 2³ = 8
The relation "reachable" is reflexive and transitive; in an undirected graph it is also symmetric.Logic and quantifiers
Loop conditions, pruning conditions and definitions are logical statements. You need to be able to read quantified sentences such as “for every n ≥ n₀, f(n) ≤ c · g(n),” to negate a statement correctly (De Morgan), and to tell “p ⇒ q” from “q ⇒ p.”
Why it mattersBig-O is defined with quantifiers; the inner loop of insertion sort stops on a compound condition.
Check question
What is the negation of the statement “every vertex has at least one neighbor”?
“There is at least one vertex with no neighbors.” ∀ and ∃ swap places and the inner statement is negated.
¬(a ∧ b) ≡ ¬a ∨ ¬b (De Morgan)
while (i > 0 && A[i] > x) loop exit condition: i <= 0 || A[i] <= x
f(n) = O(g(n)) ⇔ ∃c > 0, ∃n₀, ∀n ≥ n₀ : f(n) ≤ c · g(n)Induction and loop invariants
Induction proves a statement for every n by showing that P(1) is true and that P(k) ⇒ P(k + 1). A loop invariant is its adaptation to algorithms: a statement that is true before the loop (initialization), is preserved in every iteration (maintenance) and gives the result when the loop ends (termination). The correctness of recursive algorithms is also proved by induction.
Why it mattersThe correctness of sorting algorithms and the solutions of recurrences are shown by induction.
Check question
How is the equality 1 + 3 + 5 + … + (2n − 1) = n² shown by induction?
For n = 1, 1 = 1². If the equality holds for k, the sum for k + 1 is k² + (2k + 1) = (k + 1)².
Insertion sort, invariant: "at the start of iteration j, A[0..j−1] is sorted."
Initialization: j = 1 → A[0..0] is a single element, so it is sorted.
Maintenance: A[j] is shifted into place → A[0..j] is sorted.
Termination: j = n → A[0..n−1], that is, the whole array is sorted.Analysis tools
Sums, logarithms and growth rates for computing running times.
Summation notation and series
The cost of nested loops and recursion trees is written as a sum. Three series are fundamental: the arithmetic series grows quadratically; a geometric series with ratio less than 1 converges to a constant, while one with ratio greater than 1 is of the order of its largest term; the harmonic series grows logarithmically.
Why it mattersCounting loop iterations, adding up the levels of a recursion tree and the expected number of comparisons of randomized quicksort use these series.
Check question
How many times does the body of the loop for (i = 1; i < n; i *= 2) for (j = 0; j < i; j++) run?
1 + 2 + 4 + … < 2n times, that is, Θ(n) (a geometric series).
Σ (i = 1..n) i = n(n + 1) / 2 = Θ(n²)
Σ (i = 0..k) 2^i = 2^(k+1) − 1 (1 + 2 + 4 + … + 2^k)
Σ (i = 0..∞) (1/2)^i = 2
H(n) = Σ (i = 1..n) 1/i ≈ ln n = Θ(log n)Logarithm and exponent rules
Every algorithm that halves its input (binary search, merge sort, heaps) produces logarithmic depth: reducing n to 1 means halving log₂ n times. You should know the rules of exponents and logarithms, that the base of a logarithm is asymptotically irrelevant, and the approximation 2¹⁰ ≈ 10³.
Why it mattersThe number of steps of binary search, the n^(log_b a) term in the master theorem and Karatsuba's exponent n^1.585 are computed with logarithms.
Check question
At most about how many comparisons does binary search make on a sorted array of a billion elements?
About 30, because 2³⁰ ≈ 1.07 · 10⁹.
log2(1024) = 10 log2(10^6) ≈ 20 log2(10^9) ≈ 30
a^(m+n) = a^m · a^n (a^m)^n = a^(m·n) log(x·y) = log x + log y
n^(log_b a) = a^(log_b n) appears in the master theorem
log_3 n = log_2 n / log_2 3 the base changes only a constant factorFloor and ceiling
When an array is split in two, the halves hold ⌊n/2⌋ and ⌈n/2⌉ elements; in Java n / 2 gives the floor for positive numbers. Floor and ceiling appear in the middle index of binary search, the parent index in a heap, the height of a binary tree and approximation ratios.
Why it mattersThe split step of merge sort, the middle index of binary search and the index computations of a heap use floor and ceiling.
Check question
What is −7 / 2 in Java? What is ⌊−7/2⌋?
Java gives −3 (it truncates toward zero), whereas ⌊−3.5⌋ = −4. For negative numbers, Math.floorDiv gives the floor.
⌊7/2⌋ = 3 ⌈7/2⌉ = 4 ⌊n/2⌋ + ⌈n/2⌉ = n
height of a heap with n nodes is ⌊log2 n⌋: n = 10 → 3
Java: 7 / 2 == 3, (7 + 2 − 1) / 2 == 4 for positive a, b: ⌈a/b⌉ = (a + b − 1) / bAsymptotic growth
For large n the dominant term decides: 3n² + 100n + 7 = Θ(n²). You should be able to order the growth classes and, assuming roughly 10⁸–10⁹ simple operations per second, estimate which complexity is practical for which n. O is the upper bound, Ω the lower bound and Θ the tight bound.
Why it mattersEvery chapter compares algorithms by their complexity; growth classes determine which method suits which input size.
Check question
Which eventually grows faster: n¹⁰⁰ or 1.01ⁿ?
1.01ⁿ; every exponential function with a base greater than 1 eventually overtakes every polynomial.
approximate operation counts for n = 10^6
n log2 n ≈ 2 · 10^7 → under a second
n² = 10^12 → hours
2^n : even n = 60 is ≈ 10^18 → infeasibleRecurrence relations
The running time of a recursive algorithm is written in terms of itself: merge sort solves two halves and merges in linear time, so T(n) = 2T(n/2) + n. Being used to solving a recurrence by unrolling it, or by adding up the work at each level of the recursion tree, makes the master theorem much easier to follow.
Why it mattersRecurrences are solved with the master theorem; every divide-and-conquer algorithm is analyzed with a recurrence.
Check question
What is the recurrence of binary search, and what is its solution?
T(n) = T(n/2) + O(1); its solution is Θ(log n).
T(n) = 2T(n/2) + n
level 0: n = n
level 1: n/2 + n/2 = n
level 2: 4 · n/4 = n
… log2 n levels ⇒ T(n) = Θ(n log n)
T(n) = T(n − 1) + 1 ⇒ Θ(n) T(n) = 2T(n − 1) + 1 ⇒ Θ(2^n)Probability and counting
For measuring the size of search spaces and the behavior of randomized algorithms.
Combinatorics: permutations and combinations
The cost of brute force, backtracking and branch and bound is the size of the search space; counting it takes the multiplication rule, n! permutations, C(n, k) combinations and 2ⁿ subsets. For example, in a TSP with n cities, once the starting city is fixed there are (n − 1)! tours.
Why it mattersGenerating permutations, the brute-force solution of TSP and the size of the n-queens search tree are found by counting.
Check question
In how many ways can 8 queens be placed on an 8 × 8 board with one queen in each row? In how many ways if the columns must also be distinct?
In 8⁸ = 16,777,216 ways; if the columns must be distinct as well, in 8! = 40,320 ways.
P(n, k) = n! / (n − k)! C(n, k) = n! / (k! · (n − k)!)
C(5, 2) = 10 5! = 120 2^10 = 1024
n = 10 cities: 9! = 362,880 tours n = 20 cities: 19! ≈ 1.2 · 10^17 toursOther mathematics and concepts
Matrices, modular arithmetic, bit operations, and the basics of optimization and concurrency used in particular chapters.
Matrix operations
Directly multiplying two n × n matrices performs n³ multiplications in three nested loops; Strassen reduces this number with block matrices. For adjacency matrices, Floyd-Warshall's distance table and the matrix–vector product in power iteration, you need to know the row–column product, the identity matrix and how to split a matrix into blocks.
Why it mattersMatrix multiplication is the O(n³) example in complexity analysis, the subject of Strassen's algorithm and the basic step of power iteration.
Check question
What is the product [[1, 2], [3, 4]] · [[0, 1], [1, 0]]?
[[2, 1], [4, 3]]; multiplying by this permutation matrix on the right swaps the columns.
static int[][] multiply(int[][] a, int[][] b) {
int n = a.length;
int[][] c = new int[n][n];
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
for (int k = 0; k < n; k++)
c[i][j] += a[i][k] * b[k][j]; // n³ multiplications in total
return c;
}
int[][] c = multiply(new int[][] {{1, 2}, {3, 4}}, new int[][] {{0, 1}, {1, 0}});
System.out.println(Arrays.deepToString(c)); // [[2, 1], [4, 3]]Plane geometry and distance measures
The Euclidean distance between two points in the plane is √((x₁ − x₂)² + (y₁ − y₂)²), while the Manhattan distance, measured on a grid with horizontal and vertical steps only, is |x₁ − x₂| + |y₁ − y₂|. If a distance measure satisfies the triangle inequality, then d(a, c) ≤ d(a, b) + d(b, c): visiting a third point never shortens the route. The cross product of the vectors from A to B and from A to P, (B.x − A.x)(P.y − A.y) − (B.y − A.y)(P.x − A.x), is computed with integers; its sign tells whether P is to the left of line AB, to the right, or on it. To merely compare distances there is no need to take square roots; comparing their squares gives the same result.
Why it mattersThe heuristics of the A* algorithm are the Euclidean and Manhattan distances; the convex hull relies on the orientation test, the closest pair of points on Euclidean distance, and the 2-approximation of metric TSP on the triangle inequality.
Check question
What are the Euclidean and Manhattan distances for A = (0, 0) and B = (3, 4)? On which side of line AB is the point P = (1, 5)?
The Euclidean distance is √(9 + 16) = 5 and the Manhattan distance is 3 + 4 = 7. Since the cross product 3 · 5 − 4 · 1 = 11 > 0, P is to the left of the line when looking from A toward B.
static double euclid(int x1, int y1, int x2, int y2) {
return Math.hypot(x1 - x2, y1 - y2);
}
static int manhattan(int x1, int y1, int x2, int y2) {
return Math.abs(x1 - x2) + Math.abs(y1 - y2);
}
static long cross(int ax, int ay, int bx, int by, int px, int py) {
return (long) (bx - ax) * (py - ay) - (long) (by - ay) * (px - ax);
}
System.out.println(euclid(0, 0, 3, 4)); // 5.0
System.out.println(manhattan(0, 0, 3, 4)); // 7
System.out.println(cross(0, 0, 3, 4, 1, 5)); // 11 (P is on the left)Modular arithmetic and GCD
Hash functions, Rabin-Karp's rolling hash, pseudorandom number generators and the Miller–Rabin test work with modular arithmetic. You need to know that taking the remainder at every step of additions and multiplications does not change the result, how the GCD is computed with Euclid's algorithm, and the definition of a prime number.
Why it mattersEuclid's algorithm, rolling hashes, Miller–Rabin and pseudorandom numbers use modular arithmetic.
Check question
How is (17 · 23) mod 5 computed by taking remainders before multiplying?
17 mod 5 = 2 and 23 mod 5 = 3; 2 · 3 = 6 and 6 mod 5 = 1.
static int gcd(int a, int b) {
return b == 0 ? a : gcd(b, a % b);
}
System.out.println(gcd(48, 18)); // 6
long M = 1_000_000_007L, h = 0;
for (char c : "abc".toCharArray()) h = (h * 31 + c) % M; // the basis of a rolling hash
System.out.println(h); // 96354Binary numbers and bit operations
Computers store numbers in binary; powers of 2, shifts and masks shorten many algorithms. The bits of an integer can represent a subset; the expression 1 << k gives 2^k, and x & (x − 1) clears the lowest 1 bit. In the n-queens problem an O(1) safety test, and iterating over all subsets for small n, are done with bit masks.
Why it mattersRadix sort works digit by digit; the n-queens solution uses bit masks.
Check question
What is the binary representation of 13? What are 13 >> 1 and 13 & 1?
1101₂; 13 >> 1 = 6 (110₂) and 13 & 1 = 1 (the number is odd).
int n = 3;
for (int mask = 0; mask < (1 << n); mask++) { // 2³ = 8 subsets
StringBuilder s = new StringBuilder("[");
for (int i = 0; i < n; i++)
if ((mask & (1 << i)) != 0) s.append(i);
System.out.print(s.append("] "));
}
// [] [0] [1] [01] [2] [02] [12] [012]
System.out.println((16 & (16 - 1)) == 0); // true: 16 is a power of 2No topics match the search and filter.