×

Uh-oh, it looks like your Internet Explorer is out of date.

For a better shopping experience, please upgrade now.

Algorithms in C++ / Edition 1
     

Algorithms in C++ / Edition 1

by Robert Sedgewick
 

See All Formats & Editions

ISBN-10: 0201510596

ISBN-13: 9780201510591

Pub. Date: 04/30/1992

Publisher: Addison-Wesley

The latest addition to Robert Sedgewick's popular series of books c arries his comprehensive collection of algorithms into anobject-oriented programming (OOP) environment with implementationin the C++ programming language. These algorithms cover a broadrange of fundamental and more advanced methods: sorting,searching, string-processing, geometric, graph,

Overview

The latest addition to Robert Sedgewick's popular series of books c arries his comprehensive collection of algorithms into anobject-oriented programming (OOP) environment with implementationin the C++ programming language. These algorithms cover a broadrange of fundamental and more advanced methods: sorting,searching, string-processing, geometric, graph, and mathematicalalgorithms. The algorithms are all expressed in terms of conciseimplementations in C++, so that readers can both appreciate theirbasic properties and test them on real applications.

The treatment of analysis of algorithsm is carefully developed. When appropriate, analytic results are discussed to illustratewhy certain algorithms are prefered, and in some cases, therelationship of the proactical algorithms being discussed topurely theoretical results is also described.

The ultimate aim of the book is to improve programming practice,whatever the environment, whatever the implementation language. Sedgweick describes the basic methods to be considered in everycase.

Product Details

ISBN-13:
9780201510591
Publisher:
Addison-Wesley
Publication date:
04/30/1992
Edition description:
New Edition
Pages:
672
Product dimensions:
6.66(w) x 9.54(h) x 1.59(d)

Table of Contents

