< Day Day Up >
List of Problems
Chapter 1:
The Role of Algorithms in Computing
Problems 1-1:
Comparison of running times
Chapter 2:
Getting Started
Problems 2-1:
Insertion sort on small arrays in merge sort
Problems 2-2:
Correctness of bubblesort
Problems 2-3:
Correctness of Horner's rule
Problems 2-4:
Inversions
Chapter 3:
Growth of Functions
Problems 3-1:
Asymptotic behavior of polynomials
Problems 3-2:
Relative asymptotic growths
Problems 3-3:
Ordering by asymptotic growth rates
Problems 3-4:
Asymptotic notation properties
Problems 3-5:
Variations on O and
Ω
Problems 3-6:
Iterated functions
Chapter 4:
Recurrences
Problems 4-1:
Recurrence examples
Problems 4-2:
Finding the missing integer
Problems 4-3:
Parameter-passing costs
Problems 4-4:
More recurrence examples
Problems 4-5:
Fibonacci numbers
Problems 4-6:
VLSI chip testing
Problems 4-7:
Monge arrays
Chapter 5:
Probabilistic Analysis and Randomized Algorithms
Problems 5-1:
Probabilistic counting
Problems 5-2:
Searching an unsorted array
Chapter 6:
Heapsort
Problems 6-1:
Building a heap using insertion
Problems 6-2:
Analysis of d-ary heaps
Problems 6-3:
Young tableaus
Chapter 7:
Quicksort
Problems 7-1:
Hoare partition correctness
Problems 7-2:
Alternative quicksort analysis
Problems 7-3:
Stooge sort
Problems 7-4:
Stack depth for quicksort
Problems 7-5:
Median-of-3 partition
Problems 7-6:
Fuzzy sorting of intervals
Chapter 8:
Sorting in Linear Time
Problems 8-1:
Average-case lower bounds on comparison sorting
Problems 8-2:
Sorting in place in linear time
Problems 8-3:
Sorting variable-length items
Problems 8-4:
Water jugs
Problems 8-5:
Average sorting
Problems 8-6:
Lower bound on merging sorted lists
Chapter 9:
Medians and Order Statistics
Problems 9-1:
Largest i numbers in sorted order
Problems 9-2:
Weighted median
Problems 9-3:
Small order statistics
Chapter 10:
Elementary Data Structures
Problems 10-1:
Comparisons among lists
Problems 10-2:
Mergeable heaps using linked lists
Problems 10-3:
Searching a sorted compact list
Chapter 11:
Hash Tables
Problems 11-1:
Longest-probe bound for hashing
Problems 11-2:
Slot-size bound for chaining
Problems 11-3:
Quadratic probing
Problems 11-4:
k-universal hashing and authentication
Chapter 12:
Binary Search Trees
Problems 12-1:
Binary search trees with equal keys
Problems 12-2:
Radix trees
Problems 12-3:
Average node depth in a randomly built binary search tree
Problems 12-4:
Number of different binary trees
Chapter 13:
Red-Black Trees
Problems 13-1:
Persistent dynamic sets
Problems 13-2:
Join operation on red-black trees
Problems 13-3:
AVL trees
Problems 13-4:
Treaps
Chapter 14:
Augmenting Data Structures
Problems 14-1:
Point of Maximum Overlap
Problems 14-2:
Josephus Permutation
Chapter 15:
Dynamic Programming
Problems 15-1:
Bitonic euclidean traveling-salesman problem
Problems 15-2:
Printing neatly
Problems 15-3:
Edit distance
Problems 15-4:
Planning a company party
Problems 15-5:
Viterbi algorithm
Problems 15-6:
Moving on a checkerboard
Problems 15-7:
Scheduling to maximize profit
Chapter 16:
Greedy Algorithms
Problems 16-1:
Coin changing
Problems 16-2:
Scheduling to minimize average completion time
Problems 16-3:
Acyclic subgraphs
Problems 16-4:
Scheduling variations
Chapter 17:
Amortized Analysis
Problems 17-1:
Bit-reversed binary counter
Problems 17-2:
Making binary search dynamic
Problems 17-3:
Amortized weight-balanced trees
Problems 17-4:
The cost of restructuring red-black trees
Chapter 18:
B-Trees
Problems 18-1:
Stacks on secondary storage
Problems 18-2:
Joining and splitting 2-3-4 trees
Chapter 19:
Binomial Heaps
Problems 19-1:
2-3-4 heaps
Problems 19-2:
Minimum-spanning-tree algorithm using binomial heaps
Chapter 20:
Fibonacci Heaps
Problems 20-1:
Alternative implementation of deletion
Problems 20-2:
More Fibonacci-heap operations
Chapter 21:
Data Structures for Disjoint Sets
Problems 21-1:
Off-line minimum
Problems 21-2:
Depth determination
Problems 21-3:
Tarjan's off-line least-common-ancestors algorithm
Chapter 22:
Elementary Graph Algorithms
Problems 22-1:
Classifying edges by breadth-first search
Problems 22-2:
Articulation points, bridges, and biconnected components
Problems 22-3:
Euler tour
Problems 22-4:
Reachability
Chapter 23:
Minimum Spanning Trees
Problems 23-1:
Second-best minimum spanning tree
Problems 23-2:
Minimum spanning tree in sparse graphs
Problems 23-3:
Bottleneck spanning tree
Problems 23-4:
Alternative minimum-spanning-tree algorithms
Chapter 24:
Single-Source Shortest Paths
Problems 24-1:
Yen's improvement to Bellman-Ford
Problems 24-2:
Nesting boxes
Problems 24-3:
Arbitrage
Problems 24-4:
Gabow's scaling algorithm for single-source shortest paths
Problems 24-5:
Karp's minimum mean-weight cycle algorithm
Problems 24-6:
Bitonic shortest paths
Chapter 25:
All-Pairs Shortest Paths
Problems 25-1:
Transitive closure of a dynamic graph
Problems 25-2:
Shortest paths in
∈
-dense graphs
Chapter 26:
Maximum Flow
Problems 26-1:
Escape problem
Problems 26-2:
Minimum path cover
Problems 26-3:
Space shuttle experiments
Problem 26-4:
Updating maximum flow
Problem 26-5:
Maximum flow by scaling
Problem 26-6:
Maximum flow with negative capacities
Problem 26-7:
The Hopcroft-Karp bipartite matching algorithm
Chapter 27:
Sorting Networks
Problems 27-1:
Transposition sorting networks
Problems 27-2:
Batcher's odd-even merging network
Problems 27-3:
Permutation networks
Chapter 28:
Matrix Operations
Problems 28-1:
Tridiagonal systems of linear equations
Problems 28-2:
Splines
Chapter 29:
Linear Programming
Problems 29-1:
Linear-inequality feasibility
Problems 29-2:
Complementary slackness
Chapter 30:
Polynomials and the FFT
Problems 30-1:
Divide-and-conquer multiplication
Problems 30-2:
Toeplitz matrices
Problems 30-3:
Multidimensional Fast Fourier Transform
Problems 30-4:
Evaluating all derivatives of a polynomial at a point
Problems 30-5:
Polynomial evaluation at multiple points
Problems 30-6:
FFT using modular arithmetic
Chapter 31:
Number-Theoretic Algorithms
Problems 31-1:
Binary gcd algorithm
Problems 31-2:
Analysis of bit operations in Euclid's algorithm
Problems 31-4:
Quadratic residues
Chapter 32:
String Matching
Problems 32-1:
String matching based on repetition factors
Chapter 33:
Computational Geometry
Problems 33-1:
Convex layers
Problems 33-2:
Maximal layers
Problems 33-3:
Ghostbusters and ghosts
Problems 33-4:
Picking up sticks
Problems 33-5:
Sparse-hulled distributions
Chapter 34:
NP-Completeness
Problems 34-1:
Independent set
Problems 34-2:
Bonnie and Clyde
Problems 34-3:
Graph coloring
Problems 34-4:
Scheduling with profits and deadlines
Chapter 35:
Approximation Algorithms
Problems 35-1:
Bin packing
Problems 35-2:
Approximating the size of a maximum clique
Problems 35-3:
Weighted set-covering problem
Problems 35-4:
Maximum matching
Problems 35-5:
Parallel machine scheduling
Appendix A:
Summations
Problems A-1:
Bounding summations
Appendix B:
Sets, Etc.
Problems B-1:
Graph coloring
Problems B-2:
Friendly graphs
Problems B-3:
Bisecting trees
Appendix C:
Counting and Probability
Problems C-1:
Balls and bins
< Day Day Up >
