Michael T. (Johns Hopkins University) Goodrich,
MY Goodrich,
Roberto (Brown University) Tamassia
Algorithm Design and Applications
Gebonden Engels 2014 9781118335918
Verwachte levertijd ongeveer 9 werkdagen
Samenvatting
Introducing a NEW addition to our growing library of computer science titles, Algorithm Design and Applications, by Michael T. Goodrich & Roberto Tamassia! Algorithms is a course required for all computer science majors, with a strong focus on theoretical topics. Students enter the course after gaining hands–on experience with computers, and are expected to learn how algorithms can be applied to a variety of contexts. This new book integrates application with theory.
Goodrich & Tamassia believe that the best way to teach algorithmic topics is to present them in a context that is motivated from applications to uses in society, computer games, computing industry, science, engineering, and the internet. The text teaches students about designing and using algorithms, illustrating connections between topics being taught and their potential applications, increasing engagement.
Specificaties
ISBN13:9781118335918
Taal:Engels
Bindwijze:gebonden
Aantal pagina's:800
Uitgever:John Wiley & Sons
Hoofdrubriek:Programmeren, Computer en informatica
Lezersrecensies
Wees de eerste die een lezersrecensie schrijft!
Inhoudsopgave
<p>Preface xi</p>
<p>1 AlgorithmAnalysis 1</p>
<p>1.1 Analyzing Algorithms 3</p>
<p>1.2 A Quick Mathematical Review 19</p>
<p>1.3 A Case Study in Algorithm Analysis 29</p>
<p>1.4 Amortization 34</p>
<p>1.5 Exercises 42</p>
<p>Part I: Data Structures</p>
<p>2 BasicDataStructures 51</p>
<p>2.1 Stacks and Queues 53</p>
<p>2.2 Lists 60</p>
<p>2.3 Trees 68</p>
<p>2.4 Exercises 84</p>
<p>3 BinarySearchTrees 89</p>
<p>3.1 Searches and Updates 91</p>
<p>3.2 Range Queries 101</p>
<p>3.3 Index–Based Searching 104</p>
<p>3.4 Randomly–Constructed Search Trees 107</p>
<p>3.5 Exercises 110</p>
<p>4 BalancedBinarySearchTrees 115</p>
<p>4.1 Ranks and Rotations 117</p>
<p>4.2 AVL Trees 120</p>
<p>4.3 Red–Black Trees 126</p>
<p>4.4 Weak AVL Trees 130</p>
<p>4.5 Splay Trees 139</p>
<p>4.6 Exercises 149</p>
<p>5 PriorityQueuesandHeaps 155</p>
<p>5.1 Priority Queues 157</p>
<p>5.2 PQ–Sort, Selection–Sort, and Insertion–Sort 158</p>
<p>5.3 Heaps 163</p>
<p>5.4 Heap–Sort 174</p>
<p>5.5 Extending Priority Queues 179</p>
<p>5.6 Exercises 182</p>
<p>6 HashTables 187</p>
<p>6.1 Maps 189</p>
<p>6.2 Hash Functions 192</p>
<p>6.3 Handling Collisions and Rehashing 198</p>
<p>6.4 Cuckoo Hashing 206</p>
<p>6.5 Universal Hashing 212</p>
<p>6.6 Exercises 215</p>
<p>7 Union–FindStructures 219</p>
<p>7.1 Union–Find and its Applications 221</p>
<p>7.2 A List–Based Implementation 225</p>
<p>7.3 A Tree–Based Implementation 228</p>
<p>7.4 Exercises 236</p>
<p>Part II: Sorting and Selection</p>
<p>8 Merge–SortandQuick–Sort 241</p>
<p>8.1 Merge–Sort 243</p>
<p>8.2 Quick–Sort 250</p>
<p>8.3 A Lower Bound on Comparison–Based Sorting 257</p>
<p>8.4 Exercises 259</p>
<p>9 FastSortingandSelection 265</p>
<p>9.1 Bucket Sort and Radix Sort 267</p>
<p>9.2 Selection 270</p>
<p>9.3 Weighted Medians 276</p>
<p>9.4 Exercises 279</p>
<p>Part III: Fundamental Techniques</p>
<p>10 The Greedy Method 283</p>
<p>10.1 The Fractional Knapsack Problem 286</p>
<p>10.2 Task Scheduling 289</p>
<p>10.3 Text Compression and Huffman Coding 292</p>
<p>10.4 Exercises 298</p>
<p>11 Divide–and–Conquer 303</p>
<p>11.1 Recurrences and the Master Theorem 305</p>
<p>11.2 Integer Multiplication 313</p>
<p>11.3 Matrix Multiplication 315</p>
<p>11.4 The Maxima–Set Problem 317</p>
<p>11.5 Exercises 319</p>
<p>12 Dynamic Programming 323</p>
<p>12.1 Matrix Chain–Products 325</p>
<p>12.2 The General Technique 329</p>
<p>12.3 Telescope Scheduling 331</p>
<p>12.4 Game Strategies 334</p>
<p>12.5 The Longest Common Subsequence Problem 339</p>
<p>12.6 The 0–1 Knapsack Problem 343</p>
<p>12.7 Exercises 346</p>
<p>Part IV: Graph Algorithms</p>
<p>13 Graphs and Traversals 353</p>
<p>13.1 Graph Terminology and Representations 355</p>
<p>13.2 Depth–First Search 365</p>
<p>13.3 Breadth–First Search 370</p>
<p>13.4 Directed Graphs 373</p>
<p>13.5 Biconnected Components 386</p>
<p>13.6 Exercises 392</p>
<p>14 Shortest Paths 397</p>
<p>14.1 Single–Source Shortest Paths 399</p>
<p>14.2 Dijkstra s Algorithm 400</p>
<p>14.3 The Bellman–Ford Algorithm 407</p>
<p>14.4 Shortest Paths in Directed Acyclic Graphs 410</p>
<p>14.5 All–Pairs Shortest Paths 412</p>
<p>14.6 Exercises 418</p>
<p>15 Minimum Spanning Trees 423</p>
<p>15.1 Properties of Minimum Spanning Trees 425</p>
<p>15.2 Kruskal s Algorithm 428</p>
<p>15.3 The Prim–Jarn´ýk Algorithm 433</p>
<p>15.4 Bar°uvka s Algorithm 436</p>
<p>15.5 Exercises 439</p>
<p>16 Network Flow and Matching 443</p>
<p>16.1 Flows and Cuts 445</p>
<p>16.2 Maximum Flow Algorithms 452</p>
<p>16.3 Maximum Bipartite Matching 458</p>
<p>16.4 Baseball Elimination 460</p>
<p>16.5 Minimum–Cost Flow 462</p>
<p>16.6 Exercises 469</p>
<p>Part V: Computational Intractability</p>
<p>17 NP–Completeness 473</p>
<p>17.1 P and NP 476</p>
<p>17.2 NP–Completeness 483</p>
<p>17.3 CNF–SAT and 3SAT 489</p>
<p>17.4 VERTEX–COVER, CLIQUE, and SET–COVER 492</p>
<p>17.5 SUBSET–SUM and KNAPSACK 496</p>
<p>17.6 HAMILTONIAN–CYCLE and TSP 499</p>
<p>17.7 Exercises 502</p>
<p>18 Approximation Algorithms 507</p>
<p>18.1 The Metric Traveling Salesperson Problem 511</p>
<p>18.2 Approximations for Covering Problems 515</p>
<p>18.3 Polynomial–Time Approximation Schemes 518</p>
<p>18.4 Backtracking and Branch–and–Bound 521</p>
<p>18.5 Exercises 525</p>
<p>Part VI: Additional Topics</p>
<p>19 Randomized Algorithms 529</p>
<p>19.1 Generating Random Permutations 531</p>
<p>19.2 Stable Marriages and Coupon Collecting 534</p>
<p>19.3 Minimum Cuts 539</p>
<p>19.4 Finding Prime Numbers 546</p>
<p>19.5 Chernoff Bounds 551</p>
<p>19.6 Skip Lists 557</p>
<p>19.7 Exercises 563</p>
<p>20 B–Trees and External–Memory 569</p>
<p>20.1 External Memory 571</p>
<p>20.2 (2,4) Trees and B–Trees 574</p>
<p>20.3 External–Memory Sorting 590</p>
<p>20.4 Online Caching Algorithms 593</p>
<p>20.5 Exercises 600</p>
<p>21 Multi–Dimensional Searching 603</p>
<p>21.1 Range Trees 605</p>
<p>21.2 Priority Search Trees 609</p>
<p>21.3 Quadtrees and k–D Trees 614</p>
<p>21.4 Exercises 618</p>
<p>22 Computational Geometry 623</p>
<p>22.1 Operations on Geometric Objects 625</p>
<p>22.2 Convex Hulls 630</p>
<p>22.3 Segment Intersection 638</p>
<p>22.4 Finding a Closest Pair of Points 642</p>
<p>22.5 Exercises 646</p>
<p>23 String Algorithms 651</p>
<p>23.1 String Operations 653</p>
<p>23.2 The Boyer–Moore Algorithm 656</p>
<p>23.3 The Knuth–Morris–Pratt Algorithm 660</p>
<p>23.4 Hash–Based Lexicon Matching 664</p>
<p>23.5 Tries 669</p>
<p>23.6 Exercises 680</p>
<p>24 Cryptography 685</p>
<p>24.1 Greatest Common Divisors (GCD) 687</p>
<p>24.2 Modular Arithmetic 691</p>
<p>24.3 Cryptographic Operations 699</p>
<p>24.4 The RSA Cryptosystem 703</p>
<p>24.5 The El Gamal Cryptosystem 706</p>
<p>24.6 Exercises 708</p>
<p>25 The Fast Fourier Transform 711</p>
<p>25.1 Convolution 713</p>
<p>25.2 Primitive Roots of Unity 715</p>
<p>25.3 The Discrete Fourier Transform 717</p>
<p>25.4 The Fast Fourier Transform Algorithm 721</p>
<p>25.5 Exercises 727</p>
<p>26 Linear Programming 731</p>
<p>26.1 Formulating the Problem 734</p>
<p>26.2 The Simplex Method 739</p>
<p>26.3 Duality 746</p>
<p>26.4 Applications of Linear Programming 750</p>
<p>26.5 Exercises 753</p>
<p>A UsefulMathematicalFacts 761</p>
<p>Bibliography 765</p>
<p>Index 774</p>
<p>1 AlgorithmAnalysis 1</p>
<p>1.1 Analyzing Algorithms 3</p>
<p>1.2 A Quick Mathematical Review 19</p>
<p>1.3 A Case Study in Algorithm Analysis 29</p>
<p>1.4 Amortization 34</p>
<p>1.5 Exercises 42</p>
<p>Part I: Data Structures</p>
<p>2 BasicDataStructures 51</p>
<p>2.1 Stacks and Queues 53</p>
<p>2.2 Lists 60</p>
<p>2.3 Trees 68</p>
<p>2.4 Exercises 84</p>
<p>3 BinarySearchTrees 89</p>
<p>3.1 Searches and Updates 91</p>
<p>3.2 Range Queries 101</p>
<p>3.3 Index–Based Searching 104</p>
<p>3.4 Randomly–Constructed Search Trees 107</p>
<p>3.5 Exercises 110</p>
<p>4 BalancedBinarySearchTrees 115</p>
<p>4.1 Ranks and Rotations 117</p>
<p>4.2 AVL Trees 120</p>
<p>4.3 Red–Black Trees 126</p>
<p>4.4 Weak AVL Trees 130</p>
<p>4.5 Splay Trees 139</p>
<p>4.6 Exercises 149</p>
<p>5 PriorityQueuesandHeaps 155</p>
<p>5.1 Priority Queues 157</p>
<p>5.2 PQ–Sort, Selection–Sort, and Insertion–Sort 158</p>
<p>5.3 Heaps 163</p>
<p>5.4 Heap–Sort 174</p>
<p>5.5 Extending Priority Queues 179</p>
<p>5.6 Exercises 182</p>
<p>6 HashTables 187</p>
<p>6.1 Maps 189</p>
<p>6.2 Hash Functions 192</p>
<p>6.3 Handling Collisions and Rehashing 198</p>
<p>6.4 Cuckoo Hashing 206</p>
<p>6.5 Universal Hashing 212</p>
<p>6.6 Exercises 215</p>
<p>7 Union–FindStructures 219</p>
<p>7.1 Union–Find and its Applications 221</p>
<p>7.2 A List–Based Implementation 225</p>
<p>7.3 A Tree–Based Implementation 228</p>
<p>7.4 Exercises 236</p>
<p>Part II: Sorting and Selection</p>
<p>8 Merge–SortandQuick–Sort 241</p>
<p>8.1 Merge–Sort 243</p>
<p>8.2 Quick–Sort 250</p>
<p>8.3 A Lower Bound on Comparison–Based Sorting 257</p>
<p>8.4 Exercises 259</p>
<p>9 FastSortingandSelection 265</p>
<p>9.1 Bucket Sort and Radix Sort 267</p>
<p>9.2 Selection 270</p>
<p>9.3 Weighted Medians 276</p>
<p>9.4 Exercises 279</p>
<p>Part III: Fundamental Techniques</p>
<p>10 The Greedy Method 283</p>
<p>10.1 The Fractional Knapsack Problem 286</p>
<p>10.2 Task Scheduling 289</p>
<p>10.3 Text Compression and Huffman Coding 292</p>
<p>10.4 Exercises 298</p>
<p>11 Divide–and–Conquer 303</p>
<p>11.1 Recurrences and the Master Theorem 305</p>
<p>11.2 Integer Multiplication 313</p>
<p>11.3 Matrix Multiplication 315</p>
<p>11.4 The Maxima–Set Problem 317</p>
<p>11.5 Exercises 319</p>
<p>12 Dynamic Programming 323</p>
<p>12.1 Matrix Chain–Products 325</p>
<p>12.2 The General Technique 329</p>
<p>12.3 Telescope Scheduling 331</p>
<p>12.4 Game Strategies 334</p>
<p>12.5 The Longest Common Subsequence Problem 339</p>
<p>12.6 The 0–1 Knapsack Problem 343</p>
<p>12.7 Exercises 346</p>
<p>Part IV: Graph Algorithms</p>
<p>13 Graphs and Traversals 353</p>
<p>13.1 Graph Terminology and Representations 355</p>
<p>13.2 Depth–First Search 365</p>
<p>13.3 Breadth–First Search 370</p>
<p>13.4 Directed Graphs 373</p>
<p>13.5 Biconnected Components 386</p>
<p>13.6 Exercises 392</p>
<p>14 Shortest Paths 397</p>
<p>14.1 Single–Source Shortest Paths 399</p>
<p>14.2 Dijkstra s Algorithm 400</p>
<p>14.3 The Bellman–Ford Algorithm 407</p>
<p>14.4 Shortest Paths in Directed Acyclic Graphs 410</p>
<p>14.5 All–Pairs Shortest Paths 412</p>
<p>14.6 Exercises 418</p>
<p>15 Minimum Spanning Trees 423</p>
<p>15.1 Properties of Minimum Spanning Trees 425</p>
<p>15.2 Kruskal s Algorithm 428</p>
<p>15.3 The Prim–Jarn´ýk Algorithm 433</p>
<p>15.4 Bar°uvka s Algorithm 436</p>
<p>15.5 Exercises 439</p>
<p>16 Network Flow and Matching 443</p>
<p>16.1 Flows and Cuts 445</p>
<p>16.2 Maximum Flow Algorithms 452</p>
<p>16.3 Maximum Bipartite Matching 458</p>
<p>16.4 Baseball Elimination 460</p>
<p>16.5 Minimum–Cost Flow 462</p>
<p>16.6 Exercises 469</p>
<p>Part V: Computational Intractability</p>
<p>17 NP–Completeness 473</p>
<p>17.1 P and NP 476</p>
<p>17.2 NP–Completeness 483</p>
<p>17.3 CNF–SAT and 3SAT 489</p>
<p>17.4 VERTEX–COVER, CLIQUE, and SET–COVER 492</p>
<p>17.5 SUBSET–SUM and KNAPSACK 496</p>
<p>17.6 HAMILTONIAN–CYCLE and TSP 499</p>
<p>17.7 Exercises 502</p>
<p>18 Approximation Algorithms 507</p>
<p>18.1 The Metric Traveling Salesperson Problem 511</p>
<p>18.2 Approximations for Covering Problems 515</p>
<p>18.3 Polynomial–Time Approximation Schemes 518</p>
<p>18.4 Backtracking and Branch–and–Bound 521</p>
<p>18.5 Exercises 525</p>
<p>Part VI: Additional Topics</p>
<p>19 Randomized Algorithms 529</p>
<p>19.1 Generating Random Permutations 531</p>
<p>19.2 Stable Marriages and Coupon Collecting 534</p>
<p>19.3 Minimum Cuts 539</p>
<p>19.4 Finding Prime Numbers 546</p>
<p>19.5 Chernoff Bounds 551</p>
<p>19.6 Skip Lists 557</p>
<p>19.7 Exercises 563</p>
<p>20 B–Trees and External–Memory 569</p>
<p>20.1 External Memory 571</p>
<p>20.2 (2,4) Trees and B–Trees 574</p>
<p>20.3 External–Memory Sorting 590</p>
<p>20.4 Online Caching Algorithms 593</p>
<p>20.5 Exercises 600</p>
<p>21 Multi–Dimensional Searching 603</p>
<p>21.1 Range Trees 605</p>
<p>21.2 Priority Search Trees 609</p>
<p>21.3 Quadtrees and k–D Trees 614</p>
<p>21.4 Exercises 618</p>
<p>22 Computational Geometry 623</p>
<p>22.1 Operations on Geometric Objects 625</p>
<p>22.2 Convex Hulls 630</p>
<p>22.3 Segment Intersection 638</p>
<p>22.4 Finding a Closest Pair of Points 642</p>
<p>22.5 Exercises 646</p>
<p>23 String Algorithms 651</p>
<p>23.1 String Operations 653</p>
<p>23.2 The Boyer–Moore Algorithm 656</p>
<p>23.3 The Knuth–Morris–Pratt Algorithm 660</p>
<p>23.4 Hash–Based Lexicon Matching 664</p>
<p>23.5 Tries 669</p>
<p>23.6 Exercises 680</p>
<p>24 Cryptography 685</p>
<p>24.1 Greatest Common Divisors (GCD) 687</p>
<p>24.2 Modular Arithmetic 691</p>
<p>24.3 Cryptographic Operations 699</p>
<p>24.4 The RSA Cryptosystem 703</p>
<p>24.5 The El Gamal Cryptosystem 706</p>
<p>24.6 Exercises 708</p>
<p>25 The Fast Fourier Transform 711</p>
<p>25.1 Convolution 713</p>
<p>25.2 Primitive Roots of Unity 715</p>
<p>25.3 The Discrete Fourier Transform 717</p>
<p>25.4 The Fast Fourier Transform Algorithm 721</p>
<p>25.5 Exercises 727</p>
<p>26 Linear Programming 731</p>
<p>26.1 Formulating the Problem 734</p>
<p>26.2 The Simplex Method 739</p>
<p>26.3 Duality 746</p>
<p>26.4 Applications of Linear Programming 750</p>
<p>26.5 Exercises 753</p>
<p>A UsefulMathematicalFacts 761</p>
<p>Bibliography 765</p>
<p>Index 774</p>
Rubrieken
- advisering
- algemeen management
- coaching en trainen
- communicatie en media
- economie
- financieel management
- inkoop en logistiek
- internet en social media
- it-management / ict
- juridisch
- leiderschap
- marketing
- mens en maatschappij
- non-profit
- ondernemen
- organisatiekunde
- personal finance
- personeelsmanagement
- persoonlijke effectiviteit
- projectmanagement
- psychologie
- reclame en verkoop
- strategisch management
- verandermanagement
- werk en loopbaan