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 example

1.2.2 Integer operators

1.2.3 Float operators

1.2.4 Quadratic formula

1.2.5 Leap year

Conditionals and Loops

1.3.1 Flipping a fair coin

1.3.2 Your first 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 Function graph

1.5.7 Bouncing ball

1.5.8 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)

Modules and Clients

2.2.1 Gaussian functions module

2.2.2 Sample Gaussian client

2.2.3 Random number module

2.2.4 Iterated function systems

2.2.5 Data analysis module

2.2.6 Plotting data values

2.2.7 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

Case Study: Percolation

2.4.1 Percolation scaffolding

2.4.2 Vertical percolation detection

2.4.3 Percolation input/output

2.4.4 Visualization client

2.4.5 Percolation probability estimate

2.4.6 Percolation detection

2.4.7 Adaptive plot client

Object-Oriented Programming

Data Types

3.1.1 Identifying a potential gene

3.1.2 Charged-particle client

3.1.3 Albers squares

3.1.4 Luminance module

3.1.5 Converting color to grayscale

3.1.6 Image scaling

3.1.7 Fade effect

3.1.8 Visualizing electric potential

3.1.9 Concatenating files

3.1.10 Screen scraping for stock quotes

3.1.11 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 numbers

3.2.7 Mandelbrot set

3.2.8 Stock account

Designing Data Types

3.3.1 Complex numbers (polar)

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 (in a sorted array)

4.2.4 Insertion sort

4.2.5 Doubling test for sorts

4.2.6 Mergesort

4.2.7 Frequency counts

Stacks and Queues

4.3.1 Stack (resizing array)

4.3.2 Stack (linked list)

4.3.3 Expression evaluation

4.3.4 FIFO queue (linked list)

4.3.5 M/M/1 queue simulation

4.3.6 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

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