Advanced Algorithms · Prerequisites

Prerequisites for Advanced Algorithms

Advanced Algorithms is the continuation of the Algorithms course; it assumes you know complexity analysis and sorting, searching, graph, and string algorithms. The course combines programming in Java, basic data structures, discrete mathematics, proof techniques, sums and logarithms, probability, and counting. The 20 topics on this page gather the background the course builds on into 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 reveals its answer.

Java and programming

What you need to read and trace the code in the slides and to write solutions in Java.

Arrays and two-dimensional arrays

indices from 0 · length · int[][]

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 matters

Sorting 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.

Example (Java)
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]);      // 5

Recursion and the call stack

base case · recursive call · depth

Merge sort, quicksort, DFS, backtracking, and divide-and-conquer algorithms are all 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 matters

Fast exponentiation, merge sort, recursive DFS, and the backtracking template are written directly with recursion.

Check question

In the call power(2, 10), counting the first call, how many times does the power method run?

5 times: n = 10, 5, 2, 1, 0.

Example (Java)
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

class · Comparable · Comparator · generics

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 matters

Most greedy algorithms begin with a sort; Dijkstra and Prim put comparable objects into a priority queue.

Check question

Why is it risky to write return w - o.w; inside compareTo?

With large positive and negative values the subtraction can overflow the int range and flip the sign; Integer.compare does not overflow.

Example (Java)
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);                // 7

Java collections

ArrayList · HashMap · ArrayDeque · PriorityQueue

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, and HashMap for memoization. Knowing the cost of each basic operation is a prerequisite for computing the total running time of an algorithm correctly.

Why it matters

BFS is written with a queue, Dijkstra with a priority queue, and 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 beginning to end.

Example (Java)
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 55

Basic data structures

The structures that algorithms operate on, and the cost of their basic operations. These structures are covered in detail in the prerequisite Data Structures course.

Linked lists

node · next · O(1) insertion at the head

Like an array, it stores a sequence, but the elements are not adjacent 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 all rely on linked lists.

Why it matters

Hash tables with chaining 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, and reaching that node requires walking from the head.

Example (Java)
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 + " ");

Heaps and priority queues

complete binary tree · array layout · O(log n)

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 extract-min take O(log n); heap sort, Dijkstra, Prim, Huffman, and the online median all rely on this structure.

Why it matters

Heap sort, the complexity of Dijkstra's algorithm, the construction of the Huffman tree, and the online median all rest 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); most nodes are close to the leaves, so the total sifting-down work stays linear.

Example
array:  [2, 5, 3, 9, 6, 4]
index:   0  1  2  3  4  5
children of 2: 5 and 3   (indices 1, 2)
children of 5: 9 and 6   (indices 3, 4)
child of 3:    4         (index 5)

Trees and binary search trees

root · parent · child · leaf · height

A tree with n nodes has n − 1 edges, and there is exactly one path between any two nodes. The terms root, parent, child, leaf, depth, and height are used unchanged for 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 matters

BFS trees, spanning trees, tries, and state-space trees are all described with the same terms.

Check question

What is the maximum number of nodes in a binary tree of height h?

2^(h+1) − 1 (if a single node is taken to have height 0).

Example
        8            height 2; leaves 1, 6, 14
      /   \
     3     10        parent of 3 is 8, children 1 and 6
    / \      \
   1   6      14     inorder traversal: 1 3 6 8 10 14

Discrete mathematics and proof

The language used to define algorithms and to prove them correct.

Sets, functions, and relations

∪ ∩ \ · |A| · f: A → B · relation

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 a knapsack. You should know union, intersection, difference, the Cartesian product, and subsets; the domain and codomain of a function; and the reflexive, symmetric, and transitive properties of relations.

Why it matters

The cut property, the transitive closure in Floyd-Warshall, and the feasible solutions in branch and bound are all defined with sets.

Check question

How many subsets does a set of n elements have, and which brute-force method costs that much?

2ⁿ; trying every selection one by one in subset sum or in the 0/1 knapsack.

Example
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.

Proof techniques: direct proof, contradiction, counterexample

