Descripciones mejoradas de Syndetics:

Drawing upon combined decades of teaching experience, Sara Baase and Allen Van Gelder have extensively revised this best seller to make it the most current and accessible choice for anyone interested in gaining a solid understanding of computer algorithm analysis and design. This edition features the addition of new topics such as computing with DNA, the accelerated version of heapsort, and dynamic sets, as well as an increased emphasis on algorithm design techniques such as divide-and-conquer and greedy algorithms. It continues the tradition of solid mathematical analysis and clear writing style that made it so popular in previous editions. This edition features implementations in a Java-like pseudocode, and includes an appendix with Java examples.

Tabla de contenidos provista por Syndetics

• Preface(p. vii)
• 1 Analyzing Algorithms and Problems: Principles and Examples(p. 1)
• 1.1 Introduction(p. 2)
• 1.2 Java as an Algorithm Language(p. 3)
• 1.3 Mathematical Background(p. 11)
• 1.4 Analyzing Algorithms and Problems(p. 30)
• 1.5 Classifying Functions by Their Asymptotic Growth Rates(p. 43)
• 1.6 Searching an Ordered Array(p. 53)
• Exercises(p. 61)
• Notes and References(p. 67)
• 2 Data Abstraction and Basic Data Structures(p. 69)
• 2.1 Introduction(p. 70)
• 2.2 ADT Specification and Design Techniques(p. 71)
• 2.3 Elementary ADTs--Lists and Trees(p. 73)
• 2.4 Stacks and Queues(p. 86)
• 2.5 ADTs for Dynamic Sets(p. 89)
• Exercises(p. 95)
• Notes and References(p. 100)
• 3 Recursion and Induction(p. 101)
• 3.1 Introduction(p. 102)
• 3.2 Recursive Procedures(p. 102)
• 3.3 What Is a Proof?(p. 108)
• 3.4 Induction Proofs(p. 111)
• 3.5 Proving Correctness of Procedures(p. 118)
• 3.6 Recurrence Equations(p. 130)
• 3.7 Recursion Trees(p. 134)
• Exercises(p. 141)
• Notes and References(p. 146)
• 4 Sorting(p. 149)
• 4.1 Introduction(p. 150)
• 4.2 Insertion Sort(p. 151)
• 4.3 Divide and Conquer(p. 157)
• 4.4 Quicksort(p. 159)
• 4.5 Merging Sorted Sequences(p. 171)
• 4.6 Mergesort(p. 174)
• 4.7 Lower Bounds for Sorting by Comparison of Keys(p. 178)
• 4.8 Heapsort(p. 182)
• 4.9 Comparison of Four Sorting Algorithms(p. 197)
• 4.10 Shellsort(p. 197)
• 4.11 Radix Sorting(p. 201)
• Exercises(p. 206)
• Programs(p. 221)
• Notes and References(p. 221)
• 5 Selection and Adversary Arguments(p. 223)
• 5.1 Introduction(p. 224)
• 5.2 Finding max and min(p. 226)
• 5.3 Finding the Second-Largest Key(p. 229)
• 5.4 The Selection Problem(p. 233)
• 5.5 A Lower Bound for Finding the Median(p. 238)
• 5.6 Designing Against an Adversary(p. 240)
• Exercises(p. 242)
• Notes and References(p. 246)
• 6 Dynamic Sets and Searching(p. 249)
• 6.1 Introduction(p. 250)
• 6.2 Array Doubling(p. 250)
• 6.3 Amortized Time Analysis(p. 251)
• 6.4 Red-Black Trees(p. 253)
• 6.5 Hashing(p. 275)
• 6.6 Dynamic Equivalence Relations and Union-Find Programs(p. 283)
• 6.7 Priority Queues with a Decrease Key Operation(p. 295)
• Exercises(p. 302)
• Programs(p. 309)
• Notes and References(p. 309)
• 7 Graphs and Graph Traversals(p. 313)
• 7.1 Introduction(p. 314)
• 7.2 Definitions and Representations(p. 314)
• 7.3 Traversing Graphs(p. 328)
• 7.4 Depth-First Search on Directed Graphs(p. 336)
• 7.5 Strongly Connected Components of a Directed Graph(p. 357)
• 7.6 Depth-First Search on Undirected Graphs(p. 364)
• 7.7 Biconnected Components of an Undirected Graph(p. 366)
• Exercises(p. 375)
• Programs(p. 384)
• Notes and References(p. 385)
• 8 Graph Optimization Problems and Greedy Algorithms(p. 387)
• 8.1 Introduction(p. 388)
• 8.2 Prim's Minimum Spanning Tree Algorithm(p. 388)
• 8.3 Single-Source Shortest Paths(p. 403)
• 8.4 Kruskal's Minimum Spanning Tree Algorithm(p. 412)
• Exercises(p. 416)
• Programs(p. 421)
• Notes and References(p. 422)
• 9 Transitive Closure, All-Pairs Shortest Paths(p. 425)
• 9.1 Introduction(p. 426)
• 9.2 The Transitive Closure of a Binary Relation(p. 426)
• 9.3 Warshall's Algorithm for Transitive Closure(p. 430)
• 9.4 All-Pairs Shortest Paths in Graphs(p. 433)
• 9.5 Computing Transitive Closure by Matrix Operations(p. 436)
• 9.6 Multiplying Bit Matrices--Kronrod's Algorithm(p. 439)
• Exercises(p. 446)
• Programs(p. 449)
• Notes and References(p. 449)
• 10 Dynamic Programming(p. 451)
• 10.1 Introduction(p. 452)
• 10.2 Subproblem Graphs and Their Traversal(p. 453)
• 10.3 Multiplying a Sequence of Matrices(p. 457)
• 10.4 Constructing Optimal Binary Search Trees(p. 466)
• 10.5 Separating Sequences of Words into Lines(p. 471)
• 10.6 Developing a Dynamic Programming Algorithm(p. 474)
• Exercises(p. 475)
• Programs(p. 481)
• Notes and References(p. 482)
• 11 String Matching(p. 483)
• 11.1 Introduction(p. 484)
• 11.2 A Straightforward Solution(p. 485)
• 11.3 The Knuth-Morris-Pratt Algorithm(p. 487)
• 11.4 The Boyer-Moore Algorithm(p. 495)
• 11.5 Approximate String Matching(p. 504)
• Exercises(p. 508)
• Programs(p. 512)
• Notes and References(p. 512)
• 12 Polynomials and Matrices(p. 515)
• 12.1 Introduction(p. 516)
• 12.2 Evaluating Polynomial Functions(p. 516)
• 12.3 Vector and Matrix Multiplication(p. 522)
• 12.4 The Fast Fourier Transform and Convolution(p. 528)
• Exercises(p. 542)
• Programs(p. 546)
• Notes and References(p. 546)
• 13 NP-Complete Problems(p. 547)
• 13.1 Introduction(p. 548)
• 13.2 P and NP(p. 548)
• 13.3 NP-Complete Problems(p. 559)
• 13.4 Approximation Algorithms(p. 570)
• 13.5 Bin Packing(p. 572)
• 13.6 The Knapsack and Subset Sum Problems(p. 577)
• 13.7 Graph Coloring(p. 581)
• 13.8 The Traveling Salesperson Problem(p. 589)
• 13.9 Computing with DNA(p. 592)
• Exercises(p. 600)
• Notes and References(p. 608)
• 14 Parallel Algorithms(p. 611)
• 14.1 Introduction(p. 612)
• 14.2 Parallelism, the PRAM, and Other Models(p. 612)
• 14.3 Some Simple PRAM Algorithms(p. 616)
• 14.4 Handling Write Conflicts(p. 622)
• 14.5 Merging and Sorting(p. 624)
• 14.6 Finding Connected Components(p. 628)
• 14.7 A Lower Bound for Adding n Integers(p. 641)
• Exercises(p. 643)
• Notes and References(p. 647)
• A Java Examples and Techniques(p. 649)
• A.1 Introduction(p. 650)
• A.2 A Java Main Program(p. 651)
• A.3 A Simple Input Library(p. 656)
• A.4 Documenting Java Classes(p. 658)
• A.5 Generic Order and the "Comparable" Interface(p. 659)
• A.6 Subclasses Extend the Capability of Their Superclass(p. 663)
• A.7 Copy via the "Cloneable" Interface(p. 667)
• Bibliography(p. 669)
• Index(p. 679)

Notas de autor provistas por Syndetics

Sara Baase is a Professor of Computer Science at San Diego State University and has been teaching CS for 25 years. Dr. Baase is a three-time recipient of the San Diego State University Alumni Association's Outstanding Faculty Award, and she has written a number of textbooks in the areas of algorithms, assembly language, and social and ethical issues related to computing. She earned her doctorate at the University of California, Berkeley.
Allen Van Gelder is a Professor of Computer Science at the University of California at Santa Cruz, where he has been teaching CS for 12 years. He received his Ph.D. in Computer Science at Stanford University and is a past recipient of the Presidential Young Investigator Award.