• MergeSort: Motivation and Example (Section 1.4, part 1)
• MergeSort: Pseudocode (Section 1.4, part 2)
• MergeSort: Analysis (Section 1.5)

Kotlin ```java fun sort(A: IntArray): IntArray { fun merge(A: IntArray, B: IntArray): IntArray { var C = mutableListOf() var i = 0 var j = 0 while (i < A.size && j < B.size) if (A[i] < B[j]) C.add(A[i++]) else C.add(B[j++]) A.slice(i..A.lastIndex).forEach { C.add(it) } B.slice(j..B.lastIndex).forEach { C.add(it) } return C.toIntArray() } fun go(A: IntArray): IntArray { var N = A.size if (N < 2) return A var half = Math.floor(N / 2.0).toInt() var first = go(A.slice(0 until half).toIntArray()) var second = go(A.slice(half until N).toIntArray()) return merge(first, second) } return go(A) }

fun main(args: Array) { sort(intArrayOf(5,3,8,9,1,7,0,2,6,4)).forEach { print("$it ") } // 0 1 2 3 4 5 6 7 8 9 println() } ```

Javascript ```javascript let sort = A => { let go = A => { let N = A.length; if (N < 2) return A; let half = Math.floor(N / 2); let first = go([...A.slice(0, half)]), second = go([...A.slice(half, N)]); return merge(first, second); }; let merge = (A, B, C = []) => { let M = A.length, N = B.length; let i = 0, j = 0; while (i < M && j < N) C.push(A[i] < B[j] ? A[i++] : B[j++]); C.push(...A.slice(i, M)); C.push(...B.slice(j, N)); return C; }; return go(A); };

console.log(sort([5,3,8,9,1,7,0,2,6,4])); // (10) [0, 1, 2, 3, 4, 5, 6, 7, 8, 9] ```

Python3 ```python from math import floor

def sort(A): def go(A): N = len(A) if N < 2: return A half = floor(N / 2) first = go(A[:half]) second = go(A[half:]) return merge(first, second) def merge(A, B): C = [] i = 0 j = 0 while i < len(A) and j < len(B): if A[i] < B[j]: C.append(A[i]); i += 1 else: C.append(B[j]); j += 1 C.extend(A[i:]) C.extend(B[j:]) return C return go(A)

print(sort([5,3,8,9,1,7,0,2,6,4])) # [0, 1, 2, 3, 4, 5, 6, 7, 8, 9] ```

C++ ```cpp

include

include

using namespace std;

class Solution { public: using VI = vector; VI mergesort(VI& A) { return go(move(A)); } private: VI go(VI&& A) { auto N = A.size(); if( N < 2 ) return A; auto half = A.begin() + (N / 2); auto first = go({ A.begin(), half }), second = go({ half, A.end() }); return merge(first, second); } VI merge(VI& A, VI& B, VI C = {}) { auto i{ 0 }, j{ 0 }; while (i < A.size() && j < B.size()) C.push_back(A[i] < B[j] ? A[i++] : B[j++]); C.insert(C.end(), A.begin() + i, A.end()); C.insert(C.end(), B.begin() + j, B.end()); return C; } };

int main() { Solution::VI A{ 3,5,7,1,3,9,2,0 }; auto ans = Solution().mergesort(A); copy(ans.begin(), ans.end(), ostream_iterator(cout, " ")), cout << endl; // 0 1 2 3 4 5 6 7 8 9 return 0; } ```

• The Divide-and-Conquer Paradigm (Section 3.1; part 1 of Section 3.2)
• Counting Inversions in O(n log n) Time (Section 3.2, part 2)

Kotlin ```java import java.io.File

fun sort(A: IntArray): Pair { fun merge(A: IntArray, B: IntArray): Pair { var C = mutableListOf() var inv: Long = 0 var i = 0 var j = 0 while (i < A.size && j < B.size) if (A[i] < B[j]) { C.add(A[i++]) } else { inv += A.size - i // ⭐️ B[j] comes before all remaining A[i...], thus all remaining A[i...] are inversions C.add(B[j++]) } A.slice(i..A.lastIndex).forEach { C.add(it) } B.slice(j..B.lastIndex).forEach { C.add(it) } return Pair(C.toIntArray(), inv) } fun go(A: IntArray): Pair { var N = A.size if (N < 2) return Pair(A, 0) var half = Math.floor(N / 2.0).toInt() var (first, inv1) = go(A.slice(0 until half).toIntArray()) var (second, inv2) = go(A.slice(half until N).toIntArray()) var (third, inv3) = merge(first, second) return Pair(third, inv1 + inv2 + inv3) } return go(A) }

fun run(filename: String): Long { var A = mutableListOf() File(filename).forEachLine { A.add(it.toInt()) } var (_, inv) = sort(A.toIntArray()) return inv }

fun main() { println("problem3.5test.txt: " + run("problem3.5test.txt")) // problem3.5test.txt: 28 println("problem3.5.txt: " + run("problem3.5.txt")) // problem3.5.txt: 2407905288 } ```

Javascript ```javascript let sort = A => { let go = A => { let N = A.length; if (N < 2) return [A, 0]; let half = Math.floor(N / 2); let [first, inv1] = go([...A.slice(0, half)]), [second, inv2] = go([...A.slice(half, N)]), [third, inv3] = merge(first, second); return [third, inv1 + inv2 + inv3]; }; let merge = (A, B, C = [], inv = 0) => { let M = A.length, N = B.length; let i = 0, j = 0; while (i < M && j < N) if (A[i] < B[j]) C.push(A[i++]); else inv += M - i, // ⭐️ B[j] comes before all remaining A[i...], thus all remaining A[i...] are inversions C.push(B[j++]); C.push(...A.slice(i, M)); C.push(...B.slice(j, N)); return [C, inv]; }; return go(A); };

let run = filename => { let A = []; require('fs').readFileSync(filename, 'utf-8').split(/\r?\n/).forEach(line => A.push(Number(line))); let [_, inv] = sort(A); return inv; }

console.log(problem3.5test.txt: ${run('problem3.5test.txt')}); // problem3.5test.txt: 28 console.log(problem3.5.txt: ${run('problem3.5.txt')}); // problem3.5.txt: 2407905288 ```

Python3 ```python from math import floor

def sort(A): def go(A): N = len(A) if N < 2: return [A, 0] half = floor(N / 2) first, inv1 = go(A[:half]) second, inv2 = go(A[half:]) third, inv3 = merge(first, second) return [third, inv1 + inv2 + inv3] def merge(A, B, inv = 0): C = [] i = 0 j = 0 while i < len(A) and j < len(B): if A[i] < B[j]: C.append(A[i]); i += 1 else: inv += len(A) - i # ⭐️ B[j] comes before all remaining A[i...], thus all remaining A[i...] are inversions C.append(B[j]); j += 1 C.extend(A[i:]) C.extend(B[j:]) return [C, inv] return go(A)

def run(filename): A = [] with open(filename) as fin: while True: line = fin.readline() if not line: break A.append(int(line)) _, inv = sort(A) return inv

print(f"problem3.5test.txt: {run('problem3.5test.txt')}") # problem3.5test.txt: 28 print(f"problem3.5.txt: {run('problem3.5.txt')}") # problem3.5.txt: 2407905288 ```

C++ ```cpp

include

include

include

using namespace std;

class Solution { public: using VL = vector; using Pair = pair; using fun = functionback(A[i++]); } else { inv += A.size() - i; // ⭐️ B[j] comes before all remaining A[i...], thus all remaining A[i...] are inversions C.pushback(B[j++]); } } C.insert(C.end(), A.begin() + i, A.end()); C.insert(C.end(), B.begin() + j, B.end()); return { C, inv }; } Pair inversions(VL& A) { fun go = & -> Pair { int N = A.size(); if (N < 2) return { A, 0 }; int half = N / 2; auto [first, inv1] = go({ A.begin(), A.begin() + half }); auto [second, inv2] = go({ A.begin() + half, A.end() }); auto [third, inv3] = merge(first, second); return { third, inv1 + inv2 + inv3 }; }; return go(move(A)); } };

long run(string filename) { Solution solution; Solution::VL A; fstream fin{ filename }; for (string line; fin >> line; A.pushback(stol(line))); auto [, inv] = solution.inversions(A); return inv; }

int main() { cout << "problem3.5test.txt: " << run("problem3.5test.txt") << endl // problem3.5test.txt: 28 << "problem3.5.txt: " << run("problem3.5.txt") << endl; // problem3.5.txt: 2407905288 return 0; } ```

• QuickSort: Overview (Section 5.1)
• Partitioning Around a Pivot Element (Section 5.2)
• Choosing a Good Pivot (Sections 5.3 and 5.4)
• QuickSort Analysis (Part 1) (Section 5.5, part 1)
• QuickSort Analysis (Part 2) (Section 5.5, part 2)
• QuickSort Analysis (Part 3) (Section 5.5, part 3)
• Sorting Requires Omega(n log n) Comparisons (Section 5.6)
• Proofs by Induction and the Correctness of QuickSort (Appendix A)
• Quick Review of Discrete Probability (Appendix B)

Kotlin ```java import java.io.File

typealias PivotFunc = (A: MutableList, L: Int, R: Int) -> (Int) var pivotLeft: PivotFunc = { _: MutableList, L: Int, _: Int -> L } var pivotRight: PivotFunc = { _: MutableList, _: Int, R: Int -> R } fun _pivotMedian(A: MutableList, L: Int, R: Int): Int { var M = L + (R - L) / 2 var cand = intArrayOf(A[L], A[M], A[R]) cand.sort() var target = cand[1] if (target == A[L]) return L if (target == A[M]) return M if (target == A[R]) return R return -1 } var pivotMedian: PivotFunc = { A: MutableList, L: Int, R: Int -> _pivotMedian(A, L, R) }

fun partition(A: MutableList, L: Int, R: Int, choosePivot: (A: MutableList, L: Int, R: Int) -> (Int)): Int { var i = L + 1 var j = L + 1 var k = choosePivot(A, L, R) A[k] = A[L].also { A[L] = A[k] } // swap pivot A[k] with first element of subarray A[L] while (j <= R) { if (A[j] < A[L]) { // maintain loop invariant A[i] < pivot < A[j] A[i] = A[j].also { A[j] = A[i] } ++i } ++j } A[L] = A[i - 1].also { A[i - 1] = A[L] } // swap pivot A[L] with last value less-than pivot A[i - 1] return i - 1 }

fun quicksort(A: MutableList, L: Int, R: Int, choosePivot: (A: MutableList, L: Int, R: Int) -> (Int)): Int { if (R <= L) return 0 var k = partition(A, L, R, choosePivot) return (R - L) + quicksort(A, L, k - 1, choosePivot) + quicksort(A, k + 1, R, choosePivot) }

fun run(filename: String, choosePivot: (A: MutableList, L: Int, R: Int) -> (Int)): Int { var A = mutableListOf() File(filename).forEachLine { A.add(it.toInt()) } return quicksort(A, 0, A.size - 1, choosePivot) }

fun main() { var filename = "problem5.6.txt" println(" left: ${run(filename, pivotLeft)}") // left: 162085 println(" right: ${run(filename, pivotRight)}") // right: 164123 println("median: ${run(filename, pivotMedian)}") // median: 138382 } ```

Javascript ```javascript let pivotLeft = (A, L, R) => L; let pivotRight = (A, L, R) => R; let pivotMedian = (A, L, R) => { let M = L + Math.floor((R - L) / 2); let cand = [A[L], A[M], A[R]].sort((a, b) => a - b), target = cand[1]; if (target == A[L]) return L; if (target == A[M]) return M; if (target == A[R]) return R; };

let partition = (A, L, R, choosePivot) => { let i = L + 1, j = L + 1, k = choosePivot(A, L, R); [A[L], A[k]] = [A[k], A[L]]; // swap pivot A[k] with first element of subarray A[L] while (j <= R) { if (A[j] < A[L]) { // maintain loop invariant A[i] < pivot < A[j] [A[i], A[j]] = [A[j], A[i]]; ++i; } ++j; } [A[L], A[i - 1]] = [A[i - 1], A[L]]; // swap pivot A[L] with last value less-than pivot A[i - 1] return i - 1; };

let quicksort = (A, L, R, choosePivot) => { if (R <= L) return 0; let k = partition(A, L, R, choosePivot); return (R - L) + quicksort(A, L, k - 1, choosePivot) + quicksort(A, k + 1, R, choosePivot); };

let run = (filename, choosePivot) => { let A = []; let LineByLine = require("n-readlines"); let input = new LineByLine(filename); for (let line; line = input.next(); A.push(Number(line))); return quicksort(A, 0, A.length - 1, choosePivot); }

let filename = 'problem5.6.txt'; console.log(left: ${run(filename, pivotLeft)}); // left: 162085 console.log(right: ${run(filename, pivotRight)}); // right: 164123 console.log(median: ${run(filename, pivotMedian)}); // median: 138382 ```

Python3 ```python def pivotLeft(A, L, R): return L def pivotRight(A, L, R): return R def pivotMedian(A, L, R): M = L + (R - L) // 2 cand = sorted([A[L], A[M], A[R]]) target = cand[1] if target == A[L]: return L if target == A[M]: return M if target == A[R]: return R

def partition(A, L, R, choosePivot): i = L + 1 j = L + 1 k = choosePivot(A, L, R) A[L], A[k] = A[k], A[L] # swap pivot A[k] with first element of subarray A[L] while j <= R: if A[j] < A[L]: # maintain loop invariant A[i] < pivot < A[j] A[i], A[j] = A[j], A[i] i += 1 j += 1 A[L], A[i - 1] = A[i - 1], A[L] # swap pivot A[L] with last value less-than pivot A[i - 1] return i - 1

def quicksort(A, L, R, choosePivot): if R <= L: return 0 k = partition(A, L, R, choosePivot) return (R - L) + quicksort(A, L, k - 1, choosePivot) + quicksort(A, k + 1, R, choosePivot)

def run(filename, choosePivot): A = [] with open(filename) as fin: while True: line = fin.readline() if not line: break A.append(int(line))

return quicksort(A, 0, len(A) - 1, choosePivot)

filename = 'problem5.6.txt' print(f' left: {run(filename, pivotLeft)}') # left: 162085 print(f' right: {run(filename, pivotRight)}') # right: 164123 print(f'median: {run(filename, pivotMedian)}') # median: 138382 ```

C++ ```cpp

include

include

include

using namespace std; using VI = vector; using fun = function

fun pivotLeft = { return L; }; fun pivotRight = { return R; }; fun pivotMedian = { auto M = L + (R - L) / 2; VI cand{ A[L], A[M], A[R] }; sort(cand.begin(), cand.end()); auto target = cand[1]; if (target == A[L]) return L; if (target == A[M]) return M; if (target == A[R]) return R; };

int partition(VI& A, int L, int R, fun choosePivot) { auto i = L + 1, j = L + 1, k = choosePivot(A, L, R); swap(A[L], A[k]); // swap pivot A[k] with first element of the subarray A[L] while (j <= R) { if (A[j] < A[L]) { // maintain loop invariant A[i] < pivot < A[j] swap(A[i], A[j]); ++i; } ++j; } swap(A[L], A[i - 1]); // swap pivot A[L] with last value less-than pivot A[i - 1] return i - 1; }

int quicksort(VI& A, int L, int R, fun choosePivot) { if (R <= L) return 0; auto k = partition(A, L, R, choosePivot); return (R - L) + quicksort(A, L, k - 1, choosePivot) + quicksort(A, k + 1, R, choosePivot); }

int run(string& filename, fun choosePivot) { VI A; fstream fin{ filename }; for (string line; fin >> line; A.push_back(stoi(line))); int N = A.size(); return quicksort(A, 0, N - 1, choosePivot); }

int main() { string filename{ "problem5.6.txt" }; cout << " left: " << run(filename, pivotLeft) << endl // left: 162085 << " right: " << run(filename, pivotRight) << endl // right: 164123 << "median: " << run(filename, pivotMedian) << endl; // median: 138382 return 0; } ```