direct proof · proof by contradiction · counterexample

We prove that an algorithm works on every input with a proof, and show that it is wrong with a single counterexample. The correctness of greedy algorithms is usually proved by contradiction or by an exchange argument; the claim “greedy change-making always gives the best answer” is refuted by a counterexample.

Why it matters

The correctness of greedy choices, the cut property of the MST, and 2-approximation ratios are all shown by proof.

Check question

Which technique is used to prove that √2 is irrational?

Contradiction: if √2 = p/q is assumed to be in lowest terms, both p and q must be even, which contradicts the assumption.

Example
Claim: greedy change-making uses the fewest coins in every coin system.
Counterexample: coins {1, 3, 4}, amount 6
  greedy: 4 + 1 + 1  → 3 coins
  best:   3 + 3      → 2 coins        ⇒ the claim is false.

Analysis tools

Sums, logarithms, and growth rates for computing running times.

Summation notation and series

arithmetic · geometric · harmonic

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 matters

Loop counting, summing the levels of a recursion tree, and the expected number of comparisons of randomized quicksort all 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).

Example
Σ (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

log₂ n · exponent rules · change of base

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 for exponents and logarithms, that the base of a logarithm is asymptotically irrelevant, and the approximation 2¹⁰ ≈ 10³.

Why it matters

The number of steps of binary search, the n^(log_b a) term in the master theorem, and the exponent n^1.585 of Karatsuba are all computed with logarithms.

Check question

About how many comparisons does binary search make at most on a sorted array of one billion elements?

About 30, because 2³⁰ ≈ 1.07 · 10⁹.

Example
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 only changes a constant factor

Probability and counting

For measuring the size of search spaces and the behavior of randomized algorithms.

Combinatorics: permutations and combinations

multiplication rule · n! · C(n, k) · 2ⁿ

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 matters

Generating permutations, the brute-force solution of the TSP, and the size of the n-queens search tree are all 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? And if the columns must also be distinct?

8⁸ = 16,777,216 ways; if the columns are also distinct, 8! = 40,320 ways.

Example
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 tours

Probability basics

sample space · independence · conditional probability

Computing the success and error probabilities of randomized algorithms requires the sample space, events, complements, independent events, and conditional probability. An important pattern: if a single trial fails with probability p, all k independent trials fail with probability p^k; this is how the error of Monte Carlo algorithms is reduced.

Why it matters

The error analysis of the Miller–Rabin test and of Karger's algorithm uses exactly this pattern.

Check question

An algorithm finds the correct answer with probability 1/2 in a single run. What is the probability that at least one of 10 independent runs finds the correct answer?

1 − (1/2)¹⁰ = 1023/1024 ≈ 0.999.

Example
P(A ∪ B) = P(A) + P(B) − P(A ∩ B)
A and B independent  ⇔  P(A ∩ B) = P(A) · P(B)
Miller–Rabin: error per round ≤ 1/4  ⇒  after 20 rounds ≤ (1/4)^20 ≈ 9 · 10^−13

Expected value and linearity of expectation

random variable · E[X] · indicator variable

Results such as the expected O(n log n) running time of randomized quicksort are stated as expected values. Linearity of expectation, E[X + Y] = E[X] + E[Y], holds even when the variables are dependent; splitting a complicated count into a sum of 0/1 indicator variables and adding their probabilities is a standard technique.

Why it matters

The analyses of randomized quicksort, QuickSelect, and randomized paging are done with expected values.

Check question

The worst case of randomized quicksort is O(n²). Why do we say “expected O(n log n)”?

Because the pivot is chosen at random, the running time is a random variable; for every input its average is O(n log n), and O(n²) occurs only with a very small probability.

Example
Die: E[X] = (1 + 2 + … + 6) / 6 = 3.5
In a random permutation of n elements, let X be the number of elements that stay in place:
  X = X1 + … + Xn,  Xi = 1 (if element i stays in place),  P(Xi = 1) = 1/n
  E[X] = n · (1/n) = 1
Repeating a trial with success probability p until the first success: E[number of trials] = 1/p

Other mathematics and concepts

Matrices, modular arithmetic, bit operations, optimization, and the basics of concurrency used in particular chapters.

Matrix operations

row–column product · identity matrix · block form

Multiplying two n × n matrices directly takes n³ multiplications in three nested loops; Strassen reduces this number with block matrices. For adjacency matrices, the distance table of Floyd-Warshall, 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 matters

Matrix 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 on the right by this permutation matrix swaps the columns.

Example (Java)
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

Euclidean distance · Manhattan distance · triangle inequality · cross product

The Euclidean distance between two points in the plane is √((x₁ − x₂)² + (y₁ − y₂)²), while the Manhattan distance, measured on a grid with only horizontal and vertical steps, is |x₁ − x₂| + |y₁ − y₂|. If a distance measure satisfies the triangle inequality, d(a, c) ≤ d(a, b) + d(b, c): visiting a third point never shortens the path. 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), can be computed with integers; its sign tells whether P lies to the left of the 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 matters

