Professor Scarlet's Notebook: A companion volume to Dennis Shasha's The Puzzling Adventures of Dr. Ecco

1 Introduction 1
1.1 The general approach . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.1.1 Adaptive and nonadaptive solutions . . . . . . . . . . . . . . . . . . . 3
1.1.2 Extending the solution . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
1.1.3 The pigeonhole principle . . . . . . . . . . . . . . . . . . . . . . . . . . 6
1.2 Modular Arithmetic . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
1.3 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
1.4 Questions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
2 Coding Theory 17
2.1 Error detection . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
2.1.1 What is a code? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
2.1.2 Binary codes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
2.2 Error-correction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
2.2.1 Binary Codes and single digit error correction . . . . . . . . . . . . . . 24
2.3 The Hamming codes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
2.3.1 The Baskerhound case . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
2.3.2 The optimality of the Hamming Code . . . . . . . . . . . . . . . . . . 29
2.4 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30
2.5 Questions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
3 Cryptography 33
3.1 Simple ciphers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
3.1.1 Caesar’s Code . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
3.1.2 Linear Codes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35
3.1.3 Finding the decoding function for a linear code . . . . . . . . . . . . . 36
3.1.4 Mono-alphabetic codes . . . . . . . . . . . . . . . . . . . . . . . . . . . 38
3.1.5 Poly-alphabetic codes . . . . . . . . . . . . . . . . . . . . . . . . . . . 40
3.1.6 Public key cryptography . . . . . . . . . . . . . . . . . . . . . . . . . . 41
3.2 The Couriers Problem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43
3.3 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47
3.4 Questions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49
4 Recursion & Induction 51
4.1 Recursion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51
4.2 Induction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58
4.3 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63
4.4 Questions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65
5 Graph Theory 69
5.1 Basic properties . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69
5.1.1 Subgraphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71
5.2 Trees . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72
5.2.1 When is a graph really a tree? . . . . . . . . . . . . . . . . . . . . . . 75
5.3 Spanning Trees . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 76
5.4 Kruskal’s Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 77
5.5 Dijkstra’s Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 80
5.6 Planar Graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 84
5.7 Centre, radius, and diameter . . . . . . . . . . . . . . . . . . . . . . . . . . . 87
5.8 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 88
5.9 Questions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 89
6 Digraph Theory 93
6.1 Basic properties . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 93
6.1.1 Tournaments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 94
6.2 Critical Paths . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 99
6.3 Transportation Networks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 100
6.3.1 Orienting a graph . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 102
6.4 Centre, radius, and diameter of digraphs . . . . . . . . . . . . . . . . . . . . . 103
6.5 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 104
6.6 Questions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 106
7 Miscellaneous Topics 109
7.1 Parallel sorting . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 109
7.2 Circuits, gates, and logic . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 113
7.3 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 117
7.4 Questions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 119
A Appendix 121
A.1 The pigeonhole principle . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 121
A.2 Multiples, divisors, and congruences . . . . . . . . . . . . . . . . . . . . . . . 123
A.2.1 Two important consequences. . . . . . . . . . . . . . . . . . . . . . . . 124
A.3 We’ve got your number . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 126
A.4 Binary Numbers – what are they? . . . . . . . . . . . . . . . . . . . . . . . . 130
B Solutions for the exercises 135
B.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 135
B.2 Coding Theory . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 136
B.3 Cryptography . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 137
B.4 Recursion & Induction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 139
B.5 Graph Theory . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 142
B.6 Digraph Theory . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 145
B.7 Miscellaneous Topics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 147