• Randomized Linear-Time Selection (Section 6.1)
• Randomized Linear-Time Selection (Analysis) (Section 6.2)

Kotlin ```java import java.io.File import kotlin.random.Random

fun partition(A: MutableList, L: Int, R: Int): Int { var i = L + 1 var j = L + 1 var k = Random.nextInt(L, R + 1) // +1 for L..R inclusive A[L] = A[k].also { A[k] = A[L] } // swap pivot A[k] with first element of subarray A[L] while (j <= R) { if (A[j] < A[L]) { // maintain loop invariant A[i] < pivot < A[j] A[i] = A[j].also { A[j] = A[i] } ++i } ++j } A[L] = A[i - 1].also { A[i - 1] = A[L] } // swap pivot A[L] with last value less-than pivot A[i - 1] return i - 1 }

fun rselect(A: MutableList, i: Int, L: Int, R: Int): Int { var L = L_ var R = R_ var k = partition(A, L, R) if (i == k) return A[k] // 🎯 lucky guess if (i < k) R = k - 1 else L = k + 1 return rselect(A, i, L, R) }

fun run(filename: String, i: Int): Int { var A = mutableListOf() File(filename).forEachLine { A.add(it.toInt()) } var N = A.size return rselect(A, i - 1, 0 , N - 1) // -1 for 0-based indexing }

fun main() { println("problem6.5test1.txt: " + run("problem6.5test1.txt", 5)) // problem6.5test1.txt: 5469 println("problem6.5test2.txt: " + run("problem6.5test2.txt", 50)) // problem6.5test2.txt: 4715 } ```

Javascript ```javascript let random = (L, R) => Math.floor(Math.random() * (R + 1 - L) + L); // +1 for L..R inclusive

let partition = (A, L, R) => { let i = L + 1, j = L + 1, k = random(L, R); [A[L], A[k]] = [A[k], A[L]]; // swap pivot A[k] with first element of subarray A[L] while (j <= R) { if (A[j] < A[L]) { // maintain loop invariant A[i] < pivot < A[j] [A[i], A[j]] = [A[j], A[i]]; ++i; } ++j; } [A[L], A[i - 1]] = [A[i - 1], A[L]]; // swap pivot A[L] with last value less-than pivot A[i - 1] return i - 1; };

let rselect = (A, i, L, R) => { let k = partition(A, L, R); if (i == k) return A[k]; // 🎯 lucky guess if (i < k) R = k - 1; else L = k + 1; return rselect(A, i, L, R); }

let run = (filename, i) => { let A = []; let LineByLine = require("n-readlines"); let input = new LineByLine(filename); for (let line; line = input.next(); A.push(Number(line))); let N = A.length; return rselect(A, i - 1, 0, N - 1); // -1 for 0-based indexing };

console.log(problem6.5test1.txt: ${run('problem6.5test1.txt', 5)}); // problem6.5test1.txt: 5469 console.log(problem6.5test2.txt: ${run('problem6.5test2.txt', 50)}); // problem6.5test2.txt: 4715 ```

Python3 ```python from random import uniform from math import floor

def partition(A, L, R): i = L + 1 j = L + 1 k = floor(uniform(L, R)) A[L], A[k] = A[k], A[L] # swap pivot A[k] with first element of subarray A[L] while j <= R: if A[j] < A[L]: # maintain loop invariant A[i] < pivot < A[j] A[i], A[j] = A[j], A[i] i += 1 j += 1 A[L], A[i - 1] = A[i - 1], A[L] # swap pivot A[L] with last value less-than pivot A[i - 1] return i - 1

def rselect(A, i, L, R): k = partition(A, L, R) if i == k: return A[k] # 🎯 lucky guess if i < k: R = k - 1 else: L = k + 1 return rselect(A, i, L, R)

def run(filename, i): A = [] with open(filename) as fin: while True: line = fin.readline() if not line: break A.append(int(line)) N = len(A) return rselect(A, i - 1, 0, N - 1) # -1 for 0-based indexing

print('problem6.5test1.txt:', run('problem6.5test1.txt', 5)) # problem6.5test1.txt: 5469 print('problem6.5test2.txt:', run('problem6.5test2.txt', 50)) # problem6.5test2.txt: 4715 ```

C++ ```cpp

include

include

include

include

using namespace std; using VI = vector;

int random(int L, int R) { randomdevice rd; mt19937 gen{ rd() }; uniformint_distribution dist(L, R); return dist(gen); }

int partition(VI& A, int L, int R) { auto i = L + 1, j = L + 1, k = random(L, R); swap(A[L], A[k]); // swap pivot A[k] with first element of the subarray A[L] while (j <= R) { if (A[j] < A[L]) // maintain loop invariant A[i] < pivot < A[j] swap(A[i++], A[j]); ++j; } swap(A[L], A[i - 1]); // swap pivot A[L] with last value less-than pivot A[i - 1] return i - 1; }

int rselect(VI& A, int i, int L, int R) { auto k = partition(A, L, R); if (i == k) return A[k]; // 🎯 lucky guess if (i < k) R = k - 1; else L = k + 1; return rselect(A, i, L, R); }

int run(string filename, int i, VI A = {}) { fstream fin{ filename }; for (string line; fin >> line; A.push_back(stoi(line))); int N = A.size(); return rselect(A, i - 1, 0, N - 1); // -1 for 0-based indexing }

int main() { cout << "problem6.5test1.txt: " << run("problem6.5test1.txt", 5) << endl; // problem6.5test1.txt: 5469 cout << "problem6.5test2.txt: " << run("problem6.5test2.txt", 50) << endl; // problem6.5test2.txt: 4715 return 0; } ```

• Graphs: The Basics (from 2:06 to 6:39) (Sections 7.1 and 7.2)
• Graph Representations (Sections 7.3 and 7.4)
• Graph Search Overview (Section 8.1)
• Breadth-First Search (Section 8.2, Part 1)
• Depth-First Search (Section 8.4)
• Topological Sort (Section 8.5)

Kotlin ```java import java.util.Queue import java.util.LinkedList

class Solution(val adj: MutableMap>) {

var N: Int
var color: Int
var m = mutableMapOf<Char, Int>()
var seen = mutableSetOf<Char>()

init {
    N = adj.size
    color = 0
}

fun init(start: Int) {
    color = start
    m.clear()
    seen.clear()
}

fun topoSortBFS(): String {
    init(1)  // 👉 color forward from 1..N
    bfs()
    return toString()
}

fun topoSortDFS(): String {
    init(N)  // 👈 color reverse from N..1 (as the recursive stack unwinds)
    adj.forEach{ (u, _) -> dfs(u) }
    return toString()
}

fun bfs() {
    var degree = mutableMapOf<Char, Int>()
    adj.forEach{ (_, neighbors) ->
        neighbors.forEach{ v ->
            degree[v] = 1 + degree.getOrDefault(v, 0)
        }
    }
    var q: Queue<Char> = LinkedList(adj.map{ (u, _) -> u }.filter{ !degree.contains(it) })
    while (0 < q.size) {
        var u = q.poll()
        m[u] = color++
        adj[u]!!.forEach{ v ->
            degree[v] = degree[v]!!.minus(1)
            if (degree[v] == 0 && !seen.contains(v)) {
                q.add(v); seen.add(v)
            }
        }
    }
}

fun dfs(u: Char) {
    if (seen.contains(u))
        return
    seen.add(u)
    adj[u]!!.forEach{ v ->
        dfs(v)
    }
    m[u] = color--
}

override fun toString(): String {
    var s = mutableListOf<String>()
    adj.forEach{ (u, _) ->
        s.add("$u: ${m[u]}")
    }
    return s.joinToString("\n")
}

}

fun main() { var adj = mutableMapOf>( 's' to listOf('v', 'w'), 'v' to listOf('t'), 'w' to listOf('t'), 't' to listOf() ) var solution = Solution(adj) println("BFS:\n${solution.topoSortBFS()}\n\nDFS:\n${solution.topoSortDFS()}")

// BFS: // s: 1 // v: 2 // w: 3 // t: 4

// DFS: // s: 1 // v: 3 // w: 2 // t: 4

} ```