The 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 the Euclidean distance, and the 2-approximation for 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 the line AB is the point P = (1, 5)?

The Euclidean distance is √(9 + 16) = 5 and the Manhattan distance is 3 + 4 = 7. Because the cross product 3 · 5 − 4 · 1 = 11 > 0, P is to the left of the line when looking from A toward B.

Example (Java)
static double euclidean(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(euclidean(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

a mod m · (a · b) mod m · GCD · prime numbers

Hash functions, the rolling hash of Rabin-Karp, pseudo-random number generators, and the Miller–Rabin test all work with modular arithmetic. You should 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 matters

Euclid's algorithm, the rolling hash, Miller–Rabin, and pseudo-random 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.

Example (Java)
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);                                     // 96354

Binary numbers and bit operations

& | ^ ~ << >> · powers of 2 · subset masks

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, the O(1) safety test and, for small n, the enumeration of all subsets are done with bit masks.

Why it matters

Radix 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).

Example (Java)
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 2

Decision and optimization problems

objective function · constraint · feasible solution · lower/upper bound

Greedy, dynamic programming, approximation, and branch-and-bound algorithms solve optimization problems: among the solutions that satisfy the constraints (the feasible solutions), we look for the one that maximizes or minimizes the objective function. The decision version of the same problem (“is there a solution with value at least K?”) is used in the discussion of P, NP, and NP-completeness. In a maximization problem, the value of every feasible solution is a lower bound on the optimum.

Why it matters

The knapsack problem, NP-hardness, approximation ratios, and the bounds in branch and bound are all expressed in this language.

Check question

In a maximization problem, a greedy algorithm finds a feasible solution of value 40, and the value of the fractional relaxation is 46. In what range does the optimum lie?

40 ≤ OPT ≤ 46: the feasible solution gives a lower bound, and the relaxation gives an upper bound.

Example
0/1 knapsack, capacity W = 5
  items (weight, value): 1 = (2, 3), 2 = (3, 4), 3 = (4, 5)
  feasible: {1, 2} → weight 5, value 7      not feasible: {2, 3} → weight 7
  optimization: what is the largest value?             → 7
  decision: is there a feasible choice with value ≥ 8? → no

Concurrency basics

thread · shared variable · synchronization

The chapter on parallel algorithms uses Java to show how work is divided among several threads and how the results are combined. An intuitive grasp is enough: what a thread is, that two threads updating the same variable without protection cause a race condition, and that the sequential part of a program limits the speedup.

Why it matters

Race conditions, parallel sorting with fork/join, and Amdahl's law all build on these ideas.

Check question

If 20% of a program remains sequential, what is the largest speedup that can be obtained with an unlimited number of processors?

1 / 0.2 = 5 times (Amdahl's law).

Example (Java)
final AtomicInteger counter = new AtomicInteger();
Runnable job = () -> { for (int i = 0; i < 100_000; i++) counter.incrementAndGet(); };
Thread t1 = new Thread(job), t2 = new Thread(job);
t1.start(); t2.start();
t1.join(); t2.join();
System.out.println(counter.get());   // always 200000; an unprotected int++ may give less