xviii Contents 10.4 Constructing Optimal Binary Search Trees 466 10.5 Separating Sequences of Words into Lines 471 10.6 Developing a Dynamic Programming Algorithm 474 Exercises 475 Programs 481 Notes and References 482 11 String Matching 483 11.1 Introduction 484 11.2 A Straightforward Solution 485 11.3 The Knuth-Morris-Pratt Algorithm 487 11.4 The Boyer-Moore Algorithm 495 11.5 Approximate String Matching 504 Exercises 508 Programs 512 Notes and References 512 12 Polynomials and Matrices 515 12.1 Introduction 516 12.2 Evaluating Polynomial Functions 516 12.3 Vector and Matrix Multiplication 522 *12.4 The Fast Fourier Transform and Convolution 528 Exercises 542 Programs 546 Notes and References 546 13 NP-Complete Problems 547 13.I Introduction 548 13.2 P and NP 548 13.3 NP-Complete Problems 559 13.4 Approximation Algorithms 570 13.5 Bin Packing 572 13.6 The Knapsack and Subset Sum Problems 577 13.7 Graph Coloring 58] 13.8 The Traveling Salesperson Problem 589 13.9 Computing with DNA 592 Exercises 600 Notes and References 608