Javascript ``javascript class Solution { constructor(adj) { this.adj = adj; this.N = this.adj.size; } init(start) { this.color = start; this.seen = new Set(); this.m = new Map(); } topo_sort_bfs() { this.init(1); // 👉 color forward from 1..N this.bfs(); return this.to_string(); } topo_sort_dfs() { this.init(this.N); // 👈 color reverse from N..1 (as the recursive stack unwinds) for (let [u, _] of [...this.adj]) this.dfs(u); return this.to_string(); } bfs() { let degree = new Map(); for (let [u, _] of [...this.adj]) { degree.set(u, (degree.get(u) || 0)); for (let v of this.adj.get(u)) degree.set(v, 1 + (degree.get(v) || 0)); } let q = [...this.adj].map(([u, _]) => u).filter(u => !degree.get(u)); let seen = new Set(q); while (q.length) { let u = q.shift(); this.m.set(u, this.color++); for (let v of this.adj.get(u)) { degree.set(v, -1 + degree.get(v)); if (!degree.get(v) && !seen.has(v)) q.push(v), seen.add(v); } } } dfs(u) { if (this.seen.has(u)) return; this.seen.add(u); for (let v of this.adj.get(u)) if (!this.seen.has(v)) this.dfs(v); this.m.set(u, this.color--); } to_string() { let s = []; for (let [u, color] of [...this.m]) s.push(${u}: ${color}`); return s.join('\n'); } }

let adj = new Map(); adj.set('s', ['v', 'w']); adj.set('v', ['t']); adj.set('w', ['t']); adj.set('t', []); let solution = new Solution(adj); console.log(BFS:\n${solution.topo_sort_bfs()}\n\nDFS:\n${solution.topo_sort_dfs()});

// BFS: // s: 1 // v: 2 // w: 3 // t: 4

// DFS: // t: 4 // v: 3 // w: 2 // s: 1 ```

Python3 ```python from collections import deque

class Solution: def init(self, adj): self.adj = adj self.N = len(adj) self.seen = set() self.m = {}

def init(self, start):
    self.color = start
    self.seen.clear()
    self.m.clear()

def topo_sort_bfs(self):
    self.init(1)         # 👉 color forward from 1..N
    self.bfs()
    return self.to_string()

def topo_sort_dfs(self):
    self.init(self.N)  # 👈 color reverse from N..1 (as the recursive stack unwinds)
    for u, _ in self.adj.items():
        self.dfs(u)
    return self.to_string()

def bfs(self):
    degree = {}
    for _, neighbors in self.adj.items():
        for v in neighbors:
            degree[v] = 1 + (degree[v] if v in degree else 0)
    q = deque(u for u, _ in self.adj.items() if u not in degree)
    self.seen.update(*q)
    while q:
        u = q.popleft()
        self.m[u] = self.color; self.color += 1
        for v in adj[u]:
            degree[v] -= 1
            if not degree[v] and v not in self.seen:
                q.append(v); self.seen.add(v)

def dfs(self, u):
    if u in self.seen:
        return
    self.seen.add(u)
    for v in adj[u]:
        self.dfs(v)
    self.m[u] = self.color; self.color -= 1

def to_string(self):
    s = []
    for u, color in self.m.items():
        s.append(f'{u}: {color}')
    return '\n'.join(s)

#

graph from Quiz 8.3 on page 45 of Algorithms Illuminated: Part 2

# adj = { 's': ['v', 'w'], 'v': ['t'], 'w': ['t'], 't': [] } solution = Solution(adj)

print(f'BFS:\n{solution.toposortbfs()}\n\nDFS:\n{solution.toposortdfs()}')

BFS:

s: 1

v: 2

w: 3

t: 4

DFS:

t: 4

v: 3

w: 2

s: 1

```

C++ ```cpp

include

include

include

include

include

include

using namespace std;

using VI = vector; using AdjList = unorderedmap; using Set = unorderedset; using Map = unordered_map; using Queue = queue; using fun = function

class Solution { private: AdjList adj; const int N; Map m; Set seen; int color; public: Solution(AdjList& adj) : adj{ adj }, N{ int(adj.size()) } { } void init(int start) { m.clear(); seen.clear(); color = start; } string toposortbfs() { init(1); // 👉 color forward from 1..N bfs(); return tostring(); } string toposortdfs() { init(N); // 👈 color reverse from N..1 (as the recursive stack unwinds) for (auto [u, _]: adj) dfs(u); return tostring(); } void bfs() { Map degree; for (auto [, neighbors]: adj) for (auto v: neighbors) ++degree[v]; Queue q; for (auto [u, _]: adj) if (!degree[u] && seen.insert(u).second) q.push(u); while (q.size()) { auto u = q.front(); q.pop(); m[u] = color++; for (auto v: adj[u]) if (!--degree[v] && seen.insert(v).second) q.push(v); } } void dfs(char start) { fun go = & { if (!seen.insert(u).second) return; for (auto v: adj[u]) go(v); m[u] = color--; }; go(start); } string tostring() { ostringstream os; for (auto [u, color]: m) os << u << ": " << color << endl; return os.str(); } };

int main() { // // graph from Quiz 8.3 on page 45 of Algorithms Illuminated: Part 2 // AdjList adj{ { 's', { 'v', 'w' } }, { 'v', { 't' } }, { 'w', { 't' } }, { 't', {} } }; Solution solution{ adj };

cout << "BFS:" << endl << solution.topo_sort_bfs() << endl
     << "DFS:" << endl << solution.topo_sort_dfs() << endl;

// BFS: // t: 4 // w: 3 // v: 2 // s: 1 // // DFS: // s: 1 // w: 2 // v: 3 // t: 4

return 0;

} ```

• Computing Strongly Connected Components (Part 1) (Section 8.6, Part 1)
• Computing Strongly Connected Components (Part 2) (Section 8.6, Part 2)
• The Structure of the Web (Section 8.7)

Kotlin ```java import java.util.Stack import java.io.File

class RecursiveSolution(var adj: MutableMap>, var rev: MutableMap>) { fun toposort(): MutableList { var list = mutableListOf() var seen = mutableSetOf() fun go(u: Int) { if (seen.contains(u)) return seen.add(u) for (v in rev[u]!!) go(v) list.add(0, u) } for ((u, _) in rev) go(u) return list } fun kosaraju(): MutableList> { var lists = mutableListOf>() var seen = mutableSetOf() fun go(u: Int, list: MutableList) { if (seen.contains(u)) return list.add(u); seen.add(u) for (v in adj[u]!!) go(v, list) } for (u in toposort()) { if (seen.contains(u)) continue var list = mutableListOf() go(u, list) lists.add(list.toList()) } return lists } }

class IterativeSolution(var adj: MutableMap>, var rev: MutableMap>) { fun toposort(): MutableList { var list = mutableListOf() var seen = mutableSetOf() for ((u, _) in rev) { if (seen.contains(u)) continue var stack = Stack() stack.push(u); seen.add(u) while (!stack.empty()) { var u = stack.last() for (v in rev[u]!!) { if (!seen.contains(v)) { stack.push(v); seen.add(v) } } if (u == stack.last()) list.add(0, stack.pop()) } } return list } fun kosaraju(): MutableList> { var lists = mutableListOf>() var seen = mutableSetOf() for (u in toposort()) { if (seen.contains(u)) continue var list = mutableListOf() var stack = Stack() stack.push(u); seen.add(u) while (!stack.empty()) { var u = stack.last() for (v in adj[u]!!) { if (!seen.contains(v)) { stack.push(v); seen.add(v) } } if (u == stack.last()) list.add(stack.pop()) } lists.add(list.toList()) } return lists } }

fun run(filename: String) { var adj = mutableMapOf>() var rev = mutableMapOf>() File(filename).forEachLine { var (u, v) = it.trim().split(" ").map{ it.toInt() } if (!adj.contains(u)) adj[u] = mutableListOf(); if (!adj.contains(v)) adj[v] = mutableListOf() if (!rev.contains(u)) rev[u] = mutableListOf(); if (!rev.contains(v)) rev[v] = mutableListOf() adj[u]!!.add(v) rev[v]!!.add(u) } // var solution = RecursiveSolution(adj, rev) var solution = IterativeSolution(adj, rev) var A = solution.kosaraju() A.sortWith(Comparator{ a: List, b: List -> b.size - a.size }) println(filename + ": " + A.map{ it.size }.slice(0 until Math.min(A.size, 5)).joinToString(" ")) }

fun main() { run("section8.6.5page64.txt"); // Graph from section 8.6.5 on page 64 of Algorithms Illuminated: Part 2 run("problem8.10test1.txt"); // Test case #1: A 9-vertex 11-edge graph. Top 5 SCC sizes: 3,3,3,0,0 run("problem8.10test2.txt"); // Test case #2: An 8-vertex 14-edge graph. Top 5 SCC sizes: 3,3,2,0,0 run("problem8.10test3.txt"); // Test case #3: An 8-vertex 9-edge graph. Top 5 SCC sizes: 3,3,1,1,0 run("problem8.10test4.txt"); // Test case #4: An 8-vertex 11-edge graph. Top 5 SCC sizes: 7,1,0,0,0 run("problem8.10test5.txt"); // Test case #5: A 12-vertex 20-edge graph. Top 5 SCC sizes: 6,3,2,1,0 run("problem8.10.txt"); // Challenge data set: Vertices are labeled as positive integers from 1 to 875714

// section8.6.5page64.txt: 4 3 3 1 // problem8.10test1.txt: 3 3 3 // problem8.10test2.txt: 3 3 2 // problem8.10test3.txt: 3 3 1 1 // problem8.10test4.txt: 7 1 // problem8.10test5.txt: 6 3 2 1 // problem8.10.txt: 434821 968 459 313 211

} ```

Javascript ```javascript class BaseSolution { constructor(adj, rev) { this.adj = adj; this.rev = rev; } }

class RecursiveSolution extends BaseSolution { constructor(adj, rev) { super(adj, rev); } toposort() { let list = []; let seen = new Set(); let go = u => { if (seen.has(u)) return; seen.add(u); for (let v of [...this.rev.get(u)]) go(v); list.unshift(u); }; for (let [u, _] of [...this.rev]) go(u); return list; } kosaraju() { let lists = []; let seen = new Set(); let go = (u, list) => { if (seen.has(u)) return; seen.add(u); list.push(u); for (let v of [...this.adj.get(u)]) go(v, list); }; for (let u of this.toposort()) { let list = []; go(u, list); lists.push([...list]); } lists.sort((a, b) => b.length - a.length); return lists; } }

class IterativeSolution extends BaseSolution { constructor(adj, rev) { super(adj, rev); } toposort() { let list = []; let seen = new Set(); for (let [u, _] of [...this.rev]) { if (seen.has(u)) continue; let stack = [ u ]; seen.add(u); stack.back = () => stack[stack.length - 1]; while (stack.length) { let u = stack.back(); for (let v of [...this.rev.get(u)]) if (!seen.has(v)) stack.push(v), seen.add(v); if (u == stack.back()) list.unshift(stack.pop()); } } return list; } kosaraju() { let lists = []; let seen = new Set(); for (let u of this.toposort()) { if (seen.has(u)) continue; let list = []; let stack = [ u ]; seen.add(u); stack.back = () => stack[stack.length - 1]; while (stack.length) { let u = stack.back(); for (let v of [...this.adj.get(u)]) if (!seen.has(v)) stack.push(v), seen.add(v); if (u == stack.back()) list.push(stack.pop()); } lists.push([...list]); } lists.sort((a, b) => b.length - a.length); return lists; } }

let run = filename => { let adj = new Map(), rev = new Map(); let LineByLine = require('n-readlines'); let input = new LineByLine(filename); let line; while (line = input.next()) { let [u, v] = String.fromCharCode(...line).split(' ').map(Number); if (!adj.has(u)) adj.set(u, []); if (!adj.has(v)) adj.set(v, []); if (!rev.has(u)) rev.set(u, []); if (!rev.has(v)) rev.set(v, []); adj.get(u).push(v); rev.get(v).push(u); } // let A = new RecursiveSolution(adj, rev).kosaraju(); let A = new IterativeSolution(adj, rev).kosaraju(); console.log(${filename}: ${A.slice(0, Math.min(A.length, 5)).map(scc => scc.length).join(' ')}); };

run('section8.6.5page64.txt') // Graph from section 8.6.5 on page 64 of Algorithms Illuminated: Part 2 run('problem8.10test1.txt') // Test case #1: A 9-vertex 11-edge graph. Top 5 SCC sizes: 3,3,3,0,0 run('problem8.10test2.txt') // Test case #2: An 8-vertex 14-edge graph. Top 5 SCC sizes: 3,3,2,0,0 run('problem8.10test3.txt') // Test case #3: An 8-vertex 9-edge graph. Top 5 SCC sizes: 3,3,1,1,0 run('problem8.10test4.txt') // Test case #4: An 8-vertex 11-edge graph. Top 5 SCC sizes: 7,1,0,0,0 run('problem8.10test5.txt') // Test case #5: A 12-vertex 20-edge graph. Top 5 SCC sizes: 6,3,2,1,0 run('problem8.10.txt') // Challenge data set: Vertices are labeled as positive integers from 1 to 875714

// section8.6.5page64.txt: 4 3 3 1 // problem8.10test1.txt: 3 3 3 // problem8.10test2.txt: 3 3 2 // problem8.10test3.txt: 3 3 1 1 // problem8.10test4.txt: 7 1 // problem8.10test5.txt: 6 3 2 1 // problem8.10.txt: 434821 968 459 313 211 ```

Python3 ```python from collections import deque from functools import cmptokey

class BaseSolution: def init(self, adj, rev): self.adj = adj self.rev = rev

class RecursiveSolution(BaseSolution): def topo_sort(self): list = deque() seen = set() def go(u): if u in seen: return seen.add(u) for v in self.rev[u]: go(v) list.appendleft(u) for u in self.rev.keys(): go(u) return list

def kosaraju(self):
    lists = []
    seen = set()
    def go(u, list):
        if u in seen:
            return
        seen.add(u)
        list.append(u)
        for v in self.adj[u]:
            go(v, list)
    for u in self.topo_sort():
        list = []
        go(u, list)
        lists.append(list.copy())
    lists.sort(key = cmp_to_key(lambda a, b: len(b) - len(a)))
    return lists

class IterativeSolution(BaseSolution): def topo_sort(self): list = deque() seen = set() for u in self.rev.keys(): if u in seen: continue stack = [ u ]; seen.add(u) while len(stack): u = stack[-1] for v in self.rev[u]: if v not in seen: stack.append(v); seen.add(v) if u == stack[-1]: list.appendleft(stack.pop()) return list

def kosaraju(self):
    lists = []
    seen = set()
    for u in self.topo_sort():
        if u in seen:
            continue
        list = deque()
        stack = [ u ]; seen.add(u)
        while len(stack):
            u = stack[-1]
            for v in self.adj[u]:
                if v not in seen:
                    stack.append(v); seen.add(v)
            if u == stack[-1]:
                list.appendleft(stack.pop())
        lists.append(list.copy())
    lists.sort(key = cmp_to_key(lambda a, b: len(b) - len(a)))
    return lists

def run(filename): adj, rev = {}, {} with open(filename) as fin: while True: line = fin.readline().strip() if not line: break u, v = [int(x) for x in line.split()] if u not in adj: adj[u] = [] if v not in adj: adj[v] = [] if u not in rev: rev[u] = [] if v not in rev: rev[v] = [] adj[u].append(v) rev[v].append(u) # solution = RecursiveSolution(adj, rev) solution = IterativeSolution(adj, rev) A = solution.kosaraju() print(filename + ': ' + ' '.join(str(len(scc)) for scc in A[:5]))

run('section8.6.5page64.txt') # Graph from section 8.6.5 on page 64 of Algorithms Illuminated: Part 2 run('problem8.10test1.txt') # Test case #1: A 9-vertex 11-edge graph. Top 5 SCC sizes: 3,3,3,0,0 run('problem8.10test2.txt') # Test case #2: An 8-vertex 14-edge graph. Top 5 SCC sizes: 3,3,2,0,0 run('problem8.10test3.txt') # Test case #3: An 8-vertex 9-edge graph. Top 5 SCC sizes: 3,3,1,1,0 run('problem8.10test4.txt') # Test case #4: An 8-vertex 11-edge graph. Top 5 SCC sizes: 7,1,0,0,0 run('problem8.10test5.txt') # Test case #5: A 12-vertex 20-edge graph. Top 5 SCC sizes: 6,3,2,1,0 run('problem8.10.txt') # Challenge data set: Vertices are labeled as positive integers from 1 to 875714

section8.6.5page64.txt: 4 3 3 1

problem8.10test1.txt: 3 3 3

problem8.10test2.txt: 3 3 2

problem8.10test3.txt: 3 3 1 1

problem8.10test4.txt: 7 1

problem8.10test5.txt: 6 3 2 1

problem8.10.txt: 434821 968 459 313 211

```

C++ ```cpp

include

include

include

include

include

include

using namespace std;

using List = deque; using Lists = deque; using AdjList = unorderedmap; using Set = unorderedset; using Map = unordered_map;

namespace Base { class Solution { protected: AdjList adj, rev; public: Solution(AdjList& adj, AdjList& rev) : adj{ adj }, rev{ rev } {} }; } namespace Recursive { struct Solution : public Base::Solution { Solution(AdjList& adj, AdjList& rev) : Base::Solution{ adj, rev } {} Lists kosaraju() { Lists lists; Set seen; using fun = function& { if (!seen.insert(u).second) return; list.pushback(u); for (auto v: adj[u]) go(v, list); }; for (auto u: toposort()) { List list; go(u, list); lists.emplaceback(list); } sort(lists.begin(), lists.end(), { return b.size() < a.size(); }); return lists; } List toposort() { List list; Set seen; using fun = function& { if (!seen.insert(u).second) return; for (auto v: rev[u]) go(v); list.pushfront(u); }; for (auto [u, _]: rev) go(u); return list; } }; } namespace Iterative { struct Solution : public Base::Solution { Solution(AdjList& adj, AdjList& rev) : Base::Solution{ adj, rev } {} Lists kosaraju() { Lists lists; Set seen; for (auto u: toposort()) { if (seen.find(u) != seen.end()) continue; List list; List stack{ u }; seen.insert(u); while (stack.size()) { auto u = stack.back(); for (auto v: adj[u]) if (seen.insert(v).second) stack.pushback(v); if (u == stack.back()) list.pushback(u), stack.popback(); } lists.emplaceback(list); } sort(lists.begin(), lists.end(), { return b.size() < a.size(); }); return lists; } List toposort() { List list; Set seen; for (auto [u, _]: rev) { if (seen.find(u) != seen.end()) continue; List stack{ u }; seen.insert(u); while (stack.size()) { auto u = stack.back(); for (auto v: rev[u]) if (seen.insert(v).second) stack.pushback(v); if (u == stack.back()) list.pushfront(stack.back()), stack.popback(); } } return list; } }; }

void run(string filename) { int u, v; AdjList adj, rev; fstream fin{ filename }; for (string line; fin >> u >> v;) { adj[u].pushback(v); rev[v].pushback(u); } auto A = Iterative::Solution{ adj, rev }.kosaraju(); A.resize(min(A.size(), size_t(5))); cout << filename << ": "; for (auto i{ 0 }; i < A.size(); cout << A[i++].size() << " "); cout << endl; }

int main() { run("section8.6.5page64.txt"); // Graph from section 8.6.5 on page 64 of Algorithms Illuminated: Part 2 run("problem8.10test1.txt"); // Test case #1: A 9-vertex 11-edge graph. Top 5 SCC sizes: 3,3,3,0,0 run("problem8.10test2.txt"); // Test case #2: An 8-vertex 14-edge graph. Top 5 SCC sizes: 3,3,2,0,0 run("problem8.10test3.txt"); // Test case #3: An 8-vertex 9-edge graph. Top 5 SCC sizes: 3,3,1,1,0 run("problem8.10test4.txt"); // Test case #4: An 8-vertex 11-edge graph. Top 5 SCC sizes: 7,1,0,0,0 run("problem8.10test5.txt"); // Test case #5: A 12-vertex 20-edge graph. Top 5 SCC sizes: 6,3,2,1,0 run("problem8.10.txt"); // Challenge data set: Vertices are labeled as positive integers from 1 to 875714

// section8.6.5page64.txt: 4 3 3 1 // problem8.10test1.txt: 3 3 3 // problem8.10test2.txt: 3 3 2 // problem8.10test3.txt: 3 3 1 1 // problem8.10test4.txt: 7 1 // problem8.10test5.txt: 6 3 2 1 // problem8.10.txt: 434821 968 459 313 211

return 0;

} ```

• Shortest Paths and Dijkstra's Algorithm (Sections 9.1 and 9.2, Part 1)
• Dijkstra's Algorithm: Examples (Section 9.2, Part 2)
• Correctness of Dijkstra's Algorithm (Section 9.3)
• Implementation and Running Time of Dijkstra's Algorithm (0:00-4:30) (Section 9.4)
• Data Structures Overview (Section 10.1)
• Heaps: Operations and Applications (Sections 10.2 and 10.3)
• Speeding Up Dijkstra's Algorithm With Heaps (4:30-26:27) (Section 10.4)
• Heaps: Implementation Details (Section 10.5)

Kotlin ```java import java.io.File import java.util.PriorityQueue

var INF = (1e9 + 7).toInt()

interface BaseSolution { fun run(filename: String, queries: Array): String }

class NaiveSolution : BaseSolution { fun dijkstra(E: List>): MutableMap { var dist = mutableMapOf() var seen = mutableSetOf() var start = 1 dist[start] = 0; seen.add(start) var found: Boolean; do { found = false var bestv = INF var bestw = INF for ((u, v, w) in E) { if (!seen.contains(u) || seen.contains(v)) continue found = true if (bestw > dist[u]!! + w) { bestv = v bestw = dist[u]!! + w } } var v = bestv var w = best_w dist[v] = w; seen.add(v) } while (found) return dist } override fun run(filename: String, queries: Array): String { var E = mutableListOf>() File(filename).forEachLine { var words = it.trim().split("\t") var u = words[0].toInt() for (i in 1 until words.size) { var (v, w) = words[i].split(",").map{ it.toInt() } E.add(Triple(u, v, w)) } } var dist = dijkstra(E.toList()) return queries.map{ dist[it] }.joinToString(" ") } }

class HeapSolution : BaseSolution { fun dijkstra(adj: MutableMap>>): MutableMap { var dist = mutableMapOf() var seen = mutableSetOf() var start = 1 dist[start] = 0 var q = PriorityQueue>(Comparator{ a: Pair, b: Pair -> a.first.compareTo(b.first) }) q.add(Pair(0, start)) while (0 < q.size) { var (cost, u) = q.poll() if (seen.contains(u)) continue dist[u] = cost; seen.add(u) for ((w, v) in adj[u]!!) { if (seen.contains(v)) continue q.add(Pair(cost + w, v)) } } return dist } override fun run(filename: String, queries: Array): String { var adj = mutableMapOf>>() File(filename).forEachLine { var words = it.trim().split("\t") var u = words[0].toInt() if (!adj.contains(u)) adj[u] = mutableListOf() for (i in 1 until words.size) { var (v, w) = words[i].split(",").map{ it.toInt() } adj[u]!!.add(Pair(w, v)) } } var dist = dijkstra(adj) return queries.map{ dist[it] }.joinToString(" ") } }

fun run(solution: BaseSolution) { println(solution.run("problem9.8test.txt", arrayOf(1, 2, 3, 4, 5, 6, 7, 8))) println(solution.run("problem9.8.txt", arrayOf(7, 37, 59, 82, 99, 115, 133, 165, 188, 197))) }

fun main() { run(NaiveSolution()) // 0 1 2 3 4 4 3 2 // 2599 2610 2947 2052 2367 2399 2029 2442 2505 3068 run(HeapSolution()) // 0 1 2 3 4 4 3 2 // 2599 2610 2947 2052 2367 2399 2029 2442 2505 3068 } ```

Javascript ```javascript let LineByLine = require('n-readlines');

let INF = Number(1e9 + 7);

class NaiveSolution { dijkstra(E) { let dist = new Map(); let seen = new Set(); let start = 1; dist[start] = 0; seen.add(start); for (;;) { let found = false; let bestv = INF, bestw = INF; for (let [u, v, w] of E) { if (!seen.has(u) || seen.has(v)) continue; found = true; if (bestw > dist[u] + w) bestv = v, bestw = dist[u] + w; } if (!found) break; let [v, w] = [bestv, best_w]; dist[v] = w; seen.add(v); } return dist; } run(filename, queries) { let E = []; let input = new LineByLine(filename); let line; while (line = input.next()) { let words = String.fromCharCode(...line).trim().split(/\s+/); let u = Number(words[0]); for (let i = 1; i < words.length; ++i) { let [v, w] = words[i].split(',').map(Number); E.push([ u, v, w ]); } } let dist = this.dijkstra(E); return queries.map(x => dist[x]).join(' '); } }

let heapkey = x => Array.isArray(x) ? x[0] : x; let heappush = (A, x, f = Math.min) => { let P = i => Math.floor((i - 1) / 2); // parent A.push(x); let N = A.length, i = N - 1; while (0 < i && heapkey(A[i]) == f(heapkey(A[i]), heapkey(A[P(i)]))) { [A[i], A[P(i)]] = [A[P(i)], A[i]]; i = P(i); } }; let heappop = (A, f = Math.min) => { let L = i => 2 * i + 1, // children R = i => 2 * i + 2; let N = A.length, i = 0; let top = A[0]; [A[0], A[N - 1]] = [A[N - 1], A[0]], A.pop(), --N; let ok = true; do { ok = true; let left = f == Math.min ? Infinity : -Infinity, right = left; if (L(i) < N && heapkey(A[i]) != f(heapkey(A[i]), heapkey(A[L(i)]))) ok = false, left = heapkey(A[L(i)]); if (R(i) < N && heapkey(A[i]) != f(heapkey(A[i]), heapkey(A[R(i)]))) ok = false, right = heapkey(A[R(i)]); if (!ok) { let j = left == f(left, right) ? L(i) : R(i); [A[i], A[j]] = [A[j], A[i]]; i = j; } } while (!ok); return top; };

class HeapSolution { dijkstra(adj) { let dist = {}; let seen = new Set(); let start = 1; let q = [[ 0, start ]]; while (q.length) { let [cost, u] = heappop(q); if (seen.has(u)) continue; dist[u] = cost, seen.add(u); for (let [w, v] of (adj[u] || [])) heappush(q, [ dist[u] + w, v ]); } return dist; } run(filename, queries) { let adj = {}; let input = new LineByLine(filename); let line; while (line = input.next()) { let words = String.fromCharCode(...line).trim().split('\t'); let u = Number(words[0]); if (!(u in adj)) adj[u] = []; for (let i = 1; i < words.length; ++i) { let [v, w] = words[i].split(',').map(Number); adj[u].push([ w, v ]); } } let dist = this.dijkstra(adj); return queries.map(x => dist[x]).join(' '); } }

let run = solution => { console.log(solution.run('problem9.8test.txt', [1, 2, 3, 4, 5, 6, 7, 8])); console.log(solution.run('problem9.8.txt', [7, 37, 59, 82, 99, 115, 133, 165, 188, 197])); };

run(new NaiveSolution()); // 0 1 2 3 4 4 3 2 // 2599 2610 2947 2052 2367 2399 2029 2442 2505 3068

run(new HeapSolution()); // 0 1 2 3 4 4 3 2 // 2599 2610 2947 2052 2367 2399 2029 2442 2505 3068 ```

Python3 ```python from abc import ABC, abstractmethod from heapq import heappush, heappop

INF = int(1e9 + 7)

class BaseSolution(ABC): @abstractmethod def run(self, filename, queries): raise NotImplementedError

class NaiveSolution(BaseSolution): def dijkstra(self, E): dist = {} seen = set() start = 1 dist[start] = 0; seen.add(start) while True: found = False bestv = INF bestw = INF for u, v, w in E: if u not in seen or v in seen: continue found = True if bestw > dist[u] + w: bestv = v bestw = dist[u] + w if not found: break v, w = bestv, best_w dist[v] = w; seen.add(v) return dist def run(self, filename, queries): E = [] with open(filename) as fin: while True: line = fin.readline() if not line: break words = line.split() u = int(words[0]) for i in range(1, len(words)): v, w = map(int, words[i].split(',')) E.append([ u, v, w ]) dist = self.dijkstra(E) return ' '.join(str(dist[x]) for x in queries)

class HeapSolution(BaseSolution): def dijkstra(self, adj, start = 1): dist = {} seen = set() q = [[ 0, start ]] while len(q): cost, u = heappop(q) if u in seen: continue dist[u] = cost; seen.add(u) for w, v in adj[u]: if v not in seen: heappush(q, [ dist[u] + w, v ]) return dist def run(self, filename, queries): adj = {} with open(filename) as fin: while True: line = fin.readline() if not line: break words = line.split() u = int(words[0]) if u not in adj: adj[u] = [] for i in range(1, len(words)): v, w = map(int, words[i].split(',')) adj[u].append([ w, v ]) dist = self.dijkstra(adj) return ' '.join(str(dist[x]) for x in queries)

def run(solution): print(solution.run('problem9.8test.txt', [1, 2, 3, 4, 5, 6, 7, 8])) print(solution.run('problem9.8.txt', [7, 37, 59, 82, 99, 115, 133, 165, 188, 197]))

run(NaiveSolution())

0 1 2 3 4 4 3 2

2599 2610 2947 2052 2367 2399 2029 2442 2505 3068

run(HeapSolution())

0 1 2 3 4 4 3 2

2599 2610 2947 2052 2367 2399 2029 2442 2505 3068

```

C++ ```cpp

include

include

include

include

include

include

include

using namespace std;

using Queries = vector; using Distance = unorderedmap; using Set = unorderedset;

class BaseSolution { protected: static constexpr auto INF = int(1e9 + 7); public: virtual string run(string filename, Queries&& queries) = 0; };

class NaiveSolution : public BaseSolution { using Edge = tuple; using Edges = vector; public: Distance dijkstra(Edges& E) { Distance dist; Set seen; auto start{ 1 }; dist[start] = 0, seen.insert(start); for (;;) { auto found = false; auto bestv = INF, bestw = INF; for (auto [u, v, w]: E) { if (seen.find(u) == seen.end() || seen.find(v) != seen.end()) continue; found = true; if (bestw > dist[u] + w) bestv = v, bestw = dist[u] + w; } if (!found) break; auto [v, w] = tie(bestv, bestw); dist[v] = w, seen.insert(v); } return dist; } string run(string filename, Queries&& queries) { Edges E; fstream fin{ filename }; string line; int u, v, w; char _; while (getline(fin, line)) { istringstream is{ line }; for (is >> u; is >> v >> _ >> w; E.pushback({ u, v, w })); } auto dist = dijkstra(E); ostringstream os; transform(queries.begin(), queries.end(), ostream_iterator(os, " "), & { return dist[x]; }); return os.str(); } };

class HeapSolution : public BaseSolution { using Pair = pair; using Pairs = vector; using AdjList = unorderedmap; priorityqueue> q; public: Distance dijkstra(AdjList& adj) { Distance dist; Set seen; for (auto [u, ]: adj) dist[u] = INF; auto start{ 1 }; q.push({ 0, start }); while (q.size()) { auto [cost, u] = q.top(); q.pop(); if (!seen.insert(u).second) continue; dist[u] = cost; for (auto [w, v]: adj[u]) if (seen.find(v) == seen.end()) q.push({ dist[u] + w, v }); } return dist; } string run(string filename, Queries&& queries) { AdjList adj; fstream fin{ filename }; string line; int u, v, w; char _; while (getline(fin, line)) { istringstream is{ line }; for (is >> u; is >> v >> _ >> w; adj[u].pushback({ w, v })); } auto dist = dijkstra(adj); ostringstream os; transform(queries.begin(), queries.end(), ostream_iterator(os, " "), & { return dist[x]; }); return os.str(); } };

void run(BaseSolution&& solution) { cout << "problem9.8test.txt: " << solution.run("problem9.8test.txt", Queries{1, 2, 3, 4, 5, 6, 7, 8 }) << endl << "problem9.8.txt " << solution.run("problem9.8.txt", Queries{7, 37, 59, 82, 99, 115, 133, 165, 188, 197 }) << endl; }

int main() { run(NaiveSolution()); // problem9.8test.txt: 0 1 2 3 4 4 3 2 // problem9.8.txt 2599 2610 2947 2052 2367 2399 2029 2442 2505 3068

run(HeapSolution());

// problem9.8test.txt: 0 1 2 3 4 4 3 2 // problem9.8.txt 2599 2610 2947 2052 2367 2399 2029 2442 2505 3068 return 0; } ```

• Introduction to Greedy Algorithms (Section 13.1)
• A Scheduling Problem (Section 13.2)
• Developing a Greedy Algorithm (Section 13.3)
• Scheduling: Correctness Proof (Part 1) (Section 13.4, Part 1)
• Scheduling: Correctness Proof (Part 2) (Section 13.4, Part 2)
• Scheduling: Correctness Proof (Part 3) (Section 13.4, Part 3)

Kotlin ```kotlin import java.io.File

data class Job(val weight: Long, val length: Long)

class Solution { fun minSum(jobs: Array): Pair { class Diff: Comparator { override fun compare(a: Job?, b: Job?): Int { if (a == null || b == null) return 0 var first = a.weight - a.length var second = b.weight - b.length return if (first == second) b.weight.compareTo(a.weight) else second.compareTo(first) // sort by descending difference, break ties in favor of jobs with larger weights } } class Ratio: Comparator { override fun compare(a: Job?, b: Job?): Int { if (a == null || b == null) return 0 var first = a.weight.toDouble() / a.length var second = b.weight.toDouble() / b.length return if (first == second) b.weight.compareTo(a.weight) else second.compareTo(first) // sort by descending difference, break ties in favor of jobs with larger weights } } return Pair(calcSum(jobs, Diff()), calcSum(jobs, Ratio())) } private fun calcSum(jobs: Array, comp: Comparator): Long { jobs.sortWith(comp) var time: Long = 0 var total: Long = 0 jobs.forEach { job -> time += job.length total += job.weight * time } return total } }

fun run(filename: String) { var jobs = mutableListOf() var first = true File(filename).forEachLine { if (!first) { var words = it.trim().split(" ").map{ it.toLong() } var (weight, length) = words jobs.add(Job(weight, length)) } else { first = false } } var (diff, ratio) = Solution().minSum(jobs.toTypedArray()) println("$diff, $ratio") // sub-optimal, optimal }

fun main() { run("problem13.4test1.txt") // 23, 22 run("problem13.4test2.txt") // 68615, 67247 run("problem13.4.txt") // 69119377652, 67311454237 } ```

Javascript ```javascript let LineByLine = require('n-readlines');

class Job { constructor(weight, length) { this.weight = weight; this.length = length; } }

class Solution { minSum(jobs) { let diff = (a, b) => { let first = a.weight - a.length, second = b.weight - b.length; return first == second ? b.weight - a.weight : second - first; // sort by descending difference, break ties in favor of jobs with larger weights }; let ratio = (a, b) => { let first = a.weight / a.length, second = b.weight / b.length; return first == second ? b.weight - a.weight : second - first; // sort by descending ratio, break ties in favor of jobs with larger weights }; return [ this.calcSum(jobs, diff), this.calcSum(jobs, ratio) ]; } _calcSum(jobs, comp, time = 0) { jobs.sort((a, b) => comp(a, b)); return jobs.reduce((total, job) => total + job.weight * (time += job.length), 0); } }

let run = filename => { let jobs = []; let input = new LineByLine(filename); let line = input.next(); // N while (line = input.next()) { let words = String.fromCharCode(...line).trim().split(' '); let [weight, length] = words.map(Number); jobs.push(new Job(weight, length)); } let [diff, ratio] = new Solution().minSum(jobs); console.log(${diff}, ${ratio}); // sub-optimal, optimal };

run('problem13.4test1.txt'); // 23, 22 run('problem13.4test2.txt'); // 68615, 67247 run('problem13.4.txt'); // 69119377652, 67311454237 ```

Python3 ```python from functools import cmptokey

class Job: def init(self, weight, length): self.weight = weight self.length = length

class Solution: def minSum(self, jobs): def diff(a, b): first = a.weight - a.length second = b.weight - b.length return b.weight - a.weight if first == second else second - first # sort by descending difference, break ties in favor of jobs with larger weights def ratio(a, b): first = a.weight / a.length second = b.weight / b.length return b.weight - a.weight if first == second else second - first # sort by descending difference, break ties in favor of jobs with larger weights return [ self.calcSum(jobs, diff), self.calcSum(jobs, ratio) ] def calcSum(self, jobs, comp, time = 0, total = 0): jobs.sort(key = cmpto_key(lambda a, b: comp(a, b))) for job in jobs: time += job.length total += job.weight * time return total

def run(filename): jobs = [] with open(filename) as fin: line = fin.readline() # N while True: line = fin.readline().strip() if not line: break words = line.split() weight, length = [int(x) for x in words] jobs.append(Job(weight, length)) diff, ratio = Solution().minSum(jobs) print(f'{diff}, {ratio}') # sub-optimal, optimal

run('problem13.4test1.txt') # 23, 22 run('problem13.4test2.txt') # 68615, 67247 run('problem13.4.txt') # 69119377652, 67311454237 ```

C++ ```cpp

include

include

include

include

using namespace std;

using LL = long long; struct Job { LL weight, length; Job(LL weight, LL length) : weight{ weight }, length{ length } {} }; using Jobs = vector;

class Solution { public: using Pair = pair; // sub-optimal, optimal Pair minSum(Jobs& jobs) { auto diff = { auto first = a.weight - a.length, second = b.weight - b.length; return first == second ? b.weight < a.weight : second < first; // sort by descending difference, break ties in favor of jobs with larger weights }; auto ratio = { auto first = double(a.weight) / a.length, second = double(b.weight) / b.length; return first == second ? b.weight < a.weight : second < first; // sort by descending ratio, break ties in favor of jobs with larger weights }; return { calcSum(jobs, diff), calcSum(jobs, ratio) }; } private: template LL calcSum(Jobs& jobs, Comp comp, LL time = 0LL) { sort(jobs.begin(), jobs.end(), comp); return accumulate(jobs.begin(), jobs.end(), 0LL, & { return total += job.weight * (time += job.length); }); } };

void run(const string& filename) { Jobs jobs; LL N, weight, length; fstream fin{ filename }; for (fin >> N; fin >> weight >> length; jobs.emplace_back(Job{ weight, length })); auto [diff, ratio] = Solution().minSum(jobs); cout << diff << ", " << ratio << endl; }

int main() { run("problem13.4test1.txt"); // 23, 22 run("problem13.4test2.txt"); // 68615, 67247 run("problem13.4.txt"); // 69119377652, 67311454237 return 0; } ```

• Codes (Section 14.1)
• Codes as Trees (Section 14.2)
• Huffman's Greedy Algorithm (Part 1) (Section 14.3, Part 1)
• Huffman's Greedy Algorithm (Part 2) (Section 14.3, Part 2)
• Huffman's Algorithm: Correctness Proof (Part 1) (Section 14.4, Part 1)
• Huffman's Algorithm: Correctness Proof (Part 2) (Section 14.4, Part 2)

Kotlin ```kotlin import java.io.File import java.util.PriorityQueue import java.util.Queue import java.util.LinkedList

var INF = (1e9 + 7).toInt()

data class Tree(val weight: Int, val left: Tree? = null, val right: Tree? = null)

/* fun encode(A: List): Tree { var q = PriorityQueue(Comparator{ a: Tree, b: Tree -> a.weight.compareTo(b.weight) }) for (weight in A) q.add(Tree(weight)) while (1 < q.size) { var a = q.poll() var b = q.poll() var c = Tree(a.weight + b.weight, a, b) q.add(c) } return q.poll() } */

/* * Problem 14.5: Give an implementation of Huffman's greedy algorithm that uses a single invocation * of a sorting subroutine, followed by a linear amount of additional work. */ fun encode(A: MutableList): Tree { A.sort() var first: Queue = LinkedList(A.map{ weight -> Tree(weight) }.toList()) var second: Queue = LinkedList() var next = mutableListOf() while (1 < first.size + second.size) { next.clear() do { if (0 < first.size && 0 < second.size) { if (first.peek().weight < second.peek().weight) next.add(first.poll()) else next.add(second.poll()) } else if (0 < first.size) next.add(first.poll()) else if (0 < second.size) next.add(second.poll()) } while (next.size < 2) var (a, b) = next var c = Tree(a.weight + b.weight, a, b) second.add(c) } return second.poll() }

fun run(filename: String): Pair { var A = mutableListOf() var first = true File(filename).forEachLine { if (!first) { var weight = it.trim().toInt() A.add(weight) } else { first = false } } var tree = encode(A.toMutableList()) var lo = INF var hi = -INF fun go(root: Tree? = tree, depth: Int = 0) { if (root == null) return var isLeaf = { node: Tree? -> node?.left == null && node?.right == null } if (isLeaf(root)) { lo = Math.min(lo, depth) hi = Math.max(hi, depth) } else { go(root.left, depth + 1) go(root.right, depth + 1) } } go() return Pair(lo, hi) }

fun main() { for (filename in listOf("problem14.6test1.txt", "problem14.6test2.txt", "problem14.6.txt")) { var (lo, hi) = run(filename) println("$filename: $lo, $hi") // min, max encoding length in the corresponding optimal prefix-free tree } }

// problem14.6test1.txt: 2, 5 // problem14.6test2.txt: 3, 6 // problem14.6.txt: 9, 19 ```

Javascript ```javascript let LineByLine = require('n-readlines');

class Tree { constructor(weight, left = null, right = null) { this.weight = weight; this.left = left; this.right = right; } }

/* let key = x => Array.isArray(x) ? x[0] : x; let heappush = (A, x, f = Math.min) => { let P = i => Math.floor((i - 1) / 2); // parent A.push(x); let N = A.length, i = N - 1; while (0 < i && key(A[i]) == f(key(A[i]), key(A[P(i)]))) { [A[i], A[P(i)]] = [A[P(i)], A[i]]; i = P(i); } }; let heappop = (A, f = Math.min) => { let L = i => 2 * i + 1, // children R = i => 2 * i + 2; let N = A.length, i = 0; let top = A[0]; [A[0], A[N - 1]] = [A[N - 1], A[0]], A.pop(), --N; let ok; do { ok = true; let left = f == Math.min ? Infinity : -Infinity, right = left; if (L(i) < N && key(A[i]) != f(key(A[i]), key(A[L(i)]))) ok = false, left = key(A[L(i)]); if (R(i) < N && key(A[i]) != f(key(A[i]), key(A[R(i)]))) ok = false, right = key(A[R(i)]); if (!ok) { let j = left == f(left, right) ? L(i) : R(i); [A[i], A[j]] = [A[j], A[i]]; i = j; } } while (!ok); return top; };

let encode = A => { let T = []; for (let weight of A) heappush(T, [ weight, new Tree(weight) ]); while (1 < T.length) { let [ a, b ] = [ heappop(T), heappop(T) ]; let c = [ a[0] + b[0], new Tree(a[0] + b[0], a[1], b[1]) ]; heappush(T, c); } return T[0][1]; }; */

/* * Problem 14.5: Give an implementation of Huffman's greedy algorithm that uses a single invocation * of a sorting subroutine, followed by a linear amount of additional work. */ let encode = A => { A.sort((a, b) => a - b) let first = A.map(weight => new Tree(weight)), second = []; while (1 < first.length + second.length) { let next = []; while (next.length < 2) { if (first.length && second.length) { next.push(first[0].weight < second[0].weight ? first.shift() : second.shift()); } else if (first.length) next.push(first.shift()); else if (second.length) next.push(second.shift()); } let [a, b] = next; let c = new Tree(a.weight + b.weight, a, b); second.push(c); } return second.shift(); };

let run = filename => { let A = []; let input = new LineByLine(filename); let line; line = input.next(); // N while (line = input.next()) { let weight = Number(String.fromCharCode(...line).trim()); A.push(weight); } let tree = encode(A); let [lo, hi] = [Infinity, -Infinity]; let go = (root = tree, depth = 0) => { if (!root) return; let isLeaf = root => !root.left && !root.right; if (isLeaf(root)) lo = Math.min(lo, depth), hi = Math.max(hi, depth); else go(root.left, depth + 1), go(root.right, depth + 1); }; go(); return [ lo, hi ]; }

for (let filename of [ 'problem14.6test1.txt', 'problem14.6test2.txt', 'problem14.6.txt' ]) { let [lo, hi] = run(filename); console.log(${filename}: ${lo}, ${hi}); // min, max encoding length in the corresponding optimal prefix-free tree }

// problem14.6test1.txt: 2, 5 // problem14.6test2.txt: 3, 6 // problem14.6.txt: 9, 19 ```

Python3 ```python class Tree: def init(self, weight, left = None, right = None): self.weight = weight self.left = left self.right = right def lt(self, other): return self.weight < other.weight

#

priority queue

#

from heapq import heappush

from heapq import heappop

def encode(A):

T = []

for weight in A:

heappush(T, Tree(weight))

while 1 < len(T):

a, b = heappop(T), heappop(T)

c = Tree(a.weight + b.weight, a, b)

heappush(T, c)

return heappop(T)

#

Problem 14.5: Give an implementation of Huffman's greedy algorithm that uses a single invocation

of a sorting subroutine, followed by a linear amount of additional work.

# from collections import deque def encode(A): A.sort() first, second = deque([Tree(weight) for weight in A]), deque() while 1 < len(first) + len(second): next = [] while len(next) < 2: if len(first) and len(second): next.append(first.popleft() if first[0].weight < second[0].weight else second.popleft()) elif len(first): next.append(first.popleft()) elif len(second): next.append(second.popleft()) a, b = next c = Tree(a.weight + b.weight, a, b) second.append(c) return second.popleft()

def run(filename): A = [] with open(filename) as fin: N = int(fin.readline()) while True: line = fin.readline() if not line: break weight = int(line.strip()) A.append(weight) tree = encode(A) lo, hi = float('inf'), float('-inf') def go(root = tree, depth = 0): nonlocal lo, hi if not root: return isLeaf = lambda root: not root.left and not root.right if isLeaf(root): lo = min(lo, depth) hi = max(hi, depth) else: go(root.left, depth + 1) go(root.right, depth + 1) go() return [ lo, hi ]

for filename in [ 'problem14.6test1.txt', 'problem14.6test2.txt', 'problem14.6.txt' ]: lo, hi = run(filename) print(f'{filename}: {lo}, {hi}') # min, max encoding length in the corresponding optimal prefix-free tree

problem14.6test1.txt: 2, 5

problem14.6test2.txt: 3, 6

problem14.6.txt: 9, 19

```

C++ ```cpp

include

include

include

include

include

define PRIORITY_QUEUE // O(N * logN)

ifndef PRIORITY_QUEUE

define TWO_QUEUES // O(N)

endif

using namespace std; using LL = long long; using Weight = LL; using Weights = vector;

struct Tree; using TreePtr = shared_ptr; struct Tree { Weight weight; TreePtr left, right; Tree(Weight weight, TreePtr left = nullptr, TreePtr right = nullptr) : weight{ weight }, left{ left }, right{ right } {} }; using TreePtrs = vector;

ifdef PRIORITY_QUEUE

struct Comp { sizet operator()(const TreePtr& a, const TreePtr& b) const { return b->weight < a->weight; } }; using Queue = priorityqueue; TreePtr encode(const Weights& A, Queue q = {}) { for (auto weight: A) q.emplace(makeshared(weight)); while (1 < q.size()) { auto a = q.top(); q.pop(); auto b = q.top(); q.pop(); auto c = makeshared(a->weight + b->weight, a, b); q.emplace(c); } return q.top(); }

else // TWO_QUEUES

/* * Problem 14.5: Give an implementation of Huffman's greedy algorithm that uses a single invocation * of a sorting subroutine, followed by a linear amount of additional work. */ using Queue = queue; TreePtr encode(Weights& A, Queue first = {}, Queue second = {}) { sort(A.begin(), A.end()); for (auto weight: A) first.push(makeshared(weight)); TreePtrs next; auto takeFirst = & { next.pushback(first.front()), first.pop(); }; auto takeSecond = & { next.pushback(second.front()), second.pop(); }; while (1 < first.size() + second.size()) { next.clear(); do { if (first.size() && second.size()) { if (first.front()->weight < second.front()->weight) takeFirst(); else takeSecond(); } else if (first.size()) takeFirst(); else if (second.size()) takeSecond(); } while (next.size() < 2); auto [a, b] = tie(next[0], next[1]); auto c = makeshared(a->weight + b->weight, a, b); second.emplace(c); } return second.front(); }

endif

using MinMax = pair; constexpr auto Min = numericlimits::min(); constexpr auto Max = numericlimits::max(); MinMax run(const string& filename) { Weights A; // weight of each symbol fstream fin{ filename }; LL N, weight; for (fin >> N; fin >> weight; A.pushback(weight)); auto tree = encode(A); LL lo = Max, hi = Min; using fun = function& { if (!root) return; auto isLeaf = { return !root->left && !root->right; }; if (isLeaf(root)) lo = min(lo, depth), hi = max(hi, depth); else go(root->left, depth + 1), go(root->right, depth + 1); }; go(tree, 0); return makepair(lo, hi); }

int main() { for (auto& filename: { "problem14.6test1.txt", "problem14.6test2.txt", "problem14.6.txt" }) { auto [lo, hi] = run(filename); cout << filename << ": " << lo << ", " << hi << endl; // min, max encoding length in the corresponding optimal prefix-free tree } // problem14.6test1.txt: 2, 5 // problem14.6test2.txt: 3, 6 // problem14.6.txt: 9, 19 return 0; } ```

• Minimum Spanning Trees: Problem Definition (Section 15.1)
• Prim's MST Algorithm (Section 15.2)
• Speeding Up Prim's Algorithm via Heaps (Part 1) (Section 15.3, Part 1)
• Speeding Up Prim's Algorithm via Heaps (Part 2) (Section 15.3, Part 2)
• Prim's Algorithm: Correctness Proof (Part 1) (Section 15.4, Part 1) [Note: this video provides an alternative treatment to that in the book.]
• Prim's Algorithm: Correctness Proof (Part 2) (Section 15.4, Part 2) [Note: this video provides an alternative treatment to that in the book.]

Kotlin ```kotlin import java.io.File import java.util.PriorityQueue import java.util.Random

fun prim(N: Int, adj: MutableMap>>): Int { var total: Int = 0 var start = Random().nextInt(N) + 1 var q = PriorityQueue>(Comparator{ a: Pair, b: Pair -> a.first.compareTo(b.first) }) var seen = mutableSetOf(start) for ((w, v) in adj[start]!!) q.add(Pair(w, v)) while (0 < q.size) { var (cost, u) = q.poll() if (seen.contains(u)) continue total += cost; seen.add(u) for ((w, v) in adj[u]!!) if (!seen.contains(v)) q.add(Pair(w, v)) } return total }

fun run(filename: String) { var N: Int = 0 var adj = mutableMapOf>>() var first = true File(filename).forEachLine { line -> if (!first) { var (u, v, w) = line.split(" ").map{ it.toInt() } if (!adj.contains(u)) adj[u] = mutableListOf>() if (!adj.contains(v)) adj[v] = mutableListOf>() adj[u]!!.add(Pair(w, v)) adj[v]!!.add(Pair(w, u)) } else { var (numVertex, _) = line.split(" ").map{ it.toInt() } N = numVertex first = false } } var cost = prim(N, adj) println("$filename: $cost") }

fun main() { run("problem15.9test.txt") // problem15.9test.txt: 14 run("problem15.9.txt") // problem15.9.txt: -3612829 } ```

Javascript ```javascript let LineByLine = require('n-readlines');

let key = x => Array.isArray(x) ? x[0] : x; let heappush = (A, x, f = Math.min) => { let P = i => Math.floor((i - 1) / 2); // parent A.push(x); let N = A.length, i = N - 1; while (0 < i && key(A[i]) == f(key(A[i]), key(A[P(i)]))) { [A[i], A[P(i)]] = [A[P(i)], A[i]]; i = P(i); } }; let heappop = (A, f = Math.min) => { let L = i => 2 * i + 1, // children R = i => 2 * i + 2; let N = A.length, i = 0; let top = A[0]; [A[0], A[N - 1]] = [A[N - 1], A[0]], A.pop(), --N; let ok; do { ok = true; let left = f == Math.min ? Infinity : -Infinity, right = left; if (L(i) < N && key(A[i]) != f(key(A[i]), key(A[L(i)]))) ok = false, left = key(A[L(i)]); if (R(i) < N && key(A[i]) != f(key(A[i]), key(A[R(i)]))) ok = false, right = key(A[R(i)]); if (!ok) { let j = left == f(left, right) ? L(i) : R(i); [A[i], A[j]] = [A[j], A[i]]; i = j; } } while (!ok); return top; };

let prim = (N, adj, q = [], seen = new Set(), total = 0) => { let start = Math.ceil(N * Math.random()); seen.add(start); for (let [w, v] of adj.get(start)) heappush(q, [w, v]); while (q.length) { let [cost, u] = heappop(q); if (seen.has(u)) continue; total += cost; seen.add(u); for (let [w, v] of adj.get(u)) if (!seen.has(v)) heappush(q, [w, v]); } return total; };

let run = filename => { let adj = new Map(); let input = new LineByLine(filename); let line = input.next(); let [N, M] = String.fromCharCode(...line).trim().split(' ').map(Number); while (line = input.next()) { let [u, v, w] = String.fromCharCode(...line).trim().split(' ').map(Number); if (!adj.has(u)) adj.set(u, []); if (!adj.has(v)) adj.set(v, []); adj.get(u).push([w, v]); adj.get(v).push([w, u]); } let cost = prim(N, adj); console.log(${filename}: ${cost}); }

run('problem15.9test.txt') // problem15.9test.txt: 14 run('problem15.9.txt') // problem15.9.txt: -3612829 ```

Python3 ```python from random import randint from heapq import heappush, heappop

def prim(N, adj, total = 0): q = [] seen = set() start = randint(1, N); seen.add(start) for w, v in adj[start]: heappush(q, [w, v]) while q: cost, u = heappop(q) if u in seen: continue total += cost; seen.add(u) for w, v in adj[u]: if v not in seen: heappush(q, [w, v]) return total

def run(filename): adj = {} first = True with open(filename) as fin: while True: line = fin.readline() if not line: break words = line.split() if not first: u, v, w = [int(x) for x in words] if u not in adj: adj[u] = [] if v not in adj: adj[v] = [] adj[u].append([w, v]) adj[v].append([w, u]) else: N, M = [int(x) for x in words] first = False cost = prim(N, adj) print(f'{filename}: {cost}')

run('problem15.9test.txt') # problem15.9test.txt: 14 run('problem15.9.txt') # problem15.9.txt: -3612829 ```

C++ ```cpp

include

include

include

include

include

include

using namespace std; using Pair = pair; using Pairs = vector; using AdjList = unorderedmap; using Queue = priorityqueue>; using Set = unordered_set;

constexpr auto INF = int(1e9 + 7);

int getRandom(int N) { defaultrandomengine generator; uniformintdistribution distribution(1, N); return distribution(generator); }

int prim(int N, AdjList& adj, Queue q = {}, Set seen = {}, int total = 0) { auto start = getRandom(N); seen.insert(start); for (auto [w, v]: adj[start]) q.push({ w, v }); while (q.size()) { auto [cost, u] = q.top(); q.pop(); if (!seen.insert(u).second) continue; total += cost; for (auto [w, v]: adj[u]) if (seen.find(v) == seen.end()) q.push({ w, v }); } return total; }

void run(const string& filename) { AdjList adj; fstream fin{ filename }; int N, M; fin >> N >> M; // N vertices and M edges int u, v, w; // edge u -> v of weight w while (fin >> u >> v >> w) { adj[u].emplaceback(w, v); adj[v].emplaceback(w, u); } auto cost = prim(N, adj); cout << filename << ": " << cost << endl; }

int main() { run("problem15.9test.txt"); // problem15.9test.txt: 14 run("problem15.9.txt"); // problem15.9.txt: -3612829 return 0; } ```

• Minimum Spanning Trees: Problem Definition (Section 15.1)
• Kruskal's MST Algorithm (Section 15.5)
• Speeding Up Kruskal's Algorithm via Union-Find (Part 1) (Section 15.6, Part 1)
• Speeding Up Kruskal's Algorithm via Union-Find (Part 2) (Section 15.6, Part 2) [Note: this video provides an alternative treatment to that in the book.]
• Lazy Unions (Section 15.6, Part 3) [Note: this video is closer to the union-find implementation in the book.]
• Kruskal's Algorithm: Correctness Proof (Section 15.7) [Note: this video provides an alternative treatment to that in the book.]
• Application: Single-Link Clustering (Section 15.8)

Kotlin ```kotlin import java.io.File

fun kruskal(E: MutableList>): Int { var total: Int = 0 var M = E.size var P = IntArray(M) { it } // 🙂 parent representatives of 1..M disjoint sets fun find(x: Int): Int { P[x] = if (P[x] == x) x else find(P[x]) return P[x] } fun union(a: Int, b: Int): Boolean { var x = find(a) var y = find(b) if (x == y) return false P[x] = y // 🎲 arbitrary choice return true } E.sortWith(Comparator{ a, b -> a.third.compareTo(b.third) }) // sort edges by nondecreasing weight for ((u, v, w) in E) if (union(u, v)) total += w return total }

fun run(filename: String) { var E = mutableListOf>() var first = true File(filename).forEachLine { line -> if (!first) { var (u, v, w) = line.trim().split(" ").map{ it.toInt() } E.add(Triple(u, v, w)) } else { first = false // ignore first line with N vertices and M edges } } var cost = kruskal(E) println("$filename: $cost") }

fun main() { run("problem15.9test.txt") // problem15.9test.txt: 14 run("problem15.9.txt") // problem15.9.txt: -3612829 } ```

Javascipt ```javascript let LineByLine = require('n-readlines');

let kruskal = E => { let total = 0; let M = E.length; let P = [...Array(M).keys()]; // 🙂 parent representatives of 1..M disjoint sets let find = x => P[x] = P[x] == x ? x : find(P[x]); let union = (a, b) => { a = find(a); b = find(b); if (a == b) return false; P[a] = b; // 🎲 arbitrary choice return true; }; E.sort((first, second) => { // sort edges by nondecreasing weight let [u1, v1, w1] = first, [u2, v2, w2] = second; return w1 - w2; }); for (let [u, v, w] of E) if (union(u, v)) total += w; return total; };

let run = filename => { let E = []; let input = new LineByLine(filename); let line = input.next(); // ignore first line with N vertices and M edges while (line = input.next()) { let [u, v, w] = String.fromCharCode(...line).trim().split(' ').map(Number); E.push([ u, v, w ]); } let cost = kruskal(E); console.log(${filename}: ${cost}); };

run('problem15.9test.txt'); // problem15.9test.txt: 14 run('problem15.9.txt'); // problem15.9.txt: -3612829 ```

Python3 ```python from functools import cmptokey

def kruskal(E, total = 0): M = len(E) P = [i for i in range(M)] # 🙂 parent representatives of 1..M disjoint sets def find(x): P[x] = P[x] if P[x] == x else find(P[x]) return P[x] def union(a, b): a = find(a) b = find(b) if a == b: return False P[a] = b # 🎲 arbitary choice return True E.sort(key = cmptokey(lambda first, second: first[2] - second[2])) # sort edges by nondecreasing weight for u, v, w in E: if union(u, v): total += w return total

def run(filename): E = [] first = True with open(filename) as fin: while True: line = fin.readline() if not line: break values = [int(x) for x in line.strip().split()] if not first: u, v, w = values # edge u -> v of weight w E.append([ u, v, w ]) else: first = False # ignore first line with N vertices and M edges cost = kruskal(E) print(f'{filename}: {cost}')

run('problem15.9test.txt') # problem15.9test.txt: 14 run('problem15.9.txt') # problem15.9.txt: -3612829 ```

C++ ```cpp

include

include

include

include

include

using namespace std; using Edge = tuple; using Edges = vector; using Parents = vector; using fun = function

int kruskal(Edges& E, int total = 0) { auto M = E.size(); Parents P(M); iota(P.begin(), P.end(), 0); // 🙂 parent representatives of 1..M disjoint sets fun find = & { return P[x] = P[x] == x ? x : find(P[x]); }; auto join = & { a = find(a); b = find(b); if (a == b) return false; P[a] = b; // 🎲 arbitrary choice return true; }; sort(E.begin(), E.end(), { // sort edges by nondecreasing weight auto [u1, v1, w1] = first; auto [u2, v2, w2] = second; return w1 < w2; }); for (auto [u, v, w]: E) if (join(u, v)) total += w; return total; }

void run(const string& filename, Edges E = {}) { fstream fin{ filename }; int N, M; fin >> N >> M; // ignore first line with N vertices and M edges int u, v, w; // edge u -> v of weight w while (fin >> u >> v >> w) E.emplace_back(u, v, w); auto cost = kruskal(E); cout << filename << ": " << cost << endl; }

int main() { run("problem15.9test.txt"); // problem15.9test.txt: 14 run("problem15.9.txt"); // problem15.9.txt: -3612829 return 0; } ```

• The Weighted Independent Set Problem (Section 16.1)
• A Linear-Time Algorithm for WIS in Path Graphs (Part 1) (Section 16.2, Part 1)
• A Linear-Time Algorithm for WIS in Path Graphs (Part 2) (Section 16.2, Part 2)
• A Reconstruction Algorithm (Section 16.3)

Kotlin ```kotlin import java.io.File

fun topDown(A: MutableList): Long { var N = A.size var m = mutableMapOf() fun go(i: Int = N - 1): Long { if (m.contains(i)) // 🤔 memo return m[i]!! if (i < 0) { // 🛑 empty set m[i] = 0 return 0 } if (i == 0) { // 🛑 single set m[i] = A[0] return A[0] } var include = go(i - 2) + A[i] // ✅ include A[i] var exclude = go(i - 1) // 🚫 exclude A[i] m[i] = Math.max(include, exclude) // 🎯 best return m[i]!! } return go() }

fun bottomUp(A: MutableList): Long { var N = A.size var dp = LongArray(N + 1) // 🤔 memo dp[0] = 0 // 🛑 empty set dp[1] = A[0] // 🛑 single set for (i in 2..N) { var include = dp[i - 2] + A[i - 1] // ✅ include A[i] (use A[i - 1] since dp[i] is offset by 1 for explicit 🛑 empty set at index 0, ie. index -1 doesn't exist) var exclude = dp[i - 1] // 🚫 exclude A[i] dp[i] = Math.max(include, exclude) // 🎯 best } return dp[N] }

fun bottomUpMemOpt(A: MutableList): Long { var N = A.size var a: Long = 0 // 🤔 memo + 🛑 empty set var b: Long = A[0] // 🤔 memo + 🛑 single set var c: Long = -1 for (i in 2..N) { var include = a + A[i - 1] // ✅ include A[i] (use A[i - 1] since dp[i] is offset by 1 for explicit 🛑 empty set at index 0, ie. index -1 doesn't exist) var exclude = b // 🚫 exclude A[i] c = Math.max(include, exclude) // 🎯 best a = b; b = c // 👈 slide window } return c }

fun run(filename: String) { var A = mutableListOf() var first = true File(filename).forEachLine { line -> if (!first) { A.add(line.toLong()) } else { first = false } } var a = topDown(A) var b = bottomUp(A) var c = bottomUpMemOpt(A) assert(a == b && b == c) // 💩 sanity check println("$filename: $a") }

fun main() { run("problem16.6test.txt") // problem16.6test.txt: 2617 run("problem16.6.txt") // problem16.6.txt: 2955353732 } ```

Javascript ```javascript const assert = require('assert'); const LineByLine = require('n-readlines');

let top_down = (A, m = {}) => { let N = A.length; let go = (i = N - 1) => { if (m[i]) // 🤔 memo return m[i]; if (i < 0) return m[i] = 0; // 🛑 empty set if (!i) return m[i] = A[0]; // 🛑 single set let include = go(i - 2) + A[i], // ✅ include A[i] exclude = go(i - 1); // 🚫 exclude A[i] return m[i] = Math.max(include, exclude); // 🎯 best }; return go(); };

let bottom_up = A => { let N = A.length; let dp = Array(N + 1); // 🤔 memo dp[0] = 0; // 🛑 empty set dp[1] = A[0]; // 🛑 single set for (let i = 2; i <= N; ++i) { let include = dp[i - 2] + A[i - 1], // ✅ include A[i] (use A[i - 1] since dp[i] is offset by 1 for explicit 🛑 empty set at index 0, ie. index -1 doesn't exist) exclude = dp[i - 1]; // 🚫 exclude A[i] dp[i] = Math.max(include, exclude); // 🎯 best } return dp[N]; };

let bottomupmemopt = A => { let N = A.length; let a = 0, // 🤔 memo + 🛑 empty set b = A[0], // 🤔 memo + 🛑 single set c = -1; for (let i = 2; i <= N; ++i) { let include = a + A[i - 1], // ✅ include A[i] (use A[i - 1] since dp[i] is offset by 1 for explicit 🛑 empty set at index 0, ie. index -1 doesn't exist) exclude = b; // 🚫 exclude A[i] c = Math.max(include, exclude); // 🎯 best a = b, b = c; // 👈 slide window } return c; };

let run = filename => { let A = []; let input = new LineByLine(filename); let line; let first = true; while (line = input.next()) { if (!first) { A.push(Number(line.toString('ascii'))); } else { first = false; } } let a = topdown(A), b = bottomup(A), c = bottomupmemopt(A); assert(a == b && b == c); // 💩 sanity check console.log(${filename}: ${a}); };

run('problem16.6test.txt'); // problem16.6test.txt: 2617 run('problem16.6.txt'); // problem16.6.txt: 2955353732 ```

Python3 ```python from functools import lru_cache

def topdown(A): N = len(A) @lrucache # 🤔 memo def go(i = N - 1): if i < 0: return 0 # 🛑 empty set if i == 0: return A[0] # 🛑 single set include = go(i - 2) + A[i] # ✅ include A[i] exclude = go(i - 1) # 🚫 exclude A[i] return max(include, exclude) # 🎯 best return go()

def bottom_up(A): N = len(A) dp = [0] * (N + 1) # 🤔 memo dp[0] = 0 # 🛑 empty set dp[1] = A[0] # 🛑 single set for i in range(2, N + 1): include = dp[i - 2] + A[i - 1] # ✅ include A[i] (use A[i - 1] since dp[i] is offset by 1 for explicit 🛑 empty set at index 0, ie. index -1 doesn't exist) exclude = dp[i - 1] # 🚫 exclude A[i] dp[i] = max(include, exclude) # 🎯 best return dp[N]

def bottomupmemopt(A): N = len(A) a = 0 # 🤔 memo + 🛑 empty set b = A[0] # 🤔 memo + 🛑 single set c = -1 for i in range(2, N + 1): include = a + A[i - 1] # ✅ include A[i] (use A[i - 1] since dp[i] is offset by 1 for explicit 🛑 empty set at index 0, ie. index -1 doesn't exist) exclude = b # 🚫 exclude A[i] c = max(include, exclude) # 🎯 best a = b; b = c # 👈 slide window return c

def run(filename): A = [] with open(filename) as fin: first = True while True: line = fin.readline() if not line: break x = int(line) if not first: A.append(x) else: first = False N = x a = topdown(A) b = bottomup(A) c = bottomupmemopt(A) assert(a == b and b == c) # 💩 sanity check print(f'{filename}: {a}')

run('problem16.6test.txt') # problem16.6test.txt: 2617 run('problem16.6.txt') # problem16.6.txt: 2955353732 ```

C++ ```cpp

include

include

include

include

include

using namespace std; using LL = long long; using List = vector; using Map = unordered_map;

namespace TopDown { LL best(List& A, Map m = {}) { int N = A.size(); using fun = function& { if (m[i]) return m[i]; // 🤔 memo if (i < 0) return m[i] = 0LL; // 🛑 empty set if (!i) return m[i] = A[0]; // 🛑 single set auto include = go(i - 2) + A[i], // ✅ include A[i] exclude = go(i - 1); // 🚫 exclude A[i] return m[i] = max(include, exclude); // 🎯 best }; return go(N - 1); } } namespace BottomUp { LL best(List& A, Map m = {}) { int N = A.size(); List dp(N + 1); // 🤔 memo dp[0] = 0LL; // 🛑 empty set dp[1] = A[0]; // 🛑 single set for (auto i{ 2 }; i <= N; ++i) { auto include = dp[i - 2] + A[i - 1], // ✅ include A[i] (use A[i - 1] since dp[i] is offset by 1 for explicit 🛑 empty set at index 0, ie. index -1 doesn't exist) exclude = dp[i - 1]; // 🚫 exclude A[i] dp[i] = max(include, exclude); // 🎯 best } return dp[N]; } }

namespace BottomUpMemOpt { LL best(List& A) { int N = A.size(); LL a = 0LL, // 🤔 memo + 🛑 empty set b = A[0], // 🤔 memo + 🛑 single set c = -1; for (auto i{ 2 }; i <= N; ++i) { auto include = a + A[i - 1], // ✅ include A[i] (use A[i - 1] since dp[i] is offset by 1 for explicit 🛑 empty set at index 0, ie. index -1 doesn't exist) exclude = b; // 🚫 exclude A[i] c = max(include, exclude); // 🎯 best a = b, b = c; // 👈 slide window } return c; } }

void run(const string& filename) { List A; fstream fin{ filename }; int N; fin >> N; copyn(istreamiterator(fin), N, back_inserter(A)); auto a = TopDown::best(A), b = BottomUp::best(A), c = BottomUpMemOpt::best(A); assert(a == b && b == c); // 💩 sanity check cout << filename << ": " << a << endl; }

int main() { run("problem16.6test.txt"); // problem16.6test.txt: 2617 run("problem16.6.txt"); // problem16.6.txt: 2955353732 return 0; } ```

• Principles of Dynamic Programming (Section 16.4)
• The Knapsack Problem (Part 1) (Section 16.5, Part 1)
• The Knapsack Problem (Part 2) (Section 16.5, Part 2)
• The Knapsack Problem (Part 3) (Section 16.5, Part 3)

Kotlin ```kotlin import java.io.File

var INF = (1e9 + 7).toInt()

fun top_down(A: List>, K: Int): Int { var N = A.size var m = mutableMapOf() fun go(i: Int = 0, k: Int = K): Int { if (i == N) // 🛑 empty set return 0 var key = "$i,$k" if (m.contains(key)) // 🤔 memo return m[key]!! var (value, weight) = A[i] var include = if (0 <= k - weight) go(i + 1, k - weight) + value else -INF // ✅ include A[i] var exclude = go(i + 1, k) // 🚫 exclude A[i] m[key] = Math.max(include, exclude) // 🎯 best return m[key]!! } return go() }

fun bottom_up(A: List>, K: Int): Int { var N = A.size var dp = Array(N + 1){ Array(K + 1){ -INF } } // 🤔 memo for (k in 0..K) // 🛑 empty set dp[0][k] = 0 for (i in 1..N) { for (k in 0..K) { var (value, weight) = A[i - 1] var include = if (0 <= k - weight) dp[i - 1][k - weight] + value else -INF // ✅ include A[i] var exclude = dp[i - 1][k] // 🚫 exclude A[i] dp[i][k] = Math.max(include, exclude) // 🎯 best } } return dp[N][K] }

fun bottomupmemopt(A: List>, K: Int): Int { var N = A.size var pre = Array(K + 1) { 0 } // 🤔 memo + 🛑 empty set for (i in 1..N) { var cur = Array(K + 1) { -INF } for (k in 0..K) { var (value, weight) = A[i - 1] var include = if (0 <= k - weight) pre[k - weight] + value else -INF // ✅ include A[i] var exclude = pre[k] // 🚫 exclude A[i] cur[k] = Math.max(include, exclude) // 🎯 best } pre = cur.also { cur = pre } } return pre[K] }

fun run(filename: String) { var A = mutableListOf>() var K = 0 var N = 0 var first = true File(filename).forEachLine { line -> if (!first) { var (value, weight) = line.trim().split(" ").map{ it -> it.toInt() } A.add(Pair(value, weight)) } else { var (a, b) = line.trim().split(" ").map{ it -> it.toInt() } K = a N = b first = false } } var a = topdown(A, K) var b = bottomup(A, K) var c = bottomupmemopt(A, K) assert(a == b && b == c) // 💩 sanity check println("$filename: $a") }

fun main() { run("problem16.7test.txt") // problem16.7test.txt: 2493893 } ```

Javascript ```javascript const assert = require('assert'); const LineByLine = require('n-readlines');

let top_down = (A, K, m = new Map()) => { let N = A.length; let go = (i = 0, k = K) => { if (i == N) // 🛑 empty set return 0; let key = ${i},${k}; if (m.has(key)) // 🤔 memo return m.get(key); let [value, weight] = A[i]; let include = 0 <= k - weight ? go(i + 1, k - weight) + value : -Infinity, // ✅ include A[i] exclude = go(i + 1, k); // 🚫 exclude A[i] return m.set(key, Math.max(include, exclude)) // 🎯 best .get(key); }; return go(); };

let bottomup = (A, K) => { let N = A.length; let dp = [...Array(N + 1)].map( => Array(K + 1).fill(-Infinity)); // 🤔 memo for (let k = 0; k < K; dp[0][k++] = 0); // 🛑 empty set for (let i = 1; i <= N; ++i) { for (let k = 0; k <= K; ++k) { let [value, weight] = A[i - 1]; let include = 0 <= k - weight ? dp[i - 1][k - weight] + value : -Infinity, // ✅ include A[i] exclude = dp[i - 1][k]; // 🚫 exclude A[i] dp[i][k] = Math.max(include, exclude); // 🎯 best } } return dp[N][K]; };

let bottomupmemopt = (A, K) => { let N = A.length; let pre = Array(K + 1).fill(0); // 🤔 memo + 🛑 empty set for (let i = 1; i <= N; ++i) { let cur = Array(K + 1).fill(-Infinity); for (let k = 0; k <= K; ++k) { let [value, weight] = A[i - 1]; let include = 0 <= k - weight ? pre[k - weight] + value : -Infinity, // ✅ include A[i] exclude = pre[k]; // 🚫 exclude A[i] cur[k] = Math.max(include, exclude); // 🎯 best } [pre, cur] = [cur, pre]; } return pre[K]; };

let run = filename => { let A = []; const input = new LineByLine(filename) let [K, N] = input.next().toString().split(' ').map(Number); // K capacity, N items let line; while (line = input.next()) { let [value, weight] = line.toString().split(' ').map(Number); A.push([value, weight]); } let a = topdown(A, K), b = bottomup(A, K), c = bottomupmemopt(A, K); assert(a == b && b == c); // 💩 sanity check console.log(${filename}: ${a}); };

run('problem16.7test.txt') // problem16.7test.txt: 2493893 ```

Python3 ```python from functools import lru_cache

def topdown(A, K): N = len(A) total = [0] * N @lrucache(maxsize = None) # 🤔 memo def go(i = 0, k = K): if i == N: # 🛑 empty set return 0 value, weight = A[i] include = go(i + 1, k - weight) + value if 0 <= k - weight else float('-inf') # ✅ include A[i] exclude = go(i + 1, k) # 🚫 exclude A[i] return max(include, exclude) # 🎯 best return go()

def bottom_up(A, K): N = len(A) dp = [[float('-inf')] * (K + 1) for _ in range(N + 1)] # 🤔 memo for j in range(K): # 🛑 empty set dp[0][j] = 0 for i in range(1, N + 1): for k in range(1, K + 1): value, weight = A[i - 1] include = dp[i - 1][k - weight] + value if 0 <= k - weight else float('-inf') # ✅ include A[i] exclude = dp[i - 1][k] # 🚫 exclude A[i] dp[i][k] = max(include, exclude) # 🎯 best return dp[N][K]

def bottomupmemopt(A, K): N = len(A) pre = [0] * (K + 1) # 🤔 memo + 🛑 empty set for i in range(1, N + 1): cur = [float('-inf')] * (K + 1) for k in range(1, K + 1): value, weight = A[i - 1] include = pre[k - weight] + value if 0 <= k - weight else float('-inf') # ✅ include A[i] exclude = pre[k] # 🚫 exclude A[i] cur[k] = max(include, exclude) # 🎯 best pre, cur = cur, pre return pre[K]

def run(filename): A = [] with open(filename) as fin: line = fin.readline() [K, N] = [int(word) for word in line.split()] # K capacity, N items while True: line = fin.readline() if not line: break value, weight = [int(word) for word in line.split()] A.append([value, weight]) a = topdown(A, K) b = bottomup(A, K) c = bottomupmemopt(A, K) assert(a == b and b == c) # 💩 sanity check print(f'{filename}: {a}')

run('problem16.7test.txt') # problem16.7test.txt: 2493893 ```

C++ ```cpp

include

include

include

include

include

using namespace std; using Pair = pair; // value, weight using Pairs = vector; using fun = function;

int INF = 1e9 + 7;

int top_down(Pairs& A, int K, Map m = {}) { auto N = A.size(); fun go = & { if (i == N) // 🛑 empty set return 0; stringstream key; key << i << "," << k; if (m.find(key.str()) != m.end()) // 🤔 memo return m[key.str()]; auto [value, weight] = A[i]; auto include = 0 <= k - weight ? go(i + 1, k - weight) + value : -INF, // ✅ include A[i] exclude = go(i + 1, k); // 🚫 exclude A[i] return m[key.str()] = max(include, exclude); // 🎯 best }; return go(0, K); }

int bottom_up(Pairs& A, int K) { auto N = A.size(); using VI = vector; using VVI = vector; VVI dp(N + 1, VI(K + 1, -INF)); // 🤔 memo for (auto k{ 0 }; k < K; dp[0][k++] = 0); // 🛑 empty set for (auto i{ 1 }; i <= N; ++i) { for (auto k{ 0 }; k <= K; ++k) { auto [value, weight] = A[i - 1]; auto include = 0 <= k - weight ? dp[i - 1][k - weight] +value : -INF, // ✅ include A[i] exclude = dp[i - 1][k]; // 🚫 exclude A[i] dp[i][k] = max(include, exclude); // 🎯 best } } return dp[N][K]; }

int bottomupmemopt(Pairs& A, int K) { auto N = A.size(); using VI = vector; VI pre(K + 1, 0); // 🤔 memo + 🛑 empty set for (auto i{ 1 }; i <= N; ++i) { VI cur(K + 1, -INF); for (auto k{ 0 }; k <= K; ++k) { auto [value, weight] = A[i - 1]; auto include = 0 <= k - weight ? pre[k - weight] +value : -INF, // ✅ include A[i] exclude = pre[k]; // 🚫 exclude A[i] cur[k] = max(include, exclude); // 🎯 best } swap(pre, cur); } return pre[K]; }

void run(const string& filename) { Pairs A; fstream fin{ filename }; int K, N; // K capacity, N items fin >> K >> N; for (int value, weight; fin >> value >> weight; A.emplaceback(value, weight)); auto a = topdown(A, K), b = bottomup(A, K), c = bottomup_memopt(A, K); assert(a == b && b == c); // 💩 sanity check cout << filename << ": " << a << endl; }

int main() { run("problem16.7test.txt"); // problem16.7test.txt: 2493893 return 0; } ```

• Shortest Paths with Negative Edge Lengths (Section 18.1)
• The Bellman-Ford Algorithm (Part 1) (Section 18.2, Part 1)
• The Bellman-Ford Algorithm (Part 2) (Section 18.2, Part 2)
• The Bellman-Ford Algorithm (Part 3) (Section 18.2, Part 3)
• The Bellman-Ford Algorithm (Part 4) (Section 18.2, Part 4)

Kotlin ```kotlin import java.io.File import java.util.LinkedList import java.util.Queue

// bellman-ford: N - 1 edge relaxations (u -> v of cost w) [ie. attempting to relax M edges N - 1 times] given N vertices fun bell(E: Array>, N: Int, start: Int = 1, INF: Int = (1e6).toInt()): IntArray { var dist = IntArray(N) { INF } dist[start] = 0 var K = N - 1 while (0 < K--) E.forEach{ (u, v, w) -> dist[v] = Math.min(dist[v], dist[u] + w)} return dist }

// shortest-paths faster algorithm: only attempt to relax candidate edges (note: adjacency list needed) fun spfa(E: Array>, N: Int, start: Int = 1, INF: Int = (1e6).toInt()): IntArray { var dist = IntArray(N) { INF } dist[start] = 0 var adj = Array>>(N) { mutableListOf>() } for ((u, v, w) in E) adj[u].add(Pair(v, w)) var q: Queue = LinkedList(listOf(start)) while (0 < q.size) { var u = q.poll() for ((v, w) in adj[u]) { if (dist[v] > dist[u] + w) { dist[v] = dist[u] + w; q.add(v) } } } return dist }

fun run(filename: String): IntArray { var N = 0 var E = mutableListOf>() File(filename).forEachLine { var A = ArrayDeque(it.trim().split("\t")) var u = A.removeFirst().toInt() for ((v, w) in A.map{ it.split(",").map{ it.toInt() } }) E.add(Triple(u, v, w)) ++N; } var A = E.toTypedArray() var a = bell(A, N + 1) // +1 for 1-based indexing var b = spfa(A, N + 1) assert(a == b) // 💩 sanity check: single source shortest paths are the same return b }

fun main() { var dist = run("test.txt") println(listOf(7, 37, 59, 82, 99, 115, 133, 165, 188, 197).map{ dist[it] }.joinToString(",")) // 2599,2610,2947,2052,2367,2399,2029,2442,2505,3068 } ```

Javascript ```javascript const assert = require('assert'); const zip = require('lodash/zip'); const LineByLine = require('n-readlines');

// bellman-ford: N - 1 edge relaxations (u -> v of cost w) [ie. attempting to relax M edges N - 1 times] given N vertices let bell = (E, N, start = 1, INF = Number(1e6)) => { let dist = Array(N).fill(INF); dist[start] = 0; let K = N - 1; while (K--) E.forEach(([u, v, w]) => dist[v] = Math.min(dist[v], dist[u] + w)); return dist; };

// shortest-paths faster algorithm: only attempt to relax candidate edges (note: adjacency list needed) let spfa = (E, N, start = 1, INF = Number(1e6)) => { let dist = Array(N).fill(INF); dist[start] = 0; let adj = [...Array(N)].map(_ => []); E.forEach(([u, v, w]) => adj[u].push([v, w])); let q = [start]; while (q.length) { let u = q.shift(); for (let [v, w] of adj[u]) if (dist[v] > dist[u] + w) dist[v] = dist[u] + w, q.push(v); } return dist; };

let run = filename => { let N = 0; let E = []; let input = new LineByLine(filename); let line; while (line = input.next()) { let A = line.toString('ascii').split('\t').filter(it => it.length); let u = Number(A.shift()); A.map(pair => pair.split(',').map(Number)).forEach(([v, w]) => E.push([u, v, w])); ++N; } let a = bell(E, N + 1), // +1 for 1-based indexing b = spfa(E, N + 1); zip(a, b).forEach(([x, y]) => assert(x == y)); // 💩 sanity check: single source shortest paths are the same return a; };

let dist = run('test.txt'); console.log([7, 37, 59, 82, 99, 115, 133, 165, 188, 197].map(x => dist[x]).join(',')); // 2599,2610,2947,2052,2367,2399,2029,2442,2505,3068 ```

Python3 ```python from collections import deque

bellman-ford: N - 1 edge relaxations (u -> v of cost w) [ie. attempting to relax M edges N - 1 times] given N vertices

def bell(E, N, start = 1, INF = int(1e6)): dist = [INF] * N dist[start] = 0 k = N - 1 while k: for u, v, w in E: dist[v] = min(dist[v], dist[u] + w) k -= 1 return dist

shortest-paths faster algorithm: only attempt to relax candidate edges (note: adjacency list needed)

def spfa(E, N, start = 1, INF = int(1e6)): dist = [INF] * N dist[start] = 0 adj = {i: [] for i in range(N)} for u, v, w in E: adj[u].append([v, w]) q = deque([start]) while q: u = q.popleft() for v, w in adj[u]: if dist[v] > dist[u] + w: dist[v] = dist[u] + w; q.append(v) return dist

def run(filename): E = [] N = 0 with open(filename) as fin: while True: line = fin.readline() if not line: break line = line.strip() A = [word for word in line.split('\t') if len(word)] u = int(A[0]) for i in range(1, len(A)): v, w = [int(x) for x in A[i].split(',')] E.append([u, v, w]) N += 1 a = bell(E, N + 1) # +1 for 1-based indexing b = spfa(E, N + 1) assert(a == b) return b

dist = run('test.txt') print(','.join(str(dist[x]) for x in [7, 37, 59, 82, 99, 115, 133, 165, 188, 197])) # 2599,2610,2947,2052,2367,2399,2029,2442,2505,3068 ```

C++ ```cpp

include

include

include

include

include

include

using namespace std; using VI = vector; using VS = vector; using Edge = tuple; using Edges = vector; using Pair = pair; using Pairs = vector; using AdjList = unordered_map; using Queue = queue;

// bellman-ford: N - 1 edge relaxations (u -> v of cost w) [ie. attempting to relax M edges N - 1 times] given N vertices VI bell(Edges& E, int N, int start = 1, int INF = 1e6) { VI dist(N, INF); dist[start] = 0; auto K = N - 1; while (K--) for (auto [u, v, w]: E) dist[v] = min(dist[v], dist[u] + w); return dist; }

// shortest-paths faster algorithm: only attempt to relax candidate edges (note: adjacency list needed) VI spfa(Edges& E, int N, int start = 1, int INF = 1e6, AdjList adj = {}) { VI dist(N, INF); dist[start] = 0; for (auto [u, v, w]: E) adj[u].emplace_back(v, w); Queue q{{ start }}; while (q.size()) { auto u = q.front(); q.pop(); for (auto [v, w]: adj[u]) if (dist[v] > dist[u] + w) dist[v] = dist[u] + w, q.push(v); } return dist; }

VI run(const string& filename) { auto N = 0; Edges E; fstream fin{ filename }; VS A; for (string line; getline(fin, line); A.emplaceback(line)); for (auto& s: A) { transform(s.begin(), s.end(), s.begin(), { return c == ',' ? ' ' : c; }); stringstream ss{ s }; auto [u, v, w] = maketuple(0, 0, 0); ss >> u; while (ss >> v >> w) E.emplace_back(u, v, w); ++N; } auto a = bell(E, N + 1), // +1 for 1-based indexing b = spfa(E, N + 1); assert(a == b); return b; }

int main() { auto dist = run("test.txt"); VI A{ 7, 37, 59, 82, 99, 115, 133, 165, 188, 197 }; transform(A.begin(), A.end(), A.begin(), & { return dist[x]; }); copy(A.begin(), A.end(), ostream_iterator(cout, ",")); // 2599,2610,2947,2052,2367,2399,2029,2442,2505,3068, return 0; } ```

• The All-Pairs Shortest Path Problem (Section 18.3)
• The Floyd-Warshall Algorithm (Part 1) (Section 18.4, Part 1)
• The Floyd-Warshall Algorithm (Part 2) (Section 18.4, Part 2)

Kotlin ```kotlin import java.io.File

var key = { i: Int, j: Int -> "$i,$j" } var INF = (1e9 + 7).toInt()

fun floyd_warshall(E: MutableMap, N: Int): Array { var dp = Array(N + 1) { Array(N + 1) { IntArray(N + 1) { INF } } } for (i in 0..N) for (j in 0..N) if (i == j) dp[0][i][j] = 0 else if (E.contains(key(i, j))) dp[0][i][j] = E[key(i, j)]!! for (k in 1..N) for (i in 1..N) for (j in 1..N) dp[k][i][j] = Math.min(dp[k - 1][i][j], dp[k - 1][i][k] + dp[k - 1][k][j]) return dp[N] }

fun floydwarshallmemopt(E: MutableMap, N: Int): Array { var pre = Array(N + 1) { IntArray(N + 1) { INF } } for (i in 0..N) for (j in 0..N) if (i == j) pre[i][j] = 0 else if (E.contains(key(i, j))) pre[i][j] = E[key(i, j)]!! for (k in 1..N) { var cur = Array(N + 1) { IntArray(N + 1) { INF } } for (i in 1..N) for (j in 1..N) cur[i][j] = Math.min(pre[i][j], pre[i][k] + pre[k][j]) pre = cur.also{ cur = pre } } return pre }

fun run(filename: String) { var N = 0 var E = mutableMapOf() var first = true File(filename).forEachLine { if (!first) { var (u, v, w) = it.trim().split(" ").map{ it.toInt() } E[key(u, v)] = w } else { N = it.trim().split(" ").map{ it.toInt() }[0] first = false } } var a = floydwarshallmemopt(E, N) var b = floyd_warshall(E, N) for (i in 1..N) for (j in 1..N) assert(a[i][j] == b[i][j]) // 💩 sanity check var cycle = false for (i in 1..N) if (a[i][i] < 0) cycle = true if (cycle) { println("$filename: contains a negative cycle") return } var best = INF for (i in 1..N) for (j in 1..N) best = Math.min(best, a[i][j]) println("$filename: $best") }

fun main() { run("problem18.8test1.txt"); // problem18.8test1.txt: -2 run("problem18.8test2.txt"); // problem18.8test2.txt: contains a negative cycle run("problem18.8file1.txt"); // problem18.8file1.txt: contains a negative cycle run("problem18.8file2.txt"); // problem18.8file2.txt: contains a negative cycle run("problem18.8file3.txt"); // problem18.8file3.txt: -19 // run("problem18.8file4.txt"); } ```

Javascript ```javascript const LineByLine = require('n-readlines'); const assert = require('assert');

let key = (i, j) => ${i},${j};

let floydwarshall = (E, N) => { let dp = [...Array(N + 1)].map( => [...Array(N + 1)].map(_ => Array(N + 1).fill(Infinity))); for (let i = 1; i <= N; ++i) for (let j = 1; j <= N; ++j) if (i == j) dp[0][i][j] = 0; else if (E.has(key(i, j))) dp[0][i][j] = E.get(key(i, j)); for (let k = 1; k <= N; ++k) for (let i = 1; i <= N; ++i) for (let j = 1; j <= N; ++j) dp[k][i][j] = Math.min(dp[k - 1][i][j], dp[k - 1][i][k] + dp[k - 1][k][j]); return dp[N]; };

let floydwarshallmemopt = (E, N) => { let pre = [...Array(N + 1)].map(_ => Array(N + 1).fill(Infinity)); for (let i = 1; i <= N; ++i) for (let j = 1; j <= N; ++j) if (i == j) pre[i][j] = 0; else if (E.has(key(i, j))) pre[i][j] = E.get(key(i, j)); for (let k = 1; k <= N; ++k) { let cur = [...Array(N + 1)].map(_ => Array(N + 1).fill(Infinity)); for (let i = 1; i <= N; ++i) for (let j = 1; j <= N; ++j) cur[i][j] = Math.min(pre[i][j], pre[i][k] + pre[k][j]); [pre, cur] = [cur, pre]; } return pre; };

let run = filename => { let E = new Map(); let input = new LineByLine(filename); let [N, ] = input.next().toString('ascii').split(' ').map(Number); let line; while (line = input.next()) { let [u, v, w] = line.toString('ascii').split(' ').map(Number); E.set(key(u, v), w); } let a = floydwarshallmemopt(E, N), b = floydwarshall(E, N); for (let i = 1; i <= N; ++i) for (let j = 1; j <= N; ++j) assert(a[i][j] == b[i][j]); let cycle = false; for (let i = 1; i <= N; ++i) if (a[i][i] < 0) cycle = true; if (cycle) { console.log(${filename}: contains a negative cycle); return; } var best = Infinity; for (row of a) best = Math.min(best, ...row); console.log(${filename}: ${best}); };

run('problem18.8test1.txt'); // problem18.8test1.txt: -2 run('problem18.8test2.txt'); // problem18.8test2.txt: contains a negative cycle run('problem18.8file1.txt'); // problem18.8file1.txt: contains a negative cycle run('problem18.8file2.txt'); // problem18.8file2.txt: contains a negative cycle run('problem18.8file3.txt'); // problem18.8file3.txt: -19 // run('problem18.8file4.txt'); ```

Python3 ```python key = lambda i, j: f'{i},{j}'

def floyd_warshall(E, N): dp = [[[float('inf')] * (N + 1) for _ in range(N + 1)] for _ in range(N + 1)] for i in range(1, N + 1): for j in range(1, N + 1): if i == j: dp[0][i][j] = 0 elif key(i, j) in E: dp[0][i][j] = E[key(i, j)] for k in range(1, N + 1): for i in range(1, N + 1): for j in range(1, N + 1): dp[k][i][j] = min(dp[k - 1][i][j], dp[k - 1][i][k] + dp[k - 1][k][j]) return dp[N]

def floydwarshallmemopt(E, N): pre = [[float('inf')] * (N + 1) for _ in range(N + 1)] for i in range(1, N + 1): for j in range(1, N + 1): if i == j: pre[i][j] = 0 elif key(i, j) in E: pre[i][j] = E[key(i, j)] for k in range(1, N + 1): cur = [[float('inf')] * (N + 1) for _ in range(N + 1)] for i in range(1, N + 1): for j in range(1, N + 1): cur[i][j] = min(pre[i][j], pre[i][k] + pre[k][j]) pre, cur = cur, pre return pre

def run(filename): E = {} N = 0 first = True with open(filename) as fin: while True: line = fin.readline() if not line: break if not first: u, v, w = [int(x) for x in line.strip().split(' ')] E[key(u, v)] = w else: N = [int(x) for x in line.strip().split(' ')][0] first = False a = floydwarshallmemopt(E, N) b = floyd_warshall(E, N) for i in range(1, N + 1): for j in range(1, N + 1): assert(a[i][j] == b[i][j]) # 💩 sanity check cycle = False for i in range(1, N + 1): if a[i][i] < 0: cycle = True if cycle: print(f'{filename}: contains a negative cycle') return best = float('inf') for row in a: best = min(best, *row) print(f'{filename}: {best}')

run('problem18.8test1.txt') # problem18.8test1.txt: -2 run('problem18.8test2.txt') # problem18.8test2.txt: contains a negative cycle run('problem18.8file1.txt') # problem18.8file1.txt: contains a negative cycle run('problem18.8file2.txt') # problem18.8file2.txt: contains a negative cycle run('problem18.8file3.txt') # problem18.8file3.txt: -19

run('problem18.8file4.txt')

```

C++ ```cpp

include

include

include

include

include

define PERF_TEST

using namespace std;

using LL = long long; using VL = vector; using VVL = vector; using VVVL = vector; using Edges = unordered_map;

LL INF = 1e9 + 7;

string key(int i, int j) { stringstream ss; ss << i << "," << j; return ss.str(); }

VVL floyd_warshall(Edges& E, int N) { VVVL dp(N + 1, VVL(N + 1, VL(N + 1, INF))); for (auto i{ 1 }; i <= N; ++i) for (auto j{ 1 }; j <= N; ++j) if (i == j) dp[0][i][j] = 0; else if (E.find(key(i, j)) != E.end()) dp[0][i][j] = E[key(i, j)]; for (auto k{ 1 }; k <= N; ++k) for (auto i{ 1 }; i <= N; ++i) for (auto j{ 1 }; j <= N; ++j) dp[k][i][j] = min(dp[k - 1][i][j], dp[k - 1][i][k] + dp[k - 1][k][j]); return dp[N]; }

VVL floydwarshallmemopt(Edges& E, int N) { VVL pre(N + 1, VL(N + 1, INF)); for (auto i{ 1 }; i <= N; ++i) for (auto j{ 1 }; j <= N; ++j) if (i == j) pre[i][j] = 0; else if (E.find(key(i, j)) != E.end()) pre[i][j] = E[key(i, j)]; for (auto k{ 1 }; k <= N; ++k) { VVL cur(N + 1, VL(N + 1, INF)); for (auto i{ 1 }; i <= N; ++i) for (auto j{ 1 }; j <= N; ++j) cur[i][j] = min(pre[i][j], pre[i][k] + pre[k][j]); swap(pre, cur); } return pre; }

void run(const string& filename) { Edges E; fstream fin{ filename }; int N, M; fin >> N >> M; for (int u, v, w; fin >> u >> v >> w; E[key(u, v)] = w);

ifdef PERF_TEST

auto a = floyd_warshall_memopt(E, N);

else

auto a = floyd_warshall_memopt(E, N),
     b = floyd_warshall(E, N);
assert(a == b);  // 💩 sanity check

endif

auto cycle = false;
for (auto i{ 1 }; i <= N && !cycle; ++i)
    cycle = a[i][i] < 0;
if (cycle) {
    cout << filename << ": contains a negative cycle" << endl;
    return;
}
auto best = INF;
for (auto& row: a)
    best = min(best, *min_element(row.begin(), row.end()));
cout << filename << ": " << best << endl;

}

int main() { run("problem18.8test1.txt"); // problem18.8test1.txt: -2 run("problem18.8test2.txt"); // problem18.8test2.txt: contains a negative cycle run("problem18.8file1.txt"); // problem18.8file1.txt: contains a negative cycle run("problem18.8file2.txt"); // problem18.8file2.txt: contains a negative cycle run("problem18.8file3.txt"); // problem18.8file3.txt: -19 // run("problem18.8file4.txt"); return 0; } ```