Fundamentals 3(90)
1. Introduction Algorithms. Outline of Topics.
3(4)
2. C++ (and C) Example: Euclid's Algorithm. Types of Data. Input/Output. Concluding Remarks.
7(8)
3. Elementary Data Structures Arrays. Linked Lists. Storage Allocation. Pushdown Stacks. Queues. Linked List Implementation of Stacks. Abstract and Concrete Data Types.
15(20)
4. Trees Glossary. Properties. Representing Binary Trees. Representing Forests. Traversing Trees.
35(16)
5. Recursion Recurrences. Divide-and-Conquer. Recursive Tree Traversal. Removing Recursion. Perspective.
51(16)
6. Analysis of Algorithms Framework. Classification of Algorithms. Computational Complexity. Average-Case Analysis. Approximate and Asymptotic Results. Basic Recurrences. Perspective.
67(14)
7. Implementation of Algorithms Selecting an Algorithm. Empirical Analysis. Program Optimization. Algorithms and Systems.
81(12)
Sorting Algorithms 93(100)
8. Elementary Sorting Methods Rules of the Game. Selection Sort. Insertion Sort. Digression: Bubble Sort. Performance Characteristics of Elementary Sorts. Sorting Files with Large Records. Shellsort. Distribution Counting.
93(22)
9. Quicksort The Basic Algorithm. Performance Characteristics of Quicksort. Removing Recursion. Small Subfiles. Median-of-Three Partitioning. Selection.
115(18)
10. Radix Sorting Bits. Radix Exchange Sort. Straight Radix Sort. Performance Characteristics of Radix Sorts. A Linear Sort.
133(12)
11. Priority Queues Elementary Implementations. Heap Data Structure. Algorithms on Heaps. Heapsort. Indirect Heaps. Advanced Implementations.
145(18)
12. Mergesort Merging. Mergesort. List Mergesort. Bottom-Up Mergesort. Performance Characteristics. Optimized Implementations. Recursion Revisited.
163(14)
13. External Sorting Sort-Merge. Balanced Multiway Merging. Replacement Selection. Practical Considerations. Polyphase Merging. An Easier Way.
177(16)
Searching Algorithms 193(84)
14. Elementary Searching Methods Sequential Searching. Binary Search. Binary Tree Search. Deletion. Indirect Binary Search Trees.
193(22)
15. Balanced Trees Top-Down 2-3-4 Trees. Red-Black Trees. Other Algorithms.
215(16)
16. Hashing Hash Functions. Separate Chaining. Linear Probing. Double Hashing. Perspective.
231(14)
17. Radix Searching Digital Search Trees. Radix Search Tries. Multiway Radix Searching. Patricia.
245(14)
18. External Searching Indexed Sequential Access. B-Trees. Extendible Hashing. Virtual Memory.
259(18)
String Processing 277(70)
19. String Searching A Short History. Brute-Force Algorithm. Knuth-Morris-Pratt Algorithm. Boyer-Moore Algorithm. Rabin-Karp Algorithm. Multiple Searches.
277(16)
20. Pattern Matching Describing Patterns. Pattern Matching Machines. Representing the Machine. Simulating the Machine.
293(12)
21. Parsing Context-Free Grammars. Top-Down Parsing. Bottom-Up Parsing. Compilers. Compiler-Compilers.
305(14)
22. File Compression Run-Length Encoding. Variable-Length Encoding. Building the Huffman Code. Implementation.
319(14)
23. Cryptology Rules of the Game. Simple Methods. Encryption/Decryption Machines. Public-Key Cryptosystems.
333(14)
Geometric Algorithms 347(68)
24. Elementary Geometric Methods Points, Lines, and Polygons. Line Segment Intersection. Simple Closed Path. Inclusion in a Polygon. Perspective.
347(12)
25. Finding the Convex Hull Rules of the Game. Package-Wrapping. The Graham Scan. Interior Elimination. Performance Issues.
359(14)
26. Range Searching Elementary Methods. Grid Method. Two-Dimensional Trees. Multidimensional Range Searching.
373(16)
27. Geometric Intersection Horizontal and Vertical Lines. Implementation. General Line Intersection.
389(12)
28. Closest-Point Problems Closest-Pair Problem. Voronoi Diagrams.
401(14)
Graph Algorithms 415(94)
29. Elementary Graph Algorithms Glossary. Representation. Depth-First Search. Nonrecursive Depth-First Search. Breadth-First Search. Mazes. Perspective.
415(22)
30. Connectivity Connected Components. Biconnectivity. Union-Find Algorithms.
437(14)
31. Weighted Graphs Minimum Spanning Tree. Priority-First Search. Kruskal's Method. Shortest Path. Minimum Spanning Tree and Shortest Paths in Dense Graphs. Geometric Problems.
451(20)
32. Directed Graphs Depth-First Search. Transitive Closure. All Shortest Paths. Topological Sorting. Strongly Connected Components.
471(14)
33. Network Flow The Network Flow Problem. Ford-Fulkerson Method. Network Searching.
485(10)
34. Matching Bipartite Graphs. Stable Marriage Problem. Advanced Algorithms.
495(14)
Mathematical Algorithms 509(60)
35. Random Numbers Applications. Linear Congruential Method. Additive Congruential Method. Testing Randomness. Implementation Notes.
509(12)
36. Arithmetic Polynomial Arithmetic. Polynomial Evaluation and Interpolation. Polynomial Multiplication. Arithmetic Operations with Large Integers. Matrix Arithmetic.
521(14)
37. Gaussian Elimination A Simple Example. Outline of the Method. Variations and Extensions.
535(10)
38. Curve Fitting Polynomial Interpolation. Spline Interpolation. Method of Least Squares.
545(10)
39. Integration Symbolic Integration. Simple Quadrature Methods. Compound Methods. Adaptive Quadrature.
555(14)
Advanced Topics 569(74)
40. Parallel Algorithms General Approaches. Perfect Shuffles. Systolic Arrays. Perspective.
569(14)
41. The Fast Fourier Transform Evaluate, Multiply, Interpolate. Complex Roots of Unity. Evaluation at the Roots of Unity. Interpolation at the Roots of Unity. Implementation.
583(12)
42. Dynamic Programming Knapsack Problem. Matrix Chain Product. Optimal Binary Search Trees. Time and Space Requirements.
595(12)
43. Linear Programming Linear Programs. Geometric Interpretation. The Simplex Method. Implementation.
607(14)
44. Exhaustive Search Exhaustive Search in Graphs. Backtracking. Digression: Permutation Generation. Approximation Algorithms.
621(12)
45. NP-Complete Problems Deterministic and Nondeterministic Polynomial-Time Algorithms. NP-Completeness. Cook's Theorem. Some NP-Complete Problems.
633(10)
Index 643

Customer Reviews

Average Review:

Post to your social network

     

Most Helpful Customer Reviews

See all customer reviews