Where each thing comes from
Each header and each test cites the section, the example or the exercise
of the book that it implements, and the tests are listed with their source
in test/tests.txt; the solutions of the exercises are
in the tests, one function per exercise. Each one is checked on the
example of the book, on its edge cases and (where an enumeration is
possible) on random instances against the enumeration. Since the license
of the book does not allow its text in a repository under the LGPL, the
code cites it instead of reproducing it.
Chapter |
Section |
What |
Header |
Tests |
|---|---|---|---|---|
1.2 |
minimum, binary search |
|
||
1.4 |
multiplication of Ahmes |
|
||
2.6 |
sum and products of binary integers, Karatsuba |
|
||
2.7 |
Selection, Insertion, Merge, Counting Sort, lower bound |
|
||
2.9 |
solutions of the recurrences (Teoremi 2.2–2.5) |
|
||
3.2 |
SEQUENCE, SET, DICTIONARY |
|
||
4.1 |
LIST, bidirectional circular with sentinel |
|
||
4.2 |
sequence on a vector that doubles |
|
||
4.2.1 |
binary counter, amortized analysis |
|
||
4.3 |
STACK, QUEUE |
|||
4.3.1 |
stack simulated with a sequence |
|
||
4.3.2 |
stack on a vector |
|
||
4.3.3 |
queue on a circular vector |
|
||
4.4 |
towers of Hanoi, recursive and iterative |
|
||
4.6 |
exercises 4.1–4.11; the singly linked list of 4.6 and the linked queue of 4.10 |
|
||
5.1, 5.3 |
ordered TREE, parent/first child/sibling |
|
||
5.2 |
previsit, postvisit, invisit, by levels |
|
||
5.4 |
vector of parents |
|
||
5.5 |
binary TREE and its visits, ordered tree as binary |
|
||
5.6 |
complete d-ary tree in a vector |
|
||
5.8 |
exercises 5.1–5.13 |
|
||
6.1 |
binary search tree (ABR), DICTIONARY |
|
||
6.2 |
Red-Black tree, Teoremi 6.1–6.3 |
|
||
6.3 |
B+-tree, insertion, search, interval |
|
||
6.4 |
exercises 6.1–6.10 |
|
||
7 |
table with direct access |
|
||
7.1 |
extraction, XOR, division, multiplication, middle square |
|
||
7.2 |
lists of overflow, open addressing, deleted places |
|
||
7.3 |
I(α) and S(α) measured against the formulas |
|
||
7.4 |
restructuring, amortized cost |
|
||
– |
exercises 7.1–7.10 |
|
||
8.1 |
SET on a boolean vector |
|
||
8.2 |
SET on an unsorted list |
|
||
8.3 |
SET on a sorted list, operations by merging |
|
||
8.4 |
SET on hash tables |
|
||
8.5 |
SET on Red-Black trees |
|
||
8.7 |
exercises 8.1–8.10, LinkedHashSet, multiset |
|
||
9.1 |
definitions, the case of the duke McPollock |
|
||
9.2, 9.4 |
GRAPH, lists and vectors of adjacency |
|
||
9.3 |
adjacency matrix, incidence matrix |
|
||
9.5 |
bfs, distances, dfs, components, dfs schema, cycles, topological order, strong components |
|
||
9.7 |
exercises 9.1–9.11 |
|
||
10.1 |
PRIORITYQUEUE on a d-ary heap, on lists, on a Red-Black tree |
|
||
10.1.4 |
heapBuild(), heapsort() |
|
||
10.2 |
MFSET on a forest (rank, compression of the paths) and on lists, incremental components |
|
||
10.4 |
exercises 10.1–10.9 |
|
||
11.1–11.2 |
shortest paths, theorem of Bellman, the prototype |
|
||
11.3–11.5 |
Dijkstra, Johnson, Fredman-Tarjan on a Fibonacci heap |
|
|
|
11.6–11.8 |
Bellman-Ford-Moore, the stack, Pape-D’Esopo on a dequeue |
|
||
11.10 |
exercises 11.1–11.10 |
|
||
12.1 |
search by interpolation |
|
||
12.2 |
Quicksort, its improvements, on lists |
|
||
12.3 |
products of polynomials, Karatsuba |
|
||
12.4 |
Strassen |
|
||
12.6 |
exercises 12.1–12.13 |
|
||
13 |
binomial coefficients, Fibonacci |
|
||
13.1 |
approximate string matching, edit distance |
|
||
13.2 |
weighted independent intervals |
|
||
13.3 |
chain of matrices |
|
||
13.5 |
Floyd-Warshall, insertion of an edge |
|
||
13.6 |
knapsack, by a table and by memoization |
|
||
13.7 |
LCS, diff, longest common substring, alignments |
|
||
13.8 |
exercises 13.1–13.13 |
|
||
14 |
change with coins |
|
||
14.1 |
real knapsack |
|
||
14.2 |
independent set of intervals, coloring, towers |
|
||
14.3 |
Kruskal and Prim, Teorema 14.1 |
|
||
14.4 |
code of Huffman |
|
||
14.5 |
exercises 14.1–14.10, Shortest Job First |
|
||
15 |
local search of the minimum spanning tree |
|
||
15.1 |
Shell Sort, four sequences of gaps |
|
||
15.2 |
maximum flow (Ford-Fulkerson, Edmonds-Karp, Dinic), minimum cut, circulations |
|
||
15.4 |
exercises 15.1–15.10, Eulerian cycle |
|
||
16.1 |
convex hull, O(n³) and Graham |
|
||
16.2 |
enumeration: subsets, permutations, derangements, subset sum |
|
||
16.3 |
Sudoku |
|
||
16.4 |
exercises 16.1–16.8, n queens, tour of the knight, anagrams |
|
||
17 |
Monte Carlo: null polynomial, Freivalds, half-satisfiability |
|
||
17.1 |
selection of Hoare, median of medians |
|
||
17.2 |
Euclid, powers, Miller-Rabin, primality on 64 bits |
|
||
17.3 |
RSA |
|
||
18 |
the problems in NP, certificates and enumerations |
|
||
18.2–18.3 |
nondeterminism simulated by enumeration |
|
||
18.5–18.7 |
reductions, linear tiling in P, Teoremi 18.2–18.9 |
|
||
18.9 |
exercises 18.1–18.16 |
|
||
19.1 |
pseudopolynomial algorithms, scheduling |
|
||
19.2 |
approximation: ff, ffd, triangular salesman, apSubsetSum |
|
||
19.3 |
branch-&-bound: bbTsp, 1-tree, Little, clique, knapsack |
|
||
19.4 |
heuristics: greedyTsp, min-max-greedy, local search |
|
||
19.5 |
the fifteen puzzle |
|
||
19.6 |
exercises 19.1–19.19 |
|
||
Conclusione |
Tab. 19.1 |
easy twins of NP-hard problems, interval graphs |
|