Press "Enter" to skip to content


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 common 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 transparent. 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.

目前很多算法教材都只是提供大量优美精练代码和对这些代码的正确性证明,然而,要学会建造房子得学会使用锤子而不是光研究现成房子的结构,所以光有这些代码对初学者进化为 算法设计者 是不够的,或者说很难帮助初学者顺利快速演化成 算法设计专家 。本书设法弥补这方面的不足。著者在书中使用了一些设计模式(Paradigms ),比如循环不变量和递归,把大量算法归类成少量的元算法( meta-algorithms )。(KEMIN: 这种做法有助于看清算法设计的本质而不至于掉进问题堆中找不着北)这样做也有助于训练读者的抽象思维能力。著者也试图绕开严格的形式证明而帮助读者深刻理解为什么算法的正确性是明显和理所当然的。著者通过使用一些详尽清晰和对二三年级的计算机科学的学生可理解的方式达到这个目的,为他们将来算法创新打下基础。

Abstraction is when you translate the equations, the rules, and the underlying essences of the problem not only into a language that can be communicated to your friend standing with you on a streetcar, but also into a form that can percolate(浸透; 渗出) down and dwell(居住; 踌躇) in your subconscious(下意识, 潜意识). Because, remember, 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.

抽象思维能力表现为一种潜意识态度而不是简单对知识的运用。转换公式、规则和问题的本质为语言表达并与人交流只是知识的运用,是能力的浅层次获得;能力的深层次获得是浸透入我们的潜意识里[注1]。因为,我们思维时候,灵感的跳跃是来自潜意识的驱使,不是机械式的努力和强人逻辑所能得到的。还有,和你 (显意识)不一样,你的潜意识是不明白JAVA代码的。



To the Educator and the Student

This book is designed to be used in a twelve-week, third-year algorithms course. The goal is to teach students to think abstractly about algorithms and about the key algorithmic techniques used to develop them.


Meta-Algorithms :

Students must learn so many algorithms that they are sometimes overwhelmed(受不起, 不敢当 ). In order to facilitate their understanding, most textbooks cover the standard themes of iterative algorithms, recursion, greedy algorithms, and dynamic programming.Generally, however,when it comes to presenting the algorithms themselves and their proofs of correctness, the concepts are hidden within optimized code and slick(光滑的) proofs. One goal of this book is to present a uniform and clean way of thinking about algorithms. We do this by focusing on the structure and proof of correctness of iterative and recursive meta-algorithms, and within these the greedy and dynamic programming meta-algorithms. By learning these and their
proofs of correctness, most actual algorithms can be easily understood. The challenge is that thinking about meta-algorithms requires a great deal of abstract thinking.


Abstract Thinking :

Students are very good at learning how to apply a concrete code to a concrete input instance. They tend, however, to find it difficult to think abstractly about the algorithms. I maintain that the more abstractions a person has from which to view the problem, the deeper his understanding of it will be, the more tools he will have at his disposal(安排, 配置, 支配 ), and the better prepared he will be to design his own innovative ways to solve new problems. Hence, I present a number of different notations, analogies, and paradigms within which to develop and to think about algorithms.

学生一般都善于学习为具体问题实例套用具体算法代码,但却很难抽象地看待算法。我发现,如果一个人他越能抽象地看待要处理的问题,他就越能深刻地理解问题的本质,也越有更多的解决问题的工具,也越容易独自创新。为了训练出这样的抽象思维能力,我使用了一特别的教学方式:different notations, analogies, and paradigms。

Way of Thinking :

People who develop algorithms have various ways of thinking and intuition that tend not to get taught. The assumption, I suppose, is that these cannot be taught but must be figured out on one’s own. This text attempts to teach students to think like a designer of algorithms.


Not a Reference Book :

My intention is not to teach a specific selection of algorithms for specific purposes. Hence, the book is not organized according to the application of the algorithms, but according to the techniques and abstractions used to develop them.


Dreaming :

I would like to emphasis the importance of thinking, even daydreaming, about the material. This can be done while going through your day –while swimming, showering, cooking, or lying in bed. Ask questions. Why is it done this way and not that way? Invent other algorithms for solving a problem. Then look for input instances for which your algorithm gives the wrong answer. Mathematics is not all linear thinking.

If the essence of the material, what the questions are really asking, is allowed to seep(渗出, 漏, 渗流 ) down into your subconscious then with time little thoughts will begin to percolate up. Pursue these ideas. Sometimes even flashes of inspiration appear.

我必须强调对材料的思考和联想的重要性。这种思考可以随时随地的进行。“为什么如此而不是那样呢?”。试着为问题开发新的算法,找出你的算法有可能错误处理的问题实例。记住,数学不能使用简单的线性思维。注意,如果我们问中了一个本质的问题,那么它就很可能进入我们的潜意识[注2]。因此对思想的追捕,即便是瞬间的灵思, 是非常重要的。

注2: Kemin says:

Kemin says:

Kemin says:

Introduction From determining the cheapest way to make a hot dog to monitoring the workings of a factory, there are many complex computational problems to be solved. Before executable code can be produced, computer scientists need to be able to design the algorithms that lie behind the code, be able to understand and describe such algorithms abstractly, and be confident that they work correctly and efficiently. These are the goals of computer scientists.

计算机科学家的职责:计算机科学家的职责和能力在于,第一,抽象地描述解决计算问题(computational problems)的算法;第二,证明算法的正确性;第三,证明算法的有效性。

A Computational Problem:

A specification of a computational problem uses preconditions and postconditions to describe for each legal input instance that the computation might receive, what the required output or actions are. This may be a function mapping
each input instance to the required output. It may be an optimization problem which requires a solution to be outputted that is “optimal” from among a huge set of possible solutions for the given input instance. It may also be an ongoing system or data structure that responds appropriately to a constant stream of input.

怎么定义一个计算问题?计算问题的文字规定(specification)是由前置条件 (preconditions )和后置条件(postconditions)两部分组成,它们分别描述计算问题的合法输入和期望的输出。每一个输入实例都函数映射一个期望的输出。但不 是所有的计算问题的每一个输入实例有唯一的输出,像最优化问题,一个输入有多个输出,里边有一个最优的[注3]

注3:Kemin said: b.有意思,“问题”的答案也有从无到有,从有到好的模式;而且可根据这个模式对“问题”分类。如,判定问题就是“有没有”,“有”了之后,答案是单值、 复合值还是有结构的值分出了数值问题和组合问题;“有”了之后再评价就是“好”的问题,单一好是最佳值问题;组合好是最优化问题。

Example: The sorting problem is defined as follows:

Preconditions: The input is a list of n values, including possible repetitions.

Postconditions: The output is a list consisting of the same n values in non-decreasing order.

An Abstract Data Type :

Computers use zeros and ones, ANDs and ORs, IFs and GOTOs. This does not mean that we have to. The description of an algorithm may talk of abstract objects
such as integers, reals, strings, sets, stacks, graphs, and trees; abstract operations
such as “sort the list,” “pop the stack,” or “trace a path”; and abstract relationships
such as greater than, prefix, subset, connected, and child. To be useful, the nature of these objects and the effect of these operations need to be understood. However, in order to hide details that are tedious or irrelevant, the precise implementations of these data structure and algorithms do not need to be specified. For more on this see Chapter 3.

抽象数据类型:计算机使用最原始的数据(0和1)和操作(ANDs 、ORs、 IFs 和 GOTO)工作,但这并不意味着我们也要。算法可使用抽象的对象(像整数、实数、字符串、栈、图和树)、抽象的操作(像排序、弹出弹入、跟踪)和抽象的关 系(大于、先于、子集、连通和后代)进行描述。当然,这些抽象的东西最后还是要被转为计算机理解的原始形式,这是算法和数据结构具体实现的话题,第三章有 讲述。

Running Time :

It is not enough for a computation to eventually get the correct answer. It must also do so using a reasonable amount of time and memory space. The running time of an algorithm is a function from the size n of the input instance given to a bound on the number of operations the computation must do. (See Chapter 23.) The algorithm is said to be feasible
if this function is a polynomial like Time(n) = O(n^2), and is said to be infeasible
if this function is an exponential like Time(n) = O(2^n). (See Chapters 24 and 25 for more on the asymptotic of functions.)

To be able to compute the running time , one needs to be able to add up the times taken in each iteration of a loop and to solve the recurrence relation defining the time of a recursive program. (See Chapter 26 for an understanding of ∑( i=1,n) i = Θ(n^2),and Chapter 27 for an understanding of T(n) = 2T(n/2 ) +n = Θ(n logn).)

算法光能给出正确的计算结果是不够的,它必须在合理的时间和空间内完成才是有用的。为了估算算法的时间复杂度,必需合计循环内基本操作的次数(看26章并理解式子 :∑( i=1,n) i = Θ(n^2) ) 和解出递归算法递归关系(看27章并理解式子:T(n) = 2T(n/2 ) +n = Θ(n logn))。

Meta-algorithms :

Most algorithms are best described as being either iterative or recursive. An iterative algorithm (Part One) takes one step at a time, ensuring that each step makes progress while maintaining the loop invariant. A recursive algorithm (Part Two) breaks its instance into smaller instances, which it gets a friend to solve, and then combines their solutions into one of its own.


Optimization problems (Part Three) form an important class of computational problems. The key algorithms for them are the following.


Greedy algorithms (Chapter 16) keep grabbing the next object that looks best.

Recursive backtracking algorithms (Chapter 17) try things and, if they don’t work, backtrack and try something else.

Dynamic programming (Chapter 18) solves a sequence of larger and larger instances, reusing the previously saved solutions for the smaller instances, until a solution is obtained for the given instance.

Reductions (Chapter 20) use an algorithm for one problem to solve another.

Randomized algorithms (Chapter 21) flip coins to help them decide what actions to take. Finally, lower bounds

(Chapter 7) prove that there are no faster algorithms.

Be First to Comment

Leave a Reply

Your email address will not be published. Required fields are marked *