Chapter 1: The Role of Algorithms in Computing

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