Muutke küpsiste eelistusi

Algorithm Design Manual Third Edition 2020 [Pehme köide]

  • Formaat: Paperback / softback, 793 pages, kõrgus x laius: 235x178 mm, kaal: 1404 g, 1 Illustrations, black and white; XVII, 793 p. 1 illus., 1 Paperback / softback
  • Sari: Texts in Computer Science
  • Ilmumisaeg: 07-Oct-2021
  • Kirjastus: Springer Nature Switzerland AG
  • ISBN-10: 3030542580
  • ISBN-13: 9783030542580
  • Pehme köide
  • Hind: 53,33 €*
  • * hind on lõplik, st. muud allahindlused enam ei rakendu
  • Tavahind: 62,74 €
  • Säästad 15%
  • Raamatu kohalejõudmiseks kirjastusest kulub orienteeruvalt 2-4 nädalat
  • Kogus:
  • Lisa ostukorvi
  • Tasuta tarne
  • Tellimisaeg 2-4 nädalat
  • Lisa soovinimekirja
  • Formaat: Paperback / softback, 793 pages, kõrgus x laius: 235x178 mm, kaal: 1404 g, 1 Illustrations, black and white; XVII, 793 p. 1 illus., 1 Paperback / softback
  • Sari: Texts in Computer Science
  • Ilmumisaeg: 07-Oct-2021
  • Kirjastus: Springer Nature Switzerland AG
  • ISBN-10: 3030542580
  • ISBN-13: 9783030542580

"My absolute favorite for this kind of interview preparation is Steven Skiena’s The Algorithm Design Manual. More than any other book it helped me understand just how astonishingly commonplace … graph problems are -- they should be part of every working programmer’s toolkit. The book also covers basic data structures and sorting algorithms, which is a nice bonus. … every 1 – pager has a simple picture, making it easy to remember. This is a great way to learn how to identify hundreds of problem types." (Steve Yegge, Get that Job at Google)

"Steven Skiena’s Algorithm Design Manual retains its title as the best and most comprehensive practical algorithm guide to help identify and solve problems. … Every programmer should read this book, and anyone working in the field should keep it close to hand. … This is the best investment … a programmer or aspiring programmer can make." (Harold Thimbleby, Times Higher Education)

"It is wonderful to open to a random spot and discover an interesting algorithm. This is the only textbook I felt compelled to bring with me out of my student days.... The color really adds a lot of energy to the new edition of the book!" (Cory Bart, University of Delaware)

"The is the most approachable book on algorithms I have."   (Megan Squire, Elon University)

---

This newly expanded and updated third edition of the best-selling classic continues to take the "mystery" out of designing algorithms, and analyzing their efficiency.  It serves as the primary textbook of choice for algorithm design courses and interview self-study, while maintaining its status as the premier practical reference guide to algorithms for programmers, researchers, and students.

 

The reader-friendly Algorithm Design Manual provides straightforward access to combinatorial algorithms technology, stressing design over analysis.  The first part, Practical Algorithm Design, provides accessible instruction on methods for designing and analyzing computer algorithms.  The second part, the Hitchhiker's Guide to Algorithms, is intended for browsing and reference, and comprises the catalog of algorithmic resources, implementations, and an extensive bibliography. 


NEW to the third edition: 

-- New and expanded coverage of randomized algorithms, hashing, divide and conquer, approximation algorithms, and quantum computing 

-- Provides full online support for lecturers, including an improved website component with lecture slides and videos 

-- Full color illustrations and code instantly clarify difficult concepts 

-- Includes several new "war stories" relating experiences from real-world applications

 -- Over 100 new problems, including programming-challenge problems from LeetCode and Hackerrank. 

-- Provides up-to-date links leading to the best implementations available in C, C++, and Java

 

Additional Learning Tools: 

-- Contains a unique catalog identifying the 75 algorithmic problems that arise most often in practice, leading the reader down the right path to solve them 

-- Exercises include "job interview problems" from major software companies 

-- Highlighted "take home lessons" emphasize essential concepts 

-- The "no theorem-proof" style provides a uniquely accessible and intuitive approach to a challenging subject 

-- Many algorithms are presented with actual code (written in C) 

-- Provides comprehensive references to both survey articles and the primary literature

 

Written by a well-known algorithms researcher who received the IEEE Computer Science and Engineering Teaching Award, this substantially enhanced third edition of The Algorithm Design Manual is an essential learning tool for students and professionals needed a solid grounding in algorithms.   Professor Skiena is also the author of the popular Springer texts, The Data Science Design Manual and Programming Challenges: The Programming Contest Training Manual.

I Practical Algorithm Design 1(434)
1 Introduction to Algorithm Design
3(28)
1.1 Robot Tour Optimization
5(3)
1.2 Selecting the Right Jobs
8(3)
1.3 Reasoning about Correctness
11(4)
1.3.1 Problems and Properties
11(1)
1.3.2 Expressing Algorithms
12(1)
1.3.3 Demonstrating Incorrectness
13(2)
1.4 Induction and Recursion
15(2)
1.5 Modeling the Problem
17(4)
1.5.1 Combinatorial Objects
17(2)
1.5.2 Recursive Objects
19(2)
1.6 Proof by Contradiction
21(1)
1.7 About the War Stories
22(1)
1.8 War Story: Psychic Modeling
22(3)
1.9 Estimation
25(2)
1.10 Exercises
27(4)
2 Algorithm Analysis
31(38)
2.1 The RAM Model of Computation
31(3)
2.1.1 Best-Case, Worst-Case, and Average-Case Complexity
32(2)
2.2 The Big Oh Notation
34(3)
2.3 Growth Rates and Dominance Relations
37(2)
2.3.1 Dominance Relations
38(1)
2.4 Working with the Big Oh
39(2)
2.4.1 Adding Functions
40(1)
2.4.2 Multiplying Functions
40(1)
2.5 Reasoning about Efficiency
41(5)
2.5.1 Selection Sort
41(1)
2.5.2 Insertion Sort
42(1)
2.5.3 String Pattern Matching
43(2)
2.5.4 Matrix Multiplication
45(1)
2.6 Summations
46(2)
2.7 Logarithms and Their Applications
48(4)
2.7.1 Logarithms and Binary Search
49(1)
2.7.2 Logarithms and Trees
49(1)
2.7.3 Logarithms and Bits
50(1)
2.7.4 Logarithms and Multiplication
50(1)
2.7.5 Fast Exponentiation
50(1)
2.7.6 Logarithms and Summations
51(1)
2.7.7 Logarithms and Criminal Justice
51(1)
2.8 Properties of Logarithms
52(2)
2.9 War Story: Mystery of the Pyramids
54(3)
2.10 Advanced Analysis
57(2)
2.10.1 Esoteric Functions
57(1)
2.10.2 Limits and Dominance Relations
58(1)
2.11 Exercises
59(10)
3 Data Structures
69(40)
3.1 Contiguous vs. Linked Data Structures
69(6)
3.1.1 Arrays
70(1)
3.1.2 Pointers and Linked Structures
71(3)
3.1.3 Comparison
74(1)
3.2 Containers: Stacks and Queues
75(1)
3.3 Dictionaries
76(5)
3.4 Binary Search Trees
81(6)
3.4.1 Implementing Binary Search Trees
81(4)
3.4.2 How Good are Binary Search Trees?
85(1)
3.4.3 Balanced Search Trees
86(1)
3.5 Priority Queues
87(2)
3.6 War Story: Stripping Triangulations
89(4)
3.7 Hashing
93(5)
3.7.1 Collision Resolution
93(2)
3.7.2 Duplicate Detection via Hashing
95(1)
3.7.3 Other Hashing Tricks
96(1)
3.7.4 Canonicalization
96(1)
3.7.5 Compaction
97(1)
3.8 Specialized Data Structures
98(1)
3.9 War Story: String 'em Up
98(5)
3.10 Exercises
103(6)
4 Sorting
109(38)
4.1 Applications of Sorting
109(4)
4.2 Pragmatics of Sorting
113(2)
4.3 Heapsort: Fast Sorting via Data Structures
115(10)
4.3.1 Heaps
116(2)
4.3.2 Constructing Heaps
118(2)
4.3.3 Extracting the Minimum
120(2)
4.3.4 Faster Heap Construction
122(2)
4.3.5 Sorting by Incremental Insertion
124(1)
4.4 War Story: Give me a Ticket on an Airplane
125(2)
4.5 Mergesort: Sorting by Divide and Conquer
127(3)
4.6 Quicksort: Sorting by Randomization
130(6)
4.6.1 Intuition: The Expected Case for Quicksort
132(1)
4.6.2 Randomized Algorithms
133(2)
4.6.3 Is Quicksort Really Quick?
135(1)
4.7 Distribution Sort: Sorting via Bucketing
136(2)
4.7.1 Lower Bounds for Sorting
137(1)
4.8 War Story: Skiena for the Defense
138(2)
4.9 Exercises
140(7)
5 Divide and Conquer
147(24)
5.1 Binary Search and Related Algorithms
148(2)
5.1.1 Counting Occurrences
148(1)
5.1.2 One-Sided Binary Search
149(1)
5.1.3 Square and Other Roots
150(1)
5.2 War Story: Finding the Bug in the Bug
150(2)
5.3 Recurrence Relations
152(2)
5.3.1 Divide-and-Conquer Recurrences
153(1)
5.4 Solving Divide-and-Conquer Recurrences
154(1)
5.5 Fast Multiplication
155(2)
5.6 Largest Subrange and Closest Pair
157(2)
5.7 Parallel Algorithms
159(2)
5.7.1 Data Parallelism
159(1)
5.7.2 Pitfalls of Parallelism
160(1)
5.8 War Story: Going Nowhere Fast
161(1)
5.9 Convolution
162(4)
5.9.1 Applications of Convolution
163(1)
5.9.2 Fast Polynomial Multiplication
164(2)
5.10 Exercises
166(5)
6 Hashing and Randomized Algorithms
171(26)
6.1 Probability Review
172(7)
6.1.1 Probability
172(2)
6.1.2 Compound Events and Independence
174(1)
6.1.3 Conditional Probability
175(1)
6.1.4 Probability Distributions
176(1)
6.1.5 Mean and Variance
176(1)
6.1.6 Tossing Coins
177(2)
6.2 Understanding Balls and Bins
179(2)
6.2.1 The Coupon Collector's Problem
180(1)
6.3 Why is Hashing a Randomized Algorithm?
181(1)
6.4 Bloom Filters
182(2)
6.5 The Birthday Paradox and Perfect Hashing
184(2)
6.6 Minwise Hashing
186(2)
6.7 Efficient String Matching
188(2)
6.8 Primality Testing
190(1)
6.9 War Story: Giving Knuth the Middle Initial
191(1)
6.10 Where do Random Numbers Come From?
192(1)
6.11 Exercises
193(4)
7 Graph Traversal
197(46)
7.1 Flavors of Graphs
198(5)
7.1.1 The Friendship Graph
201(2)
7.2 Data Structures for Graphs
203(4)
7.3 War Story: I was a Victim of Moore's Law
207(3)
7.4 War Story: Getting the Graph
210(2)
7.5 Traversing a Graph
212(1)
7.6 Breadth-First Search
213(4)
7.6.1 Exploiting Traversal
216(1)
7.6.2 Finding Paths
217(1)
7.7 Applications of Breadth-First Search
217(4)
7.7.1 Connected Components
218(1)
7.7.2 Two-Coloring Graphs
219(2)
7.8 Depth-First Search
221(3)
7.9 Applications of Depth-First Search
224(6)
7.9.1 Finding Cycles
224(1)
7.9.2 Articulation Vertices
225(5)
7.10 Depth-First Search on Directed Graphs
230(5)
7.10.1 Topological Sorting
231(1)
7.10.2 Strongly Connected Components
232(3)
7.11 Exercises
235(8)
8 Weighted Graph Algorithms
243(38)
8.1 Minimum Spanning Trees
244(10)
8.1.1 Prim's Algorithm
245(3)
8.1.2 Kruskal's Algorithm
248(2)
8.1.3 The Union-Find Data Structure
250(3)
8.1.4 Variations on Minimum Spanning Trees
253(1)
8.2 War Story: Nothing but Nets
254(3)
8.3 Shortest Paths
257(7)
8.3.1 Dijkstra's Algorithm
258(3)
8.3.2 All-Pairs Shortest Path
261(2)
8.3.3 Transitive Closure
263(1)
8.4 War Story: Dialing for Documents
264(3)
8.5 Network Flows and Bipartite Matching
267(5)
8.5.1 Bipartite Matching
267(1)
8.5.2 Computing Network Flows
268(4)
8.6 Randomized Min-Cut
272(2)
8.7 Design Graphs, Not Algorithms
274(2)
8.8 Exercises
276(5)
9 Combinatorial Search
281(26)
9.1 Backtracking
281(3)
9.2 Examples of Backtracking
284(5)
9.2.1 Constructing All Subsets
284(2)
9.2.2 Constructing All Permutations
286(1)
9.2.3 Constructing All Paths in a Graph
287(2)
9.3 Search Pruning
289(1)
9.4 Sudoku
290(5)
9.5 War Story: Covering Chessboards
295(3)
9.6 Best-First Search
298(2)
9.7 The A* Heuristic
300(3)
9.8 Exercises
303(4)
10 Dynamic Programming
307(48)
10.1 Caching vs. Computation
308(6)
10.1.1 Fibonacci Numbers by Recursion
308(1)
10.1.2 Fibonacci Numbers by Caching
309(2)
10.1.3 Fibonacci Numbers by Dynamic Programming
311(1)
10.1.4 Binomial Coefficients
312(2)
10.2 Approximate String Matching
314(10)
10.2.1 Edit Distance by Recursion
315(2)
10.2.2 Edit Distance by Dynamic Programming
317(1)
10.2.3 Reconstructing the Path
318(3)
10.2.4 Varieties of Edit Distance
321(3)
10.3 Longest Increasing Subsequence
324(2)
10.4 War Story: Text Compression for Bar Codes
326(3)
10.5 Unordered Partition or Subset Sum
329(2)
10.6 War Story: The Balance of Power
331(2)
10.7 The Ordered Partition Problem
333(4)
10.8 Parsing Context-Free Grammars
337(2)
10.9 Limitations of Dynamic Programming: TSP
339(3)
10.9.1 When is Dynamic Programming Correct?
340(1)
10.9.2 When is Dynamic Programming Efficient?
341(1)
10.10 War Story: What's Past is Prolog
342(3)
10.11 Exercises
345(10)
11 NP-Completeness
355(34)
11.1 Problems and Reductions
355(3)
11.1.1 The Key Idea
356(1)
11.1.2 Decision Problems
357(1)
11.2 Reductions for Algorithms
358(3)
11.2.1 Closest Pair
358(1)
11.2.2 Longest Increasing Subsequence
359(1)
11.2.3 Least Common Multiple
359(1)
11.2.4 Convex Hull
360(1)
11.3 Elementary Hardness Reductions
361(6)
11.3.1 Hamiltonian Cycle
362(1)
11.3.2 Independent Set and Vertex Cover
363(3)
11.3.3 Clique
366(1)
11.4 Satisfiability
367(2)
11.4.1 3-Satisfiability
367(2)
11.5 Creative Reductions from SAT
369(4)
11.5.1 Vertex Cover
369(2)
11.5.2 Integer Programming
371(2)
11.6 The Art of Proving Hardness
373(2)
11.7 War Story: Hard Against the Clock
375(2)
11.8 War Story: And Then I Failed
377(2)
11.9 P vs. NP
379(4)
11.9.1 Verification vs. Discovery
380(1)
11.9.2 The Classes P and NP
380(1)
11.9.3 Why Satisfiability is Hard
381(1)
11.9.4 NP-hard vs. NP-complete?
382(1)
11.10 Exercises
383(6)
12 Dealing with Hard Problems
389(40)
12.1 Approximation Algorithms
389(1)
12.2 Approximating Vertex Cover
390(3)
12.2.1 A Randomized Vertex Cover Heuristic
392(1)
12.3 Euclidean TSP
393(3)
12.3.1 The Christofides Heuristic
394(2)
12.4 When Average is Good Enough
396(1)
12.4.1 Maximum k-SAT
396(1)
12.4.2 Maximum Acyclic Subgraph
397(1)
12.5 Set Cover
397(2)
12.6 Heuristic Search Methods
399(12)
12.6.1 Random Sampling
400(2)
12.6.2 Local Search
402(4)
12.6.3 Simulated Annealing
406(4)
12.6.4 Applications of Simulated Annealing
410(1)
12.7 War Story: Only it is Not a Radio
411(3)
12.8 War Story: Annealing Arrays
414(3)
12.9 Genetic Algorithms and Other Heuristics
417(1)
12.10 Quantum Computing
418(8)
12.10.1 Properties of "Quantum" Computers
419(1)
12.10.2 Grover's Algorithm for Database Search
420(2)
12.10.3 The Faster "Fourier Transform"
422(1)
12.10.4 Shor's Algorithm for Integer Factorization
422(2)
12.10.5 Prospects for Quantum Computing
424(2)
12.11 Exercises
426(3)
13 How to Design Algorithms
429(6)
13.1 Preparing for Tech Company Interviews
433(2)
II The Hitchhiker's Guide to Algorithms 435(334)
14 A Catalog of Algorithmic Problems
437(2)
15 Data Structures
439(26)
15.1 Dictionaries
440(5)
15.2 Priority Queues
445(3)
15.3 Suffix Trees and Arrays
448(4)
15.4 Graph Data Structures
452(4)
15.5 Set Data Structures
456(4)
15.6 Kd-Trees
460(5)
16 Numerical Problems
465(40)
16.1 Solving Linear Equations
467(3)
16.2 Bandwidth Reduction
470(2)
16.3 Matrix Multiplication
472(3)
16.4 Determinants and Permanents
475(3)
16.5 Constrained/Unconstrained Optimization
478(4)
16.6 Linear Programming
482(4)
16.7 Random Number Generation
486(4)
16.8 Factoring and Primality Testing
490(3)
16.9 Arbitrary-Precision Arithmetic
493(4)
16.10 Knapsack Problem
497(4)
16.11 Discrete Fourier Transform
501(4)
17 Combinatorial Problems
505(36)
17.1 Sorting
506(4)
17.2 Searching
510(4)
17.3 Median and Selection
514(3)
17.4 Generating Permutations
517(4)
17.5 Generating Subsets
521(3)
17.6 Generating Partitions
524(4)
17.7 Generating Graphs
528(4)
17.8 Calendrical Calculations
532(2)
17.9 Job Scheduling
534(3)
17.10 Satisfiability
537(4)
18 Graph Problems: Polynomial Time
541(44)
18.1 Connected Components
542(4)
18.2 Topological Sorting
546(3)
18.3 Minimum Spanning Tree
549(5)
18.4 Shortest Path
554(5)
18.5 Transitive Closure and Reduction
559(3)
18.6 Matching
562(3)
18.7 Eulerian Cycle/Chinese Postman
565(3)
18.8 Edge and Vertex Connectivity
568(3)
18.9 Network Flow
571(3)
18.10 Drawing Graphs Nicely
574(4)
18.11 Drawing Trees
578(3)
18.12 Planarity Detection and Embedding
581(4)
19 Graph Problems: NP-Hard
585(36)
19.1 Clique
586(3)
19.2 Independent Set
589(2)
19.3 Vertex Cover
591(3)
19.4 Traveling Salesman Problem
594(4)
19.5 Hamiltonian Cycle
598(3)
19.6 Graph Partition
601(3)
19.7 Vertex Coloring
604(4)
19.8 Edge Coloring
608(2)
19.9 Graph Isomorphism
610(4)
19.10 Steiner Tree
614(4)
19.11 Feedback Edge/Vertex Set
618(3)
20 Computational Geometry
621(56)
20.1 Robust Geometric Primitives
622(4)
20.2 Convex Hull
626(4)
20.3 Triangulation
630(4)
20.4 Voronoi Diagrams
634(3)
20.5 Nearest-Neighbor Search
637(4)
20.6 Range Search
641(3)
20.7 Point Location
644(4)
20.8 Intersection Detection
648(4)
20.9 Bin Packing
652(3)
20.10 Medial-Axis Transform
655(3)
20.11 Polygon Partitioning
658(3)
20.12 Simplifying Polygons
661(3)
20.13 Shape Similarity
664(3)
20.14 Motion Planning
667(4)
20.15 Maintaining Line Arrangements
671(3)
20.16 Minkowski Sum
674(3)
21 Set and String Problems
677(36)
21.1 Set Cover
678(4)
21.2 Set Packing
682(3)
21.3 String Matching
685(3)
21.4 Approximate String Matching
688(5)
21.5 Text Compression
693(4)
21.6 Cryptography
697(5)
21.7 Finite State Machine Minimization
702(4)
21.8 Longest Common Substring/Subsequence
706(3)
21.9 Shortest Common Superstring
709(4)
22 Algorithmic Resources
713(6)
22.1 Algorithm Libraries
713(4)
22.1.1 LEDA
713(1)
22.1.2 CGAL
714(1)
22.1.3 Boost Graph Library
714(1)
22.1.4 Netlib
714(1)
22.1.5 Collected Algorithms of the ACM
715(1)
22.1.6 GitHub and SourceForge
715(1)
22.1.7 The Stanford GraphBase
715(1)
22.1.8 Combinatorica
716(1)
22.1.9 Programs from Books
716(1)
22.2 Data Sources
717(1)
22.3 Online Bibliographic Resources
718(1)
22.4 Professional Consulting Services
718(1)
23 Bibliography
719(50)
Index 769
Dr. Steven S. Skiena is Distinguished Teaching Professor of Computer Science at Stony Brook University, with research interests in data science, natural language processing, and algorithms. He was awarded the IEEE Computer Science and Engineering Undergraduate Teaching Award for outstanding contributions to undergraduate education ...and for influential textbooks and software.