Chapter 1: Foundations

Algorithms

What is an algorithm? (Cormen et al., 2022, p. 3)
18:49

Question

What is an algorithm?

Definition (Algorithm)

Sequence of computational steps that transform an input into an output

Example: Insertion sort (Cormen et al., 2022, p. 17)
18:49

Question

When playing cards, how would you sort your hand in ascending order?

Insertion sort
18:49

Here is a more standard implementation of insertion sort

Analysis of an algorithm
18:49

For every algorithm, we shall study the following properties.

Termination: Does the algorithm terminate?
Correctness: Does it yield the desired result?
Running time: How fast is the algorithm?

Correctess and Loop invariants of insertion sort (Cormen et al., 2022, pp. 19-21)
18:49

Definition (Loop invariant)

Property which is true before each iteration of a loop.

Loop invariants are important tools to show correctness.

Proposition (Insertion sort's loop invariant)

The subarray A[:i] contains the first i elements of the original array in sorted order.

Running time
18:49

Question (Running time?)

Assume that $A$ has $n$ elements. If the cost of the $i$ -th line is $c_{i}$ , what is total running cost?

Let's consider the best and worst case scenarios

i = 1 \sum n i = \frac{n ( n + 1 )}{2}

Computing time
18:49

We are interested in $T (n)$ , where $T$ is the time an algorithm takes to solve a problem of size $n$ .

We shall only keep the asymptotic term:

T (n) = 2 n^{2} - 4 n + 10 ⟹ T (n) = Θ (n^{2})

$O$ -notation (Cormen et al., 2022, p. 54-55)
18:49

Let $f$ and $g$ be positive functions.

Definition ( $O (g)$ )

$f \in O (g)$ if there exist positive constants $C$ and $N$ such that

f (n) \leq C g (n), n \geq N .

As an abuse of notation, we shall write $f (n) = O (n)$ .

$Θ$ -notation (Cormen et al., 2022, p. 54-55)
18:49

Definition ( $Θ (g)$ )

$f \in Θ (g)$ if there exist positive constants $c, C$ and $N$ such that

c g (n) \leq f (n) \leq C g (n), n \geq N .

As an abuse of notation, we shall write $f (n) = Θ (n)$ .

Algorithmic families
18:49

$O (1)$: Constant
$O (lo g n)$: Logarithmic
$O (n)$: Linear
$O (n^{2})$: Quadratic
$O (n^{p})$: Polynomial
$O (2^{n})$: Exponential
$O (n!)$: Factorial

Exercises: $O$ -notation
18:49

Programming tasks
18:49

Exercise

Given an array A of $n$ sorted elements, write an algorithm that would search for a given value. What's the running time?
Assume A is an array of elements which are increasing then decreasing. Write an algorithm that finds the maximum value. What's its running time?
Given an array of strictly the characters R, G, and B, segregate the values of the array so that all the Rs come first, the Gs come second, and the Bs come last. You can only swap elements of the array. Do this in linear time and in-place.

Divide et impera
18:49

A common stategy is divide-and-conquer.

Divide into similar subproblems
Conquer by solving them recursively
Combine the subproblem solutions to solve the original problem

Merge sort: example
18:49

Example

Sort the following array: [11, 6, 3, 24, 46, 22, 7]

Merge sort
18:49

Running time of merge sort (Cormen et al., 2022, pp. 42-43)
18:49

Proposition (Running time of merge sort)

T (n) = O (n lo g n)

Guess an expression for $T (n)$
Rigorous proof by induction

Sorting olympics
18:49

Insertion sort

Merge sort

Solving recurrences (Cormen et al., 2022, p. 90)
18:49

Information (Substitution method)

Guess the form of the solution using symbolic constants
Proof by induction

Example

Show that the recurrence $T (n) = 2 T (⌊ n /2 ⌋) + Θ (n)$ has solution $T (n) = O (n lo g n)$ .

Exercises: solving recurrences (Cormen et al., 2022, pp. 94-95)
18:49

Exercise

Use the substitution method to show that each of the following recurrences has the asymptotic solution specified:

$T (n) = T (n - 1) + n$ has solution $T (n) = O (n^{2})$
$T (n) = T (n /2) + Θ (1)$ has solution $T (n) = O (lo g n)$
$T (n) = 2 T (n /2) + n$ has solution $T (n) = O (n lo g n)$
$T (n) = 2 T (n /2 + 17) + n$ has solution $T (n) = O (n lo g n)$
$T (n) = 2 T (n /3) + Θ (n)$ has solution $T (n) = Θ (n)$
$T (n) = 4 T (n /2) + Θ (n)$ has solution $T (n) = Θ (n^{2})$

Exercise (Lower-order term trick)

Show that $Θ (n^{2})$ is the solution to the recurrence $T (n) = 4 T (n /2) + n$ .

Exercises: solving recurrences part II (Cormen et al., 2022, p. 101)
18:49

Exercise

For each of the following recurrences, sketch its recursion tree, and guess a good asymptotic upper bound on its solution. Then use the substitution method to verify your answer.

$T (n) = T (n /2) + n^{3}$
$T (n) = 4 T (n /3) + n$
$T (n) = 4 T (n /2) + n$
$T (n) = 3 T (n - 1) + 1$

Exercise (Master theorem)

Assume that $T (n) = a T (n / b) + f (n)$ , with $a$ and $b$ being integers. If $f (n) = O (n^{l o g_{b} a - ε})$ for some $ε > 0$ , then $T (n) = Θ (n^{l o g_{b} a})$ .

Recurrences: Avoiding pitfalls (Cormen et al., 2022, pp. 93-94)
18:49

Exercise

Find the mistake in the reasoning below:

T (n) = 2 T (⌊ \frac{n}{2} ⌋) + Θ (n) .

We can check that $T (n) = O (n)$ satisfies the recurrence relation, as

T (n) \leq 2 O (⌊ \frac{n}{2} ⌋) + Θ (n) = O (n) + Θ (n) = O (n) .

Comparison of sorting algorithms
18:49

	Insertion sort	Merge sort	Quicksort
In place	Yes	No	Yes
Comparison	Yes	Yes	Yes
Stable	Yes	Yes	No
Worst case runtime	$O (n^{2})$	$O (n lo g n)$	$O (n^{2})$
Average case runtime	$O (n^{2})$	$O (n lo g n)$	$O (n lo g n)$
Best case runtime	$O (n)$	$O (n lo g n)$	$O (n lo g n)$

Comparison sort: Only uses comparisons to chose between different permutations
Stable sort: Maintain the order of identical elements

We shall see later that $O (n lo g n)$ is the best we can do for comparison sorts.

Quick sort: example
18:49

Example

Sort the following array: [11, 6, 3, 24, 46, 22, 7]

Exercise

Apply (by hand) the quicksort algorithm to:

A = [13, 19, 9, 5, 12, 8, 7, 4, 21, 2, 6, 11]

A first implementation of quicksort
18:49

The real quicksort is in place. Here, we use the first element as pivot.

Hoare partition's scheme (Cormen et al., 2022, pp. 183-184)
18:49

Example (Hoare partition's scheme)

Apply the Hoare partition scheme on [11, 6, 3, 24, 46, 22, 7]

Exercise

Illustrate the partition operation on the array

A = [13, 19, 9, 5, 12, 8, 7, 4, 21, 2, 6, 11]

In-place partitioning (Cormen et al., 2022, p. 184)
18:49

Proposition (Invariant)

In ${start, \dots, i - 1}$ , the elements are $\leq pivot$ .
In ${i, \dots, j - 1}$ , the elements are $> pivot$ .

Exercises
18:49

Exercise

Describe the worst case for quicksort. What's the runtime?
Describe the best case for quicksort. What's the runtime?
What is the runtime of the algorithm if all the elements are equal?

Exercise

Without sorting, implement an algorithm that finds the $k$ -th smallest element.

The algorithm must be in place and $O (n lo g n)$ on average.

Runtime of quicksort
18:49

Proposition (Runtime of quicksort)

The worst-case runtime is $O (n^{2})$
The average case runtime is $O (n lo g n)$
The best case runtime is $O (n lo g n)$

Remark (Choice of pivot)

The algorithm may perform poorly. One idea would be to choose a random pivot.

Exercise

Implement Quicksort with a random pivot.

Multiplication algorithm
18:49

Fast multiplication of large numbers is essential in CAS, cryptography, etc.

For a long time, people thought that the multiplication algorithm we learn in primary school was optimal.

Question

Assume we have two numbers with $n$ digits.

What is the runtime of the traditional multiplication algorithm?
What is the runtime when you sum them?

Towards the Карацу́ба (Karatsuba) algorithm
18:49

Exercise

Assume $a, b, c, d$ are digits and calculate the product $(10 a + b) \times (10 c + d) .$ Compare the result with $(a + b) (c + d)$

Hence, use this to calculate $42 \times 14$ using 3 multiplications.

Exercise (Карацу́ба's trick)

Use Карацу́ба's trick to calculate $27 \times 32$ in 3 multiplications.

Карацу́ба's algorithm in Python
18:49

Karatsuba's runtime
18:49

Exercise

Calculate the runtime of Karatsuba's algorithm.

What about if we only did divide-and-conquer without applying Karatsuba's trick?

Hint: $a^{l o g_{b} c} = c^{l o g_{b} a}$

Closest pair of points
18:49

Problem (Closest pair of points)

Given $n$ distinct points $p_{1}, \dots, p_{n} \in R^{2}$ , find $i, j$ such that

dist (p_{i}, p_{j}) = i, j = 1, \dots, n i \neq = j min dist (x, y)

Question

What is the runtime of the brute-force algorithm?
Could you think of a faster algorithm using divide-and-conquer?

Closest pair: divide and conquer
18:49

Divide points into two halves using a vertical line
Conquer: Find closest pair in each side recursively
Combine: Find closest amongst pairs crossing the line

Question (Complexity of Step III)

Is it possible to do better than $O (n^{2})$ for Step III?

Idea

If the closest pairs in each sides have distances $δ_{1}, δ_{2}$ , we only need to look at a distance $δ = def min {δ_{1}, δ_{2}}$ from the line.

Closest pair: Step III
18:49

Idea (Ordering)

Sort these points by their $y$ -coordinate ( $O (n lo g n)$ ). We now need only check each pair against their immediate neighbours.

Proposition

Assume $s_{1}, \dots, s_{k}$ are sorted according to their $y$ coordinate. If $∣ i - j ∣ > 11,$ then $dist (s_{i}, s_{j}) \geq δ$ .

Closest pair: runtime
18:49

Theorem (Runtime of closest pair)

The runtime of our closest pair algorithm is $O (n lo g^{2} n) .$

Optimality of $O (n lo g n)$ for comparison sorts
18:49

Theorem

The running time of a comparison sorting algorithm is at best $O (n lo g n)$ .

Hint: $lo g n! = \sum_{i = 1}^{n} lo g n \approx \int_{1}^{x} lo g x = Θ (n lo g n)$

Counting sort: an example
18:49

Example

Sort the list

Keep a running tally
0 1 2 3 4 5 6 7 8 9
Recontruct the sorted list

Counting sort: Python implementation
18:49

Counting sort: running time
18:49

Proposition

The running time of counting sort is $O (n + k)$ , where $k$ is the number of admissible elements.

Stability
18:49

Definition

A sorting algorithm is called stable if it preserves the order of records with equal keys.

Exercise

Which of the following sorting algorithms are stable: insertion sort, merge sort, and quicksort? Give a simple scheme that makes any comparison sort stable. How much additional time and space does your scheme entail?

Exercise

How would you transform any comparison algorithm into a stable algorithm?

Stability and counting sort
18:49

Exercise

Write a stable algorithm that sorts integers on their last digit.

Is counting sort actually good?
18:49

An active open problem is the conjecture that a list of integers can be sorted in $O (n)$ . Currently, the best known algorithm sorts in $O (n lo g lo g n) .$

Counting sort is far from that conjecture. It is $O (n)$ when $k = O (n)$ .

Stable counting sort
18:49

Towards Radix sort
18:49

Idea

Use a stable counting sort to sort on the last digit, then on the penultimate, etc.

Example

Sort the list

717, 026, 785, 636, 955, 572, 772, 304, 935, 395.

Exercise

Use radix sort to sort the following words: COW, DOG, SEA, RUG, ROW, MOB, BOX, TAB, BAR, EAR, TAR, DIG, BIG, TEA, NOW, FOX.

Implementing Radix sort
18:49

Exercise

Implement Radix sort in Python. What is the invariant? Prove the algorithm is correct. What is its runtime?

Exercise

How would you sort $n$ integers in the range $0$ to $n^{3} - 1$ in $O (n)$ time.

Counting and Radix sort
18:49

Runtime of counting sort on ${1, \dots, k}$

O (n + k) .

Runtime of radix sort on ${1, \dots, k}$ :

O (lo g_{10} k) O (n + 10) = O (n lo g k) .

Observe that for a general base $b$ , radix sort works in $O ((n + b) lo g_{b} k) .$

We can check that this is optimas as

b = n

Correctness
18:49

Exercise (Correctness)

Prove the correctness of radix sort.

(Non-examinable) Towards Fourier analysis
18:49

Exercise

Calculate

\int_{0}^{1} e^{i 2 πn t} d t .

Discuss in terms of $n$ .

(Non-examinable) Fourier and Fast Fourier Transform
18:49

Question

Signals often take the shape:

f (t) = k \in Z \sum c_{k} e^{i 2 πk t}

How could we find the values $c_{k} ?$

Idea (Averaging)

What happens if we integrate both sides?

c_{k} = \int_{0}^{1} f (t) e^{- i 2 πk t} d t

Discrete Fourier Transform
18:49

f (t) = k \in Z \sum c_{k} e^{i 2 πk t}, c_{k} = \int_{0}^{1} f (t) e^{- i 2 πk t} d t

Definition (Discrete Fourier Transform)

X_{k} = def \frac{1}{N} n = 0 \sum N - 1 f (\frac{n}{N}) e^{- i 2 πk \frac{n}{N}}

Instead of an actual function, we'll often have a discretization, so that the most common definition is

X_{k} = def n = 0 \sum N - 1 x_{n} e^{- \frac{2 πink}{N}}

Periodicity
18:49

X_{k} = def n = 0 \sum N - 1 x_{n} e^{- \frac{2 πink}{N}}

Proposition

X_{k + N} = X_{k}

Complexity of the DFT
18:49

X_{k} = def n = 0 \sum N - 1 x_{n} e^{- i 2 πk \frac{n}{N}}, k = 0, \dots, N - 1.

Proposition

Calculating all the discrete Fourier coefficients has a runtime of

O (n^{2}) .

The FFT
18:49

X_{k} = def n = 0 \sum N - 1 x_{n} e^{- i 2 πk \frac{n}{N}}, k = 0, \dots, N - 1.

Idea

Divide $x_{0}, x_{1}, \dots, x_{N - 1}$ into two sets: $x_{0}, x_{2}, \dots and x_{1}, x_{3}, \dots$
Calculate the DFTs on both subsets: $E_{k}, O_{k}, k = 0, \dots, \frac{N}{2} - 1.$
Conquer! They are enough to calculate $X_{k}$ for $k = 0, \dots, N - 1$ .

FFT in Python
18:49

Theorem

Calculate the running time of the FFT.

What is an algorithm? (Cormen et al., 2022, p. 3)18:49

Question

Definition (Algorithm)

Example: Insertion sort (Cormen et al., 2022, p. 17)18:49

Question

Insertion sort18:49

Analysis of an algorithm18:49

Correctess and Loop invariants of insertion sort (Cormen et al., 2022, pp. 19-21)18:49

Definition (Loop invariant)

Proposition (Insertion sort's loop invariant)

Running time18:49

Question (Running time?)

Computing time18:49

O-notation (Cormen et al., 2022, p. 54-55)18:49

Definition (O(g))

Θ-notation (Cormen et al., 2022, p. 54-55)18:49

Definition (Θ(g))

Algorithmic families18:49

Exercises: O-notation18:49

Programming tasks18:49

Exercise

Divide et impera18:49

Merge sort: example18:49

Example

Merge sort18:49

Running time of merge sort (Cormen et al., 2022, pp. 42-43)18:49

Proposition (Running time of merge sort)

Sorting olympics18:49

Insertion sort

Merge sort

Solving recurrences (Cormen et al., 2022, p. 90)18:49

Information (Substitution method)

Example

Exercises: solving recurrences (Cormen et al., 2022, pp. 94-95)18:49

Exercise

Exercise (Lower-order term trick)

Exercises: solving recurrences part II (Cormen et al., 2022, p. 101)18:49

Exercise

Exercise (Master theorem)

Recurrences: Avoiding pitfalls (Cormen et al., 2022, pp. 93-94)18:49

Exercise

Comparison of sorting algorithms18:49

Quick sort: example18:49

Example

Exercise

A first implementation of quicksort18:49

Hoare partition's scheme (Cormen et al., 2022, pp. 183-184)18:49

Example (Hoare partition's scheme)

Exercise

In-place partitioning (Cormen et al., 2022, p. 184)18:49

Proposition (Invariant)

Exercises18:49

Exercise

Exercise

Runtime of quicksort18:49

Proposition (Runtime of quicksort)

Remark (Choice of pivot)

Exercise

Multiplication algorithm18:49

Question

Towards the Карацу́ба (Karatsuba) algorithm18:49

Exercise

Exercise (Карацу́ба's trick)

Карацу́ба's algorithm in Python18:49

Karatsuba's runtime18:49

Exercise

Closest pair of points18:49

Problem (Closest pair of points)

Question

Closest pair: divide and conquer18:49

Question (Complexity of Step III)

Idea

Closest pair: Step III18:49

Idea (Ordering)

Proposition

Closest pair: runtime18:49

Theorem (Runtime of closest pair)

Optimality of O(nlogn) for comparison sorts18:49

Theorem

Counting sort: an example18:49

What is an algorithm? (Cormen et al., 2022, p. 3)
18:49

Example: Insertion sort (Cormen et al., 2022, p. 17)
18:49

Insertion sort
18:49

Analysis of an algorithm
18:49

Correctess and Loop invariants of insertion sort (Cormen et al., 2022, pp. 19-21)
18:49

Running time
18:49

Computing time
18:49

$O$ -notation (Cormen et al., 2022, p. 54-55)
18:49

Definition ( $O (g)$ )

$Θ$ -notation (Cormen et al., 2022, p. 54-55)
18:49

Definition ( $Θ (g)$ )

Algorithmic families
18:49

Exercises: $O$ -notation
18:49

Programming tasks
18:49

Divide et impera
18:49

Merge sort: example
18:49

Merge sort
18:49

Running time of merge sort (Cormen et al., 2022, pp. 42-43)
18:49

Sorting olympics
18:49

Solving recurrences (Cormen et al., 2022, p. 90)
18:49

Exercises: solving recurrences (Cormen et al., 2022, pp. 94-95)
18:49

Exercises: solving recurrences part II (Cormen et al., 2022, p. 101)
18:49

Recurrences: Avoiding pitfalls (Cormen et al., 2022, pp. 93-94)
18:49

Comparison of sorting algorithms
18:49

Quick sort: example
18:49

A first implementation of quicksort
18:49

Hoare partition's scheme (Cormen et al., 2022, pp. 183-184)
18:49

In-place partitioning (Cormen et al., 2022, p. 184)
18:49

Exercises
18:49

Runtime of quicksort
18:49

Multiplication algorithm
18:49

Towards the Карацу́ба (Karatsuba) algorithm
18:49

Карацу́ба's algorithm in Python
18:49

Karatsuba's runtime
18:49

Closest pair of points
18:49

Closest pair: divide and conquer
18:49

Closest pair: Step III
18:49

Closest pair: runtime
18:49

Optimality of $O (n lo g n)$ for comparison sorts
18:49

Counting sort: an example
18:49

Counting sort: Python implementation
18:49

Counting sort: running time
18:49

Stability
18:49

Stability and counting sort
18:49

Is counting sort actually good?
18:49

Stable counting sort
18:49

Towards Radix sort
18:49

Implementing Radix sort
18:49

Counting and Radix sort
18:49

Correctness
18:49

(Non-examinable) Towards Fourier analysis
18:49

(Non-examinable) Fourier and Fast Fourier Transform
18:49

Discrete Fourier Transform
18:49

Periodicity
18:49

Complexity of the DFT
18:49

The FFT
18:49

FFT in Python
18:49

Revision
18:49

Revision
18:49

Revision
18:49