Fundamentals of computers algorithms / Ellis Horowitz, Sartaj Sahni.

CONTENIDO
Chapter 1: INTRODUCTION
What is an algorithm 1
Writing algorithms in SPARKS 4
Writing structured programs 14
Analyzing algorithms 24
References and selected readings 40
Exercises 41
Chapter 2: ELEMENTARY DATA STRUCTURES
Stacks and queues 48
Trees 53
Heaps and heapsort 61
Sets and disjoint set union 70
Graphs 79
Hashing 82
References and selected readings 93
Exercises 94
Chapter 3: DIVIDE-AND-CONQUER
The general method 98
Binary search 100
Finding the maximum and minimum 108
Mergesort 113
Quicksort 121
Selection 127
Strassen's matrix multiplication 137
References and selected readings 140
Exercises 141
Chapter 4: THE GREEDY METHOD
The general method 152
Optimal storage on tapes 153
Knapsack problem 157
Job sequencing with deadlines 161
Optimal merge patterns 169
Minimum spanning trees 174
Single source shortest paths 183
References and selected readings 188
Exercises 191
Chapter 5: DYNAMIC PROGRAMMING
The general method 198
Multistage graphs 203
All pairs shortest paths 208
Optimal binary search trees 211
0/1 knapsack 219
Reliability design 228
The traveling salesperson problem 231
Flow shop scheduling 234
References and selected readings 238
Exercises 240
Chapter 6: BASIC SEARCH AND TRAVERSAL TECHNIQUES
The techniques 248
Code optimization 270
AND/OR graphs 286
Game trees 290
Biconnected components and depth first search 302
References and selected readings 309
Exercises 311
Chapter 7: BACKTRACKING
The general method 323
The 8-queens problem 337
Sum of subsets 339
Graph coloring 343
Hamiltonian cycles 348
Knapsack problem 350
References and selected readings 359
Exercises 363
Chapter 8: BRANCH AND-BOUND
The method 370
0/1 knapsack problem 390
Traveling salesperson 403
Efficiency considerations 412
References and selected readings 415
Exercises 417
Chapter 9: ALGEBRAIC SIMPLIFICATION AND TRANSFORMATIONS
The general method 422
Evaluation and interpolation 424
The fast Fourier transform 431
Modular arithmetic 440
Even faster evaluation and interpolation 447
References and selected readings 455
Exercises 457
Chapter 10: LOWER BOUND THEORY
Comparison trees for sorting and searching 461
Oracles and Adversary Arguments 469
Techniques for algebraic problems 478
Some lower bounds on parallel computation 488
References and selected readings 494
Exercises 497
Chapter 11: NP-HARD AND NP-COMPLETE PROBLEMS
Basic concepts 501
Cook's theorem 513
NP-Hard graph problems 522
NP-Hard scheduling problems 532
NP-Hard code generation problems 538
Some simplified NP-Hard problems 545
References and selected readings 548
Exercises 552
Chapter 12: APPROXIMATION ALGORITHMS FOR NP-HARD PROBLEMS
Introduction 559
Absolute approximations 562
approximations 567
Polynomial time approximation schemes 578
Fully polynomial time approximation schemes 585
Probabilistically good algorithms 596
References and selected readings 599
Exercises 604
Appendix asparks 614
Index 622