You manage a scheduling system for a conference room, and want to schedule as many meetings as possible, with no overlap between meetings and no rearranging of meeting times.

Let us call meetings jobs, the general term for this problem. Job \(j\) starts at time \(s_j\) and finishes at \(f_j\). Two jobs are compatible [to be scheduled] if they do not overlap.

Our goal is to make an algorithm with the following inputs and outputs

• in: A sequence of jobs (which are just pairs \((s_j,f_j\))
• out: The maximum subset of mutually compatible jobs

We can use a greedy algorithm to solve this, but we need the rules that allow us to implement it. We'll sort the jobs by a specific rule, then take jobs in order, provided they are compatible with all the jobs already selected.

This ordering rule can be many things: earliest start time, earliest finish time, or shortest interval time being some possibilities. (You can try work out which one is correct, but I'm going to immediately reveal it below.)

This is the correct sort rule. We can write an algorithm, for jobs \(j_i\) with starts/finishes \((s_i, f_i)\) for \(i = 1..n\).

We can prove this algorithm runs with \(O(n \log n)\). This is because:

Theorem. The Earliest Finish First (EFF) algorithm is optimal.

You are in charge of scheduling lectures into lecture rooms. Lecture \(j\) starts at \(s_j\) and finishes at \(f_j\), and your goal is to find the minimum number of classrooms needed to schedule all lectures such that no two overlap.

• in: A sequence of jobs (which are just pairs \((s_j,f_j\))
• out: The smallest possible collection of sets (classrooms) of compatible jobs

(As the section implies) we use a greedy algorithm, and need to decide the ordering rule. This can be: Earlist start first, Earliest finish first, Shortest lecture first, or something else.

This is the correct sort rule.

Running Time

If we use a suitable data structure to store the rooms in, this algorithm can be \(O(n \log n)\).

This implementation will always schedule the next compatible lecture in the room with the earliest finish time.

Definitions and Observations

Definition. The Depth of a set of open intervals is the max number of intervals that contain some point. Basically, the point where the most lectures overlap from all rooms determines the depth, which is the number of rooms.

Minimum number of rooms would equal the depth (since no lectures can overlap)

Also take note that the Earliest Start First (ESF) never schedules two incompatible lectures in one room.

Proof of Correctness

Theorem. ESF is optimal.

Minimising Lateness

You are in charge of a single mainframe that can process one job at one time. Job \(j\) requires \(t+j\) units of time to process and is due at \(d_j\) (but can be late). (If \(j\) starts at \(s_j\) it finishes at \(f_j = s_j + t_j\).) Your goal is to schedule jobs to minimise maximum lateness.

Let lateness be defined \(\ell_j = \max(0, f_j - d_j)\), and max lateness is thus \(L = \max(\textrm{all } \ell_j)\).

• in: A sequence of jobs (which are just pairs \((t_j,d_j\))
• out: An ordering of jobs with the least amount of lateness.

Some rules we can consider are order by: shortest processing time, earliest deadline, or shortest slack (\(d_j-t_j\)).

Earliest Deadline First

Important Observations and Lemmas

1. There exists an optimal schedule with no idle time. If we have a schedule with idle time between jobs, which has no lateness, we can simply remove all idle time and still have no lateness.

2. Earliest Deadline First (EDF) has no idle time by design.

Definition. Given a schedule S, an inversion is a pair of jobs \(i, j\) where \(i < j\) (meaning i is due before j) and \(j\) is scheduled before \(i\).

3. The EDF schedule is the (unique) schedule with no inversions (by design).

4. If some schedule with no idle time has an inversion, then it has an adjacent inversion (inverted jobs are next to each other)

Key Lemma. Eschanging two adjacent inverted jobs \(i, j\) reduces the number of inversions by one, and does not increase maximum lateness.

Proof of Correctness

Theorem. EDF is optimal.

Three strategies were explored for analysing and proving the optimality of greedy algorithms.

Greedy Stays Ahead

Demonstrating that after each incremental step, the greedy algorithm solution is at least as good as any other solution. This incremental building was employed in the proof of Interval Scheduling.

Structural Bound

Discover a simple bound / principle on the structure of the problem, which gives the lowest (most optimal) bound on possible solutions, and show that the greedy algorithm always reaches that bound. This was employed in Interval Partitioning with the depth bound.

Exchange Argument

By gradually transforming a hypothetical optimal solution (which is not the greedy algorithm one) into the greedy algorithm solution without hurting its quality. This was employed by swapping inversions in Minimising Lateness.

Single pair shortest paths

Problem. Given a digraph \(G = (V, E)\), with edge lengths \(\ell_e \geq 0\), a source \(s \in V\) and a destination \(t \in V\), find the shortest directed path from s to t.

Called single pair because there is one source and one destination.

Variations

We can also have just single source shortest path, where from a source we have to find the path to ALL other vertices (i.e. tree rooted at S).

Djikstra's Algorithm

Djikstra's is a well known algorithm for single source shortest path. It is a greedy algorithm, and works on graphs with non-negative weights only.

• Maintain a set of explored nodes S and an array \(d : d_u =\) length of shortest path \(s \leadsto u\).
• Initially set \(S \longleftarrow \{s\};\; d_s \longleftarrow 0\).
• Repeatedly choose new \(v \not \in S\) which minimises the "path value" of \(v: \pi(v)\). \[\pi(v) = \min_{e = \langle u, v \rangle : u \in S}(d_u + \ell_e)\] i.e. pick the edge leading out from any node \(u\) in the explored set which has the smallest \(d_u + \ell_e\) value.
• Add that \(v\) to S, and set \(d_v \longleftarrow \pi(v)\). If we need to recover the path later, store also the edge that lead to \(v\).

Proof of correctness

Assertion. For all nodes \(u \in S, \; d_u\) is the length of the shortest path.

An efficient implementation - optimisations

Optimisation 1. For all unexplored nodes \(v \not \in S\), explicitly maintain \(\pi(v)\) instead of computing from definition each time. Initialise it to \(\infty\) when we don't have a value.

\(\pi(v)\) can only decrease, since S increases and we allow more nodes into the minimisation formula. Suppose we do get a \(u\) added to S, with an edge \(e = \langle u, v \rangle\), it is sufficient to compute just \[\pi(v) = \min(\pi(v), \pi(u) + \ell_e)\]

Optimisation 2. Use a min-oriented priority queue to choose unexplored node \(v\) as efficiently as possible, sorting by the value \(\pi(v)\).

Implementation pseudocode

Time complexity

The running time is dominated by the number of priority queue operaions. We insert, delete minimum, and decrease key a total of \(O(n)\) times. Our implementation of the priority queue thus determines our running time.

Note that \(m\) is used for the number of edges, which is \(\Theta(n)\) on sparse graphs and \(\Theta(n^2)\) on dense graphs.

For dense graphs, a node-indexed array is best, whilst for sparse graphs, a binary heap is best.

Cutsets

Definition. A cut is an arbitrary partition of nodes into two non-empty sets: \(S, V \setminus S \;(\textrm{or } V - S)\).

Definition. A cutset of cut S is the set of edges : each edge has exactly one endpoint in S.

Cycle-cut intersetion

Proposition. An (arbitrary) cycle intersects a cutset on an even number of edges.

Proof. by picture:

In short, if a cycle and cut don't intersect, we're all OK. If a cycle starts in the cut and leaves the cut, it must eventually return, so leaving and returning matches, making pairs. $$\tag*{$\Box$}$$

Spanning and Minimum Spanning Trees

A spanning tree is a subgraph that is acyclic and connected. See here for notes on spanning trees.

Given an undirected, connected graph with weights, the minimum spanning tree is the spanning tree with minimum edge cost.

Theorem. Cayley's Theorem. A complete graph \(k_n\) has \(n^{n-2} \) spanning trees.

This theorem means though that brute-forcing spanning trees is a no-no.

Fundamental cycle

Define. Let \(H=(V, T)\) be spanning tree of \(G = (V, E)\). For any non-tree edge \(e \in E, \; T \cup \{e\}\) contains a unique cycle C (maximal acylcic).

Divide and Conquer Paradigm

Divide and conquer is a strategy for solving algorithms where the main problem is divided into independent subproblems, which are then solved (conquered) recursively.

In general, this goes as follows:

• Divide a problem of size \(n\) into subgroups, e.g. 2 subproblems of size \(\frac{n}{2}\) - typically \(O(n)\)
• Solve the 2 subproblems recursively
• Combine the subproblems into one - typically \(O(n)\)

Process

• For an input size (n), divide into a left half and a right half. - \(O(n)\)
• Recursively sort left and right halves (refer to above)
• Combine two sorted halves, maintaining the order. - \(O(n)\)

Combining halves

Suppose we have two sorted halves A and B, with \[A = [a_1, a_2, a_3], \; B = [b_1, b_2, b_3, b_4]\] Maintain two pointers to the sorted arrays. Scan A and B, comparing \(a_i\) and \(b_j\). Append the smaller value to the output list, and increment that pointer only. Finally, append any left over values from one array if the other has reached the end.

Linear for scanning, constant for comparing, constant for appending.

Implementation

Let's say mergesort has a procesing time of \(T(n)\). Thus, every subproblem (\(A, B\)) takes \(T(\frac{n}{2})\) time. The merge portion as we know is linear, and is \(\Theta(n)\).

Thus we can conclude \(T(n)\) is bounded by \(\Theta(n) + 2T(\frac{n}{2})\).

Useful recurrence relation

The above gives rise to a useful recurrence relation.

Definition. Let \(T(n)\) to be the number of comparisons mergesort makes proportional to list size \(n\). This satisfies the recurrence \[T(n) = \begin{cases} 0 & \textrm{if } n = 1 \\ T(\left \lfloor{\frac{n}{2}} \right \rfloor) + T(\left \lceil{\frac{n}{2}} \right \rceil) + n & \textrm{if } n > 1 \end{cases}\]

Complexity of merge sort

Claim. For mergesort, \(T(n) = O(n \log n)\).

Assume \(n\) is a power of 2. This does not affect the integrity much but makes proving easier.

The following proofs demonstrate important techniques so are shown by default. Clicking the drop-down bar (twice) will hide them.

Proof by tree

Assertion 1. \(T(n) = O(n \log n)\) if \(T(n)\) satisfies the following recurrence (given above assumption): \[T(n) = \begin{cases} 0 & \textrm{if } n = 1 \\ 2T(\frac{n}{2}) + n & \textrm{if } n > 1 \end{cases}\]

Proof. Represent the recurrence in tree form:

• On level \(i\), there are \(2^i\) nodes. Each node has \(\frac{n}{2^i} \) items so does that amount of work. Thus each level does \(n\) work.
• \(n = 2^k\) (is a power of 2), and we halve \(n\) every time, thus we do \(k\) halvings to get to \(2^0\): 1 item. Thus \(k\) = the number of levels = \(\log_2 n\).

\(\log_2 n\) times \(n\) work gets \(O(n \log n)\) $$\tag*{$\Box$}$$

Proof by induction

A proof method that may be easier to use (and certainly is easier to represent in HTML). We use the same proposition as above.

Extending inductive proof

So far we have been ignoring floors and ceilings. In fact, we can take as granted that floor and ceil may be ignored outright. However, here's an inductive proof for the assertion that uses floor and ceil.

Assertion 2. \(T(n) \leq n \left \lceil{\log_2 n} \right \rceil\) if \(T(n)\) satisfies the following recurrence. \(n\) is not assumed to be a power of 2.

Problem

Given \(n\) points in a euclidean plane, find the closest pair of points.

Possible non-divide and conquer solutions

Listed are some non-divide and conquer solutions, for interest.

The divide and conquer algorithm

Definition. the non-degeneracy assumption asserts that each point should have a unique \(x\) coordinate.

We divide by drawing a vertical line \(L : \frac{n}{2}\) points on each side. We conquer by recursively finding the closest point in each "half". We combine by checking if there's a closer pair that lies across the boundary.

It seems initially hard to do this more efficiently than the brute force \(n^2 \), but there are a few tricks we can employ.

Take the minimum distance from the pairs on either side, let it be \(\delta\). Say our two halves find closest points with length 12 and 21, \(\delta = \min(12, 21)\). It is the sufficient to only check points within \(\delta\) distance from L.

We need only sort the boundary points by their \(y\) coordinate, then compute the closest points in \(y\). This much may be quite easy to understand, but that still leaves us with quadratic time if we have to compute distances to all other points, but in fact, we only need to compute 7.

Every point checks against up to 7 others, and the minimum distance found is kept track of as the boundary points are iterated through. This actually will reduce our combine step down to linear time: \(O(n)\).

Why 7!?

To prove this, first let all boundary points be sorted by y coordinate, and numbered in increasing order, \(s_1, s_2, \dots, s_n\). \(s_i\) is the point with the \(i\)^th largest y value.

Proposition. If \(|i-j| \geq 7\), the distance between \(s_i, s_j\) is at least \(\delta\).

Let us take any point \(s_i\) with some \(y\) coordinate. Consider a rectangle \(\delta\) tall and \(2\delta\) wide, spanning the boundary region with its bottom being the \(y\) coord of \(s_i\). Split this rectangle into 8 squares, \((0.5\delta)^2\).

The furthest away two points could be in one single square is at opposite diagonals, \(\frac{\delta}{2}\) away. \(\frac{\delta}{2 } < \delta\) - this means that this is an impossible configuration: both points would be on the same side, with the distance between less than \(\delta\), which is defined to be the shortest distance from both sides.

Thus, there can only be one point per square. At most 7 other points may be valid options (have distances closer than \(\delta\)), so we need only check 7.

$$\tag*{$\Box$}$$

Implementation

Running time

The labelled sections are as follows: (1) is \(O(n)\), (2) is \(2T(\frac{n}{2})\), (3) is \(O(n)\), (4) is \(O(n \log n)\), and 5 is \(O(n)\).

As to \(T(n)\), knowing the running time of dividing and combining steps we can get the recurrence \[ T(n) = \begin{cases} \Theta(1) & n = 1 \\ T(\left\lfloor{\frac{n}{2}}\right\rfloor ) + T(\left\lceil{\frac{n}{2}}\right\rceil ) + \Theta(n \log n) & \textrm{otherwise} \end{cases} \]

This resolves down to a running time of \(\Theta(n \log^2 n)\).

Improvements on running time

Later work has been done to push the algorithm down to \(O(n \log n\). This involves techniques such as preserving sorting of delta strip, returning lists of points sorted by x and y, and sorting points by merely doing one merge, which is linear time.

Premise

The master theorem is a single method to solve all common recurrences of the form \[T(n) = aT(\frac{n}{b}) + f(n)\] Where \(a, b \in \mathbb{Z}^+\), \(b \geq 2\), and with \(T(0) = 0, \; T(1) = \Theta(1)\).

An input of size \(n\) makes \(a\) recursive calls of size \(\frac{b}{n}\). We also assume that \(f(n) \geq 0\).

Deriving via recursion trees

Master Theorem

Overview of proof

• Prove theorem when \(b \in \mathbb{Z}\) and \(n\) is a power of \(b\)
• Extend the domains of reasoning to rationals or reals
• Deal with floor and ceil for at most 2 levels, e.g. \begin{align} \left\lceil{\frac{\left\lceil{\frac{\left\lceil{\frac{n}{b}}\right\rceil }{b}}\right\rceil }{b}}\right\rceil & < \frac{n}{b^3} + (\frac{1}{b^2} + \frac{1}{b} + 1) \\ &\leq \frac{n}{b^3} + 2 \;\; (\because b \geq 2) \end{align}

Theorem extension

We can replace \(\Theta\) with \(O, \Omega\) with no problem.

We can replace the initial conditions with \(T(n) = \Theta(1)\) for all \(n \leq n_0\) (which is a constant) and only require the recurrence holds for \(n > n_0\).

Examples

\(T(n) = 3T(\left\lfloor{\frac{n}{2}}\right\rfloor + 5n\)

\(T(n) = T(\left\lfloor{\frac{n}{2}}\right\rfloor) + T(\left\lceil{\frac{n}{2}}\right\rceil ) + 17n \)

Gaps in master theorem

Master theroem will not work if the number of branches is not constant: \(T(n) = nT(\frac{n}{2 }) + n^2 \),

The number of subproblem branches is less than 1: \(T(n) = \frac{1}{2} T(\frac{n}{2}) + n^2\),

And cannot directly work if work done by subproblem is not \(\Theta(n^c)\): \(T(n) = 2T(\frac{n}{2 }) + n \log n\).

Addition and Subtraction

Numbers are stored and processed in computers at binary strings. This changes the considerations when doing basic arithmetic.

Looking at addition and subtraction first, i.e. given 2 binary strings \(a, b\) compute \(a+b\) and \(a-b\).

The addition and subtraction method one learns in primary school is the most efficient algorithm, at \(O(n)\) where \(n\) is the number of digits.

Multiplication

Problem. Given 2 \(n\) bit numbers, multiply them.

The "primary school algorithm" for binary multiplication, in short, is for every digit in the 2^nd number, write the corresponding shifted 1^st number multiplied by that digit. We can see that this performs \(\Theta(n^2)\) bit operations.

The question is, is the so-called "primary school algorithm" most efficient for multiplication?

The answer is no: one can do some divide and conquer tricks to make an algorithm more efficeint than this.

Karatsuba algorithm

An algorithm developed by Anatoly Karatsuba in 1960 allows us to do multiplication quicker than quadratic time.

Divide \(x, y\) into low and high bits as in warmup : \begin{align} \textrm{let } &m = \left\lceil{\frac{n}{2}}\right\rceil &x = 2^m a + b, \; y = 2^m c + d \\ \textrm{then } &a = \left\lfloor{\frac{x}{2^m}}\right\rfloor & b = x \mod 2^m \\ &c = \left\lfloor{\frac{y}{2^m}}\right\rfloor & d = y \mod 2^m \end{align} \begin{align} xy = (2^m a + b)(2^m c + d) &= 2^{2m} ac + 2^m(bc + ad) + bd \\ &=2^{2m} ac + 2^m(ac + bd - (a-b)(c-d)) + bd \end{align} We then have divided \(xy\) down into three (nontrivial) multiplication options.

Implementation

Running time

We have the recurrence \[T(n) = \begin{cases} \Theta(1) & n=1 \\ 3T(\left\lceil{\frac{n}{2}}\right\rceil + \Theta(n) & n > 1 \end{cases}\] Via master theorem \(log_b a \approx 1.585 \), thus \(T(n) = O(n^1.585)\).

Further comments

Integer multiplication, as one would think, is the base of many algorithms. Note that multiply, divide, square, and sqrt all have the same complexity.

Karatsuba's algorithm is still not optimal - better has been done after.

Overview

Dynamic programming involves breaking up a problem into smaller, overlapping supbroblems (of polynomial size), and then combine solutions to find an answer.

It's called dynamic programming for ... reasons, but a lot of dynamic programming solutions can be summed up with "caching intermediate values to look up later".

Problem

A job \(j\) starts and finishes at \(s_j, f_j\) respectively. It also has weight \(w_j\). Two jobs are compatible if there are no overlaps. We want the set of compatible jobs which maximises weight.

The original interval scheduling problem is a special case of this where all weights are equal.

Convention. Jobs are given in ascending order of finishing time: \(f_1 \leq f_2 \leq \dots \leq f_n\).

We define parameter \(p(j)\) to be the largest index \(i < j\) such that job i is compatible with job j: the job that finishes closest to \(s_j\) without overlapping. Index \(i\) starts at 1, and if a job doesn't have a compatible job before it, \(p(j) = 0\).

Bellman optimality equation

We can find the best possible value by representing this dynamic programming problem as a binary choice.

Consider \(n\) subproblems of only jobs \(1, 2, \dots, j\), where \(j\) ranges from \(1 .. n\).

Define. \(OPT(j)\) as the max weight of any subset of compatible jobs \(i .. j\).

Our goal is thus to find \(OPT(n)\).

Consider how we find \(OPT(j)\), if we already know all OPT values before \(j\).

1. \(OPT(j)\) does not include job \(j\): \(OPT(j) = OPT(j-1)\), since removing job \(j\) does not affect optimality.
2. \(OPT(j)\) includes job \(j\): the total weight of OPT includes \(w_j\). The rest of the jobs that are compatible cannot overlap with \(s_j\), thus the latest possible previous job is \(p(j)\). \[\implies OPT(j) = OPT(p(j)) + w_j\]

Brute-force implementation

We can try program this in a recursive, "brute-force" way.

Complexity

The important part of working out running time is computeOpt. It may be difficult to work out, but the running time of this algorith is actually \(O(\phi^n)\) - yes, that phi.

The recursive approach is very slow, since the subproblems are overlapping, the number of recursive calls grows like the fibonacci system (which is why we get phi).

This is not very good.

Memoisation

"Top-down dynamic programming", or memoisation, a fancy way of saying having a global array that you store previous results of OPT so you don't need to spend time computing it over and over again.

Generally the global array is called \(M\), and can also store a special symbol (e.g. \(-1, \infty\)) to represent "uncalculated".

Memoisation implementation

Complexity

Claim. This algorithm has time complexity \(O(n \log n)\)

Finding the optimal schedule

So far we have found the optimal value, but no actual solution. Luckily finding the solution can be done in linear time.

Since there is only one recursive call, this is linear time. We can combine this with the above algorithm to find a proper optimal schedule in \(O(n \log n)\).

Problem

There are \(n\) items. Item \(i\) has value \(v_i > 0\) and weights \(w_i > 0\). The value of a set of items is ìs the sum of their values. We also have a knapsack, which can hold a total of \(W\) weight.

Goal. Given a set of items and a knapsack with a set weight, maximise the value of items that knapsack can carry.

We assume weights and values are all integers.

Dynamic programming subproblems

We have two variables, \(i, w\), and so we need a dynamic progrmaming setup which allows us to split on both, and get a function \(OPT(i, w)\).

Define. \(OPT(i, w)\) as optimal value of knapsack with items \(1..i\) subject to weight \(w\).

Our goal is \(OPT(n, W)\).

Bellman Equation

When we reach item \(i\), we want to know if it's in OPT or not. So we have the following cases.

1. \(OPT(i, w)\) does not include \(i \implies OPT(i, w\) selects best items from \(1, 2, \dots, i-1\).
2. \(OPT(i, w)\) includes \(i \implies\) we (a) collect value \(v_i\), (b) get a new weight limit \(w-w_i\), (c) OPT keeps on selecting according to new weight limit \(w-w_i\).

Bottom-up programming

Looking at the final table, we start from the bottom right [n][W] corner. If the value above is the same, then \(i\) for that row not chosen. If value above is less, \(i\) is chosen, take \(v_i\) away from current value and find first occurence of that in row above.

Complexity

This algorithm has \(\Theta(nW)\) time and space complexity, which should be easy enough to see.

Problem

Given two strings (like occurrance and ocurrence), we want to know how "similar" they are. However this is very vague. How could we measure difference?

Possible solution considerations

We could align strings from first letter:
occurrance
ocurrence
This has 6 mismatches and 1 "gap" (where a letter matches onto an empty space). But what is the best alignment?

Perhaps we want to minimise both gaps and mismatches:
occurrance
oc urrence
This has one gap and one mismatch.

Perhaps however we think mismatches are much, much worse than gaps:
occurra nce
oc urr ence
Now we have no mismatches, but three gaps.

What we decide for the gap/mismatch weighting on will change based on the context said problem is in.

Edit distance

Edit distance. (Lehvenstein 1966) A measure of the "cost" of editing one string into another, with a gap penalty of \(\delta\), and a mismatch penalty for two letters \(pq\) to be \(\alpha_{pq}\).

The cost is then \(\sum \delta + \sum \alpha_{pq} \).
CT GACCTACG
CTGGACGAACG
has cost \(\delta + \alpha_{CG} + \alpha_{TA} \).

Sequence alignment algorithm

Problem. Given 2 strings \(x_1 x_2 \dots x_n\) and \(y_1 y_2 \dots y_n\), minimise the edit distance.

Define. An alignment M is a set of ordered pairs \(x_i - y_j\) such that each character appears in at most 1 pair, and there are no crossings:
\(x_i x_j\)

Define. the cost of alignment to be \[ cost(M) = \sum_{(x_i, y_j) \in M} \alpha_{x_i y_j} + \sum_{i : x_i \textrm{ unmatched}} + \sum_{i: y_i \textrm{ unmatched}} \] i.e. the mismatch penalty for two letters \(x_i y_j\) (may be 0), and the cost of all unmatched letters.

Problem Structure

Define. \(OPT(i, j)\) as the min cost of aligning prefix strings \(x_1 x_2 \dots x_n\) and \(y_1 y_2 \dots y_n\). Our goal is thus \(OPT(m, n)\).

There are only three options for \(x_i, y_i\):

1. \(OPT(i, j)\) matches \(x_i\) to \(y_j\). We pay the penalty (if any) \(\alpha_{x_i y_j} \) and the minimum possible cost of \(OPT(i-1, j-1)\).
2. \(OPT(i, j)\) leaves \(x_i\) unmatched. Then we pay gap penalty and min cost of \(OPT(i-1, j)\)
3. \(OPT(i, j)\) leaves \(y_j\) unmatched. Then we pay gap penalty plus min cost of \(OPT(i, j-1)\)
Thus our bellman equation goes as follows: \[ OPT(i, j) = \begin{cases} j \cdot \delta & i = 0 \\ i \cdot \delta & j = 0 \\ \min\begin{cases} \alpha_{x_i y_j} + OPT(i-1, j-1) \\ \delta + OPT(i-1, j) \\ \delta + OPT(i, j-1) \end{cases} & \textrm{otherwise. } \end{cases} \]

Bottom up implementation

Complexity

Theorem. The algorithm solves edit distance in \(\Theta(mn)\) time.

The proof is trivial and left as an exercise to the reader.

We can backtrace the algorithm to find the optimal alignment itself.

Problem

Problem. Given a directed graph \(G=(V,E)\) with arbitrary edge lengths \(\ell_{vw} \), find the shortest path from some vertex \(s\) to \(t\), assuming said path exists.

Djikstra fails

Base djikstra does not work on these types of graphs. Even adding an equal constant to all edges to teporarily remove negatives, then doing Djikstra, does not work.

On negative cycles

Definition. Negative cyces are directed cycles where the sum of weights is less than 0.

Negative cycles makes this problem somewhat difficult.

Lemma 1. If there exists a path \(v \leadsto t\) which contains any part of a negative cycle, the shortest path \(v \leadsto t\) does not exist.

Lemma 2. If there are no negative cycles, \(\exists\) shortest path \(v \leadsto t\; \forall v, t\) that is simple (no repeat vertices).

Formal problems

We can formulate some formal problems:

Single Destination Shortest Path. Given a digraph \(G = (V, E)\) with edge weights \(\ell_{wv}\), no negative cycles, and a destination node \(t\), find the shortest \(v \leadsto t \; \forall v \in V\).

Negative Cycle. Given a digraph \(G = (V, E)\) with weights \(\ell_{wv} \), find if a negative cycle exists.

Dynamic programming for shortest path

Define. \(OPT(i, v)\) as the length of the shortest path \(v \leadsto t\) that uses \(\leq i\) edges.

Our goal is thus \(OPT(n-1, v)\)

We have two cases:

1. \(OPT(i, v)\), the shortest path, uses strictly \(< i\) edges. \[OPT(i, v) = OPT(i-1, v)\]
2. The shortest path uses exactly \(i\) edges. Then let \((v, w)\) be the first edge on that path, with weight \(\ell{vw} \). This edge has to be optimal (because dynamic programming). \[OPT(i, v) = \ell_{vw} + OPT(i-1, w)\] (Find path \(w \leadsto t\))

Bellman equation

\[ OPT(i, v) = \begin{cases} 0 &i=0,v=t \\ \infty &i=0,v\neq t \\ \min \begin{cases} OPT(i-1, v) \\ \min_{\forall (v, w) \in E}(OPT(i-1, w) + \ell_{vw}) \end{cases} &i>0 \end{cases} \]

Implementation

Complexity

Theorem 1. Given a digraph with no negative cycles, we can get the length of the shortest path \(\forall v \in V\) in \(\Theta(mn)\) time and \(\Theta(n^2)\) space.

Finding paths

This algorithm so far only finds optimal lengths. To find optimal paths, we could

(Either) Maintain an array successor[(i, v)] that points to the next node on the shortest path \(v \leadsto t\) using \(\leq i\) edges, when we are setting M.

(Or) After getting the optimal length \(M[i, v]\), consider only the edges such that \(M[i, v] = M[i-1, w] + \ell_{vw} \) Any path that satisfies this all the way to \(i=0\) that is satisfactory is shortest.

Bellman Ford Moore algorithm

The Bellman-Ford-Moore (BMF) algorithm is an improvement on the shortest path algorithm.

• Space optimisation. Maintain 2 1d arrays (for linear space): \(d:d[v] \) is the length of shortest path \(v \leadsto t\) found so far; and \(\textrm{succ}: \textrm{succ}(v)\) is the next node on said \(v \leadsto t\) path.
• Performance optimisation. If \(d[w] \) is not updated in iteration \(i-1\), there is no reason to consider other edges going into \(w\) in iteration \(i\).

Implementation

Complexity

Lemma 3. For each \(v \in V, \; d[v]\) is the length of some \(v \leadsto t\) path.

Lemma 4. The value of \(d[v]\) cannot increase

Lemma 5. After iteration \(i\), \(d[v] \leq\) length of the shortet path with \(\leq i\) edges. (Please note the inequality, versus the equality of the original algorithm).

Theorem 2. Assuming no negative cycles, BFM solves in \(O(mn)\)* time and \(\Theta(n)\) space.

* Note: \(O(mn)\) not \(\Theta(mn)\). BFM is typically faster than \(\Theta(mn)\).

Edge \(\langle v, w \rangle\) is considered in pass \(i+1 \) only if \(d[w] \) is updated in pass \(i\). If the shortest path has \(k\) edges, the algorithm will find it after \(\leq k\) passes.

Getting the path

Claim. Throughout the BFM algorithm, following \(succ[v] \) pointers gives directed path from \(v \leadsto t\) of length \(d[v]\).

Counterexample. This is false - the length of \(succ[v]\) path may be shorter than \(d[v]\).

Consider the graph, with nodes \(t, 1, 2, 3\). The state of the graph is shown after the algorithm is ran on \(t, 1, 2\).

Now we consider 3, we scan incoming edges: edge from 1, \(d[1] = 10\), but \(\ell_{\langle 1, 3\rangle} = 1\), thus \(1 \leadsto t\) has a length of 2.

Update \(d[1] \longleftarrow 2, succ[1] \longleftarrow 3\). We are now done.

Look at node 2. \(d[2] = 20\) but the path \(\langle 2 1 3 t \rangle\) is of length 12, which is shorter than \(d\).

Successor graphs

If the graph has negative cycles, BFM may produce a successor graph which has a cycle.

Suppose we've considered nodes \(t, 1, 2, 3\), but not 4 (state shown). Consider the incoming edge \(\langle 1, 4 \rangle\). \(d[1] = 5\), but \(\ell_{\langle 1, 4\rangle} = -8, \; d[4] = 11, \; 11-8 < 5\), so we update \(d[1] \longleftarrow 3, \; succ[1] \longleftarrow 4\).

Now the successor edges form a cycle, and none will ever reach \(t\).

BFM and negative cycles

Lemma 6. Any directed cycle W in a successor graph produced by BFM is a negative cycle.

Correctness

Theorem 3. If there are no negative cycles, BFM algorithm will find the shortest paths.

Better algorithms than BFM have been developed in more recent years.