Contents......Page 3
Programs......Page 4
Preface......Page 6
Elements of Programming......Page 13
First Program......Page 14
Program 1.1.1 Hello, World......Page 16
Program 1.1.2 Using a command-line argument......Page 19
Built-in Types of Data......Page 25
Program 1.2.1 String concatenation......Page 31
Program 1.2.2 Integer multiplication and division......Page 34
Program 1.2.3 Quadratic formula......Page 36
Program 1.2.4 Leap year......Page 39
Program 1.2.5 Casting to get a random integer......Page 45
Conditionals & Loops......Page 61
Program 1.3.1 Flipping a fair coin......Page 64
Program 1.3.2 Your first while loop......Page 66
Program 1.3.3 Computing powers of 2......Page 68
Program 1.3.4 Your first nested loops......Page 74
Program 1.3.5 Harmonic numbers......Page 76
Program 1.3.6 Newton’s method......Page 77
Program 1.3.7 Converting to binary......Page 79
Program 1.3.8 Gambler’s ruin simulation......Page 82
Program 1.3.9 Factoring integers......Page 84
Arrays......Page 101
Program 1.4.1 Sampling without replacement......Page 109
Program 1.4.2 Coupon collector simulation......Page 113
Program 1.4.3 Sieve of Eratosthenes......Page 115
Program 1.4.4 Self-avoiding random walks......Page 124
IO......Page 137
Program 1.5.1 Generating a random sequence......Page 139
Program 1.5.2 Interactive user input......Page 147
Program 1.5.3 Averaging a stream of numbers......Page 149
Program 1.5.4 A simple filter......Page 151
Program 1.5.5 Standard input-to-drawing filter......Page 158
Program 1.5.6 Bouncing ball......Page 164
Program 1.5.7 Digital signal processing......Page 169
Case Study - Random Web Surfer......Page 181
Program 1.6.1 Computing the transition matrix......Page 184
Program 1.6.2 Simulating a random surfer......Page 186
Program 1.6.3 Mixing a Markov chain......Page 193
Functions & Modules......Page 200
Defining Functions......Page 201
Program 2.1.1 Harmonic numbers (revisited)......Page 203
Program 2.1.2 Gaussian functions......Page 212
Program 2.1.3 Coupon collector (revisited)......Page 215
Program 2.1.4 Play that tune (revisited)......Page 222
Libraries & Clients......Page 235
Program 2.2.1 Random number library......Page 243
Program 2.2.2 Array I/O library......Page 247
Program 2.2.3 Iterated function systems......Page 250
Program 2.2.4 Data analysis library......Page 254
Program 2.2.5 Plotting data values in an array......Page 256
Program 2.2.6 Bernoulli trials......Page 259
Recursion......Page 271
Program 2.3.1 Euclid’s algorithm......Page 275
Program 2.3.2 Towers of Hanoi......Page 278
Program 2.3.3 Gray code......Page 283
Program 2.3.4 Recursive graphics......Page 285
Program 2.3.5 Brownian bridge......Page 287
Program 2.3.6 Longest common subsequence......Page 295
Case Study - Percolation......Page 308
Program 2.4.1 Percolation scaffolding......Page 312
Program 2.4.2 Vertical percolation detection......Page 314
Program 2.4.3 Visualization client......Page 317
Program 2.4.4 Percolation probability estimate......Page 319
Program 2.4.5 Percolation detection......Page 321
Program 2.4.6 Adaptive plot client......Page 324
OOP......Page 335
Using Data Types......Page 336
Program 3.1.1 Identifying a potential gene......Page 343
Program 3.1.2 Albers squares......Page 348
Program 3.1.3 Luminance library......Page 351
Program 3.1.4 Converting color to grayscale......Page 354
Program 3.1.5 Image scaling......Page 356
Program 3.1.6 Fade effect......Page 358
Program 3.1.7 Concatenating files......Page 362
Program 3.1.8 Screen scraping for stock quotes......Page 365
Program 3.1.9 Splitting a file......Page 366
Creating Data Types......Page 387
Program 3.2.1 Charged particle......Page 392
Program 3.2.2 Stopwatch......Page 396
Program 3.2.3 Histogram......Page 398
Program 3.2.4 Turtle graphics......Page 401
Program 3.2.5 Spira mirabilis......Page 404
Program 3.2.6 Complex number......Page 410
Program 3.2.7 Mandelbrot set......Page 414
Program 3.2.8 Stock account......Page 418
Designing Data Types......Page 433
Program 3.3.1 Complex number (alternate)......Page 439
Program 3.3.2 Counter......Page 442
Program 3.3.3 Spatial vectors......Page 449
Program 3.3.4 Document sketch......Page 466
Program 3.3.5 Similarity detection......Page 468
Case Study - N-Body Simulation......Page 483
Program 3.4.1 Gravitational body......Page 487
Program 3.4.2 N-body simulation......Page 490
Algorithms & Data Structures......Page 497
Performance......Page 498
Program 4.1.1 3-sum problem......Page 501
Program 4.1.2 Validating a doubling hypothesis......Page 503
Sorting & Searching......Page 536
Program 4.2.1 Binary search (20 questions)......Page 538
Program 4.2.2 Bisection search......Page 541
Program 4.2.3 Binary search (sorted array)......Page 543
Program 4.2.4 Insertion sort......Page 551
Program 4.2.5 Doubling test for insertion sort......Page 553
Program 4.2.6 Mergesort......Page 556
Program 4.2.7 Frequency counts......Page 561
Stacks & Queues......Page 570
Program 4.3.1 Stack of strings (array)......Page 574
Program 4.3.2 Stack of strings (linked list)......Page 579
Program 4.3.3 Stack of strings (resizing array)......Page 583
Program 4.3.4 Generic stack......Page 588
Program 4.3.5 Expression evaluation......Page 592
Program 4.3.6 Generic FIFO queue (linked list)......Page 598
Program 4.3.7 M/M/1 queue simulation......Page 603
Program 4.3.8 Load balancing simulation......Page 611
Symbol Tables......Page 628
Program 4.4.1 Dictionary lookup......Page 635
Program 4.4.2 Indexing......Page 637
Program 4.4.3 Hash table......Page 642
Program 4.4.4 Binary search tree......Page 650
Program 4.4.5 Dedup filter......Page 657
Case Study - Small-World Phenomenon......Page 674
Program 4.5.1 Graph data type......Page 681
Program 4.5.2 Using a graph to invert an index......Page 685
Program 4.5.3 Shortest-paths client......Page 689
Program 4.5.4 Shortest-paths implementation......Page 695
Program 4.5.5 Small-world test......Page 700
Program 4.5.6 Performer–performer graph......Page 702
Context......Page 718
Glossary......Page 722
Index......Page 728
APIs......Page 749