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