Programs

Elements of Programming

Your First Program

1.1.1 Hello, World

1.1.2 Using a command-line argument

Built-in Types of Data

1.2.1 String concatenation

1.2.2 Integer multiplication and division

1.2.3 Quadratic formula

1.2.4 Leap year

1.2.5 Casting to get a random integer

Conditionals and Loops

1.3.1 Flipping a fair coin

1.3.2 Your first while loop

1.3.3 Computing powers of 2

1.3.4 Your first nested loops

1.3.5 Harmonic numbers

1.3.6 Newton’s method

1.3.7 Converting to binary

1.3.8 Gambler’s ruin simulation

1.3.9 Factoring integers

Arrays

1.4.1 Sampling without replacement

1.4.2 Coupon collector simulation

1.4.3 Sieve of Eratosthenes

1.4.4 Self-avoiding random walks

Input and Output

1.5.1 Generating a random sequence

1.5.2 Interactive user input

1.5.3 Averaging a stream of numbers

1.5.4 A simple filter

1.5.5 Standard input-to-drawing filter

1.5.6 Bouncing ball

1.5.7 Digital signal processing

Case Study: Random Web Surfer

1.6.1 Computing the transition matrix

1.6.2 Simulating a random surfer

1.6.3 Mixing a Markov chain

Functions and Modules

Defining Functions

2.1.1 Harmonic numbers (revisited)

2.1.2 Gaussian functions

2.1.3 Coupon collector (revisited)

2.1.4 Play that tune (revisited)

Libraries and Clients

2.2.1 Random number library

2.2.2 Array I/O library

2.2.3 Iterated function systems

2.2.4 Data analysis library

2.2.5 Plotting data values in an array

2.2.6 Bernoulli trials

Recursion

2.3.1 Euclid’s algorithm

2.3.2 Towers of Hanoi

2.3.3 Gray code

2.3.4 Recursive graphics

2.3.5 Brownian bridge

2.3.6 Longest common subsequence

Case Study: Percolation

2.4.1 Percolation scaffolding

2.4.2 Vertical percolation detection

2.4.3 Visualization client

2.4.4 Percolation probability estimate

2.4.5 Percolation detection

2.4.6 Adaptive plot client

Object-Oriented Programming

Using Data Types

3.1.1 Identifying a potential gene

3.1.2 Albers squares

3.1.3 Luminance library

3.1.4 Converting color to grayscale

3.1.5 Image scaling

3.1.6 Fade effect

3.1.7 Concatenating files

3.1.8 Screen scraping for stock quotes

3.1.9 Splitting a file

Creating Data Types

3.2.1 Charged particle

3.2.2 Stopwatch

3.2.3 Histogram

3.2.4 Turtle graphics

3.2.5 Spira mirabilis

3.2.6 Complex number

3.2.7 Mandelbrot set

3.2.8 Stock account

Designing Data Types

3.3.1 Complex number (alternate)

3.3.2 Counter

3.3.3 Spatial vectors

3.3.4 Document sketch

3.3.5 Similarity detection

Case Study: N-Body Simulation

3.4.1 Gravitational body

3.4.2 N-body simulation

Algorithms and Data Structures

Performance

4.1.1 3-sum problem

4.1.2 Validating a doubling hypothesis

Sorting and Searching

4.2.1 Binary search (20 questions)

4.2.2 Bisection search

4.2.3 Binary search (sorted array)

4.2.4 Insertion sort

4.2.5 Doubling test for insertion sort

4.2.6 Mergesort

4.2.7 Frequency counts

Stacks and Queues

4.3.1 Stack of strings (array)

4.3.2 Stack of strings (linked list)

4.3.3 Stack of strings (resizing array)

4.3.4 Generic stack

4.3.5 Expression evaluation

4.3.6 Generic FIFO queue (linked list)

4.3.7 M/M/1 queue simulation

4.3.8 Load balancing simulation

Symbol Tables

4.4.1 Dictionary lookup

4.4.2 Indexing

4.4.3 Hash table

4.4.4 Binary search tree

4.4.5 Dedup filter

Case Study: Small-World Phenomenon

4.5.1 Graph data type

4.5.2 Using a graph to invert an index

4.5.3 Shortest-paths client

4.5.4 Shortest-paths implementation

4.5.5 Small-world test

4.5.6 Performer–performer graph