本书是Sedgewick彻底修订和重写的丛书中的第二本，集中讲解图算法。全书共有6章（第17-22章）。第17章详细讨论图性质和类型，第18-22章分别讲解图搜索、有向图和DAG、最小生成树、最短路径以及网络流。 　　书中提供了用C语言描述的完整算法源程序，并且配有丰富插图和练习。作者用简洁的实现将理论和实践成功地结合了起来，这些实现均可在真实应用上测试，使得本书自问世以来备受程序员的欢迎。 本书可作为高等院校计算机相关专业算法与数据结构课程的教材和补充读物，也可供自学之用。

"This is an eminently readable book which an ordinary programmer, unskilled in mathematical analysis and wary of theoretical algorithms, ought to be able to pick up and get a lot out of.." - Steve Summit, author of C Programming FAQs Sedgewick has a real gift for explaining concepts in a way that makes them easy to understand. The use of real programs in page-size (or less) chunks that can be easily understood is a real plus. The figures, programs, and tables are a significant contribution to the learning experience of the reader; they make this book distinctive. - William A. Ward, University of South Alabama Robert Sedgewick has thoroughly rewritten and substantially expanded his popular work to provide current and comprehensive coverage of important algorithms and data structures. Many new algorithms are presented, and the explanations of each algorithm are much more detailed than in previous editions. A new text design and detailed, innovative figures, with accompanying commentary, greatly enhance the presentation. The third edition retains the successful blend of theory and practice that has made Sedgewick's work an invaluable resource for more than 250,000 programmers! This particular book, Parts 1-4, represents the essential first half of Sedgewick's complete work. It provides extensive coverage of fundamental data structures and algorithms for sorting, searching, and related applications. The algorithms and data structures are expressed in concise implementations in C, so that you can both appreciate their fundamental properties and test them on real applications. Of course, the substance of the book applies to programming in any language. Highlights * Expanded coverage of arrays, linked lists, strings, trees, and other basic data structures * Greater emphasis on abstract data types (ADTs) than in previous editions * Over 100 algorithms for sorting, selection, priority queue ADT implementations, and symbol table ADT (searching) implementations * New implementations of binomial queues, multiway radix sorting, Batcher's sorting networks, randomized BSTs, splay trees, skip lists, multiway tries, and much more * Increased quantitative information about the algorithms, including extensive empirical studies and basic analytic studies, giving you a basis for comparing them * Over 1000 new exercises to help you learn the properties of algorithms Whether you are a student learning the algorithms for the first time or a professional interested in having up-to-date reference material, you will find a wealth of useful information in this book.

《算法竞赛入门经典:训练指南》是《算法竞赛入门经典》的重要补充，旨在补充原书中没有涉及或者讲解得不够详细的内容，从而构建一个较完整的知识体系，并且用大量有针对性的题目，让抽象复杂的算法和数学具体化、实用化。《算法竞赛入门经典:训练指南》共6章，分别为算法设计基础、数学基础、实用数据结构、几何问题、图论算法与模型和更多算法专题，全书通过近200道例题深入浅出地介绍了上述领域的各个知识点、经典思维方式以及程序实现的常见方法和技巧，并在章末和附录中给出了丰富的分类习题，供读者查漏补缺和强化学习效果。

Dive into Python's advanced possibilities, including algorithm analysis, graphs, scale-free networks, and cellular automata with this in-depth, hands-on guide. Whether you're an intermediate-level Python programmer, or a student of computational modeling, you'll examine data structures, complexity science, and other fascinating topics through a series of exercises, easy-to-understand explanations, and case studies. Think Complexity presents features that make Python such a simple and powerful language. Author Allen Downey provides code to help you get started, along with a solution for each exercise. With this book, you will: Work with graphs and graph algorithms, NumPy arrays and SciPy methods, basic signal processing and Fast Fourier Transform, and hash tables. Discover complexity science, the field that studies abstract models of complex physical systems, including power laws, fractals and pink noise, and Turing machines. Explore the philosophy of science through the models and results in this book about the nature of scientific laws, theory choice, and realism and instrumentalism, and more.

HOW TO THINK ABOUT ALGORITHMS There are many algorithm texts that provide lots of well-polished code and proofs of correctness. Instead, this one presents insights, notations, and analogies to help the novice describe and think about algorithms like an expert. It is a bit like a carpenter studying hammers instead of houses. Jeff Edmonds provides both the big picture and easy step-by-step methods for developing algorithms, while avoiding the comon pitfalls. Paradigms such as loop invariants and recursion help to unify a huge range of algorithms into a few meta-algorithms. Part of the goal is to teach students to think abstractly. Without getting bogged down in formal proofs, the book fosters deeper understanding so that how and why each algorithm works is trans- parent. These insights are presented in a slow and clear manner accessible to second- or third-year students of computer science, preparing them to find on their own innovative ways to solve problems. Abstraction is when you translate the equations, the rules, and the under- lying essences of the problem not only into a language that can be commu- nicated to your friend standing with you on a streetcar, but also into a form that can percolate down and dwell in your subconscious. Because, remem- ber, it is your subconscious that makes the miraculous leaps of inspiration, not your plodding perspiration and not your cocky logic. And remember, unlike you, your subconscious does not understand Java code. Bookmarks Cover Half-title Title Copyright CONTENTS PREFACE Introduction PART ONE: Iterative Algorithms and Loop Invariants 1 Iterative Algorithms: Measures of Progress and Loop Invariants 1.1 A Paradigm Shift: A Sequence of Actions vs. a Sequence of Assertions 1.2 The Steps to Develop an Iterative Algorithm 1.3 More about the Steps 1.4 Different Types of Iterative Algorithms 1.5 Typical Errors 1.6 Exercises 2 Examples Using More-of-the-Input Loop Invariants 2.1 Coloring the Plane 2.2 Deterministic Finite Automaton 2.3 More of the Input vs. More of the Output 3 Abstract Data Types 3.1 Specifications and Hints at Implementations 3.2 Link List Implementation 3.3 Merging with a Queue 3.4 Parsing with a Stack 4 Narrowing the Search Space: Binary Search 4.1 Binary Search Trees 4.2 Magic Sevens 4.3 VLSI Chip Testing 4.4 Exercises 5 Iterative Sorting Algorithms 5.1 Bucket Sort by Hand 5.2 Counting Sort (a Stable Sort) 5.3 Radix Sort 5.4 Radix Counting Sort 6 Euclid’s GCD Algorithm 7 The Loop Invariant for Lower Bounds PART TWO: Recursion 8 Abstractions, Techniques, and Theory 8.1 Thinking about Recursion 8.2 Looking Forward vs. Backward 8.3 With a Little Help from Your Friends 8.4 The Towers of Hanoi 8.5 Checklist for Recursive Algorithms 8.6 The Stack Frame 8.7 Proving Correctness with Strong Induction 9 Some Simple Examples of Recursive Algorithms 9.1 Sorting and Selecting Algorithms 9.2 Operations on Integers 9.3 Ackermann's Function 9.4 Exercises 10 Recursion on Trees 10.1 Tree Traversals 10.2 Simple Examples 10.3 Generalizing the Problem Solved 10.4 Heap Sort and Priority Queues 10.5 Representing Expressions with Trees 11 Recursive Images 11.1 Drawing a Recursive Image from a Fixed Recursive and a Base Case Image 11.2 Randomly Generating a Maze 12 Parsing with Context-Free Grammars PART THREE: Optimization Problems 13 Definition of Optimization Problems 14 Graph Search Algorithms 14.1 A Generic Search Algorithm 14.2 Breadth-First Search for Shortest Paths 14.3 Dijkstra's Shortest-Weighted-Path Algorithm 14.4 Depth-First Search 14.5 Recursive Depth-First Search 14.6 Linear Ordering of a Partial Order 14.7 Exercise 15 Network Flows and Linear Programming 15.1 A Hill-Climbing Algorithm with a Small Local Maximum 15.2 The Primal…Dual Hill-Climbing Method 15.3 The Steepest-Ascent Hill-Climbing Algorithm 15.4 Linear Programming 15.5 Exercises 16 Greedy Algorithms 16.1 Abstractions, Techniques, and Theory 16.2 Examples of Greedy Algorithms 16.2.1 Example: The Job/Event Scheduling Problem 16.2.2 Example: The Interval Cover Problem 16.2.3 Example: The Minimum-Spanning-Tree Problem 16.3 Exercises 17 Recursive Backtracking 17.1 Recursive Backtracking Algorithms 17.2 The Steps in Developing a Recursive Backtracking 17.3 Pruning Branches 17.4 Satisfiability 17.5 Exercises 18 Dynamic Programming Algorithms 18.1 Start by Developing a Recursive Backtracking 18.2 The Steps in Developing a Dynamic Programming Algorithm 18.3 Subtle Points 18.3.1 The Question for the Little Bird 18.3.2 Subinstances and Subsolutions 18.3.3 The Set of Subinstances 18.3.4 Decreasing Time and Space 18.3.5 Counting the Number of Solutions 18.3.6 The New Code 19 Examples of Dynamic Programs 19.1 The Longest-Common-Subsequence Problem 19.2 Dynamic Programs as More-of-the-Input Iterative Loop Invariant Algorithms 19.3 A Greedy Dynamic Program: The Weighted Job/Event Scheduling Problem 19.4 The Solution Viewed as a Tree: Chains of Matrix Multiplications 19.5 Generalizing the Problem Solved: Best AVL Tree 19.6 All Pairs Using Matrix Multiplication 19.7 Parsing with Context-Free Grammars 19.8 Designing Dynamic Programming Algorithms via Reductions 20 Reductions and NP-Completeness 20.1 Satisfiability Is at Least as Hard as Any Optimization Problem 20.2 Steps to Prove NP-Completeness 20.3 Example: 3-Coloring Is NP-Complete 20.4 An Algorithm for Bipartite Matching Using the Network Flow Algorithm 21 Randomized Algorithms 21.1 Using Randomness to Hide the Worst Cases 21.2 Solutions of Optimization Problems with a Random Structure PART FOUR: Appendix 22 Existential and Universal Quantifiers 23 Time Complexity 23.1 The Time (and Space) Complexity of an Algorithm 23.2 The Time Complexity of a Computational Problem 24 Logarithms and Exponentials 25 Asymptotic Growth 25.1 Steps to Classify a Function 25.2 More about Asymptotic Notation 26 Adding-Made-Easy Approximations 26.1 The Technique 26.2 Some Proofs for the Adding-Made-Easy Technique 27 Recurrence Relations 27.1 The Technique 27.2 Some Proofs 28 A Formal Proof of Correctness PART FIVE: Exercise Solutions Chapter 1. Iterative Algorithms: Measures of Progress and Loop Invariants Chapter 2. Examples UsingMore-of-the-Input Loop Invariant Chapter 3. Abstract Data Types Chapter 4. Narrowing the Search Space: Binary Search Chapter 6. Euclid’s GCD Algorithm Chapter 7. The Loop Invariant for Lower Bounds Chapter 8. Abstractions, Techniques, and Theory Chapter 9. Some Simple Examples of Recursive Algorithms Chapter 10. Recursion on Trees Chapter 11. Recursive Images Chapter 12. Parsingwith Context-Free Grammars Chapter 14. Graph Search Algorithms Chapter 15. Network Flows and Linear Programming Chapter 16: Greedy Algorithms Chapter 17. Recursive Backtracking Chapter 18. Dynamic Programming Algorithms Chapter 19. Examples of Dynamic Programs Chapter 20. Reductions and NP-Completeness Chapter 22. Existential and Universal Quantifiers Chapter 23. Time Complexity Chapter 24. Logarithms and Exponentials Chapter 25. Asymptotic Growth Chapter 26. Adding-Made-Easy Approximations Chapter 27. Recurrence Relations CONCLUSION INDEX

The Encyclopedia of Algorithms will provide a comprehensive set of solutions to important algorithmic problems for students and researchers interested in quickly locating useful information. The first edition of the reference will focus on high-impact solutions from the most recent decade; later editions will widen the scope of the work. Nearly 500 entries will be organized alphabetically by problem, with subentries allowing for distinct solutions and special cases to be listed by the year. An entry will include: a description of the basic algorithmic problem the input and output specifications the key results examples of applications citations to the key literature Open problems, links to downloadable code, experimental results, data sets, and illustrations may be provided. All entries will be written by experts; links to Internet sites that outline their research work will also be provided. The entries will be peer-reviewed. This defining reference will be published in print and on line. The print publication will include an index of subjects and authors as well as a chronology for locating recent solutions. The online edition will supplement this index with hyperlinks as well as include hyperlinks in the text of the entries to related entries, xRefer citations, and other useful URLs mentioned above.