Preface |
|
xv | |
Acknowledgments |
|
xxiii | |
About the author |
|
xxv | |
|
Chapter 1 How to Solve It |
|
|
1 | (48) |
|
1.1 Understand The Problem |
|
|
3 | (3) |
|
A first problem: computing reading level |
|
|
4 | (1) |
|
|
5 | (1) |
|
|
6 | (17) |
|
|
7 | (3) |
|
|
10 | (4) |
|
Implement from the bottom |
|
|
14 | (9) |
|
|
23 | (13) |
|
|
23 | (5) |
|
|
28 | (3) |
|
|
31 | (1) |
|
|
32 | (4) |
|
|
36 | (9) |
|
|
37 | (2) |
|
|
39 | (6) |
|
1.5 Summary And Further Discovery |
|
|
45 | (4) |
|
Chapter 2 "Visualizing Abstraction |
|
|
49 | (58) |
|
|
51 | (4) |
|
|
53 | (2) |
|
2.2 Drawing Flowers And Plotting Earthquakes |
|
|
55 | (11) |
|
|
57 | (3) |
|
Tangent 2.1 Defining colors |
|
|
60 | (2) |
|
|
62 | (4) |
|
2.3 Functional Abstraction |
|
|
66 | (11) |
|
|
69 | (8) |
|
|
77 | (10) |
|
|
78 | (1) |
|
|
79 | (1) |
|
Tangent 2.2 Global variables |
|
|
80 | (3) |
|
|
83 | (4) |
|
2.5 A Return To Functions |
|
|
87 | (10) |
|
|
88 | (1) |
|
Writing functions with return values |
|
|
89 | (3) |
|
|
92 | (5) |
|
|
97 | (8) |
|
|
98 | (3) |
|
|
101 | (4) |
|
2.7 Summary And Further Discovery |
|
|
105 | (2) |
|
Chapter 3 Inside a Computer |
|
|
107 | (22) |
|
|
108 | (4) |
|
Tangent 3.1 High performance computing |
|
|
109 | (2) |
|
|
111 | (1) |
|
|
112 | (1) |
|
|
112 | (6) |
|
|
112 | (1) |
|
Bits can represent anything |
|
|
113 | (1) |
|
Tangent 3.3 Hexadecimal notation |
|
|
114 | (1) |
|
|
114 | (4) |
|
|
118 | (6) |
|
|
118 | (2) |
|
Tangent 3.4 Floating point notation |
|
|
120 | (1) |
|
|
120 | (1) |
|
|
121 | (1) |
|
|
122 | (2) |
|
|
|
|
|
Negative integers Designing an adder |
|
|
|
|
|
3.5 The Universal Machine |
|
|
124 | (2) |
|
3.6 Summary And Further Discovery |
|
|
126 | (3) |
|
Chapter 4 Growth and Decay |
|
|
129 | (36) |
|
|
130 | (20) |
|
|
130 | (6) |
|
|
136 | (3) |
|
|
139 | (11) |
|
|
150 | (5) |
|
4.3 Conditional Iteration |
|
|
155 | (6) |
|
When will the fish disappear? |
|
|
155 | (2) |
|
When will your nest egg double? |
|
|
157 | (4) |
|
|
|
|
|
|
|
Tradeoffs between accuracy and time |
|
|
|
|
|
|
|
|
|
|
|
Approximating square roots |
|
|
|
|
161 | (3) |
|
Tangent 4-1 Triangular numbers |
|
|
163 | (1) |
|
|
164 | (1) |
|
|
|
4.1 Parasitic relationships |
|
|
|
4.2 Financial calculators |
|
|
|
|
|
|
|
Chapter 5 Forks in the Road |
|
|
165 | (56) |
|
|
166 | (14) |
|
Tangent 5.1 Interval notation |
|
|
167 | (1) |
|
|
167 | (4) |
|
|
171 | (9) |
|
5.2 Pseudorandom Number Generators |
|
|
|
Implementation Testing randomness |
|
|
|
*5.3 Simulating Probability Distributions |
|
|
|
The central limit theorem |
|
|
|
|
180 | (19) |
|
|
182 | (1) |
|
|
183 | (1) |
|
|
184 | (3) |
|
|
187 | (5) |
|
|
192 | (7) |
|
5.5 Defensive Programming |
|
|
199 | (11) |
|
|
199 | (3) |
|
|
202 | (2) |
|
|
204 | (1) |
|
Tangent 5.2 Unit testing frameworks |
|
|
205 | (2) |
|
|
207 | (1) |
|
|
207 | (3) |
|
|
210 | (9) |
|
|
212 | (1) |
|
|
213 | (1) |
|
A proper win/lose message |
|
|
214 | (5) |
|
5.7 Summary And Further Discovery |
|
|
219 | (2) |
|
|
|
|
|
|
|
Chapter 6 Text, Documents, and DNA |
|
|
221 | (64) |
|
|
222 | (16) |
|
|
223 | (1) |
|
Tangent 6.1 Natural language processing |
|
|
224 | (4) |
|
|
228 | (4) |
|
|
232 | (1) |
|
|
233 | (5) |
|
|
238 | (8) |
|
|
239 | (3) |
|
|
242 | (1) |
|
|
243 | (3) |
|
|
246 | (10) |
|
|
246 | (1) |
|
|
247 | (3) |
|
Tangent 6.2 Compressing text files |
|
|
250 | (1) |
|
|
251 | (5) |
|
|
256 | (10) |
|
|
257 | (5) |
|
|
262 | (1) |
|
|
263 | (3) |
|
6.5 Word Frequency Trends |
|
|
266 | (6) |
|
Finding the frequency of a word |
|
|
268 | (1) |
|
Getting the frequencies in slices |
|
|
269 | (1) |
|
|
270 | (2) |
|
|
272 | (9) |
|
|
274 | (7) |
|
|
|
|
|
Asymptotic time complexity |
|
|
|
*6.8 Computational Genomics |
|
|
|
|
|
|
|
|
|
|
|
|
|
6.9 Summary And Further Discovery |
|
|
281 | (4) |
|
|
|
|
|
|
|
|
285 | (50) |
|
|
286 | (7) |
|
|
286 | (2) |
|
|
288 | (5) |
|
|
293 | (17) |
|
|
294 | (1) |
|
A more efficient algorithm |
|
|
295 | (2) |
|
|
297 | (5) |
|
List operators and methods |
|
|
302 | (3) |
|
|
305 | (1) |
|
|
306 | (4) |
|
|
310 | (15) |
|
|
310 | (1) |
|
|
311 | (4) |
|
|
315 | (1) |
|
Finding the most frequent word |
|
|
315 | (2) |
|
|
317 | (1) |
|
Tangent 7.3 Sentiment analysis |
|
|
318 | (7) |
|
|
325 | (8) |
|
|
326 | (7) |
|
*7.5 Designing Efficient Algorithms |
|
|
|
|
|
|
|
|
|
A more efficient algorithm |
|
|
|
|
|
|
|
|
|
|
|
Implementing A;-means clustering |
|
|
|
Locating bicycle safety programs |
|
|
|
7.8 Summary And Further Discovery |
|
|
333 | (2) |
|
Tangent 7.4 Privacy in the age of big data |
|
|
334 | (1) |
|
|
|
|
|
7.2 Does education influence unemployment? |
|
|
|
|
|
|
|
7.5 Preparing for a 100-year flood |
|
|
|
|
|
7.7 Heuristics for traveling salespeople |
|
|
|
|
335 | (30) |
|
|
335 | (7) |
|
Reading a table of temperatures |
|
|
336 | (3) |
|
|
339 | (3) |
|
|
342 | (11) |
|
|
344 | (1) |
|
|
345 | (1) |
|
Surveying the neighborhood |
|
|
346 | (1) |
|
|
347 | (2) |
|
Tangent 8.2 NumPy arrays in two dimensions |
|
|
349 | (1) |
|
|
349 | (4) |
|
|
353 | (10) |
|
|
353 | (1) |
|
Tangent 8.3 Additive vs. subtractive color models |
|
|
354 | (1) |
|
|
355 | (1) |
|
Tangent 8.4 Image storage and compression |
|
|
356 | (2) |
|
|
358 | (5) |
|
8.4 Summary And Further Discovery |
|
|
363 | (2) |
|
|
|
|
|
8.2 Modeling ferromagnetism |
|
|
|
|
|
8.4 Simulating an epidemic |
|
|
|
Chapter 9 Self-similarity and Recursion |
|
|
365 | (42) |
|
|
365 | (10) |
|
|
367 | (2) |
|
|
369 | (6) |
|
9.2 Recursion And Iteration |
|
|
375 | (13) |
|
Solving a problem recursively |
|
|
379 | (1) |
|
|
380 | (2) |
|
|
382 | (6) |
|
9.3 The Mythical Tower Of Hanoi |
|
|
388 | (4) |
|
*Is the end of the world nigh? |
|
|
390 | (2) |
|
9.4 Recursive Linear Search |
|
|
392 | (4) |
|
*Efficiency of recursive linear search |
|
|
393 | (3) |
|
|
396 | (9) |
|
|
397 | (3) |
|
|
400 | (5) |
|
|
|
Formal grammars L-systems |
|
|
|
|
|
9.7 Summary And Further Discovery |
|
|
405 | (2) |
|
|
|
9.1 Lindenmayer's beautiful plants |
|
|
|
|
|
|
|
Chapter 10 Organizing Data |
|
|
407 | (36) |
|
|
408 | (10) |
|
|
409 | (3) |
|
Efficiency of iterative binary search |
|
|
412 | (2) |
|
|
414 | (1) |
|
|
415 | (1) |
|
*Efficiency of recursive binary search |
|
|
416 | (2) |
|
|
418 | (9) |
|
Implementing selection sort |
|
|
419 | (3) |
|
Efficiency of selection sort |
|
|
422 | (1) |
|
|
423 | (4) |
|
|
427 | (6) |
|
Implementing insertion sort |
|
|
428 | (2) |
|
Efficiency of insertion sort |
|
|
430 | (3) |
|
|
433 | (8) |
|
|
433 | (4) |
|
Internal vs. external sorting |
|
|
437 | (1) |
|
|
437 | (4) |
|
*10.5 Tractable And Intractable Algorithms |
|
|
|
|
|
10.6 Summary And Further Discovery |
|
|
441 | (2) |
|
|
|
10.1 Creating a searchable database |
|
|
|
|
|
|
443 | (26) |
|
11.1 Modeling With Graphs |
|
|
444 | (7) |
|
|
446 | (5) |
|
|
451 | (7) |
|
|
451 | (4) |
|
|
455 | (3) |
|
|
458 | (6) |
|
|
458 | (1) |
|
|
459 | (2) |
|
|
461 | (3) |
|
|
464 | (3) |
|
11.5 Summary And Further Discovery |
|
|
467 | (2) |
|
|
|
11.1 Diffusion of ideas and influence |
|
|
|
|
|
|
|
Chapter 12 Object-oriented Design |
|
|
469 | (32) |
|
12.1 Simulating An Epidemic |
|
|
470 | (16) |
|
|
471 | (1) |
|
|
472 | (5) |
|
Augmenting the Person class |
|
|
477 | (2) |
|
|
479 | (2) |
|
|
481 | (5) |
|
12.2 Operators And Polymorphism |
|
|
486 | (13) |
|
|
487 | (1) |
|
|
488 | (1) |
|
|
489 | (2) |
|
|
491 | (2) |
|
|
493 | (1) |
|
|
494 | (5) |
|
12.3 A Flocking Simulation |
|
|
|
|
|
|
|
|
|
|
|
Converting numbers to other bases |
|
|
|
|
|
|
|
Implementing a hash table Indexing |
|
|
|
|
|
12.6 Summary And Further Discovery |
|
|
499 | (2) |
|
|
|
12.1 Tracking GPS coordinates |
|
|
|
|
|
12.3 Slime mold aggregation |
|
|
|
|
Bibliography |
|
501 | (4) |
Appendix A Python Library Reference |
|
Appendix B Selected Exercise Solutions |
|
Index |
|
505 | |