|
Part I Foundations of Computer Science |
|
|
|
1 Compressing and Correcting Digital Media |
|
|
3 | (30) |
|
1.1 A Compact Disk = a Sequence of Numbers |
|
|
5 | (6) |
|
1.1.1 Decimal and Binary Representation |
|
|
6 | (3) |
|
1.1.2 Decimal and Binary Notation |
|
|
9 | (1) |
|
1.1.3 Grouping Bits into Bytes |
|
|
10 | (1) |
|
|
11 | (7) |
|
1.2.1 A Run-Length Based Approach |
|
|
13 | (2) |
|
1.2.2 A Dictionary-Based Approach |
|
|
15 | (3) |
|
|
18 | (5) |
|
1.3.1 An Error Detection Approach |
|
|
18 | (3) |
|
1.3.2 An Error Correction Approach |
|
|
21 | (2) |
|
1.4 Recasting Error Correction as Matrix Arithmetic |
|
|
23 | (10) |
|
1.4.1 An Overview of Vectors |
|
|
24 | (1) |
|
1.4.2 An Overview of Matrices |
|
|
25 | (2) |
|
1.4.3 Addition and Multiplication Modulo 2 |
|
|
27 | (1) |
|
1.4.4 Using Matrices for Error Correction |
|
|
28 | (3) |
|
1.4.5 Generalising the Matrix-Based (7, 4)-Code |
|
|
31 | (1) |
|
|
31 | (2) |
|
2 Writing and Comparing Algorithms |
|
|
33 | (20) |
|
|
33 | (5) |
|
2.1.1 What Is an Algorithm? |
|
|
34 | (3) |
|
2.1.2 What Is not an Algorithm? |
|
|
37 | (1) |
|
2.2 Algorithms for Multiplication |
|
|
38 | (4) |
|
2.3 Algorithms for Exponentiation |
|
|
42 | (2) |
|
2.4 Computational Complexity |
|
|
44 | (9) |
|
2.4.1 Step Counting and Dominant Steps |
|
|
45 | (1) |
|
2.4.2 Problem Size and Step Counting Functions |
|
|
46 | (1) |
|
2.4.3 Ignoring Small Problems and Minor Terms |
|
|
47 | (2) |
|
2.4.4 Studying the Growth of Functions |
|
|
49 | (2) |
|
|
51 | (2) |
|
3 Playing Hide-and-Seek with Virus Scanners |
|
|
53 | (24) |
|
3.1 Computers and Programs |
|
|
55 | (11) |
|
3.1.1 A Theoretical Computer |
|
|
56 | (1) |
|
3.1.2 A Real, Harvard-Style Computer |
|
|
57 | (2) |
|
3.1.3 A Real, von Neumann-Style Computer |
|
|
59 | (7) |
|
3.2 Harvard Versus von Neumann Computers |
|
|
66 | (4) |
|
3.2.1 Beyond Straight-Line Programs |
|
|
67 | (1) |
|
3.2.2 Toward Self-Modifying Programs |
|
|
68 | (2) |
|
3.3 A Self-Modifying Virus |
|
|
70 | (7) |
|
3.3.1 Using XOR to Mask Numbers |
|
|
70 | (1) |
|
3.3.2 A Virus that Masks the Payload |
|
|
71 | (2) |
|
3.3.3 Preventing the Virus Without a Virus Scanner |
|
|
73 | (1) |
|
|
74 | (3) |
|
4 How Long Is a Piece of String? |
|
|
77 | (22) |
|
4.1 String Data Structures |
|
|
78 | (6) |
|
4.1.1 Problem #1: Representing Characters |
|
|
80 | (2) |
|
4.1.2 Problem #2: Representing Strings |
|
|
82 | (2) |
|
|
84 | (15) |
|
4.2.1 strlen: Finding the Length of a String |
|
|
84 | (2) |
|
4.2.2 toupper: Converting a String to Upper-Case |
|
|
86 | (3) |
|
4.2.3 strcmp: Testing if One String Is the Same as Another |
|
|
89 | (2) |
|
4.2.4 strcat: Concatenating Two Strings Together |
|
|
91 | (4) |
|
4.2.5 Problem #3: Repeated Concatenation |
|
|
95 | (2) |
|
|
97 | (2) |
|
5 Demystifying Web-Search: the Mathematics of Page Rank |
|
|
99 | (28) |
|
5.1 PageRank: the Essence of Google Web-Search |
|
|
100 | (3) |
|
5.1.1 What Actually Is Web-Search? |
|
|
100 | (1) |
|
5.1.2 Web-Search Before Google |
|
|
101 | (1) |
|
5.1.3 Web-Search After Google |
|
|
102 | (1) |
|
5.2 Using Graph Theory to Model and Explore the Web |
|
|
103 | (7) |
|
|
105 | (4) |
|
|
109 | (1) |
|
5.3 Using Probability Theory to Model Web-Browsing |
|
|
110 | (11) |
|
5.3.1 Sanitising the Web-Graph to Avoid a Subtle Problems |
|
|
113 | (1) |
|
5.3.2 A Mathematical Approach to Computing PageRank |
|
|
114 | (7) |
|
5.4 Putting It All Together: Using PageRank to Produce Web-Search Results |
|
|
121 | (6) |
|
|
123 | (4) |
|
Part II Examples from Information Security |
|
|
|
6 Using Short Programs to Make and Break Historical Ciphers |
|
|
127 | (22) |
|
|
128 | (10) |
|
6.1.1 Encryption and Decryption |
|
|
128 | (7) |
|
|
135 | (3) |
|
|
138 | (11) |
|
6.2.1 Encryption and Decryption |
|
|
139 | (2) |
|
|
141 | (6) |
|
|
147 | (2) |
|
7 Generation and Testing of Random Numbers |
|
|
149 | (20) |
|
|
150 | (4) |
|
7.1.1 Biased Versus Unbiased |
|
|
151 | (1) |
|
7.1.2 Predictable Versus Unpredictable |
|
|
152 | (1) |
|
7.1.3 Random Versus Arbitrary |
|
|
153 | (1) |
|
|
154 | (5) |
|
7.2.1 Generating Randomness |
|
|
154 | (1) |
|
|
155 | (4) |
|
|
159 | (10) |
|
7.3.1 Generating Randomness |
|
|
159 | (5) |
|
|
164 | (3) |
|
|
167 | (2) |
|
8 Safety in Numbers: Modern Cryptography from Ancient Arithmetic |
|
|
169 | (30) |
|
8.1 Modular Arithmetic: the Theory |
|
|
171 | (8) |
|
8.1.1 Rules for Modular Addition |
|
|
172 | (1) |
|
8.1.2 Rules for Modular Multiplication |
|
|
173 | (2) |
|
8.1.3 The Sets Z, ZN and Z*N |
|
|
175 | (2) |
|
8.1.4 Some Interesting Facts About Z*N |
|
|
177 | (2) |
|
8.2 Modular Arithmetic: the Practice |
|
|
179 | (11) |
|
8.2.1 Addition and Subtraction |
|
|
179 | (2) |
|
|
181 | (2) |
|
|
183 | (1) |
|
8.2.4 Division (via Inversion) |
|
|
183 | (7) |
|
8.3 From Modular Arithmetic to Cryptographic Protocols |
|
|
190 | (9) |
|
8.3.1 Diffie-Hellman Key Exchange |
|
|
190 | (2) |
|
|
192 | (2) |
|
8.3.3 Functional Versus Secure |
|
|
194 | (3) |
|
|
197 | (2) |
|
9 Hiding a Needle in a Haystack: Concealed Messages |
|
|
199 | (16) |
|
|
200 | (8) |
|
|
200 | (4) |
|
|
204 | (4) |
|
|
208 | (7) |
|
9.2.1 Rasterised Images: "Stolen LSBs" |
|
|
208 | (3) |
|
9.2.2 Vector Images: "Microdots" |
|
|
211 | (1) |
|
|
212 | (3) |
|
10 Picking Digital Pockets |
|
|
215 | (14) |
|
10.1 Passive Physical Attacks |
|
|
217 | (7) |
|
|
217 | (4) |
|
|
221 | (3) |
|
10.2 Active Physical Attacks |
|
|
224 | (5) |
|
|
224 | (1) |
|
|
225 | (2) |
|
|
227 | (2) |
Index |
|
229 | |