Contents

Introduction

Chapter 1 Algorithm Basics

Approach

Algorithms and Data Structures

Pseudocode

Algorithm Features

Big O Notation

Common Runtime Functions

Visualizing Functions

Practical Considerations

Summary

Exercises

Chapter 2 Numerical Algorithms

Randomizing Data

Generating Random Values

Randomizing Arrays

Generating Nonuniform Distributions

Finding Greatest Common Divisors

Performing Exponentiation

Working with Prime Numbers

Finding Prime Factors

Finding Primes

Testing for Primality

Performing Numerical Integration

The Rectangle Rule

The Trapezoid Rule

Adaptive Quadrature

Monte Carlo Integration

Finding Zeros

Summary

Exercises

Chapter 3 Linked Lists

Basic Concepts

Singly Linked Lists

Iterating Over the List

Finding Cells

Using Sentinels

Adding Cells at the Beginning

Adding Cells at the End

Inserting Cells After Other Cells

Deleting Cells

Doubly Linked Lists

Sorted Linked Lists

Linked-List Algorithms

Copying Lists

Sorting with Insertionsort

Linked List Selectionsort

Multithreaded Linked Lists

Linked Lists with Loops

Marking Cells

Using Hash Tables

List Retracing

List Reversal

Tortoise and Hare

Loops in Doubly Linked Lists

Summary

Exercises

Chapter 4 Arrays

Basic Concepts

One-dimensional Arrays

Finding Items

Finding Minimum, Maximum, and Average

Inserting Items

Removing Items

Nonzero Lower Bounds

Two Dimensions

Higher Dimensions

Triangular Arrays

Sparse Arrays

Find a Row or Column

Get a Value

Set a Value

Delete a Value

Matrices

Summary

Exercises

Chapter 5 Stacks and Queues

Stacks

Linked-List Stacks

Array Stacks

Double Stacks

Stack Algorithms

Queues

Linked-List Queues

Array Queues

Specialized Queues

Summary

Exercises

Chapter 6 Sorting

O(N²) Algorithms

Insertionsort in Arrays

Selectionsort in Arrays

Bubblesort

O(N log N) Algorithms

Heapsort

Quicksort

Mergesort

Sub O(N log N) Algorithms

Countingsort

Bucketsort

Summary

Exercises

Chapter 7 Searching

Linear Search

Binary Search

Interpolation Search

Summary

Exercises

Chapter 8 Hash Tables

Hash Table Fundamentals

Chaining

Open Addressing

Removing Items

Liner Probing

Quadratic Probing

Pseudorandom Probing

Double Hashing

Ordered Hashing

Summary

Exercises

Chapter 9 Recursion

Basic Algorithms

Factorial

Fibonacci Numbers

Tower of Hanoi

Graphical Algorithms

Koch Curves

Hilbert Curve

Sierpiski Curve

Gaskets

Backtracking Algorithms

Eight Queens Problem

Knight's Tour

Selections and Permutations

Selections with Loops

Selections with Duplicates

Selections Without Duplicates

Permutations with Duplicates

Permutations Without Duplicates

Recursion Removal

Tail Recursion Removal

Storing Intermediate Values

General Recursion Removal

Summary

Exercises

Chapter 10 Trees

Tree Terminology

Binary Tree Properties

Tree Representations

Building Trees in General

Building Complete Trees

Tree Traversal

Preorder Traversal

Inorder Traversal

Postorder Traversal

Depth-first Traversal

Traversal Run Times

Sorted Trees

Adding Nodes

Finding Nodes

Deleting Nodes

Threaded Trees

Building Threaded Trees

Using Threaded Trees

Specialized Tree Algorithms

The Animal Game

Expression Evaluation

Quadtrees

Tries

Summary

Exercises

Chapter 11 Balanced Trees

AVL Trees

Adding Values

Deleting Values

2-3 Trees

Adding Values

Deleting Values

B-Trees

Adding Values

Deleting Values

Balanced Tree Variations

Top-down B-trees

B+trees

Summary

Exercises

Chapter 12 Decision Trees

Searching Game Trees

Minimax

Initial Moves and Responses

Game Tree Heuristics

Searching General Decision Trees

Optimization Problems

Exhaustive Search

Branch and Bound

Decision Tree Heuristics

Other Decision Tree Problems

Summary

Exercises

Chapter 13 Basic Network Algorithms

Network Terminology

Network Representations

Traversals

Depth-first Traversal

Breadth-first Traversal

Connectivity Testing

Spanning Trees

Minimal Spanning Trees

Finding Paths

Finding Any Path

Label-Setting Shortest Paths

Label-Correcting Shortest Paths

All-Pairs Shortest Paths

Summary

Exercises

Chapter 14 More Network Algorithms

Topological Sorting

Cycle Detection

Map Coloring

Two-coloring

Three-coloring

Four-coloring

Five-coloring

Other Map-coloring Algorithms

Maximal Flow

Work Assignment

Minimal Flow Cut

Summary

Exercises

Chapter 15 String Algorithms

Matching Parentheses

Evaluating Arithmetic Expressions

Building Parse Trees

Pattern Matching

DFAs

Building DFAs for Regular Expressions

NFAs

String Searching

Calculating Edit Distance

Summary

Exercises

Chapter 16 Cryptography

Terminology

Transposition Ciphers

Row/column Transposition

Column Transposition

Route Ciphers

Substitution Ciphers

Caesar Substitution

Vigenère Cipher

Simple Substitution

One-Time Pads

Block Ciphers

Substitution-Permutation Networks

Feistel Ciphers

Public-Key Encryption and RSA

Euler's Totient Function

Multiplicative Inverses

An RSA Example

Practical Considerations

Other Uses for Cryptography

Summary

Exercises

Chapter 17 Complexity Theory

Notation

Complexity Classes

Reductions

3SAT

Bipartite Matching

NP-Hardness

Detection, Reporting, and Optimization Problems

Detection ≤_P Reporting

Reporting ≤_P Optimization

Reporting ≤_P Detection

Optimization ≤_P Reporting

NP-Complete Problems

Summary

Exercises

Chapter 18 Distributed Algorithms

Types of Parallelism

Systolic Arrays

Distributed Computing

Multi-CPU Processing

Race Conditions

Deadlock

Quantum Computing

Distributed Algorithms

Debugging Distributed Algorithms

Embarrassingly Parallel Algorithms

Mergesort

Dining Philosophers

The Two Generals Problem

Byzantine Generals

Consensus

Leader Election

Snapshot

Clock Synchronization

Summary

Exercises

Chapter 19 Interview Puzzles

Asking Interview Puzzle Questions

Answering Interview Puzzle Questions

Summary

Exercises

Appendix A Summary of Algorithmic Concepts

Appendix B Solutions to Exercises

Glossary